Grafuri orientate

Un graf orientat cu 6 vârfuri, numerotate de la 1 la 6, este reprezentat prin matricea de adiacenţă de mai jos. Care dintre vârfurile grafului au gradul exterior un număr impar?

0 1 1 0 0 0

0 0 1 1 0 1

1 1 0 1 0 0

0 0 0 0 1 0

0 1 0 0 0 0

0 1 0 0 1 0

• 1, 3, 4, 5

• 2, 3, 4, 5

• 1, 4, 5, 6

• 2, 3, 5

Se consideră graful orientat reprezentat prin matricea de adiacenţă de mai jos. Care este lungimea maximă a unui drum, de la vârful 4 până la vârful 6, format din vârfuri distincte două câte două (lungimea unui drum este egală cu numărul de arce care compun acel drum)?

0 1 1 0 0 0

0 0 0 0 1 1

0 0 0 0 0 0

0 0 1 0 1 0

1 1 0 0 0 1

1 0 1 0 0 0

• 4

• 3

• 1

• 5

Fie graful orientat G cu 5 vârfuri, numerotate cu 1,2,3,4,5, şi arcele (1,2), (1,3), (1,4), (2,3), (4,2), (4,5), (5,2), (2,4). Care dintre următoarele vârfuri au gradul extern egal cu gradul intern?

• 2 si 4

• 4 si 5

• 1 si 2

• 3 si 4

Se consideră graful orientat reprezentat prin listele de adiacenţă de mai jos. Câte noduri au gradul extern mai mare decât gradul intern?

1: 2, 6 ,5

2: 3

3: 1

4: 6

5: 6

6: 2

• 3

• 2

• 1

• 4

Î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?

• 5

• 20

• 10

• 15

Care dintre următoarele arce trebuie adăugat unui graf orientat cu 5 noduri şi cu matricea de adiacenţă de mai jos astfel încât în acest graf să existe cel puţin un drum între oricare două vârfuri?

0 1 0 1 0

0 0 1 0 0

0 0 0 0 0

0 0 0 0 1

1 0 0 0 0

• (3 , 5)

• (4 , 1)

• (5 , 3)

• (3 , 2)

Se consideră graful orientat din figură. Care este numărul minim de arce ce trebuie adăugate grafului astfel încât oricare două vârfuri din graf să fie unite prin drumuri elementare?

Numărul total de grafuri turneu cu n vârfuri este:

• 3^n*(n-1)

• 3^(n*(n-1))/2

• 2^n*(n-1)

• 2^(n*(n-1))/2

Câte grafuri orientate cu n vârfuri există?

• 2^n*(n-1)

• 2^n*(n+1)

• n*(n-1)

• 2^n*n-1

Câte grafuri orientate și complete cu n vârfuri există?

• n!

• 1

• C³_n

• 3^(n*(n-1))/2