Curs 4.

Grafuri: componente conexe,

cicluri hamiltoniene si euleriene,

parcurgerea in latime si adancime

Fie X={x1,...,xn} multime finita, fie M⊆X⨯X (produs cartezian)

Definitie. Se numeste graf perechea ordonata G=(X,M).

Elementele xiϵX se numesc noduri/varfuri.

Elementele multimii M se numesc muchii/ arce.

O muchie (xk , xl) ϵM se noteaza si cu [xk , xl].

Exemplu.

x1

x4
x2

x3

1
 X={x1,x2,x3,x4}; M={[x1, x2], [x2, x1],[x1,x4],...}

Multimea M este simetrica ddaca din [x,y]ϵM⇒[y,x]ϵM.

Daca M nu este simetrica, graful se numeste orientat. Altfel, se

numeste neorientat.

Reprezentarea grafurilor

[Link] de adiacenta A=(aij)

{
a ij= 1 ,(x i , x j)∈ M
0 ,altfel

[Link] costurilor

{
c , daca ∃ arc de cost c >0 intre isi j
a ij= 0 , daca i= j
±∞ , daca ∄ arc intrei si j

(se foloseste +∞ daca se cere drum de lungime minima intre doua

noduri, si – ∞ daca se cere drum de lungime maxima)

[Link] nodurilor adiacente fiecarui nod.

Definitie. Gradul unui varf x este egal cu numarul muchiilor

incidente cu varful x si se noteaza d(x).

Un varf cu gradul 0 se numeste varf izolat.

2
 Definitie. Un lant L=[x0, x1,... , xp] este o succesiune de varfuri cu
proprietatea ca orice doua varfuri vecine sunt adiacente: [x0,x1]ϵM,
[x1,x2]ϵM, ..., [xp-1,xp]ϵM.

x0,xp- extremitatile lantului; p-lungimea lantului.

Daca x0=xp lantul se numeste ciclu.

Parcurgerea grafurilor in latime (breadth first)

Exemplu

1 7
.9

5
3 2
6 8

1 3 2 5 4 (C- coada)

{
v[n]: v [ i ] =
0 daca inu a fost introdus∈coada
1 ,altfel

Algoritm BF
C⇐∅; C⇐i0; v[i0]=1
While C≠∅
Begin
i⇐C; vizit(i);
pentru toti j vecini ai lui i cu v[j]=0
j⇒C; v[j]=1;
end

Exercitiu. Programati BF folosind o coada implementata dinamic.

Observatie! Se vor parcurge numai varfurile din componenta conexa a lui

1 (o metoda de determinare a componentelor conexe).

3
Parcurgerea in adancime a grafurilor (DF: depth first)

Este o generalizare a parcugerii arborilor.

Li –lista vecinilor lui i

nrdf(i)= nr DF al vf i (al cat-alea apare in parcurgere)

1
L1={2,3,4}

L2={4,3}

L3={1,2}
2 L4={2,1}
3
L5={4}
4

ndf←0; nrdf(i) ←0; ꓯ i

for i=1 to n do

if nrdf(i)=0 then df(i);

procedure df(i)
{ndf←ndf+1 (ndf- contor ce foloseste la a atasa numarul de ordine

varfului)

nrdf(i)←ndf; vizit(i)

for (toti jϵLi)

4
 if nrdf(j)=0 then df(j) (tata(j)=i; j⇒𝓐i- j descendent al lui
i)

?Graf conex: df(1); daca ndf=n atunci “graf conex”, altfel neconex.

Muchii de avansare

 (i,j)= muchie de avansare ⇔ in apelul DF(i) se apeleaza DF(j);

 Celelalte muchii se numesc muchii de intoarcere

Observatie! Muchiile de avansare formeaza un arbore partial.

2) 𝓐i= lista descendentilor varfurilor in arbore (j);

1) Un vector ‘tata’, tata←0;

Initial 𝓐i ←∅;
3) Daca lucram cu matricea de adiacenta: A(i,j)⇐2.

Complexitate: n varfuri, m muchii- O(max{m,n})

Determinarea componentelor conexe intr-un graf neorientat

Definitie. Un graf se numeste conex, daca pentru orice pereche de

varfuri x si y, x≠ y, exista un lant de la x la y.

Problema. Se da un graf G=(X,M). Sa se tipareasca toate

componentele sale conexe.

Un vector t va retine daca un nod a fost deja vizitat: (t(i)=1).

5
 Algoritm.

 Se cauta un nod nevizitat (t(p)=0);

 Pornind de la acesta, se viziteaza (cu parcurgerea in adancime)
toate nodurile accesibile (i.e. pentru care exista un lant care le
leaga de nodul de pornire), avand grija sa marcam faptul ca le-
am vizitat →aceasta este o componenta conexa;
 Algoritmul se incheie cand nu mai exista nod nevizitat.

Fie a matricea de adiacenta, t- vectorul nodurilor vizitate, n nr de noduri.

Citeste a, t[i]←0, i=1 , n.

Procedure pdf(int p)
Begin
Write(p); t[p]←1;
For j=1 to n do
If (a[p,j]=1 and t[j]=0) then pdf(j)
End

Repeat
Gasit=false;
i←1;
while (i<=n) and (not gasit) do
begin
if (t[i]=0) then gasit←true;
i++;
end
if gasit then
begin
write (‘componenta conexa:’);
pdf(i-1);
end
until (not gasit)

6
 Cicluri hamiltoniene

Definitie. Fie G=(X,M) un graf. Se numeste ciclu hamiltonian un

ciclu elementar (nu repeta varfuri) care trece prin toate varfurile grafului.
Un graf care admite un ciclu hamiltonian se numeste graf hamiltonian.

Exemplu: Problema comis-voiajorului.

Un comis-voiajor trebuie sa viziteze un numar n de orase. Initial, acesta se

afla intr-unul din ele, notat 1. Comis-voiajorul doreste sa nu treaca de doua
ori prin acelasi oras, iar la intoarcere sa revina in orasul 1. Care sunt
drumurile posibile?

Nu se cunosc algoritmi polinomiali- se foloseste backtracking

(exponentiala).

a-matricea de adiacenta;

sol-vectorul solutie;

citeste a; sol[1]←1; sol[2]←1.

Caut(2);
Procedure caut(int i)
If (i=n+1) then if (a[sol[n],1]=1 then tipareste_solutia
Else
{ While (sol[i]<n) do
{sol[i]=sol[i]+1;
Gasit=false;
If (a[sol[i-1],sol[i]]=0) then gasit=true //noduri
adiacente
If not gasit then {sol[i+1]=1;
Caut(i+1);}
}
Sol[i]=1; // reinitializarea la revenire
}

7
 Cicluri si lanturi euleriene

Definitie. Un lant L al unui graf G care contine fiecare muchie exact o data
se numeste lant eulerian. Daca x0=xp si lantul este eulerian atunci ciclul se
numeste eulerian.

Definitie. Un graf care contine un ciclu eulerian se numeste eulerian.

Observatie. Faptul ca un graf este eulerian nu inseamna ca nu are varfuri

izolate.

Teorema. Un graf G, fara varfuri izolate, este eulerian daca si numai daca
(ddaca) este conex si gradele tuturor varfurilor sunt numere pare.

Exemplu. Problema podurilor: cum trecem prin n poduri exact o data si ne

intoarcem in punctul de plecare?

Idee algoritm: presupunem graf eulerian (deci toate gradele pare).

 Se formeaza un ciclu (nu neaparat eulerian) pornind de la un varf dat
v (C-ciclu);
 Se opereaza asupra grafului, renuntand la muchiile selectate in C→
graful H;
 Cel putin una din muchiile lui H are un varf comun cu una din
muchiile ciclului selectat (altfel graful n-ar fi conex). Procedand ca la
inceput se formeaza ciclul C1. Se repeta pana la formarea unui ciclu
eulerian.

Exemplu.

1 5

2
3 4

8
v=1: C:{1,2,3} / 4,5
2 are o muchie incidenta comuna cu nodurile ramase ⇒ {2,4,5} ⇒

{1,2,4,5,2,3}

Verificare graf eulerian

a- matricea de adiacenta;
n-nr de noduri; drum, drum1, drum2, ini- vectori.

Procedure ciclu (int : nod)// cauta un ciclu cu nodul de pornire nod.

{nod1←nod; i←1; gasit=false;

Repeat
j←1;
while (a[nod1,j]=0) do j++//cauta muchie incidenta la nod1,
neconsiderata inca in ciclu
drum1[i]=j;
a[nod1,j]←0; a[j,nod1]←0; //sterge muchia din matricea de adiacenta
nod1←j; i++;
if (j=nod) then gasit=true;

until gasit;}

procedure euler
{ i←1; // indicele unui nod din ciclul construit, din care pleaca o muchie ce
nu apartine inca acestui ciclu (pentru a completa pana la un ciclu
eulerian)

repeat
ciclu (drum[i]); //pleaca din varful din care a ramas- si intercaleaza un
ciclu

for l=1 to i do drum2[l]=drum[l];

j←1;
while (drum1[j]!=0) do {drum2[i+j]=drum1[j];
j++;}
j--;
l=1;

while (drum[i+l]!=0)do {drum2[i+j+l]=drum[i+l];

9
 l++;}

drum drum1 drum

drum2:

1 i i+1

drum2=drum in care s-a intercalat un ciclu retinut in drum1 (construit cu

procedura ‘ciclu’), in pozitia nodului i pe drum (adica in drum[i]), si care
mai are, eventual, muchii incidente neconsiderate.

drum←drum2; drum2←0; drum1←0;

i←1;
gasit←false;

while (drum[i]!=0) and (not gasit) do

{for j=1 to n do
If (a[drum[i],j]!=0) then gasit←true;
i++;} //cauta muchie nefolosita de ciclul din ‘drum’

i--;
until (not gasit);

Program principal:

citeste a;
drum←0; drum1←0; drum2←0; ini←0;
drum[1]=1 (nodul de plecare)
euler;
i←1;

while (drum[i]!=0) do {write (drum[i]);i++;}

10