Algoritmica Grafurilor 2008 Rezolvata

LISTA PROBLEME ALGORITMICA GRAURILOR Multiple Choice Identify the letter of the choice that best completes the statement or answers the question. ____ b

____ c

____ b

____ b

1. Dac G = (X,U) este un graf si pentru x

X, d(x) este gradul lui x atunci intre 2|U| si

avem rela ia:

a. < b. = c. > 2. Graful complet Kn este: a. n-regulat b. (n+1)-regulat c. (n-1)-regulat 3. Rezultatul urm tor: Graful G este bipartit <=> nu con ine cicluri impare se datoreaz lui: a. ORE b. KÖNIG c. EULER d. KURATOWSKI 4. Num rul muchiilor unui graf complet Kn este: a. n b.

1 n

c.

2 n 1 2

____ a

5. Num rul muchiilor unui graf bipartit complet Km,n este: a. mn b. (m-1)n c. m(n-1) d. (m-1)(n-1)

____ b

6. Intr-un graf orientat G = (X,U) dac not m pentru x X cu d s u interior atunci intre

____ b

____ c

si

x gradul exterior al lui x i cu d

avem rela ia:

a. < b. = c. > 7. Matricea de adiacen a unui graf neorientat G = (X,U) este: a. antisimetric b. simetric c. tranzitiv 8. Rangul matricei de inciden nod-arc pentru un graf conex cu n noduri i m muchii este: a. n b. m c. n-1

x gradul

____ b

9.

____ 10. d

____ 11. b

____ 12. c

____ 13. c

d. m-1 Rangul matricei de inciden nod-arc pentru un graf cu n noduri i p componente conexe este: a. n-p+1 b. n-p c. n+p d. n+p-1 Un graf G are un arbore par ial dac i numai dac G este: a. bipartit b. regulat c. ciclic d. conex Orice arbore cu n vârfuri are cel pu in x vârfuri terminale, unde x = a. 1 b. 2 c. 3 d. n Orice arbore cu n vârfuri are x muchii unde x = : a. n b. n+1 c. n-1 Algoritmul urm tor: Intrare: A-matricea de adiacen a unui graf cu n varfuri 1. Se face k=1. 2. Pentru i 1,...,n , j 1,...,n i i, j k se înlocuie elementele a ij 0 prin min a ik , a kj . 3. Se repet pasul 2 pentru k determin la iesire

2,...,n ,

a. un arbore par ial al lui G b. un arbore par ial de cost minim în G c. matricea drumurilor lui G ____ c 14. Algoritmul lui Kruskal produce: a. matricea drumurilor unui graf b. un arbore par ial in G c. un arbore par ial de cost minim in G ____ 15. Algoritmul urm tor: e Intrare: G = (X,U) conex cu n vârfuri i func ia de cost c 1. Dintre muchiile nealese ale lui U se selecteaz o muchie de cost minim care s nu formeze cicluri cu muchiile deja alese. 2. Dacã au fost alese n 1 muchii ne oprim, altfel se repet pasul 1, se datoreaz lui : a. Roy-Warshall b. Prim c. Floyd d. Dijkstra e. Kruskal ____ b 16. Complexitatea temporal a algoritmului lui Kruskal pentru un graf cu n vârfuri i m muchii este: a. O(m,n)

b. c.

O m log m O m log n

d.

O m2

n2

log n

____ 17. Algoritmul urm tor: c Intrare: G = (X,U) un graf cu n varfuri, D - matricea distan elor dintre vârfuri 1. k 1 . 2. Pentru i 1,...,n , j 1,...,n , i j i i, j k se înlocuie elementul d ij prin

min d ij , d ik

____ d 18.

d ____ 19.

____ 20. b

____ 21. a

____ 22. c

d kj .

