Parcurgerea unui graf in latime
1. Metoda generala
In tehnica de parcurgere in latime (breadth first search) ordinea in care sint vizitate virfurile rezulta astfel: prima data se viziteaza virful s, apoi succesorii lui s (evitind un virf deja vizitat), apoi succesorii succesorilor lui s, si asa mai departe. Metaforic vorbind putem spune ca aceasta tehnica descrie un cerc cu centrul in s si care se extinde (Larry, Denenberg, p 433-434) (Burdescu, p 43-52).
Prezentam mai jos tehnica generala de parcurgere a unui graf in latime. Initial toate virfurile sint nemarcate, si atunci cind un virf este intilnit prima data este marcat si introdus intr-o coada. Atunci cind un virf este extras din coada este vizitat si fiecare succesor este adaugat in coada, cu exceptia virfurilor deja intilnite care nu mai sint procesate.
Algoritm BreadthFirstSearch general (cf Lee, 1961);
Intrare. Un graf (X, G ) si un virf s din X.
Iesire. Mk, informatii obtinute de procedura de vizitare a virfurilor.
begin
for (each x I X) do Mk[x] False;
Q InitQueue(s); Mk[s] True;
while not EmptyQueue(Q) do begin
x DeQueue(Q); Visit(x);
for (each y I G (x)) do
if Mk[y] False) then begin
Mk[y] True; EnQueue(Q,y);
end
end (algoritm).
Operatia initiala de stergere a marcajelor necesita un timp de ordin O(n). Dupa cum vom vedea in exemplele prezentate in sectiunile urmatoare, procedura de Visit necesita un timp de ordin constant pentru un virf oarecare. Fiecare arc este parcurs cel mult de doua ori (cite o data pentru fiecare virf al sau vizitat), si fiecare virf este introdus in / extras din coada cel mult o data.
Sa observam ca algoritmul prezentat mai sus proceseaza virfurile grafului intr-o ordine care depinde de modul cum sint descrise listele succesorilor fiecarui virf.
Prezentam in continuare o tehnica foarte simpla de implementare a cozii, valabila numai pentru grafuri statice. Coada Q este un masiv cu n elemente, si limitele u si v au semnificatia urmatoare:
u - pozitia primului element care va fi extras din coada;
v - pozitia unde va fi inserat urmatorul element in coada.
Operatiile asupra cozii se implementeaza astfel:
Operatie Implementare
Q InitQueue(s); Q[0] s; u v
not EmptyQueue(Q) (u < v)
x DeQueue(Q); x Q[u]; u u
EnQueue(Q,y); Q[v] y; v v
Presupunind ca prelucrarea unui virf (procedura Visit) dureaza o unitate de timp, obtinem
Teorema 1. Parcurgerea in latime a unui graf necesita un timp de ordin O(n m
Componente conexe
Definitia 1. Un graf neorientat este conex daca intre orice doua virfuri exista un lant.
Un graf conex si fara cicluri se numeste arbore.
O componenta conexa a unui graf neorientat este un subgraf conex maximal in raport cu operatia de incluziune. Cu alte cuvinte, nu exista o submultime de virfuri mai numeroasa care sa induca un subgraf conex.
Problema Fie un graf neorientat G = (X, G ); sa se determine componentele sale conexe.
Aplicatie X reprezinta o multime de calculatoare, si G indica pentru fiecare calculator care sint calculatoarele conectate direct la acesta. Evident, fiecare conexiune este in ambele sensuri. Sa se determine cite retele independente exista, si care sint calculatoarele care compun fiecare retea (figura 1).
Figura 1. Graf cu doua componente conexe: si .
Algoritm CompConexe;
Intrare. Un graf neorientat (X, G
Iesire. Un masiv C: componentele conexe ale acestuia.
begin
for (each s I X) do C[s]
k
for (each s I X) do
if (C[s] 0) then begin
k k u v
C[s] k; Q[0] s;
while (u < v) do begin
x Q[u]; u u
for (each y I G (x)) do
if (C[y] 0) then begin
Q[v] y; v v
C[y] k;
end
end
end
end (algoritm).
Ideea acestui algoritm este urmatoarea. Initial toate virfurile sint nemarcate si nu avem determinata nici o componenta conexa. Primul virf nemarcat (fie acesta s) desemneaza prima componenta conexa depistata si aceasta va include toate virfurile care pot fi atinse cu ajutorul unui drum care pleaca din s. Pentru aceasta se introduc intr-o coada si se marcheaza toti succesorii nemarcati ai lui s. In continuare se extrage cite un virf din coada si se repeta procedura pina cind coada devine goala. In acest moment am determinat toate virfurile care fac parte din aceeasi componenta conexa ca si s. Toate virfurile sint marcate cu 1.
Urmatorul virf nemarcat desemneaza urmatoarea componenta conexa pentru care se repeta aceeasi procedura. Toate virfurile care fac parte din aceeasi componenta conexa sint marcate cu numarul de ordine al acesteia. In masivul C se memoreaza pentru fiecare virf componenta careia ii apartine.
3. Grafuri bipartite
Definitia Un graf neorientat G (X, U )
este bipartit daca exista o partitie X X1
X2
astfel incit pentru orice (x,y) I U avem x I X si y I X Caracterizarea unui graf bipartit este
data de
Teorema 2 (König) Urmatoarele afirmatii sint echivalente:
(i) un graf G este bipartit;
(ii) un graf G este bicromatic (poate fi colorat cu doua culori astfel incit doua virfuri adiacente sa fie colorate diferit);
(iii) un graf G nu contine cicluri de lungime impara.
Problema. Fie un graf neorientat G = (X, G ); sa se coloreze graful cu doua culori astfel incit oricare doua virfuri adiacente sa fie colorate cu culori diferite (figura 2).
Aplicatie X reprezinta o multime de muncitori si masini, si G indica pentru fiecare muncitor pe care masini poate lucra, respectiv pentru fiecare masina care muncitori o pot utiliza. Ne punem intrebarea daca graful este corect descris; raspunsul la aceasta intrebare il aflam dupa ce incercam sa coloram graful cu doua culori.
Figura Un graf bipartit: X1 = , X
Algoritm Bipartit;
Intrare. Un graf neorientat (X, G
Iesire. Un masiv C: culoarea fiecarui virf (1 sau 2).
Valoare returnata True sau False: graful este sau nu bipartit.
begin
for (each s I X) do C[s]
for (each s I X) do
if (C[s] 0) then begin
C[s] ; Q[0] s;
u v
while (u < v) do begin
x Q[u]; u u
for (each y I G (x)) do
if (C[y] 0) then begin
Q[v] y; v v
C[y] 3 - C[x];
end
else
if C[y] C[x]) then
return False
end
end
return True
end (algoritm).
Ideea acestui algoritm este urmatoarea. Initial toate virfurile sint nemarcate. Primul virf nemarcat (fie acesta s) este marcat cu culoarea 1 si toti succesorii sai nemarcati se introduc intr-o coada si se marcheaza cu culoarea In continuare se extrage cite un virf din coada si se repeta procedura pina cind coada devine goala. Daca un virf extras din coada are culoarea 2, toti succesorii sai nemarcati se marcheaza cu culoarea 1. In acest moment am marcat toate virfurile care fac parte din aceeasi componenta conexa ca si s.
Urmatorul virf nemarcat desemneaza urmatoarea componenta conexa pentru care se repeta aceeasi procedura de colorare.
Este posibil uneori ca un virf sa aiba un succesor marcat. Daca marcajele celor doua virfuri difera se continua cu alt succesor. Daca in schimb marcajele celor doua virfuri coincid graful nu poate fi colorat cu doua culori, deci nu este bipartit.
4. Ordonare topologica
Definitia 3.
Intr-un graf orientat, doua virfuri distincte x si y sint in relatie de ordine
topologica, notatie x
y, daca este indeplinita una din
urmatoarele conditii:
- fie exista un drum de la x la y si nu exista nici un drum de la y la x;
- fie nu exista nici drum de la x la y, nici drum de la y la x.
In al doilea caz relatia de ordine topologica
poate fi definita si altfel: yx, dar in acest caz nu mai poate fi definita
relatia xy.
Aceasta relatie de ordine este doar tranzitiva si nu poate fi definita intre doua virfuri care apartin unui circuit. Relatia este partiala si este doar tranzitiva; nu este reflexiva, nici simetrica, nici antisimetrica.
Figura 3. Ordonare topologica.
In figura 3 sint marcate rangurile virfurilor in conformitate cu ordonarea topologica. O ordonare topologica posibila este: (x0, x2, x1, x3, x4), cu precizarea ca virfurile x0 si x2 sint interschimbabile pe primele doua pozitii, si virfurile x1 si x3 sint interschimbabile pe urmatoarele doua pozitii.
Problema. Fie un graf orientat G = (X, G ); sa se ordoneze topologic virfurile din multimea X in concordanta cu relatiile definite de functia G
Aplicatie (capitolul cinci). X reprezinta o multime de activitati, si G reprezinta legaturi de tipul urmator: y I G (x) daca activitatea y se poate executa numai dupa ce s-a terminat activitatea x (terminarea activitatii x este necesara pentru a putea incepe activitatea y). Impreuna cu ordonarea topologica se va determina si rangul fiecarui virf, care arata pozitia acestuia in lista ordonata. Pot exista mai multe virfuri cu acelasi rang, daca intre acestea nu exista nici o relatie de dependenta.
Algoritm TopoSort;
Intrare. Un graf neorientat (X, G
Iesire. Un masiv Q: virfurile grafului in ordine topologica.
Un masiv R: rangul fiecarui virf.
Valoare True sau False: graful nu are (sau are) circuite.
begin
Se determina (prin inspectare G ) valorile g (x) pentru fiecare virf x:
for (each x I X) do g (x)
for (each x I X) do
for (each y I G (x)) do g (y) g (y)
Toate virfurile x pentru care g (x) 0 se introduc in coada Q:
v
for (each x I X) do
if g (x) then begin
Q[v] x; v v
R[x]
end
Se ordoneaza topologic virfurile grafului
while (u < v) do begin
x Q[u]; u u
for (each y I G (x)) do begin
g (y) g (y) - 1;
if (g (y) 0) then begin
Q[v] y; v v
R[y] R[x]
end
end
end
return (v n);
end (algoritm).
Ideea acestui algoritm este urmatoarea. Initial se determina, prin inspectarea tuturor virfurilor grafului si a fiecarui succesor, gradul interior al fiecarui virf. Virfurile care au gradul interior zero (nu au predecesori) sint introduse in coada, toate aceste virfuri avind rangul zero. In continuare se extrage cite un virf x din coada, si se reduce cu o unitate gradul interior al fiecarui succesor y I G (x). Daca un succesor y ajunge sa aiba gradul interior zero, acesta este introdus in coada si i se asociaza rangul imediat urmator: R[x]
In final, dupa ce coada devine vida, se verifica daca au trecut prin coada toate cele n virfuri ale grafului. In caz afirmativ graful nu are circuite si se poate defini o relatie de ordine topologica pe multimea virfurilor acestuia.
Acest algoritm va fi folosit in capitolul cinci, rezervat problemei de ordonantare.
Ideea acestui algoritm este preluata din literatura franceza (Gondran, Minoux, p 41-44) unde se determina si rangul fiecarui virf. Alte lucrari prezinta algoritmi bazati pe parcurgerea in adincime (Larry, Denenberg, p 436-438) (Burdescu, p 69-74).
