~ info project ~

Mai 6, 2010

Matricea drumurilor.

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 2:35 pm
Tags: , , ,

Este o matrice d cu n linii şi n coloane, în care fiecare element d[i,j] este :

–         1, dacă există drum de la nodul i la nodul j în graf;

–         0, în caz contrar.

Algoritmul Roy-Warshall de determinare a matricei drumurilor

Matricea drumurilor se obţine aplicând matricei de adiacenţă transformări succesive. Vom spune că există drum de la nodul i la nodul j, dacă găsim un nod k (diferit de i, j) cu proprietatea că există drum de la i la k şi drum de la j la k. Astfel:

  • un element a[i, j] care este 0, devine 1, dacă există un nod k astfel încât a[i, k]=1 şi a[k, j]=1. Pentru a găsi arcele nodului k, trebuie parcurse pe rând în varianta k toate nodurile 1, 2, …, n.

for k:=1 to n do

for i:=to n do       {i≠k}

for j:=1 to n do   {j≠k}

if (a[i, j]=0) and (i<>k) and (j<>k) then

a[i, j]:=a[i,k]*a[k, j];

Atribuirea a[i, j]:=a[i,k]*a[k, j] este o scriere elegantă a regulii de mai sus:

în cazul în care unul din elementele a[i,k], a[k, j] este 0, a[i, j] va rămâne 0;

dacă a[i, k]=1 şi a [k, j]=1, atunci a[i, j] devine 1.

Un CD valoros

Într-un grup sunt n elevi, băieţi şi fete, pe care-i numerotăm 1, 2, … , n. Fiecare elev cunoaşte o parte dintre ceilalţi elevi. Relaţia de cunoştinţă nu este neapărat reciprocă (dacă x îl cunoaşte pe y, asta nu înseamnă că şi y trebuie să îl  cunoască pe x). Unul dintre elevi are un CD foarte valoros, cu multe jocuri demonstrative, pe care toţi membri grupului vor să-l aibă fie şi pentru scurt timp, pentru a şi-l copia pe calculatorul propriu. CD—ul circulă printre membrii grupului în felul următor: fiecare elev după ce l-a primit de la altcineva îl dă mai departe, dar numai unui elev pe care îl cunoaşte, pentru că nu doreşte să ajungă în mâna unor persoane în care nu poate avea încredere. Determinaţi o modalitate  (dacă există) prin care CD-ul să circule exact o singură dată pe la fiecare elev, transmiterea lui făcându-se numai către o cunoştinţă, iar în final CD-ul să ajungă din nou la proprietarul său.

Interpretarea datelor

Relaţiile de cunoştinţă din cadrul grupului pot fi reţinute într-o matrice a cu n linii şi n coloane, în fiecare element a[i, j] este: 1 dacă elevul i îl cunoaşte pe elevul j, respectiv 0 în caz contrar. Cu datele problemei putem construi un graf în care nodurile sunt elevii 1, 2, 3,…, n, iar arcele sunt relaţiile de cunoştinţă din grup. Astfel, va exista arc de la nodul x la nodul y dacă elevul x în cunoaşte pe elevul y. Întrucât în enunţ se precizează că relaţiile de cunoştinţă nu sunt neapărat reciproce („x cunoaşte pe y” nu implică „y cunoaşte pe x”), rezultă că avem de-a face cu un graf orientat. Matricea a definită mai înainte este tocmai matricea de adiacenţă a grafului.

„Traseul” pe care îl parcurge CD-ul pleacă dintr-un nod (proprietarul său), trecând prin fiecare nod (pe la fiecare elev) o singură dată. Transmiterea se face numai către o cunoştinţă. Astfel, de la elevul x va ajunge la elevul y numai dacă există arc (cunoştinţă) de la x la y. În final, traseul se încheie în nodul de unde a plecat (CD-ul se întoarce la proprietarul iniţial). Un traseu care respectă condiţiile de mai sus nu este altceva decât un circuit elementar care trece prin toate nodurile grafului: drum deoarece poate trece de la un nod la altul numai printr-un arc, elementar deoarece nu trece de două ori prin acelaşi nod, şi în sfârşit circuit pentru că revine în nodul de plecare.

Rezolvare

Folosim metoda backtracking. Fiecare astfel de circuit elementar care trece prin toate nodurile grafului, va fi o soluţie memorată în vectorul stivă st. Aşadar elementele vectorului st sunt noduri ale grafului.

O soluţie (st[1], st[2], …, st[p] ) este finală dacă

– conţine n nivele, adică p=n (au fost „puşi pe stivă” toţi cei n elevi, adică toate cele n noduri)

st[n]=x (pentru a fi ciclu trebui să revină în nodul de plecare, adică „elevul de pe ultimul nivel”, st[n], trebuie să fie proprietarul memorat iniţial în x).

Procedura {citire_matrice;} citeşte matricea de adiacenţă (relaţiile de cunoştinţă). În două cicluri for, cu i, j=1, 2, …, n, se citesc toate elementele a[i, j]. Această procedură a fost prezentată ca aplicaţie în lecţia „Reprezentarea grafurilor orientate

Procedura {iniţializări;} realizează iniţializarea stivei şi a proprietarului CD-ului.

–         într-un ciclu for, se iniţializează cu 0 întreg vectorul-stivă;

–         se citeşte numărul de ordine al proprietarului CD-ului în variabila x (nodul de plecare).

Procedura {tipar(p:integer):} afişează o configuraţie (st[1], st[2], …, st[p]) a vectorului-stivă.

Funcţia {valid(p:integer):boolean;} verifică pentru fiecare nivel p dacă st[p]I a generat o soluţie (st[1], st[2], …, st[p]) validă.

Testarea se face prin intermediul unei variabile booleene ok, iniţializează cu TRUE. În primul rând, din nodul st[p-1] se poate ajunge în

nodul st[p] numai printr-un arc (orice drum/circuit trece prin arce). Aşadar nodul st[p] este valid numai dacă există arc de la st[p-1] la st[p], adică a[st[p-1], st[p]]=1 (această condiţie provine din faptul că fiecare elev va transmite CD-ul numai prin cunoştinţă, ia relaţia de cunoştinţă este marcată în graf printr-un arc). În caz contrar ok devine FALSE.