3. Se repet pasul 2 pentru k 2,...,n , produce la iesire: a. matricea drumurilor b. un arbore par ial de cost minim c. matricea distan elor minime Complexitatea temporala a algoritmului lui Floyd pentru un graf cu n noduri este: a. O(n) b. O(n2) c. O(1) d. O(n3) Algoritmul lui Dijkstra determin : a. matricea drumurilor b. matricea distan elor minime c. un arbore par ial de cost minim d. drumurile minime si lungimile acestora de la un vârf s dat la toate celelalte vârfuri Complexitatea temporal a algoritmului lui Dijkstra pentru un graf orientat cu n vârfuri este: a. liniar b. p tratic c. cubic d. exponen ial Pentru o re ea de transport, intre valoarea maxim a fluxului de ie ire i capacitatea minim a unei t ieturi exist rela ia: a. = b. < c. > Rezultatul urm tor: Pentru orice re ea de transport valoarea maxim a fluxului de ie ire este egal cu capacitatea minim a unei t ieturi" se datoreaz lui: a. Roy-Warshall b. Kruskal c. Ford-Fulkerson d. Dijkstra

a ____ 23. Intr-o re ea de transport pentru orice flux , intre t-fluxul de pe arcele de iesire i capacitatea oric rei t ieturi exist rela ia: a. b. c. = ____ a 24. La sfâr itul aplic rii algoritmului lui Ford-Fulkerson, arcele ce unesc vârfurile etichetate cu varfurile neetichetate constituie:

a. o t ietur de capacitate minim b. o component conex a re elei de transport c. o mul ime de arce saturate ____ c 25. Numarul tuturor grafurilor cu n noduri este: a. 2n n(n b. c. d.

1)

2

2

n ( n 1) 2

2 C n2

X x X o relatie binara pe X data prin: x y < = > x=y sau exista L=[x,...,y] lant in G. Atunci relatia este: a. relatie de ordine b. relatie de echivalenta c. relatie de preordine Algoritmul urmator: intrare G=(X,U) graf si x0 X fixat Y {x0}, V Ø repeat Y Y, V V Y Y U {y X-Y | x Y incat xy U} Y={xy U | x, y Y} until (Y=Y ) si (V=V ) determina: a. toti vecinii lui x0 b. daca G este conex c. componenta conexa ce contine pe x0 d. daca G este ciclic Algoritmul ce raspunde la intrebarea Este un graf dat G=(X,U) ciclic? se datoreaza lui: a. Fleury b. Kruskal c. Prim d. Marimont n Fie G=(X,U) un graf in care |X| = n? 3 si pentru orice x X avem d ( x) . Atunci G este: 2 a. eulerian b. hamiltonian c. complet Fie G=(X,U) un graf fara varfuri izolate, conex si pentru orice x X, d(x) este numar par. Atunci G este: a. eulerian b. hamiltonian c. complet Algoritmul pentru obtinerea unui ciclu eulerian intr-un graf eulerian se datoreaza lui:

____ 26. Fie G=(X, U) un graf si b

____ 27. c

____ d 28.

____ b 29.

____ 30. a

____ 31. d

a. b. c. d. ____ 32. b

c ____ 33.

____ b 34.

a ____ 35.

____ 36. c

____ 37. d

Euler Hamilton Marimont Fleury Algoritmul urmator: intrare G=(X,U) graf eulerian fie x0 X arbitrar, i 0, V U while d(xi)? 0 do if xiy V ce nu este punte in (X, V) then do V V-{xiy} i i+1 xi y else do alege puntea xiy V V V {xiy} i i+1 xi y , determina in G: a. o componenta conexa ce contine x0 b. un ciclu eulerian c. un lant ce porneste din x0 Fie G=(X,U) un graf. Se numeste arbore de traversare (arbore de acoperire sau arbore partial) un graf partial H=(X,V) al lui G care este: a. conex b. aciclic c. arbore Fie G=(X,U) un graf si H=(X,V) un arbore de traversare al sau. Atunci elementele lui U-V se numesc: a. punti ale lui H b. coarde ale lui H c. muchii libere in H Graful G=(X,U) contine un arbore de traversare < == > G este graf: a. conex b. ciclic c. aciclic Fie G=(X,U) un arbore cu |X| = 2 varfuri. Atunci numarul varfurilor terminale este: a. 2 b. 1 c. cel putin 2 d. cel mult 2 Fie G=(X,U) un graf in a carui reprezentare geometrica muchiile se intersecteaza doar in varfuri. Atunci G este: a. conex b. ciclic c. aciclic d. planar

