Algoritmica

Algoritmul ce raspunde la intrebarea Este un graf dat G=(X,U) ciclic? se datoreaza lui: d. Marimont Algoritmul urmator: c. componenta conexa ce contine pe x0 Algoritmul urmator: c. matricea distantelor minime Algoritmul urmator: b. un ciclu eulerian Algoritmul urmator: determina in G un ciclu EULERIAN Algoritmul urmator: determina la iesire MATRICEA DRUMURILOR lui G Algoritmul urmator: Se repeta pasul 2 pt k 2,...,n, determina la iesire c. matricea drumurilor lui G Algoritmul urmator: se datoreaza lui KRUSKAL Algoritmul urmator: produce la iesirea MATRICEA distantelor minime. Algoritmul urmator: Intrare: G = (X,U) conex cu n vârfuri i func ia de cost c e. Kruskal Algoritmul lui Dijkstra determina drumurile MINIME si lungimile acestora de la un vârf s dat la toatecelelalte vârfuri Algoritmul lui Dijkstra determin matricea DRUMURILOR MINIME ale unui graf Algoritmul lui Dijkstra:d.drumurile minime si lungimile acestora de la un vârf s dat la toate celelalte vârfuri Algoritmul pt. ordonarea topologica a unei retele de programare a activitatilor se datoreaza lui: d. Fulkerson Algoritmul pt. obtinerea unui ciclu eulerian intr-un graf eulerian se datoreaza lui FLEURY Algoritmul pt. obtinerea unui ciclu eulerian intr-un graf eulerian se datoreaza lui: d. Fleury Algoritmul lui Kruskal determina matricea drumurilor? NO Algoritmul lui Kruskal determina într-un graf conex ponderat un ARBORE PARTIAL de cost minim Algoritmul lui Kruskal produce un arbore partial de COST MINIM Algoritmul lui Kruskal produce: c. un arbore partial de cost minim in G Algoritmul lui Roy-Warshall produce MATRICEA DRUMURILOR unui graf orientat. Algoritmul lui Roy-Warshall determin un arbore par ial de cost minim într-un graf conex ? NO Complexitatea temporala algoritmului lui KRUSKAL pentru un graf cu n vârfuri i m muchii esteO mlog m n2 Complexitatea temporala a algoritmului lui FLOYD pentru un graf cu n noduri este O(n3) Complexitatea TEMPORALA a algoritmului lui Dijkstra pentru un graf orientat cu n vârfuri este patratic Complexitatea temporal a algoritmului lui Kruskal pentru un graf cu n vârfuri i m muchii este:b. O mlog m n2 Complexitatea temporala a algoritmului lui Floyd pentru un graf cu n noduri este: d. O(n3) Complexitatea temporal a algoritmului lui Dijkstra pentru un graf orientat cu n vârfuri este:b. patratic Complexitatea temporala a algoritmului de cautare a unei val date in arbore de sortare cautare este:d. logaritmica Conditia de conservare a fluxului în orice vârf x diferit.. EGALA CU suma fluxurilor de pe arcele care ies din x. Conditia de marginire a fluxului de pe arcele unor re ele de trp..tr SA DEPASEASCA capacitatea arcului respectiv. Daca G = (X,U) este un graf si pentru x X, d(x) este gradul lui x atunci intre 2|U| si avem relatia: b. = Daca G=(X,U) este un graf planar conex cu f fete atunci |X|-|U|+f=n, unde n este: c. 2 Daca dintr-un graf G = (X,U) elim anumite muchii obtinem un GRAF PARTIAL al lui G. Daca dintr-un graf G = (X,U) elim anumite vârfuri si toate muchiile incidente acestora obtinem un SUBGRAF al lui G Daca G=(X,U) este un graf planar conex cu f fete atunci |X|-|U|+f=n, unde n este 2 Daca au fost alese n 1 muchii ne oprim, altfel se repet pasul 1,se datoreaza lui: e. Kruskal Daca într-o retea de transport notam pentru sursa s cu fluxul de pe arcele de intrare si pentru iesirea t cu fluxul de pe arcele de iesire este adevarat relatia = ? YES Daca într-o retea de transport G = ( X,U) pentru arcul u U not m cu (u) fluxul arcului u i cu c(u) capacitatea lui u, atunci pentru (u) = c(u) spunem ca arcul este SATURAT Daca intr-un lan toate nodurile sunt distincte, lantul se numeste ELEMENTAR Daca intr-un lan toate muchiile sunt distincte, lantul se numeste SIMPLU Daca un graf este regulat i gradul comun al vârfurilor este k, graful se mai nume te i graf K-REGULAT Daca multimea vârfurilor unui graf admite o partitie din douã blocuri încât fiecare muchie uneste vârfuri din blocuri distincte graful se nume te graf BIPARTIT Daca intr-un graf bipartit orice vârf dintr-un bloc este adiacent cu orice vârf din celalalt bloc atunci graful se numeste graf BIPARTIT COMPLET Daca într-un graf orientat arcele unui lan au o aceiasi orientare, de la extremitatea initial spre extremitatea final, obtinem notiunea de DRUM Daca într-un graf orientat G = (X,U) pentru oricare (x,y) U => (y,x) U graful se nume te SIMETRIC Daca într-un graf orientat orice doua vârfuri sunt conectate printr-un drum, graful se numeste TARE CONEX Daca au fost alese n 1 muchii ne oprim, altfel se repeta pasul 1,se datoreaza lui KRUSKAL Determin algoritmul lui Floyd matricea distan elor minime într-un graf dat ? YES Determin algoritmul lui Dijkstra un arbore par ial de cost minim? YES Digraful redus al unui digraf dat este: d. Aciclic Este complexitatea temporal a algoritmului lui Dijkstra pentru un graf orientat cu n varfuri, cubic? NO Este nr vârfurilor de grad impar într-un graf neorientat un numar par? YES Exista n modalitati standard de reprezentare a grafurilor, unde n este: a. 2 Exista n metode de parcurgere a unui graf oarecare, unde n este: b. 3 Este complet un graf G = (X,U) în care toate varfurile au acelasi grad strict mai mic decat | X | - 1 NO Este bipartit un graf în care orice dou varfuri sunt adiacente? YES Este graful icosaedrului un graf 5-regulat cu 12 varfuri? YES Este graful dodecaedrului graf 4-regulat cu 20 vârfuri? NO Este graful-stea un graf bipartit complet Kp,q cu p,q>1? NO Este simetric un graf orientat G=(X,U) cu proprietatea c oricare ar fi (x,y) U => (y,x) U YES Este matricea de adiacen a unui graf orientat simetric ? NO Este adevarata afirmatia: Graful G=(X,U) este arbore <=> G este conex? NO Este adevarata afirmatia: Graful G=(X,U) este arbore <=> G este aciclic? NO Este adev afirmatia:GrafulG=(X,U)e arbore<=>G este conex si|U|=|X|-1<=>Geste aciclic i|U| = |X| - 1 YES

