EXERCITII MULTIMI
1.S se descrie un
algoritm care sa genereze toate grafurile cu mul imea
de virfuri 
.
2.Interpreta i
combinatoriu elementele puterilor
succesive 
, unde A este
matricea de adiacen a grafului G.
3.
se numeste secven
grafic dac exist G un graf cu n
virfuri
astfel incit 
. S se descrie un
algoritm care s decid pentru un D dat dac este sau nu secven
grafic
Demonstra i
c un graf G este conex dac i
numai dac oricare ar fi o parti ie 
,
exist 
astfel nc t
.
5. Demonstra i c un graf conex G este complet dac i numai dac mul]imea vecinilor
oricrui v@rf de grad maxim `n G este clic.
Demonstra i c oricare ar fi G un graf, m car
unul din grafurile G sau 
este conex.
7. Demonstra i c n orice graf conex G cu cel pu in dou v rfuri, exist m car dou v rfuri care nu-s puncte de articula ie.
8. Demonstra i c
oricare ar fi G un graf autocomplementar 
: este conex, 
; are m car un subgraf izomorf cu 
.
9. Se d un graf G i
astfel nc t
. Descrie i un
algoritm care s construiasc o parti ie
astfel nc t
i 
.
10. Fie 
un graf.
Definim 
graful cu
mul]imea v@rfurilor 
[i cu mul]imea
muchiilor 
.
Se consider pentru 
grafurile 
definite recursiv
astfel:
a)
Desenati 
.
b)
Determina]i
ordinul [i dimensiunea lui
c)
Dat n s se
construiasc matricea de adiacen] a lui .
d)
Demonstra]i c este bipartit [i s se
construiasc o biparti]ie a sa.
e)
S se determine
numrul de stabilitate al lui .
f)
Demonstra]i
algoritmic c este hamiltonian.
11. Fie T un arbore reprezentat cu ajutorul listelor de adiacen .
a) S se modifice reprezentarea astfel incat:
- fiecare lista de adiacen s fie circular (ultimul element puncteaza la primul).
-fiecare element al listei de adiacent A(v) con ine: vecinul curent (u); un pointer next ctre urmatorul element al listei,; un pointer invers c tre elementul din lista de adiacen a lui u care il con ine pe v; un pointer succesor care este neini ializat.
b)
Pentru orice element din listele de adiacenta, se pune succesor 
invers
.next. Se observ c
dac elementul reprezint arcul vu, atunci succesor puncteaz la un
arc uw. Demonstrati ca in acest fel (cu ajutorul pointerului succesor) se ob ine o organizare de tip list circular
a elementelor din listele de adiacen
12. Fie G un graf reprezentat cu ajutorul listelor de
adiacenta, cu multimea virfurilor . Se cere sa se
ordoneze 
astfel incat:
.
Aceasta ordonare se numeste ordinea max-adiacenta. Complexitatea algoritmului: O(n+m).
13. S se testeze dac un graf dat este bipartit utilizind parcurgerea bfs.
14. Dat D un digraf s se decid in O(n+m) dac are un circuit folosind parcurgerea dfs.
Fie un graf cu 
Demonstra]i c dac 
, atunci G este conex.
16. In graful notam 
Descrie]i un algoritm de complexitate
pentru aflarea unui v@rf de grad minim `ntr-un graf G dat cu ajutorul listelor de adiacen].
17. Fie un graf [i 
. Dac s [i t sunt dou v@rfuri ale lui G, se
define[te locul `ingust al drumului 
de la s la t ca fiind 
.
Descrie]i un algoritm care s determine drumul de la s la t cu locul `ngust maxim.
18. Desrcieti un algoritm care sa determine pentru un graf (dat cu ajutorul listelor de adiacenta) componenta conexa cu numar maxim de virfuri.
19. Fie un digraf complet fr perechi de arce simetrice
(turneu). S se construiasc un drum hamiltonian `n G.
a) Fie G un graf bipartit k-regulat (
). Demonstra]i c G
are un cuplaj
M astfel 1nc@t fiecare v@rf al grafului este incident cu o muchie din cuplaj.
b) Demonstra]i c pentru orice graf bipartit H cu gradul maxim k, se poate construi un graf bipartit G k-regulat astfel `nc@t H este subgraf indus al lui G.
c) Deduce]i c `n orice graf bipartit G exist un cuplaj M cu proprietatea c
.
Fie D un digraf [i 
. S se determine 
circuit `n D astfel
`nc@t 
.
Fie T un arbore cu 
v@rfuri 
. Pentru 
se execut : se
[terge v@rful pendant cel mai mic [i se pune 
vecinul acestui v@rf
pendant. Se ob]ine vectorul 
=
care se nume[te codul Prüfer asociat lui T. Implementa]i
algoritmul de ob]inere a lui pentru un T dat.
Fie G un graf
conex [i 
familia arborilor si
par]iali. Se consider graful
unde 
.
Demonstra]i c H este conex.
Arta]i c dac T este un arbore, atunci prin orice v@rf pendant trece o
mul]ime stabil de cardinal maxim a lui T. Deduce]i un algoritm pentru
determinarea lui 
.
25. Arta]i c `n orice digraf G, exist o mul]ime S de v@rfuri astfel `nc@t S este mul]ime stabil `n graful suport asociat [i orice v@rf dinafara lui S este accesibil din S pe un drum de lungime cel mult 2 (S se nume[te seminucleu). Dac drmul anterior se cerea s fie de lungime 1 se ob]inea ceea ce se nume[te nucleu. Construi]i un digraf care nu are nucleu.
26. Fie G=(V,E) un graf cu 
. Demonstra]i c
exist o 2-parti]ie a lui V astfel `nc@t numrul muchiilor cu extremit]i `n
clase diferite ale parti]iei este mcar 
.
Care este numrul total de sec]iuni ale unei re]ele al crei digraf suport are n+2 v@rfuri ?
Un arc al unei re]ele R=(G,s,t,c) se nume[te vital dac `ndeprtarea sa din G provoac cea mai mare scdere a valorii fluxului maxim de la s la t . Descrie]i un algoritm polinomial de determinare a unui arc vital.
Demonstra]i c dac G este bipartit, atunci 
.
30. Fie G un graf conex cu 
.
Demonstra]i c 
.
Arta]i c `n orice graf exist mcar dou v@rfuri de acela[i grad.
Fie G un graf de ordin n astfel inc@t pentru v@rfurile neadiacente v [i w ale sale are loc inegalitatea 
. Demonstra]i c G este hamiltonian dac [i numai dac G+vw este hamiltonian. Fie G un graf cu proprietatea c pentru orice
dou v@rfuri neadiacente este
satisfcut inegalitatea de mai sus. Demonstra]i c G este hamiltonian [i
construi]i un circuit hamiltonian `n G `n timp polinomial.
|