____ 38. Daca G=(X,U) este un graf planar conex cu f fete atunci |X|-|U|+f=n, unde n este: c a. 0 b. 1 c. 2 d. 3

c ____ 39. Teorema care spune ca intr-un graf planar conex G=(X,U) cu f fete are loc relatia |X|-|U|+f=2 se

____ c 40.

____ 41. c

____ 42. c

____ b 43.

____ a 44.

____ d 45.

c ____ 46.

datoreaza lui: a. Kruskal b. Prim c. Euler d. Kuratowski Grafurile complete K5 si K3,3 sunt: a. neconexe b. aciclice c. neplanare Teorema de caracterizare a grafurilor planare se datoreaza lui: a. Euler b. Kruskal c. Kuratowski d. Prim Fie G=(X,U) un digraf cu |X|=n varfuri. Atunci numarul maxim de arce in G este: a. n2-1 b. n2-n c. n2 d. n2+1 Fie G=(X,U) un digraf cu |X|=n varfuri si fara bucle (adica xx nu apartine lui U pentru orice x X). Atunci numarul maxim de arce in G este: a. n2-1 b. n2-n c. n2 d. n2+n Numarul tuturor digrafurilor cu n varfuri este: a. 2 n 2 b. 2 n 2 1 c. 2 n 2 1 d. 2 n 2 n Numarul tuturor digrafurilor G=(X,U) fara bucle (xx nu apartine lui U pentru orice x X) si cu n varfuri (|X|=n) este: a. 2 n 2 b. 2 n 2 1 c. 2 n 2 1 d. 2 n 2 n Numarul digrafurilor complete cu n varfuri ( n = 2) este:

a. 1 b. 2 c. 3 d. 3 ____ b 47. Fie G=(X,U) digraf in care exista x X caruia i se asociaza o eticheta pentru a-l identifica. Atunci G

____ 48. a

____ b 49.

____ 50. c

c 51. ____

____ d 52.

____ b 53.

____ d 54.

se numeste digraf: a. marcat b. etichetat c. complet Fie G=(X,U) un digraf in care pentru orice u din U lui u i se asociaza o marca mu . Atunci G se numeste digraf: a. marcat b. etichetat c. complet Fie G=(X,U) digraf si a X incat d-(a)? 0 si nu exista circuit in G care sa contina pe a. Atunci pentru orice A X baza in G avem: a. a A b. a nu apartine lui A Fie G=(X,U) un digraf in care oricare ar fi a,b X, b este atins prin drumuri din a. Atunci G se numeste: a. conex b. complet c. tare conex Fie G=(X,U) un digraf si X x X relatie binara data prin: x y x=y sau (x este atins din y si y este atins din x). Atunci este relatie de: a. ordine b. preordine c. echivalenta Digraful redus al unui digraf dat este: a. conex b. complet c. ciclic d. aciclic Numarul bazelor digrafului redus asociat unui digraf dat este: a. 0 b. 1 c. 2 d. 3 29. Fie G=(X,U) un digraf, R=(S,Q) condensarea sa si A={S1, S2,...,Sp} unica baza a lui R. Atunci numarul bazelor lui G este: a. 1 b. p c. |S1|+|S2|+...+|Sp| d. |S1| |S2| ... |Sp|

m

____ c 55. Fie G=(X,U) un digraf cu n noduri, A matricea sa de adiacenta si Y=A , m= 1. Atunci numarul

____ d 56.

c 57. ____

d 58. ____

____ d 59.

tuturor drumurilor de la nodul xi la nodul xj care au cate m arce este: a. aij b. m aij c. yij d. myij Fie G=(X,U) un digraf cu n noduri si A matricea sa de adiacenta. Daca exista m= n incat Am = 0 atunci G este: a. conex b. ciclic c. neconex d. aciclic Fie G=(X,U) un digraf si M o multime minimala de K formule ale lui G. Atunci nodurile principale ale K-formulelor din M constituie: a. o componenta tare conexa a lui G b. o componenta conexa a lui G c. o baza a lui G Fie A=(X,U) un d-arbore binar complet cu n noduri terminale. Atunci |U| = p , unde p este: a. n-1 b. 2n c. n+1 d. 2(n-1) Fie A=(X,U) un d-arbore binar cu n noduri terminale, d1 nivelul maxim al unui nod terminal si d2 nivelul minim al unui nod terminal. Atunci A este d-arbore binar echilibrat d1-d2 este: a. =0 b. =1 c. d.