Fie T(n,m) o tabela de decizie si f(n) numarul arborilor de decizie asociati lui T. Atunci f(n)= a=d Fie R=(E, ei, ef, A, w)o retea de progr a activ.Sp ca R este ordonata topologic oricare ar fi ij A avem:c. i<j Fie G= (X,U)un graf conex,T=(X,V)un arb de trav al sau si e=xy o coarda a lui T. c.exact un ciclu Fie G=(X,U)un digraf aciclic. Atunci G are n baze, unde n este:nb. 1 Fie G=(X,U)diraf cu n noduri, A matricea sa de adiacenta En matricea de ordin cu toate elem c. En A Fie G=(X,U)un graf in care |X| = n? 3 si pentru orice x X avem 2( )nd x. Atunci G este graf FLEURY Fie G=(X,U)un graf fara varfuri izolate,conex si pt orice x X, d(x)este nr par.At Geste graf EULERIAN Fie G=(X,U)un graf si H=(X,V)un arbore de travers al sau. At elem lui U-V se num COARDE ale lui H Fie G=(X,U)un arbore cu |X| = 2 varfuri. Atunci numarul varfurilor terminale este cel putin 2 Fie G=(X,U)un graf in a carui reprez geometrica muchiile se intersect doar in varfuri.At G este graf PLANAR Fie G=(X,U)un digraf cu |X|=n varfuri. Atunci numarul MAXIM de arce in G este n2. Fie G=(X,U)un digraf cu|X|=n varfuri si fara bucle.At nr MAXIM de arce in G este n2-n. Fie G=(X, U)un graf si X x X o rel binara pe X data prin:x y< = >x=y sau exista b. relatie de echivalenta Fie G=(X,U)un graf in care |X| = n? 3 si pentru orice x X avem b. Hamiltonian Fie G=(X,U)un graf fara varfuri izolate,conex si pt orice x X, d(x) este nr par.Atunci Geste: a. Eulerian Fie G=(X,U)un graf.Se numeste arbore de traversare un graf partial H=(X,V) al lui G care este: c. arbore Fie G=(X,U)un graf si H=(X,V) un arbore de traversare al sau. b. coarde ale lui H Fie G=(X,U)un arbore cu |X| = 2 varfuri.At nr varfurilor terminale este: c. cel putin 2 Fie G=(X,U)un graf in a carui reprez geometrica muchiile se intersecteaza doar in varfuri. d. planar Fie G=(X,U)un digraf cu |X|=n varfuri. Atunci numarul maxim de arce in G este: c. n2 Fie G=(X,U)un digraf cu |X|=n varfuri si fara bucle (adica xx nu apartine lui U pt orice x X).b. n2-n Fie G=(X,U)digraf in care exista x X caruia i se asociaza o eticheta pentru a-l identifica. b. etichetat Fie G=(X,U)un digraf in care pentru orice u din U lui u i se asociaza o marca mu . a. marcat Fie G=(X,U)digraf si a X incat d-(a)? 0 si nu exista circuit in G care sa contina pe 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. 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 c. Echivalenta Fie G=(X,U)un digraf, R=(S,Q) condensarea sa si A={S1, S2,...,Sp} unica baza a lui R. c. |S1|+|S2|+...+|Sp| Fie G=(X,U)un digraf cu n noduri, A matricea sa de adiacenta si Y=Am, m= 1. Atunci nr c. yij Fie G=(X,U)un digraf cu n noduri si A matricea sa de adiacenta. Daca exista m= n incat Am = 0 d. aciclic Fie G=(X,U)un digraf si M o multime minimala de K formule ale lui G. Atunci nodurile 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: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 d. 1 Fie A=(X,U)un d-arbore binar cu 2m noduri terminale si d nivelul unui nod terminal.Atunci d= c. m Fie A=(X,U) un d-arbore binar cu un numar de noduri terminale cuprins intre 2m si 2m+1. e. m sau m+1 Graful complet Kn este: c. (n-1)-regulat Graful complet Kn este (N-1)-regulat: Graful G=(X,U) contine un arbore de traversare < == > G este graf: a. Conex Graful G=(X,U) contine un arbore de traversare < == > G este graf CONEX Grafurile complete K5 si K3,3 sunt NEPLANARE Grafurile complete K5 si K3,3 sunt: c. Neplanare In d-arborele binar complet asociat, unei expresii aritmetice in care intervin numai b. operatori In orice graf neorientat numarul vârfurilor de grad impar este PAR Intr-o retea de transport pentru orice flux ,intre t-fluxul de pe arcele de iesire i capacitatea : a. < Intr-o retea de trp pt orice flux ,intre t-fluxul de pe arcele de iesire si capacitateaTAIETURI exista rel. Intr-un graf orientat G = (X,U) daca notam pentru x X cu d x gradul exterior al lui x i cu d x gradul: b. = Intr-un graf G = (X,U) o succesiune finit de vârfuri cu propr c oricare doua vârfuri vecine sunt… LANT Intr-un graf ORIENTAT G = (X,U) daca notam pentru x X cu d x gradul exterior al lui x i cu d xgradul Intr-un arbore de decizie asociat unei tabele de decizie nodurile terminale sunt etichetate cu: c. Actiuni La sfârsitul aplic algoritm lui Ford-Fulkerson,arcele ce unesc vârfurilea. o taietura de capacitate minim La sfârsitul aplicarii algoritmi Ford-Fulkerson,arcele ce unesc vârfurile etichetate cu varfurile..MINIMA Matricea de adiacen a unui graf neorientat G = (X,U) este: b. simetric Matricea de adiacen a unui graf neorientat G = (X,U) este SIMETRICA Numarul tuturor DIGRAFURILOR cu n varfuri este 2 2n Numarul tuturor digrafurilor G=(X,U) FARA BUCLE si cu n varfuri (|X|=n) este n n 2 2 Numarul muchiilor unui graf complet Kn este: b. n/2 Numarul muchiilor unui graf bipartit complet Km,n este: a. mn Numarul tuturor grafurilor cu n noduri este: c. 2…n-1 Numarul tuturor digrafurilor cu n varfuri este: a. 2 2n Numarul tuturor digrafurilor G=(X,U) fara bucle (xx nu apartine lui U pentru orice x X) d. n2 n 2 Numarul digrafurilor complete cu n varfuri ( n = 2) este: c. 3 Numarul bazelor digrafului redus asociat unui digraf dat este: b. 1 Numarul arborilor de sortare-cautare asociati unei liste cu n elemente este: d. n! Numarul tuturor muchiilor incidente unui vârf x într-un graf se nume te GRADUL lui x. Numarul muchiilor unui graf COMPLET Kn este 2/n Numarul muchiilor unui graf bipartit complet Km,n este : MN

