Într-un graf neorientat cu 20 muchii, fiecare nod al grafului are gradul un număr nenul. Doar patru dintre noduri au gradul un număr par, restul nodurilor având gradele numere impare.
Care este numărul maxim de noduri pe care poate să le aibă graful?
Varianta 1-32
Varianta 2-36
Varianta 3-10
Varianta 4-16
Răspunsuri la întrebare
Răspuns de
78
Bun, sa o luam pe rand:
Stim ca are fix 20 de muchii, si nici un nod nu are grad nenul, asta inseamna ca are gradul minim 1 fiecare nod, ceea ce ar duce la un graf unde nodurile sunt pur si simplu conectate 2 cate 2 cu o muchie, si ai avea asa doar perechi de noduri conectate cu o muchie in aer, asta ar insemna ca pt fiecare muchie avem 2 noduri, deci la 20 muchii vin 40 noduri.
Bun, dar stim ca EXACT 4 noduri au grad par, adica macar 2. Ne amintim ca noi vrem numarul maxim de noduri posibile asa ca nu vrem sa le dam nodurilor alea 4 un grad mai mare decat au nevoie, ramanem deci la 4 noduri cu gradul 2 si restul au gradul 1.
Asta ar insemna ca acele 4 noduri formeaza un patrat si apoi ai multe multe perechi de noduri, gen asa:
o ----- o
| |
| |
o ----- o
o ----- o
o ----- o
o ----- o
...
Asta inseamna ca pentru acel patrat de sus noi "consumam" 4 muchii si obtinem 4 noduri. Raman 16 muchii cu care sa facem multe perechi ca mai jos. Deci cu 16 muchii primim 32 noduri pt ca vin 2 noduri la fiecare muchie. 32 noduri + 4 noduri de la patratul de sus fac 36 noduri in total!
Stim ca are fix 20 de muchii, si nici un nod nu are grad nenul, asta inseamna ca are gradul minim 1 fiecare nod, ceea ce ar duce la un graf unde nodurile sunt pur si simplu conectate 2 cate 2 cu o muchie, si ai avea asa doar perechi de noduri conectate cu o muchie in aer, asta ar insemna ca pt fiecare muchie avem 2 noduri, deci la 20 muchii vin 40 noduri.
Bun, dar stim ca EXACT 4 noduri au grad par, adica macar 2. Ne amintim ca noi vrem numarul maxim de noduri posibile asa ca nu vrem sa le dam nodurilor alea 4 un grad mai mare decat au nevoie, ramanem deci la 4 noduri cu gradul 2 si restul au gradul 1.
Asta ar insemna ca acele 4 noduri formeaza un patrat si apoi ai multe multe perechi de noduri, gen asa:
o ----- o
| |
| |
o ----- o
o ----- o
o ----- o
o ----- o
...
Asta inseamna ca pentru acel patrat de sus noi "consumam" 4 muchii si obtinem 4 noduri. Raman 16 muchii cu care sa facem multe perechi ca mai jos. Deci cu 16 muchii primim 32 noduri pt ca vin 2 noduri la fiecare muchie. 32 noduri + 4 noduri de la patratul de sus fac 36 noduri in total!
Alte întrebări interesante