1 1 m

____ c 60. Fie A=(X,U) un d-arbore binar cu 2 noduri terminale si d nivelul unui nod terminal. Atunci d= a. m-1 b. m+1 c. m d. 2m m

____ e 61. Fie A=(X,U) un d-arbore binar cu un numar de noduri terminale cuprins intre 2 si 2

m+1

. Atunci

nivelul nodurilor terminale este: a. m b. m-1 c. m sau m-1 d. m+1 e. m sau m+1 ____ b 62. Se cunosc n metode de parcurgere a d-arborilor binari , unde n este: a. 2 b. 3 c. 4

b 63. In d-arborele binar complet asociat, unei expresii aritmetice in care intervin numai operatori binari, ____ nodurile neterminale sunt etichetate cu:

a. operanzi b. operatori ____ d 64. Numarul arborilor de sortare-cautare asociati unei liste cu n elemente este: a. 1 b. n c. n!-1 d. n! ____ 65. Complexitatea temporala a algoritmului de cautare a unei valori date intr-un arbore de sortared

cautare este: a. liniara b. constanta c. patratica d. logaritmica e. cubica ____ 66. Intr-un arbore de decizie asociat unei tabele de decizie nodurile terminale sunt etichetate cu: c a. conditii b. valorile 0 si 1 c. actiuni d 67. Fie T(n,m) o tabela de decizie si f(n) numarul arborilor de decizie asociati lui T. Atunci f(n)= ____ a.

n

i2

n i

i 1

b.

m

i2

m i

i 1

c.

m

i2

n i

i 1

d.

n

i2

n i

i 1

c 68. Fie R=(E, ei, ef, A, w) o retea de programare a activitatilor. Spunem ca R este ordonata topologic ____ oricare ar fi ij A avem: a. i=j b. i>j c. i<j ____ d 69. Algoritmul pentru ordonarea topologica a unei retele de programare a activitatilor se datoreaza lui: a. Ford b. Dijkstra c. Ford si Fulkerson d. Fulkerson ____ c 70. Fie G= (X,U) un graf conex, T=(X,V) un arbore de traversare al sau si e=xy o coarda a lui T. Atunci graful G=(X,VU{e}) contine: a. cel putin un ciclu

b. nici un ciclu c. exact un ciclu ____ a 71. Exista n modalitati standard de reprezentare a grafurilor, unde n este: a. 2 b. 3 c. 4 ____ b 72. Exista n metode de parcurgere a unui graf oarecare, unde n este: a. 2 b. 3 c. 4 ____ b 73. Fie G=(X,U) un digraf aciclic. Atunci G are n baze, unde n este: a. 0 b. 1 c. 2 d. 3 ____ 74. Fie G=(X,U) diraf cu n noduri, A matricea sa de adiacenta En matricea de ordin cu toate elementele c

1 si G =(X,V) complementarul lui G. Atunci matricea de adiacenta a lui G este: a. In A b. In + A c. En A d. En + A Yes/No Indicate whether you agree with the sentence or statement. ____ No 75. Este complet un graf G = (X,U) în care toate varfurile au acelasi grad strict mai mic decat | X | - 1 ____ Yes 76. Este bipartit un graf în care orice dou varfuri sunt adiacente? ____ Yes 77. Este graful icosaedrului un graf 5-regulat cu 12 varfuri? ____ No 78. Este graful dodecaedrului graf 4-regulat cu 20 vârfuri? ____ No 79. Este graful-stea un graf bipartit complet Kp,q cu p,q>1?

Yes 80. Este simetric un graf orientat G=(X,U) cu proprietatea c oricare ar fi (x,y) U => (y,x) U ____ ____ No 81. Pentru n

dat, exist diferen intre Kn si un graf (n-1)-regulat

