Grafuri orientate - Test

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

• 1, 3, 4, 5

• 2, 3, 4, 5

• 1, 4, 5, 6

• 2, 3, 5

Se consideră un graf orientat cu 6 noduri numerotate de la 1 la 6 şi cu mulţimea arcelor formată doar din arcele: - de la fiecare nod numerotat cu un număr neprim i (i>1) la toate nodurile numerotate cu numere ce aparţin mulţimii divizorilor proprii ai lui i (divizori diferiţi de 1 şi de i) - de la nodul numerotat cu 1 la nodul numerotat cu 6 - de la fiecare nod numerotat cu un număr prim i la nodul numerotat cu i-1. Pentru graful dat, care este lungimea celui mai mare drum, format doar din noduri distincte?

• 6

• 5

• 3

• 4

Câte grafuri orientate, distincte, cu 4 vârfuri se pot construi? Două grafuri se consider distincte dacă matricele lor de adiacenţă sunt diferite.

• 46

• 26

• 64

• 4

Care dintre secvenţele următoare de numere pot reprezenta şirurile gradelor exterioare şi interioare ale unui graf orientat?

• gr_ext=(1,1,1,0,1,2) gr_int=(0,2,2,1,0,0)

• gr_ext =(6,0,1,1,0,0) gr_int=(0,2,2,2,2,0)

• gr_ext=(1,1,1,1,1,1) gr_int=(6,0,0,0,0,0)

• gr_ext=(1,1,1,0,1,1) gr_int=(0,2,2,1,0,0)

Precizaţi valoarea de adevăr a următoarelor afirmaţii. În orice graf orientat: suma gradelor exterioare este totdeauna un număr par; suma gradelor interioare este totdeauna un număr par; suma gradelor exterioare este totdeauna egală cu cea a gradelor interioare; suma gradelor exterioare este totdeauna egală cu dublul numărului de muchii.

Care este numărul minim de arce pe care le poate avea un graf orientat cu 6 vârfuri şi 3 componente tare conexe?

• 4

• 5

• 6

• 10

Câte grafuri orientate cu 5 vârfuri, dintre care unul este izolat există?

• 10*211

• 10*25

• 212

• nu poate fi precizat

Care din următoarele proprietăţi 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 e

proprietăţi 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

Se consideră graful orientat din figura alăturată. Care este numărul minim de arce ce trebuie adăugate grafului şi care sunt aceste arce, astfel încât oricare două vârfuri din graf să fie unite prin drumuri elementare?