Question

Într-un graf neorientat cu 10 muchii, fiecare nod are gradul un număr nenul. Doar trei 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?
cu explicatie daca se poate <3

Answer 1

Daca nu am avea restrictia de 3 grade pare, am putea avea Cate 2 noduri cuplate (10 muchii deci 20 noduri), Este clar ca nu avem cum sa avem Mai multe noduri intr-un Graf cu 10 muchii, deoarece o muchie contribuie la 2 noduri, deci 2*10 = 20 noduri.
Pentru a forma un grad par in 3 noduri, optim Este sa avem gradul 2 si 1 la restul (tehnica greedy, cu cat Mai mici gradele, cu atat mai multe noduri avem). Astfel vom "uni" 2 noduri din perechi diferite pentru a forma un lant de lungime 3, astfel formandu-se in nod de grad par. Facem acest lucru de 3 Ori, si graful final va fi compus din 3 lanturi de lg 3, si alte 4 lanturi de lg 2. In final avem 3*3 + 4*2 noduri. Demonstratie ca asta e cel Mai bun raspuns: daca am avea un nod in plus, vom avea 3 grade de 2 si restul de 15 noduri gradul 1 pentru un total de 15+3*2 = 21, dar 10 muchii pot forma o Suma de grade maxim 20(vezi Mai sus)