____ No 82. Este matricea de adiacen a unui graf orientat simetric ? ____ No 83. Este adev rat afirma ia: Graful G=(X,U) este arbore <=> G este conex? ____ No 84. Este adev rat afirma ia: Graful G=(X,U) este arbore <=> G este aciclic? ____ Yes 85. Este adev rat afirma ia: Graful G=(X,U) este arbore <=> G este conex si |U| = |X| - 1 <=> G este aciclic i |U| = |X| - 1

No 86. Algoritmul lui Kruskal determin matricea drumurilor? ____ No 87. Algoritmul lui Roy-Warshall determin un arbore par ial de cost minim într-un graf conex ? ____ ____ Yes 88. Determin algoritmul lui Floyd matricea distan elor minime într-un graf dat ?

____ No 89. Determin algoritmul lui Dijkstra un arbore par ial de cost minim? ____ No 90. Este complexitatea temporal a algoritmului lui Dijkstra pentru un graf orientat cu n varfuri, cubic ? ____ fluxul de pe arcele de intrare i pentru iesirea t cu Yes 91. Dac într-o re ea de transport not m pentru sursa s cu fluxul de pe arcele de iesire este adev rat rela ia = ? ____ Yes 92. Este num rul vârfurilor de grad impar într-un graf neorientat un num r par ? Completion Complete each sentence or statement.

ARBORE 93. Un graf conex i aciclic se nume te ................... 94. Dac într-o re ea de transport G = ( X,U) pentru arcul u U not m cu (u) fluxul arcului u i cu c(u) SATURAT capacitatea lui u, atunci pentru (u) = c(u) spunem c arcul este ..................

GRADUL 95. Num rul tutror muchiilor incidente unui vârf x într-un graf se nume te ........................... lui x. TERMINAL 96. Un vârf de grad 1 se nume te vârf .......................... IZOLAT 97. Un vârf de grad zero se nume te vârf .............................. PAR 98. In orice graf neorientat num rul vârfurilor de grad impar este ..................... PARTIAL al lui G. 99. Dac dintr-un graf G = (X,U) elimin m anumite muchii ob inem un GRAF ...........................

100. Dac dintr-un graf G = (X,U) elimin m anumite vârfuri i toate muchiile incidente acestora ob inem un SUBGRAF ........................... al lui G. 101. Intr-un graf G = (X,U) o succesiune finit de vârfuri cu proprietatea c oricare dou vârfuri vecine sunt LANT adiacente se nume te .....................

ELEMENTAR 102. Dac intr-un lan toate nodurile sunt distincte, lan ul se nume te ........................ SIMPLU 103. Dac intr-un lan toate muchiile sunt distincte, lan ul se nume te ....................... CICLU 104. Un lan in care extremit ile coincid se nume te .................... CONEX 105. Un graf in care orice dou vârfuri sunt conectate printr-un lan se nume te .................... COMPONENTA CONEXA 106. Un subgraf conex i maximal cu aceastã proprietate se nume te .............................. COMPLET 107. Un graf în care orice dou vârfuri sunt adiacente se nume te graf ............................ REGULAT 108. Un graf în care toate vârfurile au acelasi grad se nume e graf ................. K-REGULAT 109. Dacã un graf este regulat i gradul comun al vârfurilor este k, graful se mai nume te i graf ................ n-1 regulat. 110. Un graf complet cu n vârfuri este (.....) CUBIC 111. Un graf 3-regulat se mai nume te graf ..................... 112. Dac mul imea vârfurilor unui graf admite o parti ie din douã blocuri încât fiecare muchie une te vârfuri din BIPARTIT blocuri distincte graful se nume te graf ................... 113. Dac intr-un graf bipartit orice vârf dintr-un bloc este adiacent cu orice vârf din celalalt bloc atunci graful se BIPARTIT COMPLET nume te graf ....................

STEA 114. Un graf bipartit format dintr-un vârf central adiacent cu alte n vârfuri se nume te graf ..............

CICLURI IMPARE 115. Un graf G este bipartit <=> nu con ine ........................ 116. Pentru un graf orientat G = (X,U) i x EXTERIORal lui x. se nume teGRAD .......................... 117. Pentru graful orientat G = (X,U) i x INTERIORal lui x. se nume teGRAD ..........................

