1. No Ńiunea de graf neorientat Defini Ńie. SSee nnuummeeșșttee ggrraaff nneeoorriieennttaatt oo ppeerreecchhee oorrddoonnaattăă ddee mmuullŃŃiimmii… [618875]
1GRAFURI NEORIENTATE
1. No Ńiunea de graf neorientat
Defini Ńie. SSee nnuummeeșșttee ggrraaff nneeoorriieennttaatt oo ppeerreecchhee oorrddoonnaattăă ddee mmuullŃŃiimmii nnoottaattăă GG==((VV,, MM)) uunnddee::
VV :: eessttee oo mmuullŃŃiimmee ffiinniittăă șșii nneevviiddăă,, aallee ccăărreeii eelleemmeennttee ssee nnuummeesscc nnoodduurrii ssaauu vvâârrffuurrii;;
MM :: eessttee oo mmuullŃŃiimmee,, ddee ppeerreecchhii nneeoorrddoonnaattee ddee eelleemmeennttee ddiissttiinnccttee ddiinn VV,, aallee ccăărreeii eelleemmeennttee ssee nnuummeesscc
mmuucchhiiii..
• Exemplu de graf neorientat:
G=(V, M) unde: V={1,2,3,4}
M={{1,2}, {2,3},{1,4}t}
Demonstra Ńie:
Perechea G este graf neorientat deoarece respect ă defini Ńia prezentat ă mai sus, adic ă:
V : este finit ă și nevid ă;
M : este o mul Ńime de perechi neordonate (submul Ńimi cu dou ă elemente) de elemente din V.
În continuare, vom nota submul Ńimea {x,y}, care reprezint ă o muchie , cu [x,y] (într-un graf neorientat
muchia [x,y] este aceea și cu muchia [y,x]). În baza celor spuse anterior, g raful prezentat în exemplul de
mai sus se reprezint ă textual astfel:
G=(V, M) unde: V={1,2,3,4}
M={[1,2],[2,3],[1,4]}
În teoria grafurilor neorientate, se întâlnesc frec vent no Ńiunile:
– extremit ăŃile unei muchii
• fiind data muchia m=[x,y], se numesc extremit ăŃi ale sale nodurile x și y;
– vârfuri adiacente
• dac ă într-un graf exist ă muchia m=[x,y], se spune despre nodurile x și y ca sunt adiacente;
– inciden Ńă
• dac ă ml și m2 sunt dou ă muchii ale aceluia și graf, se numesc incidente dac ă au o extremitate
comun ă.
Exemplu: m 1=[x,y] și m2=[y,z] sunt incidente
• dac ă m=[x,y] este o muchie într-un graf, se spune despr e ca și nodul x , sau nodul y , ca sunt
incidente.
Reprezentarea unui graf neorientat admite dou ă forme, și anume:
– reprezentare textual ă: a șa cum s-a reprezentat graful din exemplul anterior;
– reprezentare grafic ă : muchiile sunt reprezentate prin linii ,
iar nodurile prin puncte.
• Exemplu de graf neorientat reprezentat textual:
G=(V, M) unde: V={ 1,2,3,4]
M={[ l,2], [2,3], [1,4]}
• Exemplu de graf neorientat reprezentat grafic (este graful de la exemplul anterior):
2. No Ńiunea de graf par Ńial
Defini Ńie. FFiiee GG==((VV,, MM)) un un ggrraaff nneeoorriieennttaatt.. SSee nnuummeeșșttee ggrraaff ppaarrŃŃiiaall,, aall ggrraaffuulluuii GG,, ggrraaffuull nneeoorriieennttaatt
GG11==((VV,, MM11)) uunnddee MM11 ⊆MM..
Concluzie:
Un graf par Ńial al unui graf neorientat G=(V, M) are aceea și mul Ńime de vârfuri ca și G iar mul Ńimea
muchiilor este o submul Ńime a lui M sau chiar M.
• Exemplu : Fie graful neorientat: 1
2G=(V, M) unde: V={ 1,2,3,4}
M={[1,2], [1,4], [2,3]}
reprezentat grafic astfel:
1. Un exemplu de graf par Ńial al grafului G este graful neorientat:
G1=(V, M,) unde: V={1,2,3,4}
M1={[1,2],[1,4]} (s-a eliminat muchia [2,3])
reprezentat grafic astfel:
•3
2. Un exemplu de graf par Ńial al grafului G este graful neorientat:
G1=(V,M 1) unde: V={1,2,3,4}
M1= φ (s-au eliminat toate muchiile)
reprezentat grafic astfel:
1 •
4 •
2 •
3 •
Observa Ńie. Fie G=(V, M) un graf neorientat. Un graf par Ńial, al grafului G, se ob Ńine p ăstrând vârfurile și
eliminând eventual ni ște muchii (se pot elimina și toate muchiile, sau chiar nici una).
3. No Ńiunea de subgraf
Defini Ńie . FFiiee GG==((VV,, MM)) un un ggrraaff nneeoorriieennttaatt.. SSee nnuummeeșșttee ssuubbggrraaff aall ggrraaffuulluuii GG,, ggrraaffuull nneeoorriieennttaatt GG11==((VV11,,
MM11)) uunnddee VV11⊆VV iiaarr MM,, ccoonnŃŃiinnee ttooaattee mmuucchhiiiillee ddiinn MM ccaarree aauu eexxttrreemmiittăăŃŃiillee îînn VV11..
• Exemplu: Fie graful neorientat:
G=(V, M) unde: V={ 1,2,3,4}
M={[1,2], [2,3], [1,4]}
reprezentat grafic astfel:
1. Un exemplu de subgraf al grafului G este graful neorientat:
G1=(V 1 , M 1) unde: V 1={1,2,3 } ( s-a șters nodul 4)
M1=([1,2],[2,3]} (s-a eliminat muchia [1,4J)
reprezentat grafic astfel:
1 •
2. Un exemplu de subgraf al grafului G este graful neorie ntat:
G1=(V 1 ,M 1) unde: V 1={1,2,3,4}
(s-a eliminat nodul 1)
M1={[2,3]}(s-au eliminat muchiile [1,4], [1,2])
reprezentat grafic astfel: 4 •
1
1
3
Observa Ńie . Fie G=(V, VI) un graf neorientat. Un subgraf, al grafului G, se ob Ńine ștergând anumite
vârfuri și odat ă cu acestea și muchiile care le admit ca extremitate.
4. Gradul unui vârf
Defini Ńie. FFiiee GG==((VV,, MM)) un un ggrraaff nneeoorriieennttaatt șșii xx un un nnoodd aall ssăăuu.. SSee nnuummeeșșttee ggrraadd aall nnoodduulluuii xx,, nnuummăărruull
mmuucchhiiiilloorr iinncciiddeennttee ccuu xx,, nnoottaatt dd((xx))..
•Exemplu : Fie graful neorientat:
G=(V, M) unde: V= {1,2,3,4}
M={[l,2], [2,3], [1,4], [1,3]}
reprezentat grafic astfel:
3
Gradul nodului 1 este d(1) și d(1)=3 (în graf sunt trei muchii incidente cu 1 )
Gradul nodului 2 este d(2) și d(2)=2 (în graf sunt dou ă muchii incidente cu 2 )
Gradul nodului 3 este d(3) și d(3)=2 (în graf sunt dou ă muchii incidente cu 3)
Gradul nodului 4 este d(4) și d(4)=1 (în graf este o singur ă muchie incident ă cu 4)
Observa Ńii.
1. Dac ă gradul unui vârf este 0, vârful respectiv se nume ște vârf izolat.
2. Dac ă gradul unui vârf este l, vârful respectiv se nume ște vârf terminal.
În graful care admite reprezentarea grafic ă:
1 •
deoarece d(1)=0 , vârful 1 se nume ște vârf izolat , și
deoarece d(2)=d(3)=1 , vârfurile 2 și 3 se numesc vârfuri terminale.
Propozi Ńie .. ÎÎnn ggrraaffuull nneeoorriieennttaatt GG==((VV,, MM)),, iinn ccaarree VV=={{xx11,, xx22,, ……,, xxnn}} șșii ssuunntt mm mmuucchhiiii,, ssee vveerriiffiiccăă
eeggaalliittaatteeaa :: m xdn
ii2)(
1=∑
=
Demonstra Ńie :
Muchia [x,y] contribuie cu o unitate la gradul lui x și cu o unitate la gradul lui y, deci, cu dou ă unit ăŃi la
suma din enun Ń. Cum în total sunt m muchii, rezult ă că suma gradelor este 2m.
Având in vedere faptul ca suma gradelor vârfurilor dintr-un graf este un num ăr par (2m), a ap ărut
corolarul prezentat mai jos.
Corolar. ÎÎnn oorriiccee ggrraaff nneeoorriieennttaatt,, GG==((VV,, MM)),, eexxiissttăă un un nnuummăărr ppaarr ddee vvâârrffuurrii ddee ggrraadd iimmppaarr..
Demonstratie:
Demonstra Ńia Ńine cont de propozi Ńia de mai sus, adic ă de faptul c ă într-un graf neorientat suma S a
tuturor gradelor nodurilor este un num ăr par (dublul num ărului muchiilor).
Fie S1 suma gradelor vârfurilor de grad par, (este un num ăr par, ca sum ă de numere pare) și S2 suma
gradelor vârfurilor de grad impar.
Cum S=S1+S2, rezult ă c ă S2=S-S1, deci un num ăr par (ca diferen Ńă de numere pare).
5. Graf complet
Defini Ńie. FFiiee GG==((VV,, MM)) un un ggrraaff nneeoorriieennttaatt.. GGrraaffuull GG ssee nnuummeeșșttee ggrraaff ccoommpplleett,, ddaaccăă oorriiccaarree ddoouuăă
vvâârrffuurrii ddiissttiinnccttee aallee ssaallee ssuunntt aaddiiaacceennttee..
• Exemplu de graf neorientat complet:
G=(V, M) unde: V={ 1,2,3,4}
M={[1,2], [1,3], [l,4], [2,3], [2,4], [3,4]}
Reprezentarea sa grafic ă este: 1
1
4
Observa Ńii.
1. Într-un graf complet cu n vârfuri gradul fiec ărui vârf este n-1, deoarece fiecare vârf este legat prin
muchii de toate celelalte vârfuri.
2. Graful complet cu n vârfuri se noteaz ă cu K n
În particular, graful:
se noteaz ă K 4 (este un graf complet cu 4 vârfuri).
Propozi Ńie. ÎÎnnttrr–uunn ggrraaff ccoommpplleett ccuu nn vvâârrffuurrii,, nnoottaatt KKnn,, eexxiissttăă ()
21−nn mmuucchhiiii..
Demonstra Ńie:
Din fiecare vârf x, pleac ă n-1 muchii, deci d(x i)=n-1, pentru orice i= 1..n Cum folosind propozi Ńia
prezentat ă în sec Ńiunea gradul unui vârf.
2m= d(x 1)+ d(x 2)+ … +d(x n) → 2m=(n-1)+ (n-1)+… +(n-1)
→ 2m=n(n-1)/2
6. Graf bipartit
Defini Ńie. FFiiee GG ==((VV,, MM)) un un ggrraaff nneeoorriieennttaatt.. GGrraattuull GG ssee nnuummeeșșttee ggrraaff bbiippaarrttiitt,, ddaaccăă eexxiissttăă ddoouuăă mmuullŃŃiimmii
nneevviiddee VVll șșii VV22 ccuu pprroopprriieettăăŃŃiillee::
φ= ∩−= ∪−
2 12 1
V VV V V
– oorriiccee mmuucchhiiee aa lluuii CC aarree oo eexxttrreemmiittaattee îînn VV11 șșii ppee cceeaallaallttăă îînn VV22..
• Exemplu de graf neorientat bipartit:
G=(V, M) unde: V={ 1,2,3,4}
M={[1,3], [2,3], [2,4]}
Reprezentarea sa grafic ă este:
1
•3
Demonstra Ńie:
Graful de mai sus este bipartit deoarece respect ă întocmai defini Ńia grafului bipartit, adic ă exist ă dou ă
mul Ńimi V1={1,2} și V2={3,4} astfel încât: φ= ∩−= ∪−
2 12 1
V VV V V
– orice muchie a lui C are o extremitate în V1 și pe cealalt ă în V2 ..
Cum, în plus, pentru orice x din V1 și orice y din V2 exist ă în G muchia [x,y], rezult ă, conform defini Ńiei,
ca graful G este bipartit complet.
ObservaŃie. A demonstra c ă un graf au este bipartit complet înseamn ă a demonstra :
– că este bipartit
– pentru orice x din Vl și orice y din V2 exist ă in G muchia [x,y].
Observa Ńie. Într-un graf bipartit complet în care V1 are p ele mente și V2 are q elemente exist ă pq muchii.
Demonstra Ńie : 3
5Fiecare vârf x i din V1 este legat de toate vârfurile aflate în V2, altfel spus, exist ă q muchii care-l admit ca
extremitate pe x i. Cum în Vl sunt p elemente, adic ă i= 1…p. înseamn ă c ă elementele mul Ńimii V1 sunt
legate prin pq muchii de elementele mul Ńimii V2.
Observa Ńie . Graful bipartit complet în care V1 are p elemente și V2 are q elemente se noteaz ă cu K p,q .
În particular, graful:
se noteaz ă K 2,2 (este un graf bipartit complet cu
V1 = 2 și V2=2 , V1 și V2 din defini Ńie).
8. Reprezentarea grafurilor neorientate
Fie G=(V, M) un graf neorientat, unde V={x 1, x 2,…, x n} și M={m 1 ,m 2,…, m p }. Deoarece între mul Ńimea
{x 1, x 2,…, x n} și mul Ńimea {1, 2,…, n} exist ă o bijec Ńie, x i ↔i, putem presupune, f ără a restrânge
generalitatea, mai ales pentru a u șura scrierea, ca V={ 1, 2,…, n}.
În baza celor spuse mai sus, mai departe, ]n loc de x; vom scrie i și ]n loc de muchia [x i,xj] vom scrie [i,j].
Pentru a putea prelucra un graf neorientat cu ajutorul unui program, trebuie m ai întâi s ă fie reprezentat in
programul respectiv.
Pentru a reprezenta un graf, într-un program, exist ă mai multe modalit ăŃ i folosind diverse structuri de
date; dintre acesta, in continuare, vom prezenta:
– reprezentarea unui graf prin matricea de adiacen Ńă ;
– reprezentarea unui graf prin listele de adiacen Ńă ;
– reprezentarea unui graf prin șirul muchiilor.
Matricea de adiacent ă
Fie G=(V, M) un graf neorieritat cu n vârfuri (V={1,2, …, n}) și m muchii.
MMaattrriicceeaa ddee aaddiiaacceennŃŃăă,, aassoocciiaattăă ggrraaffuulluuii GG,, eessttee oo mmaattrriiccee ppăăttrraattiiccăă ddee oorrddiinnuull nn,, ccuu eelleemmeenntteellee ddeeffiinniittee
aassttffeell::
[]
[ ]
∉∈
=
Mji daca Mji daca
aji, , 0, , 1
,
((aallttffeell ssppuuss,, aaii,,jj==11,, ddaaccăă eexxiissttăă mmuucchhiiee îînnttrree ii șșii jj șșii aaii,,jj==00 ddaaccăă nnuu eexxiissttăă mmuucchhiiee îînnttrree ii șșii jj))
•Exemplul 1 . Fie graful reprezentat grafic ca in
figura de mai jos:
Matricea de adiacen Ńă , asociat ă grafului, este:
=
=
0011001111001100
44 43 42 41 34 33 32 31 24 23 22 21 14 13 12 11
a a a aa a a aa a a aa a a a
A
• Exemplul 2 . Fie graful reprezentat grafic ca in
figura de mai jos:
Matricea de adiacent ă, asociat ă grafului, este:
=
=
0111101111011110
44 43 42 41 34 33 32 31 24 23 22 21 14 13 12 11
a a a aa a a aa a a aa a a a
A
Comentarii:
1. Matricea de adiacen Ńă este o matrice p ătratic ă, de ordin n, și simetric ă fa Ńă de diagonala principal ă
(adic ă a[i][j]=a[j][i]).
Secven Ńele de citire a matricei de adiacen Ńă , sunt:
int a[100][100];
……….
cout<<"n="; cin>>n;
for (i=1;i<=n-l;i++) se citesc valorile elementelor for (j=i+l;j<=n;j++) de deasupra diagonalei
principale
{ cin>>a[i][j]; și se transfer ă și sub
a[j][i]=a[i][j];} diagonala principal ă 1
3
6
sau:
…….
cin>>n; cin>>m;
for (i=1;i<=n;i++) for (j=1;j<=n;j++)
a[i][j]=0;
for (i=1;i<=m;i++)
{cout<<"dati extremitatile muchiei "<<i;
cin>>x >>y;
a[x][y]=1; a[y][x]= 1;}
2. Matricea de adiacent ă are toate elementele de pe diagonala principal ă egale cu 0.
3. Numărul elementelor egale cu 1 de pe linia i (sau coloana i) este egal cu gradul vârfului i . Dac ă
vârful i este un vârf izolat pe linia i ( și coloana i) nu sunt elemente egale cu 1 .
Liste de adiacen Ńă
Fie G=(V, M) un graf neorientat cu n vârfuri (V={1,2, …, n}) și m muchii.
RReepprreezzeennttaarreeaa ggrraaffuulluuii GG pprriinn lliissttee ddee aaddiiaacceennŃŃăă ccoonnssttăă îînn::
– pprreecciizzaarreeaa nnuummăărruulluuii ddee vvâârrffuurrii,, nn;;
– ppeennttrruu ffiieeccaarree vvâârrff ii,, ssee pprreecciizzeeaazzăă lliissttaa LLii aa vveecciinniilloorr ssăăii,, aaddiiccăă lliissttaa nnoodduurriilloorr aaddiiaacceennttee ccuu nnoodduull ii..
Exemplul 1 . Fie graful reprezentat grafic ca in
figura de mai jos:
Reprezentarea sa prin liste de adiacen Ńe presupune:
– precizarea num ărului de vârfuri n, n=4;
– precizarea listei vecinilor lui i, pentru i=1..n,
astfel:
Vârful i Lista vecinilor lui i
1 3,4
2 3,4
3 1,2
4 1, 2
Exempul 2 . Fie graful reprezentat grafic ca in
figura de mai jos:
Reprezentarea sa prin liste de adiacen Ńe presupune:
– precizarea num ărului de vârfuri n, n=4;
– precizarea listei vecinilor lui i, pentru i= 1..n ,
astfel:
Vârful i Lista vecinilor lui i
1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
• Comentarii:
Acest mod de reprezentare se poate implementa astfe l:
ll.. SSee ffoolloosseeșșttee un un ttaabblloouu bbiiddiimmeennssiioonnaall TT,, ccaarraacctteerriizzaatt aassttffeell::
•• aarree nn ++22mm ccoollooaannee;;
•• TT11,,ii==ii ppeennttrruu ii==11….nn;;
•• PPeennttrruu ii==11….nn TT22,,ii==kk,, ddaaccăă TT11,,kk eessttee pprriimmuull nnoodd ddiinn lliissttaa vveecciinniilloorr lluuii ii;;
TT22,,ii==00,, ddaaccăă nnoodduull ii eessttee iizzoollaatt;;
•• DDaaccăă TT11,,jj==uu,, aaddiiccăă uu eessttee un un nnoodd ddiinn lliissttaa vveecciinniilloorr lluuii ii,, aattuunnccii::
TT22,,jj==00,, ddaaccăă uu eessttee uullttiimmuull nnoodd ddiinn lliissttaa vveecciinniilloorr lluuii ii;;
TT22,,jj==jj++ll,, ddaaccăă uu nnuu eessttee uullttiimmuull nnoodd ddiinn lliissttaa vveecciinniilloorr lluuii ii..
Exemplu de completare a tabloului pentru graful de la exemp lul 1
Prima etap ă. Se numeroteaz ă coloanele ( l ..n+2m) și se trec vârfurile.
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4
A doua etap ă. Se trec in tabel vecinii lui 1, începând de la co loana 5.
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 3 4
5 6 0
T2,1 =5, pentru ca primul vecin (3) al lui 1 s-a trecut la coloana 5 (T 1,5 =3).
T2,5 =6, pentru c ă urm ătorul vecin (4) al lui l s-a trecut la coloana 6 (T 1,6 =4). 1
1
7T2,6 =0, pentru ca vecinul T 1,6 (4) al lui 1 este ultimul din list ă.
A treia etap ă. Se trec in tabel vecinii lui 2, începând de la co loana 7.
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 3 4 3 4
5 7 6 0 8 0
T2,2 =7, pentru c ă primul vecin (3) al lui 2 s-a trecut la coloana (T 1,7 =3).
T2,7 =8, pentru ca urm ătorul vecin (4) al lui 2 s-a trecut la coloana 8 (T 1,8 =4).
T2,8 =0, pentru c ă vecinul T 1,8 (4) al lui 2 este ultimul din list ă.
A patra etap ă. Se trec in tabel vecinii lui 3, începând de la co loana 9.
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 3 4 3 4 1 2
5 7 9 6 0 8 0 10 0
T2,3 =9, pentru c ă primul vecin (1) al lui 3 s-a trecut la coloana 9 (T 1,9 =1).
T2,9 =10, pentru c ă urm ătorul vecin (2) al lui 3 s-a trecut la coloana 10 ( T 1,10 =2)
T2,10 = 0, pentru c ă vecinul T 1,10 (2) al lui 3 este ultimul din list ă.
Ultima etap ă. Se trec in tabel vecinii lui 4, începând de la co loana 11.
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 3 4 3 4 1 2 1 2
5 7 9 11 6 0 8 0 10 0 12 0
T2,4 =11, pentru c ă primul vecin (1) al lui 4 s-a trecut la coloana 11 (T 1,11 =1).
T2,11 =12, pentru c ă urm ătorul vecin (2) al lui 4 s-a trecut la coloana 12 ( T 1,12 =2)
T2,12 =0, pentru c ă vecinul T 1,12 (2) al lui 4 este ultimul din list ă.
22.. SSee ffoolloosseeșșttee un un ttaabblloouu uunniiddiimmeennssiioonnaall,, ccuu nnuummeellee ccaapp,, șșii un un ttaabblloouu bbiiddiimmeennssiioonnaall,, ccuu nnuummeellee LL
((ccaarree rreeŃŃiinnee lliisstteellee ddee vveecciinnii ppeennttrruu ffiieeccaarree nnoodd)),, ccaarraacctteerriizzaattee aassttffeell::
TTaabblloouull ccaapp::
– aarree nn ccoommppoonneennttee;;
– ccaappii ==cc,, ddaaccăă pprriimmuull nnoodd ddiinn lliissttaa vveecciinniilloorr lluuii ii eessttee ttrreeccuutt iinn ttaabblloouull LL llaa ccoollooaannaa cc,, aaddiiccăă LL11,,cc
eessttee pprriimmuull vveecciinn aall lluuii ii,,
șșii ccaappii ==00,, ddaaccăă nnoodduull ii eessttee iizzoollaatt
TTaabblloouull LL::
– aarree 22mm ccoommppoonneennttee;;
– ddaaccăă kk eessttee un un vveecciinn aall nnoodduulluuii ii,, aattuunnccii::
LL11,,kk==kk șșii LL22,,pp==00,, ddaaccăă kk eessttee uullttiimmuull vveecciinn ddiinn lliissttăă,, ssaauu
LL11,,pp==kk șșii LL22,,pp== pp++ll ddaaccăă kk nnuu eessttee uullttiimmuull vveecciinn ddiinn lliissttăă ((pp eessttee ccoollooaannaa llaa ccaarree ss–aa aajjuunnss
îînn ttaabblloouull LL))..
• Exemplu de completare a tablourilor cap și L, pentru graful de la exemplul 1.
Tabloul cap
1 2 3 4
1 3 5 7
Tabloul L
1 2 3 4 5 6 7 8
3 4 3 4 1 2 1 2
2 0 4 0 6 0 8 0
33.. SSee ffoolloosseeșșttee un un ttaabblloouu bbiiddiimmeennssiioonnaall,, ccuu nnuummeellee LL,, ccaarraacctteerriizzaatt aassttffeell::
– aarree nn lliinniiii;;
– ppee lliinniiaa ii ssee ttrreecc vveecciinnii nnoodduulluuii ii..
• Exemplu de completare a tabloului L, pentru graful:
8
Tabloul L
3
3 4
1 2 4
2 3
Implementarea în limbajul C++, a ideii prezentate m ai sus, se realizeaz ă conform secven Ńei de
program prezentat ă mai jos.
…………………
int L[20][20];
int nr_vec[20];
cout<<"n=”; cin>>n;
for (i=1;i<=n;i++)
{cout<<"Dati numarul veciniior nodului "<<i; cin>>n r_vec[i];
for (j=1;j<=nr_vec[i];j++)
cin>>L[i][j];}
………………
Construirea matricei de adiacen Ńă când se cunoa ște L (listele vecinilor fiec ărui nod).
………………………….
for (i=1;i<=n;i++)
{for (j=1;j<=nr_vec[i];j++)
a[i][L[i][j]]=1;}
……………………………
Construirea tabloului L (listele vecinilor nodurilor) când se cunoa ște matricea de adiacent ă.
……………………………
for (i=1;i<=n;i++)
{k=0;
for (j=l;j<=n;j++)
if (a[i][j]==1)
{k=k+l ;
L[i][k]=j;}
}
44.. SSee ffoolloosseeșșttee un un ttaabblloouu uunniiddiimmeennssiioonnaall,, ccuu nnuummeellee LL,, ccaarraacctteerriizzaatt aassttffeell::
– ccoommppoonneenntteellee ssaallee ssuunntt ddee ttiipp rreeffeerriinnŃŃăă;;
– aarree nn ccoommppoonneennttee;;
– LLii ppooiinntteeaazzăă sspprree îînncceeppuuttuull lliisstteeii vveecciinniilloorr nnoodduulluuii ii..
Șirul muchiilor
Fie G=(V, M) un graf neorientat cu n vârfuri (V={1,2,…, n}) și m muchii. Reprezentarea grafului G
const ă in precizarea num ărului n de noduri si num ărului m de muchii, precum și în precizarea
extremit ăŃ ilor pentru fiecare muchie în parte.
Comentarii:
Acest mod de reprezentare se implementeaz ă astfel:
11.. SSee ddăă nnuummăărruull nn ddee nnoodduurrii,, nnuummăărruull mm ddee mmuucchhiiii șșii eexxttrreemmiittăăŃŃiillee ffiieeccăărreeii mmuucchhiiii,, ccaarree ssuunntt ttrreeccuuttee îînn
vveeccttoorriiii eell șșii ee22 aassttffeell::
eexxttrreemmiittăăŃŃiillee pprriimmeeii mmuucchhiiii ssuunntt ee11[[ii]] ssii ee22[[11]];;
eexxttrreemmiittăăŃŃiillee cceelleeii ddee–aa ddoouuaa mmuucchhiiee ssuunntt eell[[22]] șșii ee22[[22]];;
…………………………………………………………………………….
ddeeccii MM=={{ [[ee11[[11]],,ee22[[11]]]] ,, [[ee11[[22]],,ee22[[22]]]] ,,……,, [[ee11[[mm]],,ee22[[mm]]]]}}..
Secven Ńa C++ corespunz ătoare este:
int el[100],e2[l00];
int n, m, i;
……………………….
cout<<"n="; cin>>n;
9cout<<"m="; cin>>m;
for (i=1;i<=m;i++)
{cout<<"Dati extremitatile muchiei cu numarul "<<i;
cin>>e1[i]>>e2[i];}
……………………….
Construirea matricei de adiacen Ńă , când se cunoa ște șirul muchiilor ca mai sus.
……………………….
cout<<"n="; cin>>n;
for (i=1;i<=m;i++)
{a[el[i]][e2[i]]=1;
a[e2[i]][el[i]]=1;}
Construirea șirului muchiilor, ca mai sus, când se d ă matricea de adiacen Ńă .
………………………..
k=0;
for (i=l;i<=n-l;i++)
for (j=i+1;j<=n;j++)
if (a[i][j]=1)
{k=k+1;
e1[k]=i;
e2[k]=j;}
m=k;
…………………………
22.. SSee ffoolloosseeșșttee un un ttaabblloouu uunniiddiimmeennssiioonnaall,, ccuu nnuummeellee ee,, ccaarraacctteerriizzaatt aassttffeell::
– ccoommppoonneenntteellee ssaallee ssuunntt ddee ttiipp ssttrruuccttuurrăă;;
– aarree mm ccoommppoonneennttee;;
– eeii rreepprreezziinnttăă mmuucchhiiaa ii..
PPeennttrruu iimmpplleemmeennttaarree eessttee nneevvooiiee ddee::
ttyyppeeddeeff ssttrruucctt{{
iinntt xx;;
iinntt yy;;
}} mmuucchhiiee;;
mmuucchhiiee ee[[2200]];;
………………………………………………..
AAcccceessuull llaa mmuucchhiiaa ii ssee ffaaccee:: ee[[ii]]..xx ………… ee[[ii]]..yy
Secven Ńa C++ corespunz ătoare este:
…………………………
cout<<"n="; cin>>n;
cout<<"m="; cin>>m;
for (i=1;i<;=m;i++)
{cout<<"Dati extremitatile muchiei cu numarul "<<i;
cin>>e[i].x>>e[i].y;}
Construirea matricei de adiacen Ńă , când se cunoa ște șirul muchiilor ca mai sus.
………………………….
cout<<"n=”; cin>>n;
for (i=l;i<=m;i++)
{a[e[i].x][e[i].y]=1;
a[e[i].y][e[i].x]=1;}
…………………………
Construirea șirului muchiilor, ca mai sus, când se d ă matricea de adiacen Ńă .
…………………………
k=0;
for (i= 1;i<=n-1;i++)
for (j=i+l;j<=n; j++)
10 if (a[i][j]==1)
{ k =k+1;
e[k].x=i;
e[k].y=j;}
m=k;
………………………….
9. Parcurgerea grafurilor
Fie G=(V, M) graf neorientat, unde V={x 1, x 2,…, x n } și M={m 1, m 2,…, m p}.
Prin parcurgerea grafului G se în Ńelege vizitarea, într-un mod sistematic, a tuturor nodurilor, plecând de
la un nod pl (nod de plecare) mergând pe muchii incidente dou ă câte dou ă.
Un graf poate fi parcurs în urm ătoarele dou ă moduri:
– în l ătime (BF = Breadth First)
– în adâncime (DF = Depth First)
Parcurgerea în l ăŃime (BF- breadth first)
Fie G=(V, M) un graf neorientat cu n vârfuri (V={1,2, …, n}) și m muchii.
AAllggoorriittmmuull–ddee ppaarrccuurrggeerree aa ggrraaffuulluuii îînn llăăŃŃiimmee,, ffoolloossiinndd oo ccooaaddăă,, eessttee::
– iinniiŃŃiiaall ttooaattee nnoodduurriillee ssee ccoonnssiiddeerrăă nneevviizziittaattee;;
– ssee cciitteeșșttee nnoodduull ddee pplleeccaarree ppll,, ccaarree ssee ccoonnssiiddeerrăă aaccuumm vviizziittaatt,, șșii ssee ttrreeccee iinn ccooaaddăă ppee ,,pprriimmaa ppoozziiŃŃiiee;;
– ssee ttrreecc iinn ccooaaddăă ttooaattee nnoodduurriillee nneevviizziittaattee ppâânnăă iinn pprreezzeenntt șșii ssuunntt aaddiiaacceennttee ccuu nnoodduull ddee pplleeccaarree
((ooddaattăă ccuu ttrreecceerreeaa lloorr iinn ccooaaddăă ssee mmaarrcchheeaazzăă ccaa ffiiiinndd vviizziittaattee));;
– ssee ttrreeccee llaa uurrmmăăttoorruull eelleemmeenntt ddiinn ccooaaddăă,, ccaarree iiaa rroolluull nnoodduulluuii ddee pplleeccaarree,, șșii ssee rreeiiaa ppaassuull aanntteerriioorr;;
……………………………………………………….
– aallggoorriittmmuull ssee tteerrmmiinnăă dduuppăă ccee ssuunntt ppaarrccuurrssee ttooaattee eelleemmeenntteellee ddiinn ccooaaddăă..
• Exemplul 1. Fie graful reprezentat grafic ca în f igura de mai jos:
1
Observa Ńie. În continuare, un nod se consider ă vizitat când este încercuit:
și cu p și u not ăm indicele primului, respectiv ultimului element di n coad ă.
Parcurgerea in l ăŃime , a grafului de mai sus, presupune parcurgerea etap elor:
* La început, nici un nod nu este vizitat (graful arat ă ca in figura ini Ńial ă, adic ă nici un nod nu este
încercuit).
* Se pleac ă de la nodul 1, care se trece in coad ă pe prima pozi Ńie și se marcheaz ă ca fiind vizitat.
p=u
1
*Se viziteaz ă și se trec în coad ă toate nodurile adiacente cu nodul 1, nevizitate în c ă (2,3,4).
11
p u
1 2 3 4
* Se trece la urm ătorul element din coad ă; acesta este 2. Se viziteaz ă și se trec în coad ă toate nodurile
adiacente cu nodul 2, nevizitate înc ă (nu este nici un nod care s ă verifice condi Ńiile).
p u
1 2 3 4
*Se trece la urm ătorul element din coad ă; acesta este 3. Se viziteaz ă și se trec în coad ă toate nodurile
adiacente cu nodul 3, nevizitate înc ă (b).
p u
1 2 3 4 6
* Se trece la urm ătorul element din coad ă; acesta este 4. Se viziteaz ă și se trec în coad ă toate nodurile
adiacente cu nodul 4, nevizitate înc ă (5).
p u
1 2 3 4 6 5
*Se trece la urm ătorul element din coad ă: acesta este 6. Se viziteaz ă și se trec în coad ă toate nodurile
adiacente cu nodul 6, nevizitale înc ă (nu este nici un nod care s ă verifice condi Ńiile).
p u
1 2 3 4 6 5
*Se trece la urm ătorul element din coada; acesta este 5. Se viziteaz ă și se trec în coada toate nodurile
adiacente cu nodul 5, nevizitate înc ă (nu este nici un nod care s ă verifice condi Ńiile).
p = u
1 2 3 4 6 5
* Algoritmul se încheie aici (nu mai sunt noduri).
Deci, parcurgerea in l ăŃime a grafului este: 1 2 3 4 6 5
12
În continuare, vom prezenta programele C++ care imp lementeaz ă algoritmul prezentat mai sus.
Programul 1 ( abordare nerecursiv ă)
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
int a[20][20],coada[20], viz[20];
int i, n , el, j, p, u, pl, m, x, y;
void main()
{clrscr();
cout<<"n="; cin>>n;
cout<<"m="; cin>>m;
for (i=1;i<=m;i++)
{cout<<"x y ="; cin>>x>>y;
a[x][y]=1; a[y][x]=1;}
for (i=1;i<=n;i++)
viz[i]=0;
cout<<"dati nodul de plecare :"; cin>>pl;
viz[pl]=1;
coada[1]=pl;
p=1; u=1;
while (p<=u)
{ el=coada[p];
for (j=1;j<=n;j++)
if ((a[el][j]==1) && (viz[j]==0))
{u=u+ 1;
coada[u]=j;
viz[j]=1;}
p=p+1;}
for (i=1;i<=u;i++) cout<<coada[i]<< " ";
getch();}
Programul 2 (abordare recursiv ă)
Comentarii la func Ńia parc_latime:
– are un parametru formal, i, care reprezint ă pozi Ńia curent ă la care s-a ajuns în coad ă;
– procedeaz ă astfel:
– se parcurg nodurile grafului, cu j:
dac ă j este adiacent cu nodul curent din coad ă și j este nevizitat
– se adaug ă la coad ă;
– și se marcheaz ă ca fiind vizitat;
– dac ă mai sunt elemente în coad ă se trece la urm ătorul și se reapeleaz ă func Ńia
# include <conio.h>
#include <iostream.h>
#include <stdio.h>
int a[20][20];
int coada[20], vizitat[20];
int i, n , j, u, pl, m,x, y;
void parc_latime(int i)
{int j;
for (j=1;j<=n;j++)
if ((a[coada[i]][j]==1) && (vizitat[j]==0))
{ u=u+1;
coada[u]=j;
vizitat[j]=1 ;}
if (i<=u) parc_latime(i+1);}
13 void main()
{ clrscr();
cout<<"n="; cin>>n;
cout<<"m="; cin>>m;
for (i=1;i<=m;i++)
{cout<<"x y" ; cin>>x>>y;
a[x][y]=1; a[y][x]=1;}
for (i=1;i<=n;i++)
viz[i]=0;
cout<<"dati nodul de plecare :"; cin>>pl;
vizitat[pl]=1;
coada[1]=pl;
u=1 ;
parc_latime(1);
for (i=1;i<=u;i++)
cout<<coada[i]<<" ";
getche(); }
Parcurgerea in adâncime (DF-depth first)
Fie G =(V, M) un graf neorientat cu n vârfuri (V={1 ,2, …. n} ) și m muchii.
Algoritmul recursiv de parcurgere a grafului in adâncime este implementat în func Ńia parc_adancime,
caracterizat ă astfel:
– are un parametru formal ( nodul curent , asupra c ăruia se aplic ă):
– procedeaz ă astfel:
– afi șează nodul asupra c ăruia se aplic ă și-l marcheaz ă ca fiind vizitat ;
– pentru fiecare vecin nevizitat de-al nodului curent
– se autoapeleaz ă asupra sa.
• Exemplul 1 . Fie graful reprezentat grafic ca în
figura de mai jos:
1
10
Aplicarea algoritmului de parcurgere în
adâncime, asupra grafului de mai sus, plecând de
la primul nod, conduce la afi șarea urm ătoarei
secven Ńe:
1 2 3 4 5 6 7 8 9 10 • Exemplul 2 . Fie graful reprezentat grafic ca în
figura de mai jos:
l
6 9 10
Aplicarea algoritmului de parcurgere în
adâncime, asupra grafului de mai sus, plecând de
la primul nod, conduce la afi șarea urm ătoarei
secven Ńe:
1 2 3 4 7 8 5 6 9 10
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
int a[20][20];
int vizitat[20];
int i,n,j,pl,m,x,y;
void parc_adancime(int pl)
{int j;
cout<<pl<<" "; viz[pl]=1;
for (j=1; j<=n;j++)
if ((a[pl][j]==1) && (vizitat[j]==0))
parc_adancime(j);}
void main()
{cout<<"n m "; cin>>n>>m;
for (i=1;i<=m;i++)
{cout<<"x y "; cin>>x>>y;
a[x][y]=1; a[y][x]=1;}
14 for (i=1;i<=n;i++)
vizitat[i]=0;
cout<<"dati nodul de plecare :"; cin>>pl; parc_adancime(pl);
getch();}
10. Conexitate
Vor fi prezentate no Ńiunile:
– lan Ń
– ciclu
– graf conex
– component ă conex ă
Lan Ń
Defini Ńie . FFiiee GG==((VV,, MM)) uunn ggrraaff nneeoorriieennttaatt.. SSee nnuummeeșșttee llaannŃŃ,, îînn ggrraaffuull GG,, oo ssuucccceessiiuunnee ddee nnoodduurrii,, nnoottaattăă LL
== [[xxii11 ,, xxii22,, ,,……,, xxiikk ]] ,, ccuu pprroopprriieettaatteeaa ccăă oorriiccaarree ddoouuăă nnoodduurrii ccoonnsseeccuuttiivvee ssuunntt aaddiiaacceennttee,, aallttffeell ssppuuss
[[xxii11,,xxii22]],,……,, [[xxiikk–11,,xxiikk]] ∈MM
Se întâlnesc no Ńiunile:
– extremit ăŃile lan Ńului
• fiind dat lan Ńul L = [x i1 , x i2 , ,…, x ik ], se numesc extremit ăŃi ale sale nodurile x i1 și x ik ( x i1 –
extremitate ini Ńial ă; x ik – extremitate final ă);
– lungimea lan Ńului
• fiind dat lan Ńul L = [x i1 , x i2 , ,…, x ik ] prin lungimea sa se în Ńelege num ărul de muchii care
apar în cadrul lui
• Exemplu de lan Ń:
Fie graful G=(V, M) unde:
V={ 1,2,3,4,5}
M={[1,3], [1,4], [2,3], [2,4], [2,5]}
cu reprezentarea grafic ă astfel:
Lan Ńul L1=[1, 3, 2, 4] este în graful G lan Ń cu lungimea 3 și extremit ăŃ ile 1 și 4.
L2=[5, 2, 4, 1, 3, 2] este în graful G lan Ń cu lungimea 5 și extremit ăŃ ile 5 si 2.
Observa Ńie Dac ă L=[x i1 , x i2 , ,…, x ik ], este lan Ń în graful G, atunci și L1= [x ik ,…,x i2 ,xi1 ], este lan Ń în graful
G.
Defini Ńie. FFiiee GG–((VV,, MM)) uunn ggrraaff nneeoorriieennttaatt.. SSee nnuummeeșșttee llaannŃŃ eelleemmeennttaarr,, îînn ggrraaffuull GG,, llaannŃŃuull LL == [[xxii11 ,, xxii22,,
,,……,, xxiikk ]],, ccuu pprroopprriieettaatteeaa ccăă oorriiccaarree ddoouuăă nnoodduurrii aallee ssaallee ssuunntt ddiissttiinnccttee ((aallttffeell ssppuuss:: pprriinnttrr–uunn nnoodd nnuu ssee
ttrreeccee ddeeccââtt oo ssiinngguurrăă ddaattăă))..
• Exemplu : În graful
lan Ńul L1=[l, 3, 2, 4] este lan Ń elementar.
Defini Ńie . FFiiee GG==((VV,,MM)) uunn ggrraaff nneeoorriieennttaatt.. SSee nnuummeeșșttee llaannŃŃ nneeeelleemmeennttaarr îînn ggrraaffuull GG llaannŃŃuull LL==[[xxii11 ,, xxii22,,
,,……,, xxiikk ]],, ccuu pprroopprriieettaatteeaa ccăă nnoodduurriillee ssaallee nnuu ssuunntt ddiissttiinnccttee ddoouuăă ccââttee ddoouuăă ((aallttffeell ssppuuss:: pprriinn aannuummiittee nnoodduurrii
ssee ttrreeccee ddee mmaaii mmuullttee oorrii))..
•Exemplu : În graful
5
5
5
15 lan Ńul L2=[5, 2, 4, 1, 3, 2] este lan Ń neelementar (prin 2 s-a trecut de dou ă ori).
Ciclu
DDeeffiinniiŃŃiiee.. FFiiee GG==((VV,, MM)) uunn ggrraaff nneeoorriieennttaatt.. SSee nnuummeeșșttee cciicclluu,, îînn ggrraaffuull GG,, llaannŃŃuull CC == [[xxii11 ,, xxii22,, ,,……,, xxiikk ]],, ccuu
pprroopprriieettaatteeaa ccăă xxii11==xxiikk șșii aarree mmuucchhiiiillee ddiiffeerriittee ddoouuăă ccââttee ddoouuăă..
• Exemplu : În graful
lan Ńul C=[ 1, 3, 2, 4, 1] este ciclu.
Defini Ńie. FFiiee GG==((VV,, MM)) uunn ggrraaff nneeoorriieennttaatt.. SSee nnuummeeșșttee cciicclluu eelleemmeennttaarr,, îînn ggrraaffuull GG,, uunn cciicclluu ccuu
pprroopprriieettaatteeaa ccăă oorriiccaarree ddoouuăă nnoodduurrii aallee ssaallee,, ccuu eexxcceeppŃŃiiaa pprriimmuulluuii șșii aa uullttiimmuulluuii,, ssuunntt ddiissttiinnccttee..
• Exemplu : În graful
ciclul C=[ 1, 3, 2, 4, 1 ] este ciclu elementar.
Defini Ńie. FFiiee GG==((VV,, MM)) uunn ggrraaff nneeoorriieennttaatt.. SSee nnuummeeșșttee cciicclluu nneeeelleemmeennttaarr,, îînn ggrraaffuull GG,, uunn cciicclluu ccuu
pprroopprriieettaatteeaa ccăă nnoodduurriillee ssaallee,, ccuu eexxcceeppŃŃiiaa pprriimmuulluuii șșii aa uullttiimmuulluuii,, nnuu ssuunntt ddiissttiinnccttee..
• Exemplu : În graful
ciclul C=[5, 3, 4, 1, 2, 4, 5] este ciclu neelement ar (prin 4 s-a trecut de dou ă ori).
Defini Ńie . FFiiee GG==((VV,, MM)) uunn ggrraaff nneeoorriieennttaatt.. DDoouuăă cciicclluurrii CC11 șșii CC22 ssuunntt eeggaallee,, ddaaccăă mmuucchhiiiillee lloorr iinndduucc
aacceellaașșii ggrraaff ppaarrŃŃiiaall aall ssuubbggrraaffuulluuii ggeenneerraatt ddee vvâârrffuurriillee ccee aappaarrŃŃiinn lluuii CC11,, rreessppeeccttiivv lluuii CC22..
• Exemplu : În graful
ciclul Cl=[1, 3, 2, 4, 1] este egal cu ciclul C2=[ 3, 2, 4, 1, 3].
Observa Ńie. Un ciclu se nume ște par , dac ă lungimea sa este un num ăr par și se nume ște impar, dacă
lungimea sa este un num ăr impar .
Graf conex
DDeeffiinniiŃŃiiee.. FFiiee GG==((VV,,MM)) uunn ggrraaff nneeoorriieennttaatt.. GGrraaffuull GG ssee nnuummeeșșttee ccoonneexx ddaaccăă ppeennttrruu oorriiccaarree ddoouuăă vvâârrffuurrii xx
șșii yy,, xx≠≠yy,, eexxiissttăă uunn llaannŃŃ îînn CC ddee llaa xx llaa yy..
• Exemplu de graf conex:
Graful este conex, deoarece oricare ar fi vârfurile x și y, x ≠≠y, exist ă un lan Ń în G care s ă le lege. 5
5
5 1
2 3 4
5
16 •Exemplu de graf care nu este conex:
Graful nu este conex, deoarece exist ă dou ă vârfuri, cum ar fi 1 si 4, pentru care nu exist ă nici un lan Ń în
graf care s ă le lege.
Component ă conex ă
DDeeffiinniiŃŃiiee.. FFiiee GG==((VV,, MM)) uunn ggrraaff nneeoorriieennttaatt.. SSee nnuummeeșșttee ccoommppoonneennttăă ccoonneexxăă,, uunn ggrraaff nneeoorriieennttaatt
GG11==((VV11,,MM11)) ccaarree vveerriiffiiccăă uurrmmăăttooaarreellee ccoonnddiiŃŃiiii::
– eessttee ssuubbggrraaff aall ggrraaffuulluuii GG;;
– eessttee ccoonneexx;;
– nnuu eexxiissttăă nniiccii uunn llaannŃŃ îînn GG ccaarree ssăă lleeggee uunn nnoodd ddiinn VV11 ccuu uunn nnoodd ddiinn VV–VV11..
•Exemplu : Fie graful G=(V, M) : V={ 1,2,3,4,5,6},M={[ 1,2], [1,3], [2,3],[4,5], [4,6]}
Pentru graful de mai sus, graful G1=(V1,M1) unde: V1={4,5,6} și M1={ [4,5], [4,6]} este component ă
conex ă, deoarece:
– este subgraf al grafului G;
– este conex:
– nu exist ă nici un lan Ń în G care și lege un nod din V 1, cu un nod din V-V 1 ={1,2 3},
La fel se poate spune și despre graful G2=(V2,M2) unde: V2={1,2,3} și M2={[1,2], [1,3], [2,3]}
În concluzie, graful, din figura de mai sus, este format din dou ă componente conexe.
Observa Ńie. Fie G=(V, M) un graf neorientat. Graful G este conex dac ă și numai dac ă este format dintr-
o singur ă component ă conex ă.
• Exemplu de graf conex (este format dintr-o singur ă component ă conex ă):
Observa Ńie . Fie G=(V, M) un graf neorientat. Pentru a verifica dac ă graful este format din una sau mai
multe componente conexe se procedeaz ă astfel:
– se parcurge graful, prin una din metodele de parc urgere;
– dac ă dup ă parcurgere mai exist ă în graf noduri nevizitate, atunci graful este form at din mai multe
componente conexe, altfel este format dintr-o singu r ă component ă conex ă, adic ă graful este conex.
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
int a[20][20];
int viz[20];
int i, n ,j, pl, m, x, y, ok;
void parc_adancime(int pl)
{int j;
viz[pl]=1;
for (i=1;j<=n;j++)
if ((a[pl][j]==1) && (viz[j]==0))
parc_adancime(j);}
void main(){
cout<<"n m "; cin>>n>>m;
for (i=1;i<=m;i++)
{cout<<"x y"; cin>>x>>y;
a[x][y]=1; a[y][x]=1;}
for (i=1;i<= n;i++) viz[i]=0;
cout<<"dati nodul de plecare :"; cin>>pl;
parc_adancime(pl); 1
2 3 4 5
1
2
3 4 5
6
1
2 3 4 5
17 ok=0; //se verifica daca mai sunt
for (i=1;i<=n;i++) //noduri nevizitate
if (viz[i]==0) ok=1;
if (ok) cout<<"graful este format din mai multe com ponente conexe";
else cout<<"graful este conex";
getche( ); }
11. Grafuri Hamiltoniene
DDeeffiinniiŃŃiiee.. FFiiee GG==((VV,, MM)) uunn ggrraaff nneeoorriieennttaatt.. SSee nnuummeeșșttee llaannŃŃ hhaammiillttoonniiaann,, îînn ggrraaffuull GG,, uunn llaannŃŃ eelleemmeennttaarr
ccaarree ccoonnŃŃiinnee ttooaattee vvâârrffuurriillee ggrraaffuulluuii GG..
• Exemplu de lan Ń hamiltonian:
Fie graful G=(V, M) unde: V={1,2,3,4}, M={[l,3], [1 ,4],[2,3],[2,4],}
Reprezentarea sa grafic ă este:
Lan Ńul L=1, 3, 2, 4 este, în graful G, lan Ń hamiltonian.
DDeeffiinniiŃŃiiee.. FFiiee GG==((VV,, MM)) uunn ggrraaff nneeoorriieennttaatt.. SSee nnuummeeșșttee cciicclluu hhaammiillttoonniiaann,, îînn ggrraaffuull GG,, uunn cciicclluu
eelleemmeennttaarr ccaarree ccoonnŃŃiinnee ttooaattee vvâârrffuurriillee ggrraaffuulluuii GG..
• Exemplu de ciclu hamiltonian:
Fie graful G=(V, M) unde: V={ 1,2,3,4} M={ [1,3], [ 1,4], [2,3],[2,4]}
Reprezentarea sa grafic ă este:
Ciclul C=1, 3, 2, 4, 1este, în graful G, ciclu hami ltonian.
DDeeffiinniiŃŃiiee.. FFiiee GG==((VV,, MM)) uunn ggrraaff nneeoorriieennttaatt.. GGrraaffuull GG eessttee hhaammiillttoonniiaann ddaaccăă ccoonnŃŃiinnee cceell ppuuŃŃiinn uunn cciicclluu
hhaammiillttoonniiaann..
•Exemplu de graf hamiltonian:
Graful G=(V, M) unde:V={ 1,2,3,4} M={[1,2], [1,3], [1,4], [2,31, [2,4]}
cu reprezentarea grafic ă:
este hamiltonian, deoarece con Ńine cel pu Ńin un ciclu hamiltonian; ciclul C= l, 3, 2, 4, 1 es te, în graful G,
ciclu hamiltonian.
Observa Ńie . Fie G=(V, M) un graf neorientat. Ca în graful G s ă existe un ciclu hamiltonian , trebuie ca el
să aib ă cel pu Ńin trei vârfuri .
Teorem ă. Graful complet K n este graf hamiltonian .
Demonstra Ńie :
Orice succesiune x i1 , x i2 , ,…, x in ; xi1 de n+ 1 noduri distincte (excep Ńie fac primul și ultimul) am alege,
poate fi privit ă ca un ciclu hamiltonian, deci graful K n este hamiltonian.
Teorem ă. Fie G= (V, M) un graf neorientat. Dac ă are n ≥3 noduri și gradul fiec ărui vârf x verific ă rela Ńia
d(x) ≥n/2, atunci G este hamiltonian .
Problema determin ări tuturor ciclurilor hamiltoniene dintr-un graf ne orientat.
Fie G=(V, M) un graf neorientat, cu n vârfuri. S ă se determine toate ciclurile hamiltoniene din graf ul G.
Rezolvare: Problema se rezolv ă folosind metoda Backtracking. Pentru rezolvare se vor folosi:
k : variabil ă întreag ă care reprezint ă la al câtelea nod s-a ajuns(al doilea, al treilea. ..)
x : vector cu componente întregi cu proprietatea: x k :reprezint ă al k-lea nod din ciclu. 3
3
3
18 Observa Ńie . Pentru a evita parcurgerea unui drum de 2 ori se va recurge la strategia de a atribui lui x,
valoarea l, adic ă toate ciclurile s ă plece de la primul nod: din acest motiv x k ∈{2…. n} pentru k ∈{2,… n}
În concluzie, a rezolva problema înseamn ă a determina vectorii:
x=(x 1,x 2,…,x n)
unde x 1=1 și xk ∈{2…. n} pentru k ∈{2,… n
Tabla va ar ăta astfel:
n
2 3 …… n-1 n
2 3 …… n-1 n
… … …… … …
2 3 …… n-1 n
2 3 …… n-1 n
1
2 n
Pentru reprezentarea grafului în program se va folo si matricea de adiacen Ńă , definit ă astfel:
ai,j =1, dac ă exist ă muchie între nodurile i și j;
ai,j =0, dac ă nu exist ă muchie între nodurile i și j.
Exemplu : Pentru graful de mai jos
matricea de adiacen Ńă se define ște astfel:
=
0011100111110001100111010
A
Concluzii:
1. Între nodurile k si i, exist ă muchie dac ă a k,i =1 ( și a i,k =1), deci între nodurile x k și x j exist ă muchie dac ă
a[x k][xi]=1 (si a[x i][xk]=1).
2. Nodul x k trebuie s ă fie diferit de nodul x i, pentru i=1…k-1.
3. Nodul x n trebuie s ă fie legat prin muchie de nodul x 1 adic ă a[x n][x1]=1
* Comentarii la procedura Valid:
Trebuie verificat c ă:
1. exist ă muchie între nodurile x k-1 și x k, adic ă trebuie verificat c ă a[x k-1][xk]=1;
2. nodul x k este diferit de toate nodurile prin care s-a trecu t, adic ă:
xk≠xi pentru i=1…k-1.
3. dac ă s-a ajuns la al n-lea nod din ciclu, trebuie s ă existe muchie între acesta primul nod, adic ă: dac ă
k=n atunci a[ x k][x 1]=1
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
typedef int sir[20];
sir x;
int i, k, n;
int as, ev;
int a[20][20];
void succ(sir x, int k, int &as)
{if (x[k]<n)
{as=1;
x[k]=x[k]+1;} k
xk
19 else as=0;}
void valid( sir x, int k, int &ev)
{ev=l ;
if (a[x[k-1]][x[k]]==0) dac ă nu exist ă drum între x k-1 și x k
ev=0;
else
{for (i=1;i=k-l;i++)
if (x[i]==x[k]) ev=0;
if ((k==n) && (a[x[n]][x[l]]==0)) ev=0;}
}
void afis(sir x, int k)
{int i;
for (i=l;i<=k;i++)
cout<<x[i]<<” ”;
cout<<x[1]<<" "; cout<<endl;}
void main() {
cout<<"n= "; cin>>n;
for (i=1;i<=n-l;i++)
for (j=i+l;j<=n;j++)
{cin>>a[i][j];
a[j][i]=a[i][j]; }
x[1]=1;
k=2;
x[k]=1; privi Ńi tabla
while (k>1){
do{succ(x,k,as);
if (as) valid(x,k,ev);
}while (as && !ev);
if (as)
if (k==n) afis(x,k);
else
{k=k+ 1;
x[k]=1;}
else k=k-l;
}
getch();}
12. Grafuri Euleriene
Defini Ńie . FFiiee GG==((VV,, MM)) uunn ggrraaff nneeoorriieennttaatt.. SSee nnuummeeșșttee llaannŃŃ eeuulleerriiaann,, iinn ggrraaffuull GG,, uunn llaannŃŃ ccaarree ccoonnŃŃiinnee
ttooaattee mmuucchhiiiillee ggrraaffuulluuii GG,, ffiieeccaarree mmuucchhiiee aappăărrâânndd îînn llaannŃŃ oo ssiinngguurrăă ddaattăă..
• Exemplu de lan Ń eulerian:
Fie graful G=(V, M) unde: V={ 1,2,3,4} M={[1,3],[2, 3], [2,4]}
Reprezentarea sa grafic ă este:
Lan Ńul L=[1, 3, 2, 4] este, in graful G, lan Ń eulerian.
Defini Ńie . FFiiee GG== ((VV,,MM)) uunn ggrraaff nneeoorriieennttaatt.. SSee nnuummeeșșttee cciicclluu eeuulleerriiaann,, îînn ggrraaffuull GG,, uunn cciicclluu ccaarree ccoonnŃŃiinnee
ttooaattee mmuucchhiiiillee ggrraaffuulluuii GG,, ffiieeccaarree mmuucchhiiee aappăărrâânndd îînn cciicclluu oo ssiinngguurrăă ddaattăă..
• Exemplu de ciclu eulerian:
Fie graful G=(V, M) unde: V={1,2,3,4} M={ [ 1,3], [ 1,4], [2,3], [2,4]}
Reprezentarea sa grafic ă este: 2 3
20
Ciclul C=[ l, 3, 2, 4, l ] este, în graful G, ciclu eulerian.
Teorem ă. Fie G=(V, M) un graf neorientat. Graful G, f ără vârfuri izolate, este eulerian dac ă și numai
daca este conex și gradele tuturor vârfurilor sale sunt numere pare.
•Exemplul l.
Fie graful G=(V, M) unde: V={1,2,3,4}
M={ [ 1,3], [ 1,4], [2,3], [2,4]}
Reprezentarea sa grafic ă este:
este graf eulerian, deoarece verific ă condi Ńiile teoremei anterioare, adic ă:
– nu are vârfuri izolate;
– este conex;
– gradele tuturor vârfurilor sunt numere pare.
DDeeffiinniiŃŃiiee.. Un Un ggrraaff ccaarree ccoonnŃŃiinnee cceell ppuuŃŃiinn uunn cciicclluu eeuulleerriiaann ssee nnuummeeșșttee ggrraaff eeuulleerriiaann..
Algoritmul de determinare a unui ciclu eulerian înt r-un graf neorientat.
Pas 1. Se detemin ă ciclul C=(c 1 ,c2 ,…, c k, c 1), unde c 1=1.
Pas 2. Se caut ă, printre nodurile ciclului determinat la pasul ant erior, un nod pentru care mai exist ă
muchii incidente cu el neluate înc ă. Fie acesta c j construim ciclul C n= (cn 1 ,cn 2 ,…, cn k, cn 1), unde cn i=c j
cn- ciclu nou
Pas 3.Ciclul determinat la pasnl 2 se "concateneaz ă" la ciclul C, ob Ńinându-se astfel ciclul C=(c 1 ,c2 ,…, c j,
cj+1 …,c j+kn-1 ,…, c k+kn , c 1), figurat mai jos:
Pas4. Dac ă nu sau ales toate muchiile, se reia pasul 2.
• Exerci Ńiu: Pentru graful din figura de mai jos, s ă se determine un ciclu eulerian.
Rezolvare:
Pas1. Se determin ă un ciclu plecând de la nodul 1; fe acesta: C-('l, 3, 4 , 2, 1) (privi Ńi figura). 2 3
2 3
c2
c1
ck
1
21
Pas2. Se caut ă, printre nodurile ciclului determinat la pasul ant erior, un nod pentru care mai exist ă muchii
incidente cu el neluate înc ă; fie acesta nodul 4 -1. Construim ciclul Cn, plecâ nd de la acest nod: Cn= (4, 5,
6,7,8,4 )
Pas3. Ciclul determinat la pasul 2 se "concateneaz ă la ciclul C, ob Ńinându-se astfel ciclul: C=(1, 3, 4, 5, 6,
7,8, 4, 2, 1 )
Pas4. Deoarece mai sunt muchii neluate înc ă, se reia pasul 2.
Pas2. Se caut ă, printre nodurile ciclului determinat pân ă în prezent, un nod pentru care mai exist ă muchii
incidente cu el neluate înc ă; acesta este nodul 4. Construim ciclul Cn, plecând de la acest nod: Cn=(4, 9,
10,4).
Pas 3. Ciclul determinat la pasul 2 se "concateneaz ă la ciclul C, ob Ńinîndu-se astfel ciclul: C=(1, 3, 4, 9,
10, 4, 5, 6, 7, 8, 4, 2, 1).
programul de determinare a unui ciclu eulerian într -un graf neorientat.
#include <iostream.h>
#include<conio.h>
#include<stdio.h>
typedef int mut[20][20];
typedef int sir[20];
int a[20][20];
sir viz, c, cn, gr;
int i, k, j, n, kn, poz, m, eulerian, x, y;
int grad(int i)
{ int s, j;
s=0;
for (j=1;j<=n;j++) s=s+a[i][j];
return s;}
int varf_izolate()
{ int i, ok;
ok=0;
for (i=1; i<=n; i++)
if (grad(i)==0) ok=1;
return ok;}
int grade_pare()
{ int i, ok;
22 ok=1;
for (i=1;i<=n;i++)
if (grad(i)%2!=0) ok=0;
return ok;}
void adancime(int i )
{ int j;
viz[i]=1;
for (j=1;j<=n;j++)
if ((viz[j]==0) && (a[i][j]==1)) adancime(j);}
int conex()
{int i, ok;
for (i=1;i<=n;i++) viz[i]=0;
adancime(1);
ok=1;
for (i=1;i<=n;i++)
if (viz[i]==0) ok= 0;
return ok;}
void main( )
{ clrscr( );
cout<<"m="; cin>>m;
cout<<"n="; cin>>n;
for (i=1;i<=m;i++)
{ cout<<"x y"; cin>>x>>y;
a[x][y]=a[y][x]=1;}
for (i=1;i<=n;i++) gr[i]=grad(i);
eulerian=(!varf_izolate()) && grade_pare()&&conex() ;
if (!eulerian) cout<<"graful nu este eulerian";
else
{c[1]=1;
k=1;
do{
for (j=1;j<=n;j++)
if (a[c[k]][j]==1)
{k=k+1;
c[k]=j;
gr[c[k] ]=gr[c[k]]-1;
gr[c[k-1]]=gr[c[k-1]]-1;
a[c[k-1]][c[k]]=0;
a[c[k]][c[k-1]]=0;
break;}
}while (c[k]!=1);
while (k-1<m){
for (j=1;j<=k-1;j++)
if (gr[c[j]]>0) { cn[1]=c[j];
poz= j;
break;}
kn=1;
do{
for (j=1;j<=n;j++)
if (a[cn[kn]][j]==1)
{ kn=kn+1;
cn[kn] =j;
gr[cn[kn]]=gr[cn[kn]]-1 ;
gr[cn[kn-1]]=gr[cn[kn-1]]-1;
a[cn[kn-1]][cn[kn]]=0;
23 a[cn[kn]][cn[kn-1]]=0;
break;}
}while (cn[kn]!=cn[1]);
for (j=k;j>=poz;j–) c[j+kn-1]=c[j] ;
for (j=1 ;j<=kn-1;j++) c[poz+j]=cn[j+1];
k=k+kn-1;
}
}
for (i=1;i<=k;i++)
cout<<c[i]<<" ";
getche(); }
Probleme
1. No Ńiunea de graf neorientat
1. Să se precizeze dac ă re Ńelei de circula Ńie din ora șul dumneavoastr ă i se poate asocia un graf neorientat;
în caz afirmativ, s ă se defineasc ă graful corespunz ător.
2. Având la dispozi Ńie un grup de n persoane, n ∈ N* , s ă se precizeze dac ă i se poate asocia un graf
neorientat; în caz afirmativ, s ă se defineasc ă graful corespunz ător.
3. Având la dispozi Ńie o hart ă cu n Ńă rii, n ∈ N*. s ă se precizeze dac ă i se poate asocia un graf neorientat;
în caz afirmativ, s ă se defineasc ă graful corespunz ător.
4. Având la dispozi Ńie toate stelele, s ă se precizeze dac ă li se poate asocia un graf neorientat; justifica Ńi
răspunsul.
5. Pentru graful reprezentat în figura de mai jos
a) preciza Ńi mul Ńimea nodurilor;
b) preciza Ńi mul Ńimea muchiilor;
c) da Ńi exemple de noduri adiacente;
d) pentru fiecare muchie preciza Ńi extremit ăŃ ile
sale;
e) da Ńi exemple de muchii incidente.
2. No Ńiunea de graf par Ńial
1. Să se determine dou ă grafuri par Ńiale ale grafului de mai jos:
2. Să se determine toate grafurile par Ńiale ale grafului de mai jos:
3. Fie G un graf neorientat, cu n vârfuri și m muchii. S ă se determine num ărul grafurilor par Ńiale ale
grafului G.
4. Se citesc din 2 fi șiere text informa Ńii despre 2 grafuri neorinetate: pe prima linie num ărul de noduri și
de pe urm ătoarele rânduri, matricea de adiacen Ńă . S ă se verifice daca graful re Ńinut în cel de-al doilea
fi șier este graf par Ńial al grafului re Ńinut în primul fi șier
5. Se citesc dintr-un fi șier informa Ńiile despre graful neorintat: de pe prima linie num ărul de noduri n și
eticheta unui nod x, și apoi, de pe urm ătoarele rânduri, matrice de adiacen Ńă a grafului. S ă se afi șeze într-
un alt fi șier text informa Ńiile despre graful pa Ńial ob Ńinut prin eliminarea tuturor muchiilor care au
extremit ăŃ i un nod cu gradul par și nodul x.
3. No Ńiunea de subgraf
1. Să se determine dou ă subgrafuri ale grafului de mai jos:
1
5
5 1
1
1
24
2. Să se determine toate subgrafurile grafului de mai jo s:
3. Fie G un graf neorientat, cu n vârfuri și m muchii. S ă se determine num ărul subgrafurilor grafului G.
4. Se citesc din 2 fi șiere informa Ńiile despre 2 grafuri neorintate: de pe prima linie num ărul de noduri n și
apoi, de pe urm ătoarele rânduri, matricea de adiacen Ńă a grafului. În fisierul al doilea pe ultimul rând dup ă
matricea de adiacen Ńă , este memorat un șir ce reprezint ă etichetele nodurilor. S ă se verifice dac ă graful 2
este subgraf al grafului 1.
4. Gradul unui vârf
l. Fiind dat graful de mai jos, s ă se determine pentru fiecare vârf în parte gradul s ău; s ă se precizeze
vârfurile terminale și vârfurile izolate.
2. Să se demonstreze c ă orice graf G, cu n ≥2 noduri, con Ńine cel pu Ńin dou ă vârfuri care au acela și grad.
3. Să se verifice dac ă exist ă grafuri cu 5 noduri pentru care:
a) șirul gradelor vârfurilor sale este: 1,2,3,0,5
b) șirul gradelor vârfurilor sale est3: 1,2,3,4,1
4.Fie graful G, cu n vârfuri și m muchii, astfel încât s ă fie îndeplinit ă rela Ńia:
()( )
22 1− −>n nm
Să se demonstreze c ă G nu are vârfuri izolate.
5. Fie G un graf neorientat, cu n vârfuri și m muchii, reprezentat prin matricea de adiacen Ńă . S ă se
realizeze programe, în C/C++, care:
a) afi șeaz ă gradele tuturor vârfurilor;
b) afi șeaz ă vârfurile de grad par;
c) afi șeaz ă vârfurile izolate;
d) afi șeaz ă vârfurile terminale;
e) verific ă dac ă graful are vârfuri izolate;
t) verific ă dac ă graful are vârfuri terminale;
g) verific ă dac ă graful are vârfuri interioare (nu sunt nici izolat e nici terminale);
h) verific ă dac ă graful are toate vârfurile izolate;
i) verific ă dac ă graful are toate vârfurile interioare (nu sunt nic i izolate nici terminale):
j) afi șeaz ă gradul unui vârf dat:
k) afi șeaz ă vecinii unui nod dat, vf;
l) verific ă dac ă un vârf dat este terminal, izolat sau interior;
m) afi șeaz ă gradul cel mai mare și toate vârfurile care au acest grad
n) afi șeaz ă frecventa vârfurilor:
izolate : n 1
terminale : n2
interioare : n3
o) fiind dat șirul g 1, …,g n, s ă se verifice dac ă poate reprezenta șirul gradelor vârfurilor în aceast ă ordine;
p) fiind dat șirul g 1 …,g n, s ă se verifice dac ă poate reprezenta șirul gradelor vârfurilor (nu neap ărat în
aceast ă ordine).
5
1
5 1
6
25 5. Graf complet
1. Fiind date grafurile de mai jos, s ă se precizeze care dintre ele este complet și s ă se justifice r ăspunsul.
a
1
b
2. Pentru grafurile K 3 și K 5 :
a) să se precizeze gradul fiec ărui vârf;
b) să se precizeze num ărul de muchii;
c) să se realizeze o reprezentare grafic ă.
3. Fie graful G, cu n vârfuri, dat prin matricea de adiacen Ńă . S ă se realizeze un subprogram care
precizeaz ă dac ă graful este complet, astfel:
a) făcând o analiz ă asupra nodurilor;
b) făcând o analiz ă asupra muchiilor.
4. Fie graful G, cu n vârfuri, dat prin matricea de adiacen Ńă . S ă se realizeze subprograme care precizeaz ă:
a) câte muchii mai trebuie ad ăugate pentru a deveni complet;
b) între ce noduri mai trebuie ad ăugate muchii astfel încât graful s ă devin ă complet.
6. Graf bipartit
l. Fiind date grafurile de mai jos, s ă se precizeze care dintre ele este bipartit și s ă se justifice r ăspunsul.
a)
b)
2. Ce muchie trebuie eliminat ă din graful prezentat mai jos astfel încât s ă devin ă bipartit?
3. Fie graful bipartit G, f ără vârfuri izolate, dat prin matricea de adiacen Ńă . S ă se realizeze un program
care determin ă mulŃimile V 1 și V2 despre care se vorbe ște în defini Ńie.
4. Fie graful G cu n vârfuri, dat prin matricea de adiacen Ńă . S ă se realizeze un program care precizeaz ă
dac ă graful este bipartit.
5. Sa se genereze toate grafurile neorientate bipar tite complete cu n noduri.
7. Graf bipartit complet
1. Fiind date grafurile de mai jos s ă se precizeze care dintre ele este bipartit complet și s ă se justifice
răspunsul.
a)
b)
2. Ce muchie trebuie ad ăugat ă în graful prezentat mai jos astfel încât s ă devin ă bipartit complet: 3 5
3 5 3
1
5
3 5 3
26
3. Fie graful G, cu n vârfuri reprezentate {1… n} . Presupunând c ă graful este bipartit complet, astfel
încât { }p Vsi npcu p V ,…, 1 ,1 1 = < = să se construiasc ă matricea de adiacen Ńă.
4. Fie graful G, cu n vârfuri reprezentate {1… n} . Presupunând c ă graful este bipartit complet și că V 1
este format ă din nodurile reprezentate prin numere pare, s ă se construiasc ă matricea de adiacen Ńă.
5. Să se determine num ărul total de grafuri bipartit complete cu n vârfuri date.
8. Reprezentarea grafurilor
l. Fiind date grafurile de mai jos
a) l
b)
să se precizeze pentru fiecare in parte:
l. matricea de adiacen Ńă
2. listele de adiacen Ńă
3. șirul muchiilor
2. Fiind dat ă o matrice p ătratic ă de ordin n, s ă se precizeze dac ă poate fi considerat ă matricea de
adiacent ă a unui graf neorientat cu n vârfuri.
3. Să se determine num ărul total de grafuri neorientate care au vârfurile { 1,…,n}.
4. Să se realizeze un program care genereaz ă matricele de adiacen Ńă ale tuturor grafurilor neorientate cu
vârfurile { 1,…,n}.
5. Să se realizeze un program în C++ care, fiind date matricele de adiace n Ńă A1 și A2 de dimensiune n,
verific ă dac ă matricea A2 poate reprezenta un graf partial al grafului reprezentat de matricea A1 .
6. Să se realizeze un program în C++ care s ă verifice dac ă un graf este pentru alt graf subgraf.
7. S ă se realizeze un program care genereaz ă toate grafurile bipartite complet cu n vârfuri.
8. Fie G un graf neorientat, cu n vârfuri și cu muchiile m 1, m 2 …, m p. S ă se realizeze un program, în C++,
care determin ă toate grafurile par Ńiale ale lui G.
9. Fie G un graf neorientat, cu vârfurile 1, 2, …, n, dat pri n matricea de adiacent ă. S ă se realizeze un
program în C++ care determin ă toate subgrafurile lui G.
10. Fiind dat un grup de persoane, reprezentate prin numere de la 1 la n, si precizându-se rela Ńiile de
simpatie astfel: pentru fiecare persoan ă i, se citesc numerele de ordine ale persoanelor pe care aceasta le
simpatizeaz ă (numerele se dau pe aceea și linie separate prin spa Ńii), s ă se precizeze dac ă în grupul de
persoane amintit, toate simpatiile sunt reciproce.
11. S ă se realizeze un program care permite desenarea unui graf neorientat cu n vârfuri și m muchii,
cunoscându-se lista muchiilor.
9. Parcurgerea grafurilor
1.Fiind date grafurile de mai jos:
a) l
b)
5
2 3
27 să se precizeze, pentru fiecare în parte, lista nodur ilor ob Ńinut ă în urma parcurgerii:
– în l ăŃ ime;
– în adâncime.
2. Fie G un graf, cu n noduri și m muchii. Precizându-se un nod, de exemplu nodul l, sa se realizeze un
program care afi șeaz ă toate nodurile accesibile din acest nod.
10. Conexitate
1.Fiind date grafurile de mai jos:
a) l
b)
sa se precizeze pentru fiecare în parte un lan Ń, un lan Ń de lungime 4, un lanŃ elementar, un ciclu, un ciclu
elementar, dou ă cicluri egale.
2. Fie G un graf neorientat, cu n noduri și m muchii. Precizându-se doua noduri np( nodul de plecare) și
ns (nodul de sosire), s ă se determine toate lan Ńurile elementare care le admit ca extremit ăŃi.
3. Fiind dat un graf neorientat, cu n noduri și m muchii s ă se determine toate lan Ńurile elementare care au
cea mai mare lungime.
4. S ă se realizeze un program care, fiind dat un graf neorientat, verific ă dac ă con Ńine un ciclu de lungime
5. Să se realizeze un program care, fiind dat un graf neorientat, afi șeaz ă toate ciclurile elementare de
lungime p, plecând de la nodul 1 .
6. Să se realizeze un program care, fiind dat un graf neorientat , determin ă câte componente conexe are.
7. Să se realizeze un program care, fiind dat un graf neorientat , determin ă toate componentele conexe ale
sale.
8. S ă se realizeze un program care, fiind dat un graf neorientat, determin ă toate perechile de vârfuri între
care exist ă cel pu Ńin un lan Ń.
9. Speologii au cercetat n culoare subterane, pentr u a stabili dac ă apar Ńin aceleia și pe șteri. Prin tehnici
specifice de curen Ńi de aer și de colorare a cursurilor de ap ă, a fost demonstrat ă existenta unor canale de
leg ătur ă între mai multe culoare. Precizându-se perechile d e culoare între care au fost stabilite leg ături, s ă
se afle dac ă sistemul de culoare apar Ńine unei singure pe șteri.
10. Într-un grup de n persoane, se precizeaz ă perechi de persoane care se consider ă prietene. Folosind
principiul c ă "prietenul prietenului meu mi-este prieten", s ă se determine grupurile cu un num ăr maxim de
persoane între care se pot stabili rela Ńii de prietenie, directe sau indirecte.
11. Cicluri Hamiltoniene
l. Pentru graful de mai jos; s ă se dea exemplu de un lan Ń si de un ciclu hamiltonian.
l
2. Să se realizeze un program care pentru un graf dat verific ă dac ă satisface condi Ńiile teoremei prezentate
in sec Ńiunea 11.
3. Să se arate c ă num ărul ciclurilor hamiltoniene ale grafului K n cu n ≥3, este ()
2! 1−n
4. S ă se arate c ă num ărul ciclurilor elementare ale grafului K n cu n ≥3, este()( )∑
=+− −n
k kkn nn
31 … 1
21
5. Să se realizeze un program care pentru un graf dat verific ă dac ă este hamiltonian.
28 6. La curtea regelui Artur s-au adunat 2n cavaleri si fiecare dintre ei are printre cei prezen Ńi cel mult n-1
du șmani. Ar ăta Ńi c ă Merlin, consilierul lui Artur, poate s ă-i a șeze pe cavaleri, la o mas ă rotund ă, în a șa fel
încât nici unul dintre ei s ă nu stea al ături de vreun du șman de-al s ău.
7. Se consider ă n persoane. Fiecare are printre cei prezen Ńi cel mult n/2 du șmani. S ă se determine toate
posibilit ăŃ ile de a șezare a acestora la o mas ă rotund ă astfel încât nici unul dintre ei s ă nu stea lâng ă un
du șman al s ău.
8. La un cenaclu literar sunt invita Ńi un num ăr de n elevi, identifica Ńii cu l…n, de la L licee, identificate
1…L. S ă se determine toate modalit ăŃile de a șezare a acestora la o mas ă rotund ă astfel încât s ă nu fie doi
elevi de la acela și liceu vecini.
1. No Ńiunea de graf neorientat
Problema 1
Răspunsul este afirmativ (Da). Definim graful neorien tat asociat re Ńelei astfel:
– mul Ńimea nodurilor este mul Ńimea intersec Ńiilor dintre str ăzi și a capetelor de str ăzi (la ie șirea din ora ș);
este mul Ńime finit ă și nevid ă
– mul Ńimea muchiilor este mul Ńimea buc ăŃilor de strad ă dintre dou ă intersec Ńii sau dintre o intersec Ńie și un
cap ăt de strad ă (ia ie șirea din ora ș).
Problema 2
Răspunsul este afirmativ (Da). Definim graful neorien tat asociat astfel:
– mul Ńimea nodurilor este mul Ńimea persoanelor (este mul Ńime finit ă și nevid ă);
– muchia dintre nodurile x și y se define ște ca fiind reprezentarea ideii "persoanele x și y se cunosc" (pot
exista nenum ărate defini Ńii; da Ńi și altele).
Problema 3
Răspunsul este afirmativ (Da). Definim graful neorien tat asociat astfel:
– mul Ńimea nodurilor este mul Ńimea Ńărilor (este mul Ńime finit ă și nevid ă):
– muchia dintre nodurile x și y se define ște ca fiind reprezentarea ideii "din Ńara x se poate ajunge în Ńara
y, cu avionul" (pot exista nenum ărate defini Ńii).
Problema 4
Dac ă admitem că exist ă o infinitate de stele: R ăspunsul este negativ (Nu), deoarece mul Ńimea nodurilor
trebuie s ă fie, conform defini Ńiei, finit ă ( și nevid ă).
Dac ă admitem ca stelele sunt într-un num ăr finit: R ăspunsul este pozitiv (Da) și putem defini graful
neorientat asociat lor astfel:
– mul Ńimea nodurilor este mul Ńimea stelelor (este mul Ńime finit ă și nevid ă);
– muchia între nodurile x și y se define ște ca fiind reprezentarea ideii "de pe steaua x se poate vedea
steaua y" (pot exista nenum ărate defini Ńii).
Problema 5
a) V={ l, 2, 3,4 ,5};
b) M={[1,2], [1,4], [1,5], [2,4], [3,5]};
c) Nodul 1 este adiacent cu nodul4; nodul 3 este ad iacent cu nodul 5; …
d) [1,2] : 1 și 2; [1,4] : 1 și 4; [1,5] : 1 și 5; [2,4] : 2 și 4; [3,5] : 3 si 5; e) [1,2] și [1,4]; [2,4] și [l,4]; …
2. No Ńiunea de graf par Ńial
Problema 1
Cele dou ă grafuri par Ńiale vor fi reprezentate prin desen în figurile de mai jos: Primul graf par Ńial (se
elimin ă muchiile [1,5], [2,4])
V1={ l, 2, 3, 4. 5}
M 1 ={ [ 1,5], [1,4] ,[3,5]}
Al doilea graf par Ńial (se elimin ă muchiile [1,2], [1,4], [3,5];)
V 1={ l, 2, 3, 4. 5}
M 1 ={ [ 1,5], [2,4] }
Problema 2
Grafurile par Ńiale, care se ob Ńin plecând de la graful din enun Ń, sunt în num ăr de: 1
2 4
3 5
1
2 3 4
5
29 1 dac ă se elimin ă 0 muchii 0
3C
3 dac ă se elimin ă o muchiile1
3C
3 dac ă se elimin ă dou ă muchii 2
3C
1 dac ă se elimin ă toate muchiile 3
3C
deci, în total, 1+3+3+1=8 grafuri par Ńiale.
Problema 3
Având in vedere c ă: "un graf par Ńial al grafului num ăr oarecare de muchii", putem scrie:
Num ărul total al grafurilor par Ńiale ale grafului G, este suma dintre num ărul grafurilor par Ńiale care se
ob Ńin:
prin eliminarea unui num ăr de 0 muchii: 0
mC
prin eliminarea unui num ăr de 1 muchii: 1
mC
prin eliminarea unui num ăr de 2 muchii: 2
mC
…………………………………………… ……
prin eliminarea unui num ăr de m-1 muchii: 1−m
mC
prin eliminarea unui num ăr de m muchii: m
mC
prin adunare se ob Ńine:0
mC+1
mC+2
mC+…+ 1−m
mC +m
mC=2 m
Observa Ńie. Suma de mai sus se calculeaz ă astfel:
În rela Ńia 0
mC+1
mCx1+2
mCx2+…+ 1−m
mC xm-1+m
mCxm=(1+x) m se înlocuie ște x cu valoarea 1.
Problema 4
Se citesc din 2 fi șiere text informa Ńii despre 2 grafuri neorinetate: pe prima linie num ărul de noduri și de
pe urm ătoarele rânduri, matricea de adiacen Ńă . S ă se verifice daca graful re Ńinut în cel de-al doilea fi șier
este graf par Ńial al grafului re Ńinut în primul fi șier.
Rezolvare:
Se verific ă dac ă cele 2 grafuri au acela și num ăr de noduri și dac ă graful G2 nu con Ńine muchii care nu
exist ă în graful G1. Matricile de adicen Ńă ale celor 2 grafuri au dimensiunea n, respectiv m. Func Ńia
grafp() verific ă dac ă G2 este graf par Ńial al grafului G1 .
#include <conio.h>
#include <iostream.h>
#include <fstream.h>
int a1[20][20],a2[20][20],i,j,n,m;
ifstream f1("gp1.txt");
ifstream f2("gp2.txt");
int grafp()
{if(m!=n) return 0;
else for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a2[i][j]==1 &&a1[i][j]==0)
return 0;
return 1;}
void main()
{
clrscr();
f1>>n;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
f1>>a1[i][j]; f1.close();
f2>>m;
for (i=1;i<=m;i++)
for (j=1;j<=m;j++) f2>>a2[i][j]; f2.close();
if(grafp()) cout<<"este graf partial";
else cout<<"nu este graf partial";
getche();}
gp1.txt
4
0 1 0 1
1 0 1 0
0 1 0 0
30 1 0 0 0
gp2.txt
0 1 0 1 1 0 0 0
0 0 0 0
1 0 0 0
Problema 5.
Se citesc dintr-un fi șier informa Ńiile despre graful neorintat: de pe prima linie num ărul de noduri n și
eticheta unui nod x, și apoi, de pe urm ătoarele rânduri, matrice de adiacen Ńă a grafului. S ă se afi șeze într-
un alt fi șier text informa Ńiile despre graful pa Ńial ob Ńinut prin eliminarea tuturor muchiilor care au
extremit ăŃ i un nod cu gradul par și nodul x.
Rezolvare:
În vectorul v se re Ńin nodurile de grad par.
#include <conio.h>
#include <iostream.h>
#include <fstream.h>
int a[20][20],v[20],i,j,n,m,x;
ifstream f1("gp3.txt");
ofstream f2("gp4.txt");
int grad(int i)
{int j,g=0;
for(j=1;j<=n;j++) g=g+a[i][j];
return g;}
void graf_partial()
{int i,k=0;
for(i=1;i<=n;i++)
if(grad(i)%2==0) {k++; v[k]=i;}
for(i=1;i<=k;i++)
if(a[v[i]][x]==1) {a[v[i]][x]=0; a[x][v[i]]=0;}}
void scrie()
{int i,j;
f2<<n<<" "<<endl;
for (i=1;i<=n;i++)
for (j=1;j<i;j++)
if(a[i][j]==1) f2<<i<<" "<<j<<endl;
f2.close();}
void main()
{
f1>>n>>x;
while(f1>>i>>j)
a[i][j]=a[j][i]=1;
f1.close();
graf_partial();
scrie();}
gp3.txt
7 6
1 2
1 3
1 4
2 3
2 5
3 5
3 6
5 6
6 7
gp4.txt
7
2 1
3 1
3 2
4 1
5 2
5 3
6 5
7 6
3. No Ńiunea de subgraf
Problema 1
Cele dou ă subgrafuri vor fi reprezentate prin desen în figur ile de mai jos:
Primul subgraf (se elimin ă nodul 1 (odat ă cu el și muchiile incidente [1,2], [1,4], [1,5]))
4
3 5
Al doilea subgraf (se elimin ă nodul 4 (odat ă cu el și muchiile incidente [l,4], [2,4]))
31 1
Problema 2
Subgrafurile care se ob Ńin plecând de la graful din enun Ń sunt în num ăr de:
1 dac ă se elimin ă 0 noduri 0
3C
3 dac ă se elimin ă 1 nod 1
3C
3 dac ă se elimin ă dou ă noduri 2
3C
deci, în total 1+3+3=7 subgrafuri.
Aten Ńie! Toate nodurile nu se pot elimina pentru c ă s-ar ob Ńine un graf cu mul Ńimea vârfurilor vid ă (acest
lucru nu este permis de defini Ńie).
Problema 3
Având în vedere c ă: un subgraf al grafului G se ob Ńine prin eliminarea unui num ăr oarecare de noduri
(diferit de num ărul total de noduri ale grafului), putem scrie:
Num ărul total al subgrafurilor grafului G este suma din tre num ărul subgrafurilor care se ob Ńin:
prin eliminarea unui num ăr de 0 noduri: 0
nC
prin eliminarea unui num ăr de 1 noduri: 1
nC
prin eliminarea unui num ăr de 2 noduri: 2
nC
…………………………………………… …..
prin eliminarea unui num ăr de n-1 noduri: 1−n
nC
prin adunare se ob Ńine: 0
nC+1
nC+2
nC+…+ 1−n
nC+=2 n -1
Problema 4
Se citesc din 2 fi șiere informa Ńiile despre 2 grafuri neorintate: de pe prima linie num ărul de noduri n și
apoi, de pe urm ătoarele rânduri, matrice de adiacen Ńă a grafului. In fisierul al doilea pe ultimul rând dup ă
matricea de adiacen Ńă , este memorat un sir ce reprezint ă etichetele acestor noduri.S ă se verifice dac ă
graful 2 este subgraf al grafului 1.
#include<iostream.h>
#include<conio.h>
#include<fstream.h>
int n,m,i,j, a1[10][10],a2[10][10],v[10];
ifstream f1("sg1.txt");
ifstream f2("sg2.txt");
int subgraf()
{if(m>n) return 0;
else
{for (i=1;i<=m;i++) if(v[i]>n) return 0;
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
if(a2[i][j]!=a1[v[i]][v[j]]) return 0;}
return 1;}
void main()
{f1>>n;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) f1>>a1[i][j];
f1.close();
f2>>m;
for (i=1;i<=m;i++)
for (j=1;j<=m;j++) f2>>a2[i][j]; for (i=1;i<=m;i++) f2>>v[i];
f2.close();
if(subgraf()) cout<<"este subgraf";
else cout<<"nu este subgraf";
getch();}
sg1.txt
4
0 1 1 1
1 0 1 0
32 1 1 0 1
1 0 1 0
sg2.txt
3 0 1 1
1 0 1
1 1 0
1 2 3
4. Gradul unui vârf
Problema 1
d(1)=3; d(3)=1; d(5)=2; 3 este vârf terminal;
d(2)=2; d(4)=2; d(6)=0; 6 este vârf izolat;
Problema 2
Fie V={x 1, x 2, …. x n}. Presupunem că graful nu con Ńine dou ă vârfuri care s ă aib ă acela și grad, deci
d(x i)#d(x j) pentru i#j și d(x i)∈{0,1,…,n-1} pentru i=1…n. În concluzie, șirul gradelor vârfurilor coincide
cu {0,1,…,n-1} f ăcând eventual abstrac Ńie de ordine (presupunem de exemplu : d(x 1)=0, d(x 2)=1, …,
d(x n)=n-1). Deci, a șa cum se vede și în exemplul prezentat între paranteze, exist ă un vârf care are gradul
0, adic ă nu este legat de nici un vârf, și un vârf care are gradul n- 1, adic ă este legat de toate celelalte, deci
și de cel de gradul 0. Contradic Ńie, deoarece cel de gradul 0 nu este legat de nici un vârf.
În concluzie, presupunerea f ăcut ă la începutul rezolv ări este fals ă.
Problema 3
a) Categoric nu, deoarece dac ă ar exista un astfel de graf ar con Ńine un vârf care ar avea gradul 5 (adic ă ar
fi legat de înc ă 5 vârfuri). Acest lucru nu se poate întâmpla deoar ece f ără el în graf mai sunt decât 4
vârfuri.
b) Dac ă un astfel de graf ar exista, l-am putea reprezenta ast fel:
3
Nodul 3 a fost legat de nodul 5 (dar putea fi legat și de nodul 1); acest lucru nu este posibil deoarece astfel
acesta ar c ăpăta gradul 2 și el practic îl are l.
Problema 4
Presupunem c ă graful are un vârf izolat și toate celelalte noduri genereaz ă un subgraf complet (oricare
dou ă dintre ele sunt legate printr-o muchie), adic ă graful ar avea ()( )
22 1− −n nmuchii, oricum nu mai
multe decât ()( )
22 1− −n nașa cum se spune în enun Ń. Cum situa Ńia aleas ă este cea mai convenabil ă în acest
sens, înseamn ă c ă un astfel de graf nu poate exista.
Problema 5
Observa Ńie. A determina gradul vârfului i, înseamn ă a determina num ărul elementelor care au valoarea 1
și se g ăsesc pe linia i în matricea de adiacen Ńă .
Mai jos, este prezentat ă muchia care returneaz ă gradul vârfului i (Func Ńia const ă în calcularea sumei
elementelor de pe linia i din matricea de adiacen Ńă ).
Func Ńia care returneaz ă gradul nodului i
int grad( int i)
{int s, j;
s=0;
for (j=1;j<=n;j++)
s=s+aIi][j];
return s;}
problema a
#include<iostream.h>
#include<conio.h>
33 #include<stdio.h>
typedef int mat[20][20];
mat a;
int i, j, n;
int grad( int i)
{int s, j;
s=0;
for (j=1;j<=n;j++)
s=s+aIi][j];
return s;}
void main()
{ clrscr();
cout<<"n="; cin>>n;
for (i=1;i<=n-1;i++)
for (j=i+1;j<=n;j++)
{cout<<"a["<<i<<",”<<j<<"]=”; se cite ște matricea de adiacen Ńă
cin>>a[i][j];
a[j][i]=a[i][j];}
for (i=1;i<=n;i++)
cout<<"varful "<<i<<" are gradul"<< grad(i)<<endl;
getche(); }
Problema b
for (i=1;i<=n;i++)
if (grad(i) % 2==0) cout<<i<<” ”;
Problema c
for (i=1;i<=n;i++)
if (grad(i) ==0) cout<<i<<” ”;
Problema d
for (i=1;i<=n;i++)
if (grad(i) ==1,) cout<<i<<” ”;
Problema e
ok=0;
for (i=1;i<=n;i++)
if (grad(i) ==0) ok=1;
if (ok) cout<<"Da";
else cout<<"Nu";
Problema f
ok=0;
for (i=1;i<=n;i++)
if (grad(i) =1) ok=1;
if (ok) cout<<"Da";
else cout<<"Nu";
Problema g
ok=0;
for (i=1;i<=n;i++)
if (grad(i) >1) ok=1;
if (ok) cout<<"Da";
else cout<<"Nu";
Problema h
ok=1;
for (i=1;i<=n;i++)
if (grad(i) !=0)
ok=0;
if (ok) cout<<"Da":
else cout<<"Nu";
34 Problema i
ok=1;
for (i=1;i<=n;i++)
if (grad(i) <=1)
ok=0;
if (ok) cout<<"Da";
else cout<<"Nu";
Problema j
cout<<"Dati varful”; cin>>vf;
cout<<" varful "<<vf<<" are gradul "<< grad(vf);
Problema k
cout<<"Dati varful”; cin>>vf;
for(j=1;j<=n;j++)
if (a[vf][j]==i ) cout<<j<<” ”;
Problema l
cout<<"Dati varful : ": cin>>vf;
if (grad(vf)==0) cout<<"varful "<<vf<<" este izolat "<<endl;
else if (grad(vf)==1) cout<<"varful "<<vf<<" este t erminal";
else cout<<"varful "<<vf<<" este interior: ";
Problema m
– se determin ă gradul cel mai mare, n gr_max (este o problem ă simpl ă de determinare a maximului);
– se parcurg toate nodurile, cu i
dac ă gradul vârfului i este egal cu gr_max
se afi șeaz ă nodul i
gr_max=grad(1);
for (i=2;i<=n;i++)
if (grad(i)>gr_max) gr_max=grad(i);
cout<<''cel mai mare grad este "<< gr_max<<endl;
cout<<"si nodurile care au acest grad sunt"<<endl;
for ( i=l ; i<=n; i++)
if (grad(i)=gr_max) cout<<i<<” ”;
Problema n
n1=0; n2=0; n3=0;
for (i=1;i<=n;i++)
if (grad(i)=0) n1=n1+1;
else if (grad(i)==1) n2=n2+1;
else n3=n3+1;
cout<<"In graful dat sunt : "<<endl;
cout<<" "<<nl<<" varfuri izolate"<<endl;
cout<<" "<<n2<<" varfuri terminale"<<endl;
cout<<" <<n3<<" varfuri interioare"<<endl;
Problema o
for (i=1;i<=n;i++) cin>>g[i];
ok=1;
for (i=1;i<=n;i++)
if (grad(i)!=g[i]) ok=0;
cout<<ok;
Problema p
– se cite ște șirul g;
– se construie ște șirul gradelor vârfurilor, gr;
– se sorteaz ă cresc ător cele dou ă șiruri, folosind func Ńia:
void sort_crescator(sir x, int n)
{int i, ok, aux;
do{
35 ok=1;
for (i=1;i<=n-l;i++)
if (x[i]>x[i+l])
{aux= x[i];
x[i]=x[i+1];
x[i+1] =aux;
ok=0; }
}while (ok==0);
}
– se verific ă dac ă sunt identice:
for (i=1;i<=n;i++) cin>>g[i];
for (i=1;i<:=n;i++) gr[i]=grad(i);
sort_crescator(g,n);
sort_crescator(gr,n);
ok=1;
for (i =1;i<=n;i++)
if (gr[i]!=g[i]) ok=0;
cout<<ok;
5. Graf complet
Problema 1
a. Graful nu este complet, deoarece exist ă dou ă noduri între care nu exist ă muchie (1 si 3).
b. Graful este complet, deoarece oricare ar fi dou ă vârfuri distincte exista o muchie care le une ște.
Problema 2
a)K 3 : d(x)=3-1=2 Vx∈∀ ; K 5 : d(x)=5-1=4 Vx∈∀ ;
b) K 3: m=3(3-1)/2=3; K 5: m=5(5-1)/2=10;
c)
d) 1
Problema 3
Problema a
Observa Ńie . A verifica c ă un graf este complet,
făcând o analiz ă asupra vârfurilor, înseamn ă a
verifica dac ă toate vârfurile au gradul n-1.
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
typedef int mat[20][20];
mat a;
int i,j,n,c;
int grad( int i)
{int s,j;
s=0; for (j=1;j<=n;j++) s=s+a[i][j];
return s;}
void complet(int &c)
{int i;
c=1;
for (i=1;i<=n;i++)
if (grad(i)!=n-1) c=0;
}
void main()
{ clrscr();
cout<<"n="; cin>>n;
for (i=1;i<=n-1;i++)
for (j=i+1 ;j<=n;j++)
36 {cout<<"a["<<i<<","<<j<<"]=";
cin>>a[i][j];
a[j][i]=a[i][j];}
complet(c);
if(c==1) cout<<"graful este complet";
else cout<<"graful nu este complet";
getche(); }
Problema b
Observa Ńie . A verifica că un graf este complet,
făcând o analiz ă asupra muchiilor, înseamn ă a
verifica dac ă are n(n-1)/2 muchii, altfel spus:
trebuie verificat dac ă toate elementele de
deasupra diagonalei principale din matricea de
adiacen Ńă sunt egale cu 1.
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
typedef int mat[20][20];
mat a;
int i, j, n; void complet()
{int i,j,nr=0;
for (i=1;i<=n-1;i++)
for (j=i+1 ;j<=n;j++)
if (a[i][j]==1) nr++;
if(nr==(n*(n-1)/2)) cout<<"graf complet";
else cout<<"graful nu este
complet";}
void main()
{ clrscr();
cout<<"n="; cin>>n;
for (i=1;i<=n-1;i++)
for (j=i+1;j<=n;j++)
{cout<<"a["<<i<<","<<j<<"]=";
cin>>a[i][j];
a[j][i]=a[i][j];}
complet();
getche();
}
6. Graf bipartit
Problema 1
a) Graful este bipartit, deoarece respect ă defini Ńia; V1={ 1, 2, 3}, V2={4, 5}.
b) Graful este bipartit, deoarece respect ă defini Ńia; Vl={ 1, 3}, V2= { 2, 4}.
Problema 2
Pentru a ob Ńine un graf bipartit, trebuie eliminat ă muchia [1,3]; V 1={ 1, 2, 3 } , V2={4, 5}.
Problema 3
Fie graful bipartit G, f ără vârfuri izolate, dat prin matricea de adiacen Ńă . S ă se realizeze un program care
determin ă mulŃimile V 1 și V2 despre care se vorbe ște în defini Ńie.
Rezolvare:
– la început V1=[ ] și V2=[ ]
– se parcurge matricea de adiacent ă, linie cu linie, deasupra diagonalei principale
dac ă pe linia i se g ăse ște elementul a[i,j]=1,
atunci
dac ă i apar Ńine deja lui V2 atunci
j se adaug ă la mul Ńimea V1: V1:=Vl+1j]
altfel
i se adaug ă la mul Ńimea V1: V 1:=V 1+[i]
j se adaug ă la mul Ńimea V2: V2:=V2+[j]
Solu Ńia este de a genera într-un vector nodurile care ap ar Ńin mul Ńimilor V1, V2, astfel: dac ă un element
are valoare a 1, nodul care eticheta corspunz ătoare indicelui elementulului mul Ńimii V1; altfel, apar Ńine
mul Ńimii V2.
Func Ńia gererare() genereaz ă grafurile bipartite complete. În vectorul a se gen ereaz ă nodurile mul Ńimilor
V1 și V2. Ini Ńial elementele vectorului auvaloarea 0. Variabila p osibil se folose ște pentru a verifica dac ă
mai exist ă posibilit ăŃile de generare de submul Ńimi ( are valoare 1 atunci când mai este posibils ă se
genereze submul Ńimile)
#include <conio.h>
#include <iostream.h>
#include<math.h>
void generare (int n)
{int a[20]={0},i,j,k=0,posibil=1;
while (posibil) {j=n;
while(j>0&&a[j]==1) {a[j]=0;j–;}
if(j==0) posibil=0;
else
{a[j]=1; k++;
if(k<=pow(2,n)-2)
37 {cout<<"graful "<<k<<endl<< "Multimea V1:";
for(i=1;i<=n;i++) if(a[i]) cout<<i<<" ";
cout<<"Multimea V2:";
for(i=1;i<=n;i++) if(!a[i]) cout<<i<<" ";
cout<<endl;
cout<<"Muchiile sunt:";
for(i=1;i<=n;i++)
if(a[i]==1)
for(j=1;j<=n;j++) if(a[j]==0&&i!=j) cout<<"["<<i<<","<<j<<"] ";
cout<<endl;}}}}
void main()
{ int n;
cout<<"numar de noduri="; cin>>n;
generare(n);
getch();}
Problema 4
4. Fie graful G cu n vârfuri, dat prin matricea de adiacen Ńă , într-un fi șier text. S ă se realizeze un program
care precizeaz ă dac ă graful este bipartit.
Rezolvare: Pt. a verifica dac ă graful este bipartit, se genereaz ă mul Ńimile de noduri V1 și V2 pân ă când
aceste mul Ńimi îndeplinesc condi Ńia unui graf bipartit, sau pân ă când s-au generat toate mul Ńimile și nici
na dintre variante nu a îndeplinit condi Ńia pt. graful bipartit ( între orice pereche de 2 e lemente din cele 2
mul Ńimi exist ă o muchie care s ă le lege în graf)
Se genereaz ă într-un vector toate submul Ńimile care se pot ob Ńine din cele n etichete de noduri (exceptând
mul Ńimea ini Ńial ă și cea vid ă) și se verific ă dac ă nodurile apar Ńinând celor 2 mul Ńimi generate pot fi
mul Ńimile unui graf bipartit.
Func Ńia bipartit() verific ă dac ă graful este bipartit furnizând un rezultat logic. Elementele vectorului x în
care se genereaz ă mul Ńimile V1 și V2 sunt ini Ńial 0. Variabila gasit se folose ște pentru a verifica dac ă s-
au g ăsit cele dou ă mul Ńimi de noduri corespunz ătoare unui graf bipartit ( are valoarea 1 atunci câ nd s-au
găsit)
#include <conio.h>
#include <iostream.h>
#include <fstream.h>
#include<math.h>
int a[20][20],v[20],i,j,n,m,x;
ifstream f("gb.txt");
int bipartit()
{int x[10]={0},i,j,m,k=0,posibil=1,gasit=0;
while(posibil&&!gasit)
{m=n;
while(m>0&&x[m]==1) {x[m]=0;m++;}
if(m==0) posibil=0;
else
{x[m]=1; k++;
if(k<=pow(2,n)-2)
for(i=1,gasit=1;i<=n&&gasit;i++)
for(j=1;j<=n&&gasit;j++)
if(a[i][j]==1) if((x[i]==1&&x[j]==1)||(x[i]==0&&x[j]==0))
gasit=0;}}
return gasit;}
void main()
{
f>>n;
while(f>>i>>j)
a[i][j]=a[j][i]=1;
f.close();
if (bipartit()) cout<<"este bipartit";
else cout<<"nu este bipartit";
getch();}
gb.txt
4
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
Problema 5.
Să se gereze toate grafurile neorientate bipartite co mplete cu n noduri.
Rezolvare: problema se reduce la a genera toate submul Ńimile care se pot ob Ńine din cele n elemente.
Num ărul total de submul Ńini ob Ńinut este 2 2-2 (mai pu Ńin mu Ńimea ini Ńial ă și mul Ńimea vid ă). Solu Ńia este
de a genera într-un vector nodurile care apar Ńin mu Ńimilor V1 și V2, astfel: dac ă un elemnt are valaorea
1, nodul care are eticheta corespunz ătoare indicelui elementului apar Ńine mul Ńimii V1; altfel apa Ńine
mul Ńimii V2.
Func Ńia generare() genereaz ă nodurile mul Ńimilor V1 și V2. Ini Ńial elementele vectorului au valaorea 0.
Variabila posibil se folose ște pentru a verifica dac ă mai exist ă posibilit ăŃi de generare de submul Ńimi(are
valorea 1 când e posibil s ă se mai genereze submul Ńimi)
include<iostream.h>
#include<conio.h>
#include<math.h>
38 void generare (int n)
{int a[10]={0},i,j,k=0,posibil=1;
while(posibil)
{j=n;
while(j>0&&a[j]==1) {a[j]=0;j–;}
if(j==0) posibil=0;
else{a[j]=1; k++;
if(k<=pow(2,n)-2)
{cout<<"graful"<<k<<endl<<"multimea V1: ";
for(i=1;i<=n;i++) if(a[i]) cout<<i<<" ";
cout<<endl;
cout<<"multimea V2:";
for(i=1;i<=n;i++) if(!a[i]) cout<<i<<" ";
cout<<endl;
cout<<"muchiile sunt: ";
for(i=1;i<=n;i++)
if(a[i]==1)
for(j=1;j<=n;j++)
if(a[j]==0&&i!=j) cout<<"["<<i<<","<<j<<"]";
cout<<endl;}}}}
void main()
{int n;
cout<<"numarul de noduri"; cin>>n;
generare(n);getch();}
7. Graf bipartit complet
Problema 1
a) Graful este bipartit , deoarece respect ă defini Ńia, V1={ 1, 2, 3 }, V2={4, 5}, dar nu este complet ,
deoarece exist ă noduri in V1 (ex. 2) nelegate de toate nodurile di n V2 (ex. 5).
b) Graful este bipartit deoarece respect ă defini Ńia, V1={ 1, 3}, V2={2, 4}, dar cum toate nodurile d in V 1
sunt legate de toate nodurile din V2 înseamn ă c ă este bipartit complet .
Problema 2
Pentru a ob Ńine un graf bipartit complet trebuie ad ăugat ă muchia [2,5]; V 1={ 1, 2, 3 } , V2={4, 5}.
Problema 3
Se procedeaz ă astfel:
Pe liniile l..p din matricea de adiacen Ńă
se pune valoarea 1 pe coloanele p+l..n, deoarece to ate elementele din V 1 sunt
legate de toate elementele din V2
(nu trebuie uitat ca matricea de adiacen Ńă este simetric ă fa Ńă de diagonala principal ă)
……………………
for (i=1;i<=p;i++)
for (j=p+l;j<=n:j++)
{ a[i][j]=1;
a[j][i]=1;}
…………………….
Problema 4
Se procedeaz ă astfel:
Este suficient s ă gândim construirea matricei deasupra diagonalei pr incipale, pentru că ea este simetric ă
fa Ńă de diagonala principal ă. Matricea se construie ște astfel:
– pe liniile pare , de deasupra diagonalei principale,
se pune valoarea 1 pe coloanele impare, deoarece to ate elementele din V 1 sunt
legate de toate elementele din V2
– pe liniile impare , de deasupra diagonalei principale, se pune valoar ea 1 pe coloanele pare, deoarece
toate elementele din V2 sunt legate de toate elemen tele din V 1
(nu trebuie uitat ca matricea de adiacen Ńă este simetric ă fa Ńă de diagonala principal ă)
…………………….
39 for (i=1;i<=n-l;i++)
for (j=i+l;j<=n;j++)
if ((i % 2==0) && (j % 2!=0})
{ a[i][j]=1;
a[j][i]=1;}
for (i=1;i<=n-l;i++)
for (j=i+1;j<n;j++)
if ((i % 2!=0) && (j % 2==0))
{ a[i][j]=1;
a[j][i]=1;}
………………………..
Problema 5
Un graf bipartit complet este unic determinat de o par ti Ńie a lui V n doua submul Ńimi V l și V2, disjuncte
și nevide. A determina toate grafurile bipartit comp lete, înseamn ă a determina în câte moduri se pot
construi mul Ńimile V1 și V2. Pentru aceasta proced ăm astfel:
În mul Ńimea V1 se pune nodul 1 , pentru a nu repeta solu Ńiile
(mai sunt n-1 noduri nepuse).
Parti Ńia_1 la V1 se adaug ă 0 noduri (sunt 0
1−nC situa Ńii ) iar la V2 restul
Parti Ńia_2 la V1 se adaug ă 1 noduri (sunt 1
1−nCsitua Ńii ) iar la V2 restul
Parti Ńia_3 la V1 se adaug ă 2 noduri (sunt 2
1−nCsitua Ńii ) iar la V2 restul
………………………………..
Parti Ńia_n-1 la V1 se adaug ă n-2 noduri (sunt 2
1−
−n
nCsitua Ńii ) iar la V2 restul
(alte parti Ńie nu mai exist ă, pentru c ă la Vl nu se pot ad ăuga înc ă n-1 noduri deoarece V2 ar fi vid ă, în
acest caz , și ar fi în contradic Ńie cu defini Ńia grafului bipartit).
În total sunt 0
1−nC+1
1−nC+2
1−nC+… +2
1−
−n
nC posibilit ăŃ i de construire. Aceast ă sum ă se calculeaz ă astfel:
0
1−nC+1
1−nC+2
1−nC+… +2
1−
−n
nC + 1
1−
−n
nC=2 n-1
de unde rezult ă ca:
0
1−nC+1
1−nC+2
1−nC+… +2
1−
−n
nC=2 n-1-1
1−
−n
nC=2 n-1-1
8. Reprezentarea grafurilor
Problema 1
a)
=
0010100010100010100010100
A
Vârful i Lista vecinilor lui
1 3,5
2 4
3 l, 5
4 2
5 1, 3
M={[e1[1],e2[1]]=[1,3],[e1[2],[2]]=
[1,5],[e1[3],e2[3]]=[2,4],[e1[4],e2[4]]=[3,5]} b)
=
0101101101011110
A
Vârful i Lista vecinilor lui
1 2,3,4
2 1,3
3 l, 2,4
4 1,3
M={[el[1],e2[1]]=[1,2], [el[2],e2[2]]=[1,3],
[el[3],e2[3]]=[1,4], [el[4],e2[4]]
=[2,3],[el[5],e2[5]]=[3,4]}
Problema 2
A verifica dac ă matricea poate reprezenta matricea de adiacen Ńă a unui graf neorientat, trebuie verificate
următoarele:
– matricea are pe diagonala principal ă numai elemente egale cu 0;
– matricea are deasupra diagonalei principale numai elemente de 0 și 1;
40 – matricea este simetric ă fa Ńă de diagonala principal ă.
…………….
ok1=1;
for (i=l;i<=n;i++)
if (a[i][i]!=0) ok1=0;
ok2=1;
for (i=1;i<=n-l;i++)
for (j=i+l;j<=n;j++)
if (!((a[i][j]==a) || (a[i][j]=1)) ok2=0;
ok3=1;
for (i=1;i<=n-l;i++)
for (j=i+l ;j<=n;j++)
if (a[i][j] !=a[j][i]) ok3=0;
ok=okl && ok2 && ok3;
cout<<ok;
………………….
Problema 3
Un graf neorientat, cu n vârfuri, este unic determi nat de o matrice de adiacen Ńă p ătratic ă de ordinul n.
Deci, a determina grafurile neorientate cu n vârfur i înseamn ă a determina toate matricele p ătratice de
ordinul n, caracterizate astfel:
– au numai elemente de 0 și/sau 1;
– pe diagonala principal ă an numai elemente de 0;
– sunt simetrice fa Ńă de diagonala principal ă.
Citind cu aten Ńie caracteristicile matricei de adiacen Ńă , constat ăm cu u șurin Ńă c ă pentru a determina o
astfel de matrice este suficient s ă-i determin ăm elementele de deasupra diagonalei principale, deo arece
matricea are deasupra diagonalei principale (n 2-n)/2 elemente, problema se reduce la a determina t o Ńi
vectori de lungime (n 2-n)/2 cu elemente de 0 și 1; ace ști vectori sunt în num ăr de ( )2 /22nn− (este vorba de
determinarea submul Ńimilor unei mul Ńimi cu (n 2-n)/2 elemente).
Problema 4
Problema se reduce la a determina to Ńi vectori de lungime (n 2-n)/2 cu elemente de 0 și/sau 1; (vezi
explica Ńiile de la problema anterioar ă). Acest lucru se face folosind metoda Backtracking , astfel:
– se genereaz ă pe rând to Ńi vectorii de lungime p=(n 2-n)/2 cu elemente de 0 și/sau 1;
– pentru fiecare vector generat, se construie ște matricea de adiacen Ńă corespunz ătoare, astfel:
– pe diagonala principal ă se pune 0;
– deasupra diagonalei principale se pun elementele vectorului, astfel:
ks=1;
for (i=1;i<=n-l;i++)
for (j=i+l ;j<=n;j++)
{a[i][j]=x[ks];
ks=ks+1;
a[j][i]=a[i][j];}
– elementele de sub diagonala principal ă trebuie puse astfel încât matricea s ă fie simetric ă
fa Ńă de diagonala principal ă.
În concluzie, trebuie generate elementele mul Ńimii{(x 1, x2,…,x p) | x k ∈{0,1}, k=1,…,p}.
x=(x 1, x2,…,x p) unde x k∈{0,1 }; k ∈{ 1,…,p}; p=(n 2-n)/2
#include <conio.h>
#include <iostream.h> p
#include <stdio.h>
typedef int sir[100];
sir x; k
int i, k, n, p;
int as, ev; 1
int a[100][1001; 0 1
void succ(sir x, int k, int &as) x k
{if (x[k]<I) 0
0
.
0
01
1
.
1
1
41 {as=1;
x[k]=x[k]+l;}
else as=0;}
void valid( int &ev)
{ev=1;}
void afis(sir x)
{int i, j, ks; generarea matricei de adiacen Ńă ,
ks=1; plecând de la vectorul generat
for (i=1;i<=n-1;i++)
for (j=i+l;j<=n;j++)
{a[i][j]=x[ks];
ks=ks+1;
a[j][i]=a [i][j];}
for (i = 1 ;i<=n;i++) afi șarea matricei de adiacen Ńă
{for (j=1;j<=n;j++)
cout<<a[i]]j]<<” ”;
cout<<endl;}
cout<<endl<<endl;}
void main()
{cout<<”n=”;cin>>n;
k=1;
x[k]=1; privi Ńi tabla
while (k>0) {
do{ succ(x,k,as);
if (as) valid(ev);
} while (as && !ev);
if (as)
if (k=p) afis(x);
else { k=k+ 1;
x[k]=1;}
else k=k-1;
}
}
Problema 5
Matricea de adiacen Ńă A2 reprezint ă un graf par Ńial al grafului reprezentat de matricea de adiacen Ńă A1
dac ă acolo unde elementele matricei A1 sunt 0 și elementele corespunz ătoare din matricea A2 sunt 0; în
rest nu conteaz ă, adic ă, dac ă elementele lui A1 sunt 1 elementele corespunz ătoare din A2 pot fi 0 sau 1
(acest lucru se exprim ă astfel: A2[i,j]<=A1[i,j]). Este suficient s ă facem verificarea pentru elementul de
deasupra diagonalei principale.
…………….
ok=1;
for (i=l;i<=n-1;i++}
for (j=i+l;j<=n;j++)
if (!(A2[i][j]<=A1[i][j]) ok=0;
if (ok) cout<<"A2 reprezinta un graf partial al gra fului reprezentat de A1";
else cout<<"A2 nu reprezinta un graf partial al gra fului reprezentat de A1 ";
…………………
Problema 7
Un graf bipartit complet este unic determinat de o parti Ńie a lui V în dou ă submul Ńimi V1 și V2, distincte
și nevide. A determina toate grafurile bipartit comp lete, înseamn ă a determina toate modurile în care se
pot construi mul Ńimile V1 si V2, din elementele {1 …n}.
Acest lucru se realizeaz ă astfel:
În mul Ńimea V1 se pune nodul 1, pentru a nu repeta solu Ńiile (mai sunt n-1 noduri nepuse). Problema
revine la a determina toate posibilit ăŃ ile de a plasa vârfurile 2…n în prima sau în a do ua mul Ńime; orice
astfel de plasare convine cu excep Ńia plas ării tuturor vârfurilor în prima mul Ńime.
42 Pentru a rezolva aceast ă problem ă vom folosi metoda Backtracking, astfel:
Se genereaz ă to Ńi vectorii:
x=(x 1×2,…,x n) cu x 1=1 și x k∈{0,1} pentru k ∈{2,…,n}, f ără ca toate elementele s ă fie egale cu 1, cu
urm ătoarea semnifica Ńie:
dac ă x i=1, atunci i face parte din V1 n
altfel i face parte din V2
#include <conio.h>
#include <iostream.h> k
#include <stdio.h>
typedef int sir[ 100];
sir x; 2
int i, k, n; int as, ev; 0 x k 1
void succ(sir x, int k, int&as)
{if (x[k]<1)
{as=1;
x[k]=x[k]+1;}
else as=0;}
void valid( int &ev )
{ev=1;}
void afis(sir x, int k)
{int i, s;
s=0;
for (i=l;i<=k;i++) dac ă toate componentele
s=s+x[i]; se verific ă au valoarea 1
if (s!=n)
{cout<<"V 1:”; din V1 fac parte numai elementel e i
for (i=1;i<=n;i++) pentru care x i =l
if (x[i]==1) cout<<i<<” ”;
cout<<endl;
cout<<"V2 :”; din V2 fac parte numai elementele i
for (i=1;i<=n;i++) pentru care x i =0
if (x[i]==0) cout<<i<<” ”;
cout<<endl<<endl;}
}
void main()
{ clrscr();
cout<<"n="; cin>>n;
x[1]=1;
k=2;
x[k]=-1; privi Ńi tabla
while (k> 1){
do{ succ(x,k,as);
if (as)
valid(ev);
}while (as && !ev);
if (as)
if (k==n) afis(x,k);
else
{k=k+ 1;
x[k]=-1;}
else k=k-1;
}
getche();}
Problema 8 0
0
.
0
01
1
.
1
1
43 Dup ă cum se vede în enun Ńul problemei, graful se d ă prin precizarea num ărului de noduri și a șirului
muchiilor sale m 1 … m p. Plecând de la faptul c ă un graf par Ńial al s ău se ob Ńine prin eliminarea unui num ăr
oarecare de muchii, p ăstrând aceea și muchie de vârfuri, problema dat ă se reduce la generarea
submul Ńimilor mul Ńimii {m 1 … m p}. Acest lucru îl vom realiza folosind metoda Backt racking, astfel:
– se genereaz ă submul Ńimile mul Ńimii {m 1 … m p}
– pentru fiecare astfel de submul Ńime generat ă, construim matricea de adiacen Ńă si o afi șăm.
Se genereaz ă to Ńi vectorii:
x=(x 1, x2,…,x p) cu x k∈{ 0,1} pentru k ∈{1,…,p} cu urm ătoarea semnifica Ńie: dac ă x i=0, atunci m i se
elimin ă din mul Ńimea {m 1 … m p} altfel m i nu se elimin ă din mul Ńimea {m 1 … m p}
#include <conio.h>
#include <iostream.h>
#include <stdio.h> p
typedef int sir[100];
typedef struct{
int x, y; } muchie; k
sir x;
int a[100][100];
int i, k, n, p, nr, j; 1
int as, ev; 0 x k 1
muchie m[100];
void succ(sir x, int k, int &as)
{if (x[k]<l)
{as= 1;
x[k]=x[k]+1;}
void valid(int &ev)
{ ev=1;}
void afis(sir x, int k)
{ int i;
for (i=1;i<=k;i++)
if (x[i]==1)
{a[m[i].x][m[i].y]=1;
a[m[i].y][m[i].x]=1;} construirea matricei de adia cent ă
nr=nr+ 1 ;
cout<<"matricea de adiacenta al celui de-al "<<nr<< "-lea graf partial"<<endl;
for (i=1;i<=n;i++) afi șarea matricei de adiacen Ńă
{for (j=1;j<=n;j++)
cout<<a[i][j]<<” ”;
cout<<endl;}
}
void main()
{ clrscr();
nr=0;
cout<<"n="., cin>>n;
cout<<"p="; cin>>p;
for (i=1;i<=p;i ++) cin>>m[i].x>>m[i].y;
k=1;
x[k]=- 1;
while (k>0){ priviti tabla
do {succ(x,k,as);
if (as) valid(ev);
}while (as &&!ev);
if (as)
if (k==p) afis(x,k);
else
{k=k+ 1; 0
0
.
0
01
1
.
1
1
44 x[k]=-1;}
else k=k-1;
}
getch();}
Problema 9
łinând cont de faptul ca un subgraf al unui graf se ob Ńine prin eliminarea unui num ăr de noduri, și a
muchiilor incidente cu aceste noduri, tragem urm ătoarea concluzie:
Problema se reduce la a genera toate submul Ńimile mul Ńimii {l, …, n} (f ără mul Ńimea vid ă), iar pentru
fiecare submul Ńime generat ă se afi șeaz ă decât acele muchii ale grafului care au ambele ext remit ăŃ i printre
elementele submul Ńimii.
Rezolvarea problemei se face folosind metoda Backtr acking, și const ă în a genera elementele mul Ńimii:
{(x 1,x 2…,x n) I x k ∈{0,1}, k=1,…,n, nu toate nule}.
(dac ă x k =1, înseamn ă c ă nodul k face parte din submul Ńime, altfel nu)
x=(x 1,×2,…,x n) unde x ∈{0,1};
k∈{ 1,…,n);
#include <conio.h> n
#include <iostream.h>
#include <stdio.h>
typedef int sir [ 100]; k
typedef int mat[20[20];
int e l, e2; 1
int i,j,n,m,ns,k; mat a; 0 1
sir x; x k
int as, ev;
void succ(sir x, int k, int &as)
{if (x[k)< 1)
{as= 1;
x[k]=x[k]+1;}
else as=0;}
void afis(sir x, int k)
{ int i;
ns=ns+1; ns este num ărul solu Ńiei
cout<<"subgraful cu numarul "<< ns<<"are nodurile " ; curente
cout<<endl;
for (i=1;i<=k;i++)
if (x[i]==1) se afi șeaz ă nodurile
cout<<i<<" ", corespunz ătoare unei solu Ńii
cout<<endl;
cout<<"si muchiile ";
for (i=1;i<=k-l;i++) se afi șeaz ă muchiile
for (j=i+l;j<=k;j++) corespunz ătoare unei solu Ńii
if ((x[i]==1) && (x[j]==1) && (a[i][j]==1))
cout<<" (,<<i<<",”<<j<<")”<<endl;
cout<<endl<<endl;}
void valid(sir x, int k, int &ev)
{ int i, s;
ev=l;
if (k=n)
{ s=0; aici se elimin ă solu Ńia
for (i=1;i<=k;i++) cu toate componentele
s=s+x[i]; egale cu 0
if (s==0) ev=0;}
}
void main() 0
0
.
0
01
1
.
1
1
45 { clrscr();
cout<<"n="; cin>>n;
cout<<"m=”; cin>>m;
for (i=1;i<=m;i++)
{cout<<"el e2 "; cin>>el>>e2;
a[el][e2]=1;
a[e2][e1]=1;}
ns=0;
x[1]=-1;
k=1;
while (k>0){
do{
succ(x,k,as);
if (as) valid(x,k,ev);
}while (as && !ev);
if (as)
if (k==n) afis(x,k);
else {
k=k+1 ;
x[k]=- 1;}
else k=k-1,
}
getch();}
Problema 10
Problema se reduce la:
– a ne imagina un graf neorientat, nodurile grafului sunt persoanele iar muchiile sunt reprezentarea
rela Ńiilor de simpatie între persoane, care este repreze ntat prin listele de adiacen Ńă (citite de la tastatur ă)
– a construi matricea de adiacen Ńă corespunz ătoare (plecând de la listele de adiacen Ńă );
– a verifica proprietatea de simetrie fat ă de diagonala principal ă, adic ă: a[i][j]=a[j][i] , pentru 1 ≤i, j ≤n.
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
typedef int mat[20][20];
int i, j, n, vec;
mat a;
int ok;
void main()
{ clrscr(); c
out<<"n="; cin>>n;
for (i=1;i<=n;i++) se construie ște matricea de adiacen Ńă plecând de la listele
{cout<<"Pentru "<<i<<endl; de adiacenta
cout<<"dati numarul vecinilor";
cin>>vec:
for (k=l;k<=vec;k++)
{cin>>j;
a[i][j]=1;}
}
ok=1; se verific ă proprietatea de simetrie
for (i=1;i<=n-l ;i++)
for (j=i+l;j<=n;j++)
if (a[i][j]!=a[j][i])
{ok =0;
46 cout<<"nepotrivire intre "<<i<<" si”<<j;}
if (ok) cout<<"toate simpatiile sunt reciproce",
getche(); }
9. Parcurgerea grafurilor
Problema 1
Listele nodurilor ob Ńinute în urma parcurgerii in l ăŃime:
a) 1, 3, 5, 4, 2;
b) l, 2, 3, 4, 6, 5;
Listele nodurilor ob Ńinute în urma parcurgerii în adâncime:
a) 1, 3, 5, 4, 2;
b) 1, 2, 3, 4, 5, 6;
Problema 2
Aceast ă problem ă este, pân ă la urm ă, o problem ă de parcurgere a unui graf. Pentru a determina nodu rile
care sunt accesibile din nodul 1, se procedeaz ă astfel:
– la început, nici un nod nu se consider ă vizitat;
– se viziteaz ă nodul 1;
– se aplic ă una dintre procedurile de parcurgere, de exemplu î n adâncime, plecând de la nodul 1;
– se afi șeaz ă toate nodurile care au fost vizitate, în urma apel ului procedurii de care am vorbit (aceste
noduri sunt, de fapt, nodurile la care se poate aju nge plecând de la nodul 1).
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
typedef int sir [100î;
typedef int mat[20][20];
int i, n, pl, m, x, y;
mat a;
sir viz;
void parc_adancime(int pl)
{ int j;
viz[pl]=l;
for (j=1;j<=n;j++)
if ((a[pl][j]==1) && (viz[j]==0))
parc_adancime(j);}
void main()
{ clrscr();
cout<<”n m”; cin>>n>>m;
for (i= l;i<=m;i++)
{cout<<"x y "; cin>>x>>y;
a[x][y]=1;
a[y][x]=1;}
for (i=1;i<=n;i++)
viz[i]=0;
p1=1;
parc adancime(pl);
cout<<" nodurile care sunt accesibile din nodul 1 s unt ";
for (i=1;i<=n;i++)
if (viz[i]==1) cout<<i<<” ”;
getche(); }
10. Conexitate
Problema1
Fiind date grafurile de mai jos:
47 a) l
b)
sa se precizeze pentru fiecare în parte un lan Ń, un lan Ń de lungime 4, un lan Ń elementar, un ciclu, un
ciclu elementar, dou ă cicluri egale.
a) L1=[1, 3, 5 ] lan Ń;
L2=[1, 3, 5, 4, 2] lan Ń de lungime 4;
Oricare dintre lan Ńurile de mai sus sunt
elementare.
C1=[1, 3, 5, 1] ciclu;
Ciclul de mai sus este elementar.
C1=[l, 3, 5, 1] este egal cu C2=[3, 5, 1, 3]; b)L1=[l, 2, 3, l, 4] lan Ń;
L2=[4, 1, 2, 3, S] lan Ń de lungime 4;
Lan Ńul de mai sus este elementar.
Cl=[1, 2, 3, 1] ciclu;
Ciclul de mai sus este elementar.
C1=[l, 2, 3, 4, 1] este egal cu C2=[4, 3, 2, l, 4];
Problema 2
Fie G un graf neorientat, cu n noduri și m muchii. Precizându-se doua noduri np (nodul de
plecare) și ns (nodul de sosire), s ă se determine toate lan Ńurile elementare care le admit ca
extremit ăŃi.
Problema se rezolv ă folosind metoda Backtracking, și se reduce la a determina șirurile de forma x 1….. x p
unde x l=np și x p=ns (deci, construc Ńia unei solu Ńi se opre ște atunci când o component ă a sa prime ște
valoarea ns), cu componente distincte, astfel încât între x i și x i+1 s ă existe muchie în graful dat.
În concluzie, solu Ńia este x=(x 1×2,…,x p), unde x 1=np, x p=ns, x k∈{1,…,n} k ∈{2….,p-1}; x i≠xj pentru i ≠j,
și a[ x i-1][x i]=1
Comentarii la functia Valid:
Trebuie verificat ca:
– exist ă muchie între nodurile x k-1 și x k, adic ă trebuie verificat c ă a[ x k-1][x k]=1;
– nodul x k este diferit de toate nodurile prin care s-a trecu t, adic ă:
xk ≠xi pentru i=1…k-1.
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
typedef int sir [ 100];
typedef int mat[20][20];
int e l, e2;
int i,j,n,m,ns,np,k;
mat a;
sir x;
int as, ev;
void succ(sir x, int k, int &as)
{if(x[k]<n)
{ as=1;
x[k]= x[k]+1;}
else as=0;}
void afis(sir x, int k)
{int i;
for (i=1;i<=k;i++)
cout<<x[i]<c” ”;
cout<<endl;}
void valid(sir x, int k, int &ev)
48 { int i;
ev=1;
if (a[x[k-1]][x[k]]==0) ev=0; trebuie s ă existe muchie între
el se x k-1 si x k
for (i=1;i<=k-l;i++)
if (x[k]==x[i]) ev=0;}
void main()
{ clrscr();
cout<<"n=": ciu>>n;
cout<<"m=”; cin>>m;
for ( i=1;i<=m;i++)
{cout<<"el e2 "; cin>>el>>e2;
a[e1][e2]=1;
a[e2] [e1]=1;}
cout<<"np="; cin>>np;
cout<<"ns="; cin>>ns;
x[1]=np;
k=2;
x[k]=0;
while (k>1){
do{
succ(x,k,as);
if (as) valid(x,k,ev);
}while (as && !ev);
if (as)
{ if (k<=n)
if (x[k]=ns)
afis(x,k);
else
{k=k+ 1;
x[k]=0;}
}
else k=k-1;
}
getche(); }
Problema 3
Problema se rezolv ă folosind metoda Backtracking, astfel:
– se genereaz ă aranjamentele mui Ńimii { 1,…, n} in vectorul x=(x 1,x 2,…,x n1 ) unde nl=n…2 (deci, se începe
cu generarea solu Ńiilor cu lungimea cea mai mare);
– dintre vectorii genera Ńi, se aleg cei care verifica proprietate: între x i si x i+1 exist ă muchie și se afi șeaz ă
cei cu lungimea cea mai mare (acest lucru estc ilus trat în functia Afis).
Comentarii la functia Afis:
– la primul apel al func Ńiei (ns=l ) se p ăstreaz ă lungimea vectorului solu Ńie (lung=k) pentru ca aceasta este
cea mai mare;
– la urmatoarele apeluri nu se ia in calcul decât v ectorii cu lungimca egal ă cu lung
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
typedef int sir [ 100];
typedef int mat[20][20];
int el, e2; int i, j , n,n l, m , k, ns, lung;
mat a;
sir x; int as, ev;
void succ(sir x, int k, int &as)
{ if (x[k]<n) {as=1;
x[k]=x[k]+1; }
else as=0;}
void afis(sir x, int k)
{ int i;
ns=ns+ 1;
if (ns==1) lung=k;
if (k==lung)
{for (i=1;i<=k,i++) cout<<x[i]<<” ”;
cout<<endl;}
49 }
void valid(sir x, int k, int &ev)
{int i; ev=1;
if (a[x[k-1]][x[k]]==0) ev=0;
else
for (i=1;i<=k-l;i++)
if (x[k]== x[i]) ev=0;
}
void main()
{ clrscr();
cout<<"n=”; cin>>n; cout<<"m=’; cin>>m;
for (i=1;i<=m;i++)
{cout<<"el e2 ";cin>>el>>e2;
a[e1][e2]=1;
a[e2][el]=1;}
ns=0;
for (n1=n;n1>=2;n1–) {x[1]=0;
k=1;
while (k>0){
do{
succ(x,k,as);
if (as) valid(x,k,ev);
}while (as && !ev);
if (as)
if (k= nl) afis(x,k);
else
{k=k+ 1;
x[k]=0;}
else k=k-1;
}
}
getche();}
Problema 4
Dac ă ar exista un ciclu de lungime 4 ar fi de forma: i, kl, j, k2, i. Pentru a demonstra existen Ńa unui astfel
de ciclu, proced ăm astfel:
– încerc ăm s ă ar ătăm că pentru o pereche de noduri (i, j) exist ă alte dou ă noduri kl și k2 diferite de acestea
și legate de ele prin muchii (a[i,kl]=1, a[j,kl]=1 și a[i,k2]=1, a[j,k2]=1)
………………..
ok=0;
for (i=1;i<=n-l;i++)
for (j=i+l ;j<=n;j++)
nr =0;
for (k=1;k<=n;k++)
if ((i!=k) && (j!=k) && (a[i][k]==1) && (a[j][k]==1 )
nr=nr+ 1;
if (nr>= 2)
ok=1;}
…………………
Problema 5
Problema se rezolv ă folosind metoda Backtracking, și se reduce la a determina șirurile de forma x 1…,x p
unde:
-x1=1
-componentele sunt distincte;
– între x i și x i+1 i=1…p-1, s ă existe muchie în graful dat;
– x 1 și x p sunt unite printr-o muchie.
În concluzie, solu Ńia este x=(x 1,x 2,….x p), unde x 1=1, x k∈ {2,…,n} k ∈ {2,…,p};
xi≠xj pentru i ≠j, a[ x i-1xi]=1 pentru i=2..p, și a[ x 1,x p]=1
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
typedef int sir[100];
typedef int mat[20][20];
int e 1., e2;
int i, j, n, m, p, k;
mat a;
sir x; int as, ev;
void succ(sir x, int k, int &as)
{if (x[k]<n)
{as=1;
x[k]=x[k]+1;}
else as=0;}
void afis(sir s, int k)
{int i;
for (i=1;i< =k;i++) cout<<x[i]<<” ”; 1…i n
1…k 1 k2…n
i… j n
50 cout<<x[1]<< " ;
cout<<endl;}
void valid(sir x, int k, int &ev)
{int i;
ev=1;
if (a[x[k-1]][x[k]]==0) ev=0;
else
{for (i=1;i<=k-l;i++)
if (x{k{==x[il) ev=0;
if ((k==p) && (a[ x[ k]][ x[1]]==0))
ev=0;}
}
void main()
{ clrscr();
cout<< " n="; cin>>n;
cout<<m="; cin>>m:
for(i=1;i<=m;i++)
{cout<<"el e2 "; cin>>el>>e2;
a[el][e2]=1; a[e2][e1]==1;}
cout< <”p=”; cin>>p;
x[1]=1;
k=2;
x[k]=1;
while (k>1) {
do{
succ(x,k,as );
if (as) valid(x,k,ev);
}while (as && !ev);
if (as)
if (k==p) afis(x,k);
else
{k=k+ l ;
x[k]=l;}
else k=k-1;
}
getche();}
Problema 6
Pân ă la urm ă, este o problem ă de parcurgere a unui graf și se rezolz ă astfel:
– se cite ște matricea de adiacen Ńă ;
– toate nodurile se consider ă ini Ńial nevizitate;
– la început, sunt 0 componente conexe;
– se parcurg nodurile grafului
– dac ă se g ăse ște un nod nevizitat înc ă
– înseamn ă ca s-a mai g ăsit o component ă conex ă
– și se viziteaz ă toate nodurile la care se poate ajunge plecând fie la acest nod (pentru
aceasta este nevoie de una dintre procedurile de pa rcurgere a unui graf (în adâncime sau în
l ăŃ ime))
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
int viz[ 100],a[20][20], i,n,m,x,y,nr,j;
void parc_adancime(int pl)
{int j;
viz[pl]=1;
for (j=1;j<=n;j++)
if ((a[pl][j]==1) && (viz[j]==0))
parc_adancime(j);}
void main()
{ clrscr();
cout<<"n="; cin>>n; cout<<"m"; cin>>m; for (i=1;i<=m;i++)
{cout<<"x y"; cin>>x>>y;
a[x][y]=1;
a[y] [x]=1;}
for (i=1;i<=n;i++) viz[i]=0;
nr=0;
for (i=1;i<=n;i++)
if (viz[i]==0)
{nr=nr+1;
parc_adancime(i);}
cout<<"are "<<nr<<" componente conexe";
getche();}
Problema 7
Se procedeaz ă astfel:
– se cite ște matricea de adiacent ă;
– toate nodurile se consider ă ini Ńial nevizitate;
– se parcurg nodurile grafului
– dac ă se g ăse ște un nod nevizitat înc ă,
– se viziteaz ă si se afiseaz ă:
-se viziteaz ă și se afi șeaz ă toate nodurile la care se poate ajunge plecând de la acest nod
51 (acest lucru se realizeaz ă printr-un apel ai procedurii parc_adancime).
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
int viz [ 100],a[20][20],i,n,m,x,y,nr;
void parc_adancime(int pl )
{int j;
viz[pl]=1; cout<<pl<<" ";
for (j =1;j<=n;j++)
if ((a[pl][j]==1) && (viz[j]==0))
parc_adancime(j);}
void main()
{ clrscr(); cout<<"n="; cin>>n;
cout<<"m="; cin>>m;
for (i=1;i<=m;i++) {cout<<" x y"; cin>>x>>y;
a[x][y]=1;
a[y][x]=1;}
for (i=1;i<=n;i++) viz[i]=0;
nr=0;
for (i=1;i<=n;i++)
if (viz[i]==0)
{nr=nr+ 1 ;
cout<< " componenta conexa cu numarul" <<nr <<" are
nodurile"<<endl;
parc_adancime(i);
cout<<endl;}
getche( );
Problema 8
Problema se reduce, pân ă la urm ă, la a afi șa toate perechile de forma (il, i2), unde il si i2 sunt noduri din
aceea și compunent ă conex ă pentru aceatsta:
– se genereaz ă toate componentele conexe:
– pentru fiecare componet ă conex ă generat ă, se afi șeaz ă toate perechile ordonate de noduri (il,i2), care s e
pot forma cu elementele sale.
ObservaŃie . Pentru a nu încurca nodurile care fac parte din c omponente conexe diferite, astfel încât s ă
afi șăm de dou ă ori acelea și noduri, proced ăm astfel:
– dup ă ce se afi șeaz ă perechile formate din nodurile unei componente con exe, se m ăresc cu 1 toate
elementele din vectorul viz, care corespund noduril or componentei afi șate, pentru a deveni 2, astfel încât
să nu fie confundate cu modurile componentei conexe c are se va determina, pentru care vectorul viz va
avea valoarea 1.
#include <conio.h>
#include <iostream.h>
#include <stdio.h>
int viz[100],a[20][20], i,n,m,x,y,i1,i2;
void parc_adancime(int pl)
{int j; viz[pl]=1;
for (j=1 ;j<= n;j++)
if ((a[pl][j]==1) && (viz[j]==0))
parc_adancime(j);}
void main()
{ clrscr();
cout<<"n="; cin>>n;
cout<<"m="; cin>>m;
for (i=1; i<=m; i++)
{cout<<"x y"; cin>>x>>y; a[x][y]=1;
a[y][x]=1;}
for (i=1;i<=n;i++) viz[i]=0;
for (i=1;i<=n;i++)if (viz[i]==0)
{ parc_adancime(i);
for (i1=1;i1<=n-1;i1++)
for (i2=i1+1 ; i2<=n; i2++)
if ((viz[i1]==1) && (viz[i2]==1))
cout<<"("<<i1<<","<<i2<
<")";
for (i1=1;i1<=n;i1++)
if (viz[i1]==1) viz[i1]=viz[i1]+1;
cout<<endl;}
getche();}
Problema 9
Sistemului de culoare i se pune în coresponden Ńă un graf neorientat, astfel:
– nodurile grafului sunt culoarele;
– muchiile grafului sunt leg ăturile între culoare.
A verifica dac ă toate culoarele fac parte din aceea și pe șter ă, înseamn ă a verifica dac ă graful asociat este
conex (adic ă este format dintr-o singur ă component ă conex ă):
– la început, nodurile sunt nevizitate;
– se aplic ă func Ńia de parcurgere a grafului, plecând de la un nod oarecare;
– dac ă, dup ă parcurgere, în graf mai sunt noduri nevizitate, nu este conex;
(Vezi problema rezolvat ă din sec Ńiunea 10)
52 cout<<"dati nodul de plecare pare adancime(pl);
ok=0;
for (i=1;i<=n;i++)
if (viz[i]==0) ok=1;
if (ok) cout<<"sunt mai multe pesteri";
else cout<<"este o singura pestera";
Problema 10
Grupului de persoane, despre care se vorbe ște i se pune în coresponden Ńă un graf neorientat, astfel:
– nodurile grafului sunt persoanele;
– muchiile grafului sunt preciz ările ideii c ă dou ă persoane sunt prietene (în mod direct).
A determina grupurile de persoane, cu un num ăr maxim de membri, între care se pot stabili priete nii,
directe sau indirecte, se reduce la a detennina com ponentele conexe cu cele mai multe noduri (este o
problem ă de maxim). Acest lucru se realizeaz ă astfel:
– pe m ăsur ă ce se determin ă componenta conex ă, cu num ărul nr,
– se determin ă num ărul de noduri ale sale în comp[nr] și i se p ăstreaz ă nodurile în mul Ńimea varfuri[nr]
– dac ă comp[nr]> max (max – cel mai mare num ăr înregistrat pân ă în prezent) devine max
– se afi șeaz ă nodurile tuturor componentelor conexe care au max noduri.
Aten Ńie! Func Ńia parc_adancime are un parametru în plus (nr), pe care îl folose ște în scopul de a diferen Ńia
elementele diferitelor componente conexe, astfel:
– la fiecare apel, elementele care au fost vizitate sunt marcate cu nr (viz[i]=nr).
#include <conio.h>
#include <iostream.h>
#include <stdio.h> t
typedef int sir [ 100];
typedef int mat[20][20];
mat a;
sir viz, comp;
int i, n , m , x, y, max,j, nr;
mat varfuri;
void parc_adancime(int pl, int nr)
{ int j;
viz[pl]=nr;
for (j=1;j<=n;j++)
if ((a[pl][j]==1) && (viz[j]==0))
parc_adancime(j,nr);}
void main()
{ clrscr();
cout<<"n="; cin>>n;
cout<<"m="; cin>>m;
for (i=1;i<=m;i++)
{ cout<<"x y"; cin>>x>>y;
a[x][y]=1; a[y][x]=1;}
for (i=1;i<=n;i++) viz[i]=0;
max=0; nr=0;
for (i=1;i<=n;i++)
if (viz[i]==0) { nr=nr+ 1;
parc_adancime(i,nr);
comp[nr]=0;
for(j=1;j <=n;j++)
if (viz[j]==nr)
{ comp[nr]=comp[nr]+1;
varfuri[nr][comp[nr]]=j;}
if (comp[nr]>max)
max=comp[nr];}
for (i=1;i<=nr;i++)
if (comp[i]==max)
{ cout<<i<<":::::";
for (j=1;j<=comp[i];j++)
cout<<varfuri[i][j]<<" ";
cout<<" ";}
getch();
}
11. Cicluri Hamiltoniene
Problema 1
L=[1, 3, 5, 4, 2]: este lan Ń hamiltonian;
C=[5, 4, 2, 3, 1, 5] : este ciclu hamiltonian;
Problema 2
Dac ă n ≥3 și d(x) ≥n/2 pentru orice nod x, atunci graful este hamilton ian.
……………………
int grad(int i)
{int s, j;
s=0;
for (j=1;j<=n;j++)
53 s=s+a [i][j];
return s;}
…………………….
ok 1=( n>=3 );
ok2=1;
for (i=1;i<=m;i++)
if (! (grad(i)>=n/2)) ok2=0;
ok==ok 1 && ok2;
if (ok) cout<<"se verifiica conditiile teoremei ";
else cout<<"nu se verifica conditiile teoremei";
……………………..
Problema 3
Demonstr ăm acest lucru folosind metoda induc Ńiei matematice. Pentru a u șura scrierea, vom nota cu H(n)
num ărul ciclurilor hamiltoniene ale grafului K n în baza acestei nota Ńii, enun Ńul problemei care s ă
demonstr ăm c ă:( )()32! 1≥∀−= nnnH
I. Verificare:
Pentru n= 3 ( ) ( )()12! 2
2! 1 33 ==−= =HnH (adev ărat, pentru c ă într-un graf complet cu trei vârfuri este
un singur ciclu hamiltonian)
II. Demonstratia P(n) →P(n+ l )
(n_1)!
P(n) : ( )()
2! 1−=nnH
P(n+l) : ( )( )
2! 111−+=+nnH
Altfel spus, dac ă se știe că num ărul ciclurilor hamiltoniene în graful K n este (n-1)!/2, s ă se demonstreze
că num ărul ciclurilor harniltoniene în K n+1 este n!/l.
Având la baz ă faptul că din fiecare ciclu hamiltonian din K n se pot ob Ńine n cicluri hamiltoniene distincte
în K n+1 prin intercalarea nodului n+l în toate cele n locu ri posibile (între dou ă noduri succesive; ex: x 1 x 2
… x n x 1(între x 1 x 2, x 2 x 3, ..)), putem spune c ă în K n+1 sunt n ori num ărul ciclurilor din K n cicluri
hamiltoniene, ceea ce ne permite s ă scriem:
( ) ( )()()( )
2! 11
2!
2! 11−+= =−⋅= ⋅=+n n nnnHn nH
Problema 4
Având la baz ă:
1) fiecare ciclu elementar este un ciclu hamiltonian in subgraful complet indus de vâr furile sale și invers,
fiecare ciclu hamiltonian dintr-un subgraf cu k vâr furi este ciclu elementar în G.
2) într-un graf complet cu k vârfuri sunt ()
2! 1−kcicluri hamiltoniene;
3) într-un graf cu n vârfuri pot exista k
nC subgrafuri cu k noduri:
tragem concluzia:
Într-un graf cu n vârfuri, num ărul ciclurilor elementare este egal cu:
() () () ()
( )()
( )()
( ) ( )∑∑ ∑∑
== = =
+− −=−
− −=−
−=−=−++−+−
n
kn
kn
kn
kk
nn
n n n
kkn nnk
kn kkn k
knkn kCnC C C
33 3 34 3
1 … 1
212! 1
! )! 1 (!
2! 1
! !!
2! 1
2! 1… 2! 1 4
2! 13
Problema 5
Problema se face la fel ca și problema determin ării ciclurilor hamiltoniene, pe care am prezentat-o în
sec Ńiunea 11., numai că în situatia de fa Ńă , va trebui ca în loc s ă se afi șeze ciclurile s ă se dea r ăspunsul da
sau nu. Acest lucru se poate face astfel:
54 Se folose ște o variabil ă boolean ă ok, care la începutul programului are valoarea fal se (se presupune ca nu
exist ă cicluri), iar în procedura de afi șare s ă primeasc ă valoarea true (adic ă s-a g ăsit un ciclu hamiltonian;
eventual, la primul apel al procedurii Afis s ă se renun Ńe la generarea ciclurilor care ar mai putea fi g ăsite)
și s ă se afi șeze înainte de terminarea programului.
Altfel:
Se procedeaz ă la fel ca la problema 2 (adic ă, se verific ă dac ă sunt satisf ăcute condi Ńiile teoremei
prezentat ă în sec Ńiunea 11)
Problema 6
Asociem grupului de persoane, despre care se vorbe ște în enun Ńul problemei, graf neorientat definit astfel:
nodurile grafului reprezint ă persoanele iar muchia între nodurile i și j reprezint ă precizarea ideii c ă
persoanele i și j sunt prietene, adic ă în rela Ńie de nedu șmănie. Din ipoteza că fiecare cavaler are cel mult
(n-1) du șmani, rezult ă c ă pentru fiecare cavaler exist ă cel pu Ńin 2n-(n-1)=(n+1) ≥2n/2 cavaleri cu care
acesta se afl ă în rela Ńie de nedu șmănie, adic ă de prietenie. łinând cont de cele spuse mai sus, putem trage
concluzia c ă în graful asociat grupului de persoane sunt veriti cate condi Ńiile teoremei prezentat ă în
sec Ńiunea 11. conform c ăreia în graful respectiv exist ă cel pu Ńin un ciclu hamiltonian. Ciclului
hamiltonian îi asociem o a șezare a cavalerilor la masa rotund ă în condi Ńiile cerute.
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: 1. No Ńiunea de graf neorientat Defini Ńie. SSee nnuummeeșșttee ggrraaff nneeoorriieennttaatt oo ppeerreecchhee oorrddoonnaattăă ddee mmuullŃŃiimmii… [618875] (ID: 618875)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.