Test grafuri orientate

O companie de colectare a fructelor are 6 depozite, numerotate de la 1 la 6: depozitele 1, 3 și 5 conțin mere, depozitele 2 și 4 conțin pere, iar depozitul 6 conține piersici. Compania a construit 4 benzi de transport unidirecțional: de la depozitul 1 la depozitul 5, de la depozitul 5 la depozitul 2, de la depozitul 5 la depozitul 4 și de la depozitul 6 la depozitul 1. Dacă depozitele reprezintă vârfurile unui graf orientat, iar benzile de transport reprezintă arcele acestuia, indicați numărul minim de benzi de transport care pot fi adăugate, astfel încât graful obținut să aibă trei componente tare conexe, fiecare dintre acestea având vârfuri care corespund depozitelor cu același tip de fructe.

• 4

• 3

• 2

• 1

Un graf turneu cu 15 vârfuri, numerotate de la 1 la 15, care nu conține niciun circuit. Indicați numărul minim de arce care pot fi adăugate acestuia, astfel încât graful obținut să fie tare conex.

• 4

• 3

• 2

• 1

Câte subgrafuri cu număr par de noduri are un graf orientat cu 5 noduri și 11 arce?

Considerăm graful orientat dat prin următoarea matrice de adiacență.

0 0 0 0 1 1

0 0 1 1 0 1

1 1 0 1 0 0

1 1 1 0 0 1

0 0 0 1 0 1

1 0 1 1 0 0

Care dintre următoarele mulțimi conțin doar noduri care au gradul interior mai mic decât cel exterior?

• {1,4}

• {2,6}

• {2,5}

• {5,6}

Se consideră graful orientat G=(X, U) unde X={1,2,3,4,5,6,7,8,9,10} și U={(2,3),(2,4),(3,2),(3,7),(4,3),(4,6),(5,6),(6,7),(7,6),(9,10)}. Precizați câte componente tare conexe are graful.

Un graf orientat cu 5 vârfuri, numerotate de la 1 la 5, este reprezentat alăturat. Numărul maxim de arce care se pot elimina, astfel încât graful parțial obținut să fie tare conex este:

• 2

• 3

• 4

• 5

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?

• 5

• 6

• 7

• 8

Se consideră graful orientat cu vârfurile numerotate cu numere distincte 1, 2, 3, … . Graful este reprezentat printr-o matrice de adiacenţă A. Precizaţi care este semnificaţia sumei valorilor de pe o linie oarecare x a matricei A.

• reprezintă numărul arcelor care au ca extremitate iniţială vârful x

• reprezintă numărul drumurilor care conţin vârful x

• reprezintă numărul arcelor care au ca extremitate finală x

• reprezintă numărul drumurilor care pornesc din vârful x

Un graf orientat cu 6 vârfuri, numerotate de la 1 la 6 are mulțimea arcelor {(1,4), (1,6), (3,1), (3,4), (3,6), (6,1)}. Indicați numărul de subgrafuri ale sale, pentru fiecare dintre acestea mulțimea arcelor fiind {(1,6), (3,1), (3,6), (6,1)}.

• 2

• 3

• 4

• 5

Care este numărul minim de arce într-un graf orientat complet cu 7 noduri?

• 10

• 15

• 21

• 28