X, num rul arcelor care au pe x extremitate ini ial (care pleac din x) X, num rul arcelor care il au pe x extremitate final deci care intr în x

118. Dac într-un graf orientat arcele unui lan au o aceiasi orientare, de la extremitatea initial spre extremitatea DRUM final , ob inem no iunea de ................ 119. Dac într-un graf orientat G = (X,U) pentru oricare (x,y)

U => (y,x)

SIMETRIC U graful se nume te ....................

CONEX 120. Dac într-un graf orientat orice dou vârfuri sunt conectate printr-un drum, graful se nume te TARE ......................... FRUNZE 121. Vârfurile terminale într-un arbore se mai numesc si ....................... PARTIAL 122. Dac într-un graf dat G un graf par ial al sau este arbore, acesta se nume te ARBORE ............................ al lui G.

123. Orice arbore cu n

VARFURI TERMINALE vârfuri are cel pu in dou ..................................

n-1 124. Orice arbore cu n vârfuri are ...................... muchii ARBORE PARTIAL

125. Algoritmul lui Kruskal determin într-un graf conex ponderat un ............................ de cost minim

COST MINIM 126. Algoritmul lui Kruskal produce un arbore par ial de .............................. DRUMURILOR MINIME

127. Algoritmul lui Dijkstra determin matricea ........................... ale unui graf MATRICEA DRUMURILOR

128. Algoritmul lui Roy-Warshall produce .................................. unui graf orientat. 129. Condi ia de conservare a fluxului în orice vârf x diferit de intrarea i ie irea unei re ele de transport spune c EGALA CU suma fluxurilor de pe arcele care ies din x. suma fluxurilor de pe arcele care intr în x este ..................... 130. Condi ia de marginire a fluxului de pe arcele unor re ele de transport spune c fluxul asociat unui arc nu DEPASEASCA trebuieSA ......................... capacitatea arcului respectiv. 131. Pentru re eaua de transport G = (X,U) i A X, mul imea arcelor lui G pentru care extremitatea ini ial nu se afl în A dar extremitatea final se g seste în A se nume te TAIETURA ................ de suport A

MINIMA a 132. Pentru orice re ea de transport valoarea maximã a fluxului la iesire este egala cu capacitatea ................... unei tãieturi 133. Dac G = (X,U) este un graf si pentru x

X, d(x) este gradul lui x atunci intre 2|U| si

avem rela ia

= .: 134. Graful complet Kn este ( n-1 )-regulat: 135. Rezultatul urm tor: Graful G esteBIPARTIT <=> nu con ine cicluri impare se datoreaz lui KÖNIG. 136. Num rul muchiilor unui graf COMPLETKn este

n 2

137. Num rul muchiilor unui graf bipartit complet Km,n este mn

:

138. Intr-un grafORIENTATG = (X,U) dac not m pentru x X cu d x gradul exterior al lui x i cu d x gradul s u interior atunci intre

si

avem rela ia =.

139. Matricea de adiacen a unui graf neorientat G = (X,U) este SIMETRICA . 140. Rangul matricei de inciden nod-arc pentru un graf conex cu n noduri i m muchii este n-1 . nod-arc pentru un graf cu n noduri i p componente conexe este n-p

141. Rangul matricei de inciden

142. Un graf G are un arbore par ial dac

i numai dac G este CONEX

..

..

vârfuri are cel pu in x vârfuri terminale, unde x =..2

143. Orice arbore cu n

144. Orice arbore cu n vârfuri are x muchii unde x = n-1 . 145. Algoritmul urm tor: Intrare: A-matricea de adiacen a unui graf cu n varfuri 1. Se face k=1. 2. Pentru i 1,..., n , j 1,..., n i i, j k se înlocuie elementele prin

min

a

ik

, a

kj

a

ij

0

.

3. Se repet pasul 2 pentru k MATRICEA DRUMURILOR determin la iesire lui G

2 ,...,

n

,

146. Algoritmul urm tor: Intrare: G = (X,U) conex cu n vârfuri i func ia de cost c 1. Dintre muchiile nealese ale lui U se selecteaz o muchie de cost minim care s nu formeze cicluri cu muchiile deja alese. 2. Dacã au fost alese n 1 muchii ne oprim, altfel se repet pasul 1, se datoreaz lui KRUSKAL 147. Complexitatea temporal a algoritmului lui KRUSKAL. pentru un graf cu n vârfuri i m muchii este

