Question

Un graf neorientat cu 20 de muchii; 4 noduri au rangul par restul impar.Care este numarul maxim de noduri. Raspunsul nu ma incalzeste foarte tare, as vrea o explicatie daca se poate.Multumesc anticipat.

Answer 1

In informatica folosim  deseori observatii de la sine intelese, nu neaparat demonstratii riguroase. 
Un graf cu 20 de muchii poate avea maxim 21 de noduri (daca nu contine cicluri). Se observa ca putem aranja cele 21 de noduri incat sa obtinem un graf care respecta restrictiile din enunt. Un astfel de graf arata astfel:
1 ii are ca vecini pe 2, 3, 4, ..., 17
17 il are ca vecin pe 18
18 il are ca vecin pe 19
19 il are ca vecin pe 20
20 il are ca vecin pe 21

Se observa ca 1 are gradul 17
Nodurile 2, 3, ..., 16  si 20 au gradul 1
Iar 17, 16, 19 si 20 au gradul 2. ( de exemplu 17 se invecineaza cu 1 si cu 18, 18 se invecineaza cu 17 si cu 19 etc)

Deci raspunsul este 21. Sper ca te-am ajutat. 

Answer 2

Deci pentru a avea numar maxim de noduri, in acel numar de muchii ar trebui sa folosesc cate o muchie(pentru cate 2 noduri).In graful nostru o sa existe o componenta conexa care va fi un graf regulat ( adica o sa avem un patrat si fiind legate 2 cate 2 vom indeplini conditia sa contina 4 noduri cu grad par).Deci avem 4 noduri din graful regulat si am folosit 4 muchii.Iar restul va fi numarul de noduri ramase * 2 ( deoarece pentru a forma o muchie folosim 2 noduri)4 + 2 * 16 = 36 de noduri