ok:=TRUE;

if  a [ st[p],  st[p-1]]=0 then

ok:=FALSE;

Dacă ok a rămas TRUE, urmează testarea celei de-a doua condiţii. Am spus că soluţia este finală dacă p=n, iar pe ultimul nivel trebuie să se găsească  nodul x. Dar pe ultimul nivel anterior lui n nu putem avea nodul x (CD-ul revine la proprietar, dar numai după ce a trecut pe la ceilalţi elevi, pe la fiecare o singură dată).

if ok then

if (p<n) and (st[p]=x)

then

ok:=FALSE

Dacă ok a rămas în continuare TRUE, mai avem şi o a treia condiţie. Nodul st[p] să nu se mai găsească pe stivă (urmare a faptului că CD-ul trebuie să treacă pe la fiecare elev o singură dată). Parcurgem într-un ciclu nivelele i=1, 2, …, p-1 anterioare lui p. Dacă găsim un st[i] egal cu st[p], înseamnă că st[p] se mai găsesc pe un nivel anterior, deci ok devine şi în cazul acesta FALSE.

if ok then

for i:=1 to p-1 do

if  st[p]= st[i] then

ok:=FALSE

Procedura recursivă {bktr(p:integer);} “tratează” un nivel oarecare p al stivei.

  • Ø prin variabila val vor trece pe rând, într-un ciclu, toate valorile care teoretic ar putea fi puse pe nivelul p. Pentru fiecare dintre aceste valori:
    • dacă respectiva valoare a generat o soluţie validă (dacă funcţia valid(p) a returnat TRUE), atunci:

–         dacă soluţia respectivă e şi finală o tipărim (apelând procedura tipar (p)); în caz contrar trecem la nivelul următor (pentru a completa soluţia cu un nou nivel), prin auto-apelul bktr(p+1).

În programul principal, apelăm procedurile iniţializări şi citire_matrice, apoi declanşăm lanţul recursiv prin apelul bktr(1) (plecăm de la nivelul 1 al stivei).

Program XI_10;

var n,x:integer;

st:array[1..20] of integer;

a:array[1..20,1..20] of integer;

procedure citire_matrice;

{citeste matricea de adiacenta a de la tastatura}

var I,j:integer;

begin

write (‘numarul de noduri:  ’);  readln(n);

for i:=1 to n do

for j:=1 to n do

begin

write (‘[‘, i, ’,’, j, ‘]=’); readln(a[i, j]);

end;

end;

procedure initializari;

{initializeaza stiva si citeste datele problemei}

var i:integer;

begin

write (‘Cine este proprietarul: ’); readln(x);

for i:=1 to 25 do st[i]:=0;

end;

procedure tipar (p:integer);

{tipareste o solutie memorata in vectorul st}

var k:integer;

begin;

write (x, ’ ’);

for k:=1 to p do write (st[k]:4, ‘ ’);

writeln;

end;

function valid (p:integer): boolean;

{testeaza daca valoarea pusa pe nivelul p a generat o solutie valida, returnand TRUE sau FALSE}

var nr, i:integer; ok:boolean;

begin

{CD-il poate circula numai intre elevii care se cunosc, deci elevul st[p-1] trebuie sa il cunoasca pe st[p] pentru a-i putea da CD-ul mai departe}

ok:=TRUE;

if a[st[p-1], st[p]]=0 then ok:=FALSE;

if ok then

{proprietarul x nu se poate gasi pe un nivel anterior ultimului}

if (p<n) and (st[p]=x) then ok:=FALSE;

if ok then

{elevul st[p] nu trebuie sa se mai gaseasca pe nivelele anterioare}

for i:=1 to p-1 do

if st[p]= st[i] then ok:=FALSE;

valid:=ok;

end;

procedure bktr (p:integer);

{implementeaza algoritmul de backtracking recursiv}

var val:integer;

begin

{in variabila val trec pe rand toate valorile care ar putea fi incercate pe nivelul p al stivei}

for val:=1 to n do

begin

st[p]:=val;  {pune o noua valoare pe nivelul p}

if valid(p) then {daca solutia obtinuta e valida}

{o solutie e finala daca CD-ul a trecut pe la n elevi (p=n) si ultimul e proprietarul (st[p]=x)}

if (p=n) and (st[n]=x) then tipar (p) {daca e si finala, tipareste solutia}

else bktr (p+1); {trece la nivelul urmator in stiva, pentru a completa solutia}

end;

end;

begin;

initializai; citire_matrice; bktr(1); {plecam de la nivelul 1 pe stiva}

end.

Nodurile izolate într-un graf orientat

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 2:17 pm
Tags: , , , ,

Se citesc de la tastatură m perechi de numere întregi (x,y) reprezentând extremităţile arcelor unui graf orientat cu n noduri şi m arce. Să se stabilească dacă în graful astfel definit există noduri izolate (prin care să nu treacă nici un arc).

Întreaga rezolvare este cuprinsă în procedura {noduri_izolate;} fără parametri.

Mai întâi citim numărul de noduri n şi numărul de arce m. Definim doi vectori:

–         dp va conţine gradele exterioare (d*) ale tuturor nodurilor;

–         dm va conţine gradele interioare (d) ale tuturor nodurilor.

Astfel, dp[i] şi dm[i] vor fi gradul exterior respectiv gradul interior al nodului i, pentru i=1, 2, …, n. Iniţializăm cu 0 toate gradele exterioare şi interioare ale tuturor nodurilor: într-un ciclu cu i de la 1 la n, facem atribuirile dp[i]:=0 şi dm[i]:=0

Pentru a citi cele m arce, parcurgem un ciclu k de la 1 la m, şi la fiecare pas:

–         citim o pereche de numere întregi (x,y), cu validarea valorilor introduse: repetă (reia) citirea lui x şi y, până când ambele valori sunt >= 1 şi >= n. Fiecare pereche va reprezenta care iese din nodul x şi intră în nodul y.

–         întrucât arcul (x,y) iese din nodul x şi intră în nodul y, rezultă că:

–        gradul exterior al nodului x (numărul arcelor care ies din nodul x) va creşte cu 1;

