~ info project ~

Mai 6, 2010

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.

Lasă un comentariu »

Niciun comentariu până acum.

RSS feed for comments on this post. TrackBack URI

Lasă un răspuns

Completează mai jos detaliile despre tine sau dă clic pe un icon pentru autentificare:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s

Blog la WordPress.com.

%d blogeri au apreciat asta: