Exerciții

Fie n un număr natural, n>4. Orice graf neorientat cu n noduri şi n muchii:

Fie T un arbore cu rădăcină. Arborele are 8 noduri etichetate cu numere naturale de la 1 la 8 şi este descris prin următorul vector „de taţi”: (4,5,0,3,4,5,4,5). Care sunt frunzele arborelui?

Scrieți etichetele în ordine crescătoare, separate prin exact un spațiu.

Dacă G este un graf neorientat cu 8 noduri şi 2 componente conexe, atunci graful are cel mult:

Dacă T este un arbore cu rădăcină, cu 100 de noduri, care este numărul minim de frunze pe care le poate avea T?

Care este numărul minim de muchii pe care le poate avea graful neorientat G, dacă graful din figura 1 reprezintă un subgraf al lui G, iar graful reprezentat în figura 2 este graf parţial al lui G?

Figura 1	Figura 2

Se consideră un arbore cu rădăcină, cu 100 noduri, numerotate de la 1 la 100. Dacă nodul 13 are exact 14 fraţi şi nodul 100 este tatăl nodului 13, care este numărul total de descendenţi direcţi (fii) ai nodului 100?

Care dintre următoarele afirmaţii referitoare la graful neorientat G, reprezentat în figura de mai jos, este adevărată?

Se consideră un arbore G, cu rădăcină, memorat cu ajutorul vectorului de „taţi” următor: T=(2,0,4,2,4,7,2). Care dintre următoarele afirmaţii este adevărată?

Se consideră un graf neorientat dat prin listele de adiacenţă următoare:

1: 2 3
2: 1 3 4
3: 1 2 4 5
4: 2 3 5
5: 3 4

Care este numărul maxim de muchii care pot fi eliminate din graf astfel încât graful parţial rezultat să fie conex ?

Care este numărul minim de muchii care trebuie adăugate grafului următor pentru a
deveni conex şi eulerian?