Orice arbore cu n vârfuri are cel pu in x vârfuri terminale, unde x =: b. 2 Orice arbore cu n vârfuri are x muchii unde x = : c. n-1 Orice arbore cu n vârfuri are cel pu in doua VARFURI TERMINALE Orice arbore cu n vârfuri are N-1 muchii Orice arbore cu n vârfuri are cel pu in x vârfuri terminale, unde x = 2 Orice arbore cu n vârfuri are x muchii unde x = N-1 Pt o retea de transport, intre valoarea maxim a fluxului de iesire si capacitatea minim a exista relatia: a. = Pt o retea de transport, intre valoarea maxim a fluxului de iesire si capacitatea minim a unei TAIETURI Pt n dat, exist diferen intre Kn si un graf (n-1)-regulat NO Pt un graf orientat G = (X,U) i x X, nr arcelor care au pe x..se numeste GRAD EXTERIOR al lui x. Pt graful orientat G = (X,U) i x X, nr arcelor care il au pe x extremitate final deci.. GRAD INFERIOR al lui x. Pt reteaua de transport G = (X,U) i A X, mul imea arcelor lui G pt care extremitatea… TAIETURA de suport A Pt orice retea de transport valoarea maximã a fluxului la iesire este egala cu capacitatea MINIMA a.. Rangul matricei de inciden nod-arc pentru un graf conex cu n noduri i m muchii este: c. n-1 Rangul matricei de inciden nod-arc pentru un graf cu n noduri i p componente conexe este: b. n-p Rangul matricei de inciden nod-arc pentru un graf conex cu n noduri i m muchii este N-1 Rangul matricei de inciden nod-arc pentru un graf cu n noduri i p componente conexe este N-P Rezultatul urmator:Graful G este bipartit <=> nu contine cicluri impare se datoreaz lui:b. KÖNIG Rezultatul urmator:Graful G este BIPARTIT <=> nu contine cicluri impare se datoreaz lui KÖNIG. Rezultatul urmator:Pt orice retea de trp val max a fluxului de iesire este egal cu capacitatea c. Ford-Fulkerson Rezultatul urmator:Pt orice retea de transport valoarea maxim a fluxului de iesire...FORD-Fulkerson. Se cunosc n metode de parcurgere a d-arborilor binari , unde n este: b. 3 Teorema care spune ca intr-un graf planar conex G=(X,U) cu f fete are loc relatia |X|-|U|+f=2 se dat. EULER Teorema de caracterizare a grafurilor planare se datoreaza lui KURATOWSKI Teorema care spune ca intr-un graf planar conexG=(X,U)cu f fete are loc relatia|X|-|U|+f=2se dat lui:c. Euler Teorema de caracterizare a grafurilor planare se datoreaza lui: c. Kuratowski Un graf G are un arbore partial daca si numai daca G este CONEX Un graf G are un arbore partial daca si numai daca G este: d. conex Un graf in care orice dou vârfuri sunt conectate printr-un lan se nume te CONEX Un graf în care orice dou vârfuri sunt adiacente se nume te graf COMPLET Un graf în care toate vârfurile au acelasi grad se nume e graf REGULAT Un graf complet cu n vârfuri este (N-1) regulat. Un graf 3-regulat se mai nume te graf CUBIC Un graf bipartit format dintr-un vârf central adiacent cu alte n vârfuri se nume te graf STEA Un graf G este bipartit <=> nu con ine CICLURI IMPARE Un lan in care extremit ile coincid se nume te CICLU Un subgraf conex i maximal cu aceastã proprietate se nume te COMPONENTA CONEXA Un vârf de grad 1 se numeste vârf TERMINAL Un vârf de grad zero se numeste vârf IZOLAT Vârfurile terminale într-un arbore se mai numesc si FRUNZE