–        gradul interior al nodului y (numărul arcelor care intră în nodul y) va creşte cu 1.

Deci se fac atribuirile dp[x]:= dp[x]+1 şi dm[y]:= dm[y]+1.

Aşadar la citirea fiecărui arc am actualizat gradele nodurilor – extremităţi ale sale. Astfel, după încheierea citirii vectorii dp şi dm vor conţine gradele exterioare respectiv interioare ale tuturor nodurilor.

Un nod x se numeşte izolat dacă prin el nu trece nici un arc. Altfel spus, nu iese nici un arc din el şi nu intră nici un arc în el, adică dp[x]=dm[x]=0. În continuare, vom număra nodurile izolate în variabila nr, pe care o iniţializăm cu 0. Parcurgem “în paralel” cei doi vectori ai gradelor dp şi dm, într-un ciclu cu i=1, 2, 3, …, n. La fiecare pas, testăm dacă nodul i este izolat, adică dacă dp[i]=0 şi dm[i]=0; în caz afirmativ afişăm respectivul nod i şi incrementăm numărul nr al nodurilor izolate.

nr:=0;

for i:=1 to n do

if(dp[i]=0) and (dp[i]=0) then

begin

write(i,’ ‘);

nr:=nr+1;

end;

După încheierea acestei parcurgeri, dacă numărul vârfurilor izolate este diferit de 0 atunci îl afişăm, iar în caz contrar tipărim un mesaj din care să rezulte că graful nu are noduri izolate.

Program XI_7;

type vect =array[1..20] of integer;

var n,m:integer;

a:array[1..20,1..20] of integer;

dp,dm:vect;

procedure noduri_izolate;

var i,j,k,x,y,nr:integer;

begin

write(‘Nr.arce : ‘); readln(m);

write(‘Nr.noduri: ‘); readln(n);

{iniţializează cu 0 vectorii gradelor dp şi dm}

for i:=1 to n do

begin

dp[i]:=0; dm[i]:=0;

end;

{citeşte m perechi (x,y) reprezentând arcele grafului}

for k:=1 to m do

begin

write(‘Arcul ‘,k,’: ‘);

repeat

readln(x,y);

until (x>=1) and (x<=n) and (y>=1) and (y<=n) and (x<>y);

{pentru fiecare arc (x,y), incrementează gradul exterior al lui x şi gradul interior al lui y}

dp[x]:=dp[x]+1; dm[y]:=dm[y]+1;

end;

writeln; nr:=0; {nr=numărul nodurilor izolate}

for i:=1 to n do

{dacă ambele grade ale lui i sunt 0,am găsit un vârf izolat, pe care-l afişăm şi incrementăm nr}

if (dp[i]=0) and (dm[i]=0) then

begin

write(i,’ ‘); nr:=nr+1;

end;

writeln;

if nr<>0 then writeln(‘Graful are ‘,nr, ‘ noduri izolate’)

else writeln (‘Graful nu are noduri izolate’);

end;

begin

noduri_izolate;

end.

Celebritate.

Se dă un grup format din n persoane, care se cunosc sau nu între ele. De la tastatură se introduc m perechi de numere întregi (x,y) cu semnificaţia ”persoana x cunoaşte pe persoana y”. relaţia de cunoştinţă nu este neapărat reciprocă. Numim celebritate, o persoană care este cunoscută de către toate celelalte persoane din grup, dar ea nu cunoaşte pe nici un alt membru al grupului. Să se determine dacă din grup există o astfel de celebritate.

Interpretarea datelor.

Problema poate fi modelată într-un graf orientat, în care nodurile sunt persoanele 1,2,3…n, iar arcele sunt relaţiile de cunoştinţă între aceste persoane. O relaţie de cunoştinţă este de forma (x,y) cu semnificaţia “persoana x o cunoaşte pe persoana y”. De exemplu, dacă grupul are n=4 persoane, iar cele m=5 “relaţii de cunoştinţă” sunt (1,3), (2,3), (4,3), (1,2), (1,4), atunci graful şi matricea sa de adiacenţă arată astfel:

<!– /* Font Definitions */ @font-face {font-family:Wingdings; panose-1:5 0 0 0 0 0 0 0 0 0; mso-font-charset:2; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:0 268435456 0 0 -2147483648 0;} @font-face {font-family:”Cambria Math”; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:-1610611985 1107304683 0 0 159 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:””; margin:0in; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:”Times New Roman”,”serif”; mso-fareast-font-family:”Times New Roman”; mso-ansi-language:RO;} .MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; font-size:10.0pt; mso-ansi-font-size:10.0pt; mso-bidi-font-size:10.0pt;} @page Section1 {size:8.5in 11.0in; margin:1.0in 1.0in 1.0in 1.0in; mso-header-margin:.5in; mso-footer-margin:.5in; mso-paper-source:0;} div.Section1 {page:Section1;} /* List Definitions */ @list l0 {mso-list-id:103231387; mso-list-type:hybrid; mso-list-template-ids:528617746 1452602364 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;} @list l0:level1 {mso-level-start-at:4; mso-level-number-format:bullet; mso-level-text:-; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; font-family:”Times New Roman”,”serif”; mso-fareast-font-family:”Times New Roman”;} @list l1 {mso-list-id:248316141; mso-list-type:hybrid; mso-list-template-ids:1431185870 1452602364 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;} @list l1:level1 {mso-level-start-at:4; mso-level-number-format:bullet; mso-level-text:-; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; font-family:”Times New Roman”,”serif”; mso-fareast-font-family:”Times New Roman”;} ol {margin-bottom:0in;} ul {margin-bottom:0in;} –>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:”Table Normal”;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-priority:99;
mso-style-qformat:yes;
mso-style-parent:””;
mso-padding-alt:0in 5.4pt 0in 5.4pt;
mso-para-margin:0in;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:”Times New Roman”,”serif”;}

Să analizăm persoana reprezentată prin nodul 3:

– există relaţiile de cunoştinţă (1,3), (2,3) şi (4,3), adică persoana 3 este cunoscută de către 1,2 şi 4. Mai exact, persoana 3 este cunoscută de către toate celelalte persoane din grup;

