Grafuri orientate

Care este numărul minim de arce ce trebuie adăugate în graful orientat din figura de mai jos astfel încât fiecare vârf să aparţină unui circuit?

• 1

• 2

• 3

• 4

Se consideră graful orientat cu vârfurile numerotate cu numere distincte 1, 2, 3, … . Graful este reprezentat printr-o matrice de adiacenţă A. Sumei valorilor de pe o linie oarecare x a matricei A reprezinta gradul exterior al varfului x.

• Adevarat

• Fals

Fie graful orientat cu 7 vârfuri, numerotate de la 1 la 7, şi arcele (1,2), (2,3), (3,1), (4,5), (5,6), (5,7), (6,7), (7,4). Care este numărul minim de arce ce ar trebui eliminate pentru ca graful parţial obţinut să nu mai conţină circuite?

(a)  

Ce notiuni dintre cele de mai jos se intalnesc in teoria grafurilor orientate?

• grad interior

• grad exterior

• muchie

• arc

• circuit

Se consideră graful orientat definit prin mulţimea vârfurilor {1,2,3,4,5,6} şi arcele (1,2), (1,6), (1,5), (2,3), (3,6), (4,1), (6,4).

Vârful accesibil din toate celelalte vârfuri ale grafului prin intermediul unor drumuri elementare este 4?

• True

• False

Care dintre următoarele propoziţii NU este adevărată pentru graful orientat cu 6 vârfuri, numerotate de la 1 la 6 şi ale cărui arce sunt: (2,1), (3,6), (4,1), (4,3), (4,5), (5,2), (6,4)?

• vârful numerotat cu 6 aparţine unui circuit

• vârful numerotat cu 1 are gradul extern 0

• gradul intern al vârfului numerotat cu 4 este 1

• graful nu are circuite

Fie graful orientat cu 6 vârfuri, numerotate de la 1 la 6, şi arcele (1,2), (2,3), (3,1), (4,5), (5,6), (3,5). Care este numărul minim de arce ce trebuie adăugate pentru ca toate vârfurile să aibă gradul interior egal cu gradul exterior?

(a)  

Într-un graf orientat cu 7 noduri suma gradelor interioare ale tuturor nodurilor este egală cu 10. Care este valoarea sumei gradelor exterioare ale tuturor nodurilor?

(a)  

Care din următoarele proprietăţi NU este adevărată pentru un graf orientat cu n vârfuri şi n arce (n>3) care are un circuit de lungime n:

• există un vârf cu gradul intern n-1

• pentru orice vârf gradul intern şi gradul extern sunt egale

• graful nu are drumuri de lungime strict mai mare decât 2

• gradul intern al oricărui vârf este egal cu 2

Pentru punctul din oficiu alegeti TRUE!

• True

• False