Fie graful neorientat cu 6 noduri, numerotate de la 1 la 6, şi muchiile [1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [3,5], [4,5], [4,6], [5,6]. Care este numărul maxim de muchii ce pot fi eliminate astfel încât graful parţial obţinut să-şi păstreze proprietatea de graf hamiltonian?
Un graf orientat are 8 arce şi fiecare nod al grafului are gradul exterior un număr nenul. Doar două dintre noduri au gradul exterior un număr impar, restul având gradele exterioare numere pare. Care este numărul maxim de noduri pe care le poate avea graful?
Care dintre următoarele afirmaţii este adevărată pentru graful neorientat având mulţimea nodurilor X={1,2,3,4,5} şi mulţimea muchiilor U={[1,2], [1,5], [2,3], [2,4], [3,4], [4,5]}?
| Varianta 1 |
Este graf hamiltonian, dar nu este eulerian. |
| Varianta 2 |
Este graf eulerian, dar nu este hamiltonian. |
| Varianta 3 |
Este şi graf hamiltonian şi graf eulerian. |
| Varianta 4 |
Nu este graf hamiltonian, şi nici nu este graf eulerian. |
Se consideră graful orientat cu nodurile numerotate de la 1 la 5 şi arcele (1,2), (1,5), (2,1), (2,3), (2,5), (3,4), (5,2), (5,4). Care este lungimea maximă a unui drum de la nodul 1 la nodul 4, format doar din arce distincte?
| Varianta 1 |
5 |
| Varianta 2 |
6 |
| Varianta 3 |
4 |
| Varianta 4 |
7 |
Se consideră graful neorientat cu nodurile numerotate de la 1 la 6 şi având muchiile [1,2], [2,3], [2,5], [2,6], [3,4], [4,5], [4,6], [5,6]. Câte lanţuri elementare distincte şi de lungime 3 există de la nodul 1 la nodul 4 în graful dat? Două lanţuri sunt distincte dacă diferă prin cel puţin o muchie.
| Varianta 1 |
2 |
| Varianta 2 |
0 |
| Varianta 3 |
4 |
| Varianta 4 |
3 |
Un arbore cu rădăcină, cu 9 noduri, numerotate de la 1 la 9, este memorat cu ajutorul vectorului „de taţi” t=(9,3,4,7,3,9,0,7,2). Mulţimea tuturor nodurilor de tip frunză este:
| Varianta 1 |
|
| Varianta 2 |
|
| Varianta 3 |
|
| Varianta 4 |
|
Se consideră graful orientat cu vârfurile numerotate de la 1 la 7 şi arcele (1,2), (1,7), (2,3), (3,2), (3,4), (4,3), (5,4), (5,6), (6,4), (7,6). Câte vârfuri din graful dat au gradul extern impar?
| Varianta 1 |
4 |
| Varianta 2 |
3 |
| Varianta 3 |
2 |
| Varianta 4 |
1 |
Un arbore cu rădăcină, cu 9 noduri, numerotate de la 1 la 9, este memorat cu ajutorul vectorului „de taţi” t=(9,3,4,7,3,9,0,7,2). Care este numărul minim de noduri ce trebuie eliminate pentru ca lungimea celui mai lung lanţ elementar, cu o extremitate în rădăcină, să fie 3 şi subgraful obţinut să fie tot arbore?
| Varianta 1 |
2 |
| Varianta 2 |
3 |
| Varianta 3 |
4 |
| Varianta 4 |
5 |
Determinaţi ultima valoare (notată cu ?) din vectorului „de taţi” (0, 1, 1, 2, 3, 3, ?) astfel încât arborele cu rădăcină, cu 7 noduri, numerotate de la 1 la 7, descris de acest vector, să aibă pe fiecare nivel n exact 2n noduri, nodul rădăcină fiind pe nivelul n=0, şi fiecare nod să aibă cel mult doi descendenţi.
| Varianta 1 |
2 |
| Varianta 2 |
3 |
| Varianta 3 |
4 |
| Varianta 4 |
5 |
Se consideră un arbore cu 6 noduri, numerotate de la 1 la 6, reprezentat prin matricea de adiacenţă dată mai jos.
0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0
Scrieţi toate nodurile care pot fi alese ca rădăcină a arborelui astfel încât acesta să aibă un număr par de frunze.
Scrieți valorile în ordine crescătoare, separate prin exact un spațiu.