– nu există nici o relaţie de cunoştinţă de forma (3,p). Cu alte cuvinte, persoana 3 nu cunoaşte pe nimeni.

În concluzie, persoana 3 este ceea ce numim celebritate. În graf, existenţa celebrităţii se interpretează astfel:

– în nodul 3 intră arce “ieşite” din toate celelalte noduri;

– din nodul 3 nu iese nici un arc.

Rezolvare

În procedura citire_graf se citesc de la tastatură m perechi de numere întregi de forma (x,y) reprezentând extremităţile celor m arce ale grafului, şi se constituie matricea de adiacenţă a, cu n linii * n coloane.

Algoritmul de căutare a celebrităţii cuprins în procedura celebritate.

Pentru început, vom căuta o persoană pe care o vom numi în continuare candidat la celebritate. Memorăm acest candidat în variabila candid. Presupunem că iniţial candidatul este persoana 1 (candid:=1). “Cercetăm” celelalte persoane, într-un ciclu cu i de la 2 la n. Pentru fiecare persoană i, trebuie să facem o testare. În cazul în care candidatul “actual” candid o cunoaşte i (a[candid,i] este 1) candid nu mai poate fi celebritate (celebritate nu trebuie să cunoască nici o altă persoană din grup !). În această situaţie, noul candidat la celebritate devine i (candid:=1).

La finele parcurgerii de mai sus, în variabila candid vom avea aşadar un candidat la celebritate. Mai rămâne să vedem dacă acest candidat este cunoscut de către celelalte persoane. În exemplul de mai sus, urmare a faptului că persoana 3 este celebritate, avem relaţiile (1,3), (2,3) şi (4,3), adică a[1,3]=a[2,3]=a[4,3]=0. În consecinţă, pe coloana 3 avem n-1 valori de 1. Pe caz general, trebuie să numărăm valorile de 1 de pe coloana candid în matricea de adiacenţă, în adiacenţă, iar dacă găsim n-1 valori, atunci persoana candid este într-adevăr celebritate.

Program XI_8;

var n, m: integer; a: array[1..20, 1..20] of integer;

procedure citire_graf;

var i, j, k, x, y: integer;

begin

write(‘Nr. arce: ‘); readln(m);

write(‘Nr. noduri: ‘); readln(n);

{iniţializează cu 0 toata matricea de adiacenta}

for i:=1 to n do

for j:=1 to m do

a[i,j]:=0;

{citeşte m perechi (x,y) reprezentând arcele grafului}

for k:=1 to m do

begin

write(‘Arcul ‘,k,’: ‘);

repeat

readln(x,y);

until (x>=1) and (x<=n) and (y>=1) and (y<=n) and (x<>y);

{pentru fiecare pereche marchează arcul in matricea de adiacenta}

a[x,y]:=1;

end;

end;

procedure celebritate;

var i, j, candid, nr : integer;

begin

candid:=1; {candid va reprezenta candidatul la celebritate, care iniţial este persoana 1}

for i:=2 to n do

{daca candidatul îl cunoaşte pe i, el nu mai poate fi celebritate noul candidat devine i}

if a[candid, i]=1 then candid:=i;

nr:=0; {numaram in nr cate persoane îl cunosc pe candidatul candid}

for i:=1 to n do

if a[i, candid]=1 then nr:=nr+1;

{verificam daca intr-adevăr candid este celebritate}

if nr=n-1 then writeln(‘Persoana ‘, candid,’ este celebritate’)

else writeln(‘Nu exista celebritate in grup’);

end;

begin

citire_graf; celebritate;

end.

Drumuri si circuite in grafuri orientate

Se numeşte lanţ intr-un graf orientat, o mulţime de arce L={u1,u2,…,uk}, cu proprietatea ca oricare doua arce vecine in mulţime au o extremitate comuna.

Un lanţ este de fapt un traseu care uneşte prin arce doua noduri numite extremităţile lanţului, fără a tine cont de orientarea arcelor componente.

Se numeşte drum în graful G, un şir de noduri D={z1, z­2, z3, …, zk}, unde z­1, z­2, z3, …, zk aparţin lui x, cu proprietatea că oricare două noduri consecutive sunt adiacente, adică există arcele [z­1, z­2], [z­2, z3], …, [zk-1,zk] aparţin lui U.

Practic, un drum poate fi privit ca un traseu în care toate arcele au aceeaşi orientare, dată de sensul de deplasare de la z­1 la z­k.

Dacă nodurile z­1, z­2, z3, …, zk sunt distincte două câte două, drumul se numeşte elementar. În caz contrar, drumul este ne-elementar.

Asemenea uni lanţ într-un graf neorientat, un drum într-un graf orientat este de fapt un traseu pe care l-am parcurge între două noduri deplasându-ne de-a lungul unor arce şi trecând prin nişte noduri intermediare. Deosebirea unui drum faţă de un lanţ constă în faptul că de-a lungul unui arc ne putem deplasa numai în sensul dat de orientarea arcului.

Se numeşte circuit într-un graf, un lanţ L={z­1, z­2, z3, …, zk} cu proprietatea că z1=zk şi arcele [z­1, z­2], [z­2, z3], …, [zk-1,zk] sunt distincte două câte două.

Dacă într-un circuit, toate nodurile cu excepţia primului şi ultimului sunt distincte două câte două, atunci circuitul se numeşte elementar. În caz contrar, el este ne-elementar.

Reprezentarea grafului ca un vector de muchii

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 2:14 pm
Tags: , , , , , ,

Fiecare arc al grafului poate fi privit ca o înregistrare cu două componente, în speţă cele două noduri care constituie extremităţile arcului:

–         nod_in -> nodul din care iese arcul (“nodul de început” al arcului);

–         nod_sf -> nodul în care intră arcul (“nodul de sfârşit” al arcului);

Putem defini tipul de date ARC, astfel:

type ARC=record

nod_in, nod_sf: integer;

end;

Graful în ansamblul său, este o mulţime de arce, adică o mulţime de elemente de tipul ARC. În consecinţă, definim graful ca un “vector de arce”, adică un vector de elemente de tipul ARC:

var v: array [1..25] of ARC;

Numărul real de elemente este numărul de arce m. Astfel, elementele efectiv folosite ale vectorului vor fi v[1], v[2],…, v[m]. Fiecare element  {1, 2, …, m}) este de tipul ARC şi reprezintă unev[i] (cu i  arc al grafului, având două componente:

v[i].nod_in şi v[i].nod_sf -> nodurile extremităţi ale arcului.

Listele vecinilor

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 2:13 pm
Tags: , , ,

Pentru fiecare nod x se construiesc două liste ale vecinilor săi:

–         L*(x) → lista vecinilor succesori; conţine nodurile ce sunt extremităţi finale ale arcelor care ies din nodul x.

–         L(x) → lista vecinilor predecesori; conţine nodurile ce sunt extremităţi iniţiale ale arcelor care intră în nodul x.

Exemplu:

În graful din figura 6 de mai sus, pentru nodul x=4 avem:

–         arcele care ies din nodul 4 sunt (4,2) şi (4,3). În consecinţă, lista vecinilor succesori L*(4) conţine nodurile 2 şi 3;

–         în nodul 4 intră un singur arc, şi anume (3,4), motiv pentru care lista vecinilor predecesori L-(4) conţine doar nodul 3.

Prezentăm în continuare aceste liste ale vecinilor pentru graful din figura

Mai 5, 2010

Matricea vârfuri – arce

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 12:48 pm
Tags: , ,

Este o matrice b cu n linii şi m coloane, în care fiecare element b[i,j] este:

–         1, dacă nodul i este o extremitate iniţială a arcului uj;

–         -1, dacă nodul i este o extremitate finală a arcului uj;

–         0, dacă nodul i nu este o extremitate a arcului uj.

Exemplu:

Pentru graful de mai jos cu n=4 noduri şi m=5 arce, matricea vârfuri – arce este:

Pentru a exemplifica construcţia matricei, vom deduce elementele liniei 3:

–         a[3,1]= 0 pentru că nodul 3 nu este o extremitate a arcului u1. Analog, a[3,3]= 0 deoarece nodul 3 nu este extremitate a arcului u3.

–         a[3,5]= -1 pentru că nodul 3 este o extremitate finală a arcului u5.

–         a[3,2]= 1 şi a[3,4]= 1 întrucât nodul 3 este o extremitate iniţială a arcului u2 respectiv u4.

Observaţii:

Pe fiecare coloană j (aferentă arcului uj), avem exact două elemente nenule: un 1 (linia i pe care se află reprezintă extremitatea iniţială a arcului uj) şi un -1 (linia i pe care se află reprezintă extremitatea finală a arcului uj)

Numărul valorilor de 1 de pe linia i, reprezintă gradul exterior al nodului i (numărul arcelor ce au ca extremitate iniţială pe i), iar numărul valorilor de -1 de pe linia i reprezintă gradul interior al nodului i (numărul arcelor care au ca extremitate finală pe i).

Reprezentarea grafurilor orientate

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 12:45 pm
Tags: , , , , , , , ,

Considerăm un graf orientat G= (X,U) cu m arce şi n noduri.

Cele mai cunoscute forme de reprezentare sunt: matricea de adiacenţă, matricea vârfuri – arce, matricea drumurilor şi listele vecinilor.

Matricea de adiacenţă

Are aceeaşi semnificaţie ca în cazul grafurilor neorientate: fiecare element a[i,j], cu i,j ε {1,2,…,n}, este: 1 dacă există arcul (i,j), respectiv 0 în caz contrar.

Datorită orientării, aşa cum am mai spus, arcul (i,j) nu este totuna cu arcul (j,i). Prin urmare, a[i,j] ≠ a[j,i]. Aşadar matricea de adiacenţă nu mai este simetrică faţă de diagonala principală, aşa cum se întâmpla în cazul grafurilor neorientate.

Exemplu:

Pentru graful G=(X,U) din figura 5, matricea de adiacenţă este:

Continuăm cu câteva aplicaţii.

Aplicaţie:

Citirea de la tastatură şi afişarea matricei de adiacenţă

Prin citirea matricei de adiacenţă de la tastatură, putem memora arcele existente între nodurile unui graf. În cazul grafurilor neorientate, citeam doar “porţiunea” de deasupra diagonalei principale în matrice, deoarece matricea este simetrică. Acum trebuie să citim toate elementele matricei. Avem de-a face cu algoritmii banali de citire şi afişare a unei matrice cu n linii şi n coloane (unde n este numărul de noduri) în două cicluri for, deci nu considerăm că mai sunt necesare alte explicaţii. Prezentăm în continuare procedurile citire_matrice şi afişare_matrice.

Procedure citire_matrice;

{citeşte matricea de adiacenţă a de la tastatură}

var i,j: integer;

begin

writeln(‘Nr. Noduri: ‘); readln(n);

for i:=1 to n do

for j:=1 to n do

begin

write(‘[‘,i,’,’,j,’]=’);

readln(a[i,j]);

end;

end;

Procedure afişare_matrice;

{afişează matricea de adiacenţă a}

var i,j: integer;

begin

for i:=1 to n do

begin

for j:=1 to n do

write(a[i,j],’ ‘);

writeln();

end;

end;

Aplicaţie:

Citirea matricei de adiacenţă dintr-un fişier text

Aceasta este absolut similară cu cea prezentată la grafuri neorientate, unde a fost explicată pe larg. De fapt, este vorba despre algoritmul de citire a unei matrice oarecare dintr-un fişier text. Plecăm de la presupunerea că fişierul conţine pe primul rând valoarea lui n, apoi pe fiecare din următoarele n rânduri elementele unei linii a matricei separate de spaţii.

Procedure cit_matr_fis;

{citeşte numărul de noduri si matricea de adiacenta a din fişierul text cu descriptorul f}

var i,j: integer; nume_fis: string;

begin

write(‘Daţi numele fişierului ‘); readln(nume_fis);

assign(f,nume_fis); reset(f);

readln(f,n);

for i:=1 to n do

begin

for j:=1 to n do read(f,a[i,j]);

readln(f);

end;

close(f);

end;

Aplicaţie:

Construirea matricei de adiacenţă prin citirea “arcelor” de la tastatură

Se citesc de la tastatură m perechi de numere întregi de forma (x,y) reprezentând extremităţile celor m arce ale grafului, şi se construieşte matricea de adiacenţă a, cu n linii şi n coloane.

Mai întâi citim m şi n (numărul de arce respectiv numărul de noduri), şi iniţializăm toată matricea de adiacenţă cu 0, în două cicluri for. Apoi, într-un alt ciclu for, cu k de la i la m, citim cele m perechi de întregi (x,y).

–         Citirea fiecărei perechi (x,z) se face cu validare: repetă citirea lui x şi y până când ambele valori sunt în intervalul [1,n].

repeat

readln(x,y);

until (x>=1) and x(<=n) and (y>=1) and (y<=n) and (x<>y);

–         Pentru fiecare (x,y), marcăm în matricea de adiacenţă existenţa arcului (x,y), prin atribuirea a[x,y]:=1. Spre deosebire de grafurile neorientate, nu se mai face şi atribuirea a[y,x]:=1, deoarece arcul (x,y) nu e identic cu arcul (y,x).

Algoritmul prezentat a fost inclus în procedura citire_graf.

Procedure citire_graf;

var i, j, k, x, y: integer;

begin

write(‘Nr. Arce:’); readln(m);

write(‘Nr. Vârfuri’); readln(n);

{iniţializează cu 0 toata matricea de adiacenta}

for i:=1 to n do

for j:=1 to n do

a[i,j]:=0;

{citeşte m perechi (x,y) reprezentând arcele grafului}

for k:=1 to m do

begin

write(‘Muchia ‘,k,’: ‘);

repeat

readln(x,y);

until (x>=1) and x(<=n) and (y>=1) and (y<=n) and (x<>y);

{pentru fiecare pereche, marchează arcul in matricea de adiacenta}

a[x,y]:=1;

end;

end;

Aplicaţie:

Determinarea gradului exterior şi a gradului interior ale unui nod oarecare x

Scriem o funcţie {d_plus(x:integer):integer;} care returnează, gradul exterior al nodului x (notat d*(x)).

Gradul exterior al unui nod x este numărul arcelor care ies din nodul x, adică numărul arcelor de forma (x,j), cu j ε {1, 2, … , n}. Luăm ca exemplu graful cu n=4 noduri de mai jos, împreună cu matricea sa de adiacenţă:

Analizăm gradul exterior al nodului 2. Arcele care ies din nodul 2 sunt: (2,1), (2,3), (2,4) (nu şi (4,2)). Urmare a existenţei acestor arce, în matricea de adiacenţă vom avea a[2,1] = a[2,3] = a[2,4] = 1. Unde se găsesc în matricea de adiacenţă toate valorile de 1 corespunzătoare arcelor ce ies din nodul 2? Pe linia 2! Pe caz general, valorile de 1 de pe linia x în matricea de adiacenţă, reprezintă arcele care ies din nodul x. Deci gradul exterior al nodului x, adică numărul arcelor care ies din nodul x este egal cu numărul valorilor de 1 de pe linia x a matricei.

Aşadar algoritmul implementat în funcţia d_plus este foarte simplu:

Iniţializăm cu 0 o variabilă nr. în care numărăm valorile de 1 de pe linia x a matricei. Într-un ciclu, parcurgem coloanele j=1, 2, …, n ale liniei x. Pentru fiecare valoare a lui j, testăm elementul a[x,j] de pe linia x şi coloana j. Dacă aceasta are valoarea 1, atunci incrementăm nr. În final funcţia va returna ultima valoare a variabilei nr.

Function d_plus(x:integer):integer;

{returnează gradul exterior d* pentru un nod x; acesta este numărul valorilor de 1 de pe linia x a matricei de adiacenta}

var nr.,j: integer;

begin

nr.:=0;

for j:=1 to n do

if a[x,j] = 1 then nr:=nr + 1;

d_plus:=nr;

end;

Observaţie:

Destul de asemănător este şi algoritmul pentru determinarea gradului interior al nodului x (d- (x) ). Acesta reprezintă numărul arcelor care intră în nodul x, adică numărul arcelor de forma (i,x), cu i ε {1, 2, …, n}. Să vedem unde se regăsesc în matricea de adiacenţă arcele care intră în nodul x, luând ca exemplu x=4 pentru graful anterior. Arcele care intră în nodul 4 sunt (3,4) şi (2,4). Rezultă că în matrice avem a[3,4] = a[2,4] = 1. Am “reperat” astfel valorile de 1 de pe coloana 4 a matricei de adiacenţă. În acest moment putem concluziona că gradul interior al unui nod oarecare x reprezintă numărul valorilor de 1 de pe coloana x a matricei. Se poate scrie o funcţie asemănătoare cu cea de mai sus, care să returneze câte valori de 1 se găsesc pe coloana x.

function d_minus(x: integer): integer;

{returnează gradul interior d- pentru un nod x; acesta este numărul valorilor de 1 de pe coloana x a matricei de adiacenta}

var nr, i: integer;

begin

nr:=0;

for i:=1 to n do

if a[i,x]=1 then nr:=nr+1;

d_minus:=nr;

end;

Graful unui vârf. Mulţimile Γ şi ω

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 12:41 pm
Tags: , , , , ,

Gradul exterior al unui vârf x, notat d*(x), reprezintă numărul arcelor care ies din nodul x, adică numărul arcelor de forma (x,z) ε U.

Analog, se defineşte gradul interior al unui vârf x, notat d-(x), ca fiind numărul arcelor care intră în nodul x (de forma (y,x) ε U).

Exemplu:

În graful reprezentat în figura*, pentru nodul x=2, avem:

d*(2) =3 → există trei arce care ies din nodul 2, şi anume : u2=(2,1), u4=(2,3) şi u5 = (2,4).

d-(2) =1 → în nodul 2 intră un singur arc, în speţă arcul u3=(3,2).

Se mai definesc următoarele mulţimi:

→ mulţimea nodurilor ce constituie extremităţi finale ale arcelor care pleacă din nodul x. Pe scurt, mulţimea succesorilor lui x;

→ mulţimea nodurilor ce constituie extremităţi iniţiale ale arcelor care pleacă din nodul x. Pe scurt, mulţimea predecesorilor lui x;

Exemplu:

În graful din figura, pentru nodul x=2, avem:

– Γ+(2) = {1,3,4} → urmare a faptului că muchiile care pleacă din nodul 2 sunt (2,1), (2,3) şi (2,4), putem spune că mulţimea succesorilor nodului 2 este {1,3,4}.

– Γ(2) = {3} → în nodul 2 intră doar muchia (3,2), deci mulţimea predecesorilor lui 2 conţine doar nodul 3.

ω+(x) = {u = (x,y)| u ε U} → mulţimea arcelor care ies din nodul x;

ω-(x) = {u = (y,x)| u ε U} → mulţimea arcelor care intră în nodul x;

Exemplu:

În graful din figura, pentru nodul 2, avem:

ω+(x) = {(2,1), (2,3), (2,4)}, ω-(x) = {(3,2)}

*figura = graful orientat din postarea anterioară

Graf parţial şi subgraf

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 12:40 pm
Tags: , , ,

Fie graful G = (X,U). Un graf parţial al lui G, este un graf G1= (X,V), cu . Altfel spus, un graf parţial G1 al lui G, este chiar G, sau se obţine din G păstrând toate vârfurile şi suprimând nişte muchii.

Fie graful G = (X,U). Un graf parţial al lui G, este un graf G1= (Y,T), unde şi , iar T va conţine numai muchiile care au ambele extremităţi în Y. Altfel spus, un graf parţial G1 al lui G, se obţine din G eliminând nişte vârfuri şi păstrând doar acele muchii care au ambele extremităţi în mulţimea vârfurilor rămase.

Exemplu:

Se consideră graful G = (X,U) din figura 2, în care X = {1,2,3,4,5,6} şi U={u1, u2, u3, u4, u5, u6, u7}.

–         Construim graful parţial G1 = (X,V), unde X = {1,2,3,4,5,6} şi V = { u2, u3, u4, u6, u7} (figura 3) din graful G au fost eliminate arcele u1 şi u5.

–         Construim subgraful G2 = (Y,T), unde Y = {3,4,5,6} şi T = {u4, u5, u6, u7} (figura 4) din graful G au fost eliminate nodurile 1 şi 2 precum şi arcele u1, u2 şi u3 care au o extremitate în afara mulţimii nodurilor rămase.

Grafuri orientate – noţiuni de bază

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 12:29 pm
Tags: , , , , ,

Noţiunea de graf orientat.

Un exemplu de graf orientat este: reţeaua de străzi a unui oraş. Străzile sunt muchii în graf, iar intersecţiile reprezintă vârfurile grafului. Întrucât mergând pe jos ne putem deplasa pe orice stradă în ambele sensuri, vom spune că din punctul de vedere al pietonilor, „graful unui oraş” este neorientat.

Cu totul altfel stau lucrurile în ceea ce priveşte conducătorii auto, pentru că în orice oraş există străzi cu sens unic. Pentru un şofer străzile trebuie să primească în graf o anumită orientare. Desigur că acele străzi pe care se poate circula în ambele sensuri vor primi orientare dublă. Am ajuns astfel la noţiunea de graf orientat.

Numim graf orientat, o pereche ordonată de mulţimi G=(X,U), unde:

X este o mulţime finită şi nevidă numită mulţimea nodurilor (vârfurilor);

U este o mulţime formată din perechi ordonate de elemente ale lui X, numită mulţimea arcelor (muchiilor)

Observaţii:

Prin noţiunea de perechi ordonate nu trebuie să înţelegem că o muchie este mai mare decât alta, ci pur şi simplu că facem deosebire între o muchie de forma (x,z) şi o alta de forma (y,x). Cu alte cuvinte muchiile sunt diferenţiate prin ordinea de scriere a simbolurilor.

Arcul (x,y) nu este tot una cu arcul (y,x).

Exemplu:

Pentru graful G=(X,U) din figură. avem: X={1, 2, 3, 4} şi U={u1, u2, u3, u4, u5, u6, u7,}= {(1,1), (2,1), (3,2), (2,3), (2,4), (3,4), (3,4)}

arc va fi de forma u= (x,y), unde x se numeşte extremitate iniţială, iar y se  numeşte extremitate finală a arcului. Cu alte cuvinte, “arcul iese din nodul x şi intră în nodul y”. La fel ca la grafurile neorientate, vom spune că nodurile x şi y sunt adiacente, iar arcul u şi nodul x sunt incidente (la fel arcul x şi nodul y). Nodul y se numeşte succesor al lui x, iar nodul x se numeşte predecesor al lui y. Un arc de forma (x,x), care iese din nodul x şi intră tot x, se numeşte buclă.

Exemplu:

În graful din figura de mai sus, avem bucla (1,1).

Într-un graf putem avea două sau mai multe arce identice.

Exemplu:

În graful din figura de mai sus, există două arce identice, u6 = u7 = (3,4)

Definiţie

Se numeşte p-graf, un graf orientat în care numărul arcelor identice este mai mic sau egal cu o valoare dată p.

În cele ce urmează vom analiza numai 1-grafuri fără bucle.

Aprilie 17, 2010

Grafuri neorientate

Definiţie

Se numeşte graf neorientat G=(X,U) o pereche de mulţimi (X,U), unde X este o mulţime finită şi nevidă de elemente numite noduri (vârfuri) iar U o mulţime de perechi, formate cu elemente distincte din mulţimea X numite muchii.

Se numesc noduri adiacente orice pereche de noduri între care există o muchie.

ex:muchia (1,2)

Spunem că un nod este incident cu o muchie daca nodul reprezintă o extremitate pentru aceea muchie.

ex:nodul 1 este incident cu muchia (1,2)

Spunem ca 2 muchii sunt incidente daca au un nod comun .

ex: muchia (1,2), (1,3) au nodul 1 comun

Nodurile vecine unui nod sunt toate noduriile adiacente cu nodul respectiv.

Gradul unui nod X al grafului G este egal cu numarul de muchii incidente cu nodul respectiv şi se noteaza cu d(x).

ex:d(3)=5

Un nod care are gradul 1 se numeşte nod terminal.

ex: d(4)=1

Un nod care are gradul 0 se numeşte vârf izolat.

ex: d(7)=0

Numim lanţ o succesiune de noduri cu proprietatea că oricare ar fi 2 noduri successive ele sunt adiacente.

Se numeşte ciclu ,un lanţ în care toate muchiile sunt distincte 2 câte 2 şi între primul şi ultimul nod există o muchie.

Se numeşte lungimea unui lanţ ,numărul de muchii din care este format.

Se numeşte lanţ elementar,un lanţ care conţine doar noduri distincte.

Se numeşte lanţ simplu,un lanţ care conţine doar muchii distincte.

Un lanţ care nu este simplu se numeşte lanţ compus.

Se numeşte un ciclu elementar,ciclul în care toate nodurile sunt distincte 2 câte 2; excepţie primul şi ultimul nod.

Observaţii :
Orice lanţ elementar este un lanţ simplu.

Nu este ciclu lanţul compus deoarece muchiile nu sunt distincte 2 câte 2.

TEOREME :
Numărul total de grafuri neorientate este:
2 la puterea Cn2 = 2 la puterea [n(n-1)]/2
Suma gradelor tuturor noduriilor unui graf neorientat este egală cu dublul nr. de muchii.
Dacă graful G neorientat are n noduri, iar n>2 atunci cel puţin 2 noduri au acelaşi grad.
Pentru orice graf neorientat,numărul noduriilor de grad impar este par.
Numărul minim de muchii pe care trebuie să le conţina un graf neorientat cu n noduri ca să nu existe vârfuri izolate este [(n+1)/2].

Moduri de reprezentare a grafurilor în memorie
a) Matrice de adiacenţă
Matricea de adiacenţă este o matrice patratică cu n linii şi m coloane .
Fiecare element i,j este de forma
aij= 0,dacă nu există muchie între nodul i şi nodul j;
1,dacă există muchie între nodul i şi nodul j.