O m log m n 2 148. Algoritmul urm tor: Intrare: G = (X,U) un graf cu n varfuri, D - matricea distan elor dintre vârfuri 1. k 1 . 2. Pentru i 1,..., n , j 1,..., n , i j i i, j k se înlocuie elementul d prin ij

min

d

ij

, d

ik

d

kj

.

3. Se repet pasul 2 pentru k 2 ,..., n , produce la iesireMATRICEAdistan elor minime. 149. Complexitatea temporala a algoritmului lui FLOYD

pentru un graf cu n noduri este O(n3)

150. Algoritmul lui Dijkstra determin drumurile MINIME .. si lungimile acestora de la un vârf s dat la toate celelalte vârfuri 151. ComplexitateaTEMPORALAa algoritmului lui Dijkstra pentru un graf orientat cu n vârfuri este p tratic . 152. Pentru o re ea de transport, intre valoarea maxim a fluxului de ie ire i capacitatea minim a unei TAIETURI exist rela ia =. 153. Rezultatul urm tor: Pentru orice re ea de transport valoarea maxim a fluxului de ie ire este egal cu capacitatea minim a unei t ieturi" se datoreaz lui FORD -Fulkerson. 154. Intr-o re ea de transport pentru orice flux TAIETURI . exist rela ia

, intre

t-fluxul de

pe arcele de iesire i capacitatea oric rei

155. La sfâr itul aplic rii algoritmului Ford-Fulkerson, arcele ce unesc vârfurile etichetate cu varfurile neetichetate constituie o t ietur de capacitate MINIMA . 156. Fie G=(X,U) un graf in care |X| = n? 3 si pentru orice x X avem d ( x )

HAMILTONIAN .

n . Atunci G este graf 2

157. Fie G=(X,U) un graf fara varfuri izolate, conex si pentru orice x X, d(x) este numar par. Atunci G

este graf EULERIAN 158. Algoritmul pentru obtinerea unui ciclu eulerian intr-un graf eulerian se datoreaza lui

FLEURY

.

159. Algoritmul urmator:

intrare G=(X,U) graf eulerian fie x0 X arbitrar, i 0, V U while d(xi)? 0 do if xiy V ce nu este punte in (X, V) then do V V - {xiy} i i+1 xi y else do alege puntea xiy V V V {xiy} i i+1 xi y , EULERIAN determina in G un ciclu .................... 160. Fie G=(X,U) un graf si H=(X,V) un arbore de traversare al sau. Atunci elementele lui U-V se

numesc COARDE .ale lui H 161. Graful G=(X,U) contine un arbore de traversare < == > G este graf CONEX

..

162. Fie G=(X,U) un arbore cu |X| = 2 varfuri. Atunci numarul varfurilor terminale este cel putin 2 . 163. Fie G=(X,U) un graf in a carui reprezentare geometrica muchiile se intersecteaza doar in varfuri.

Atunci G este graf PLANAR

.

164. Daca G=(X,U) este un graf planar conex cu f fete atunci |X|-|U|+f=n, unde n este 2 165. Teorema care spune ca intr-un graf planar conex G=(X,U) cu f fete are loc relatia |X|-|U|+f=2 se

datoreaza lui EULER

. 166. Grafurile complete K5 si K3,3 sunt NEPLANARE 167. Teorema de caracterizare a grafurilor planare se datoreaza lui KURATOWSKI .. 168. Fie G=(X,U) un digraf cu |X|=n varfuri. Atunci numarul MAXIM .. de arce in G este n . 2

169. Fie G=(X,U) un digraf cu |X|=n varfuri si fara bucle (adica xx nu apartine lui U pentru orice x X).

Atunci numarul MAXIM .. de arce in G este n2-n. 170. Numarul tuturorDIGRAFURILOR ........................... cu n varfuri este 2 n

2

FARA BUCLE si cu n varfuri (|X|=n) este 2 n 171. Numarul tuturor digrafurilor G=(X,U) ........................

2

n