Question

Fie T un arbore si v un nod al acestuia. Construim un graf G astfel: cream 11 copii distincte T1, T2, . . . , T11 ale arborelui T si adaugam toate muchiile posibile intre nodurile v1, v2, . . . , v11, unde $v_{i}$ este copia din arborele $T_i}$ corespunzatoare nodului ales v. In graful rezultat, numarul de muchii este dublul numarului de noduri. Cate noduri are arborele initial T?

Sursa: Admitere UAIC Informatica 2017

Answer 1

Un arbore T are n noduri (asta înseamnă că are n-1 muchii, fiind arbore, fiecare nod are un singur părinte, înafară de rădăcină, care are 0, deci n-1 muchii).

11 copii ale arborelui au 11*n noduri, deci implicit 11*(n-1) muchii.

Apoi, dacă un anumit nod din fiecare copie este conectat cu același nod din celelalte copii, vor apărea câteva noi muchii. Și numărul nou de muchii va fi numărul maxim posibil de conexiuni (muchii) dintre cele 11 noduri, adică 55 de muchii.

Deci în noul graf generat din cele 11 copii ale arborelui + cele 55 de noi muchii, vor fi în total:

11*n noduri (nu se schimbă numărul de noduri)

11*(n-1) + 55 muchii = 11n - 11 + 55 = 11n + 44 muchii

Ipoteza spune: „In graful rezultat, numarul de muchii este dublul numarului de noduri.”

Păi, în acest caz, înseamnă că (11n + 44) este dublul lui (11n).

Deci:

(11n + 44) = 2*11n

=> 11n + 44 = 22n

=> 44 = 22n - 11n = 11n

=> n = 4 => arborele inițial are 4 noduri, deci 4-1 = 3 muchii.