Observatii :
1) Diagonala principală este întotdeauna egală cu 0.
2) Matricea este simetrică faţă de diagonala principală.

b) Matricea de incidenţă
Are n linii(n=numărul de noduri) şi m coloane (m=numărul de muchii).
! Pe fiecare coloană există 2 valori de 1 care reprezintă extremităţile unei muchii; toate celelalte elemente fiind 0.

Grafuri speciale

Graful G se numeşte nul dacă mulţimea U este vidă (nu are muchii).
Un graf se numeşte complet dacă are proprietatea că oricare 2 noduri ale sale sunt adiacente.
Teoremă: Numărul de muchii ale unui graf complet cu n noduri este
[n(n-1)]/2.
Se numeşte graf parţial al lui G=(X,U) graful Gp=(X,V) unde V este egal sau inclus în U (din graful G eliminăm muchii).
Se numeşte subgraf al lui G=(X,U), Gs=(Y,V) unde Y este egal sau inclus în X şi toate muchiile din mulţimea V aparţin şi mulţimii U,care au ambele extremităţi în mulţimea Y,adică se obţine din graful G prin eliminarea unor noduri şi a tuturor muchilor incidente cu acestea.
Se numeşte graf complementar al lui G,graful Gc care are propritatea că 2 noduri sunt adiacente în graful complementar dacă şi numai dacă nu sunt adiacente în graful G.
Teoremă: Numărul grafurilor parţiale ale unui graf cu m muchii este 2 la puterea m.
Teoremă: Numărul de subgrafuri ale unui graf cu n noduri este 2ⁿ-1.
Conexitate
Definitie:

1) Un graf G se numeşte graf conex dacă are proprietatea că pentru orice pereche de noduri distincte există un lanţ care le leagă.
2) Dacă un graf G nu este conex se numeşte componentă conexă a grafului, un subgraf conex
al său maximal în raport cu această proprietate (conţine numărul maxim de noduri din graful G care au proprietatea că sunt legate de un lanţ).

Teoreme:
1) Numărul minim de muchii necesare pentru ca un graf neorientat să fie conex este: n-1,unde n reprezintă numărul de noduri.
2) Un graf conex cu n noduri şi n-1 muchii este aciclic şi maximal în raport cu această proprietate.
3) Dacă un graf neorientat conex are n noduri şi m muchii, numărul de muchii care trebuie eliminate pentru a obţine un graf parţial conex aciclic este: m-n+1.
4) Dacă un graf are n noduri şi m muchii şi p componente conexe, numărul de muchii care trebuie eliminat pentru a obţine un graf parţial aciclic(arbore) este egal cu: m-n+p.
5) Pentru a obţine dintr-un graf neorientat conex 2 componente conexe numărul minim de muchii care trebuie eliminate este egal cu gradul minim din graf.
6) Numărul maxim de muchii dintr-un graf cu n noduri şi p componente conexe este [(n-p)(n-p+1)]/2.
Grafuri speciale

Un graf G se numeşte graf bipartit dacă există două mulţimi nevide de noduri A si B care au proprietatea: A ∩ B= Ø iar A U B=X şi orice muchie din mulţimea U are o extremitate în mulţimea A şi o altă extremitate în mulţimea B.
Un graf bipartit se numeşte graf bipartit complet dacă pentru oricare nod X care aparţine mulţimii A şi orice nod Y care aparţine mulţimii B există o muchie care le leagă.

Se numeşte lanţ Hamiltonian,lanţul care conţine toate nodurile grafului şi este elementar.
Un graf care conţine un ciclu Hamiltonian se numeşte graf Hamiltonian.
Un ciclu se numeşte eulerian,ciclul elementar ce conţine toate muchiile grafului.
Se numeşte graf eulerian,graful care conţine un ciclu eulerian.

TEOREME


1) Un graf cu mai mult de 2 noduri este Hamiltonian dacă graful fiecărui nod este mai mare sau egal decât n/2.
2) Un graf ce nu conţine vârfuri izolate este eulerian dacă şi numai dacă este conex iar gradele tuturor noduriilor sunt numere pare.
3) Numărul de cicluri hamiltoniene dintr-un graf complet cu n noduri este (n-1)!/2.

Creează un sit web gratuit sau un blog la WordPress.com.