2. Parcurgere
3. Lanțuri
4. Grafuri conexe
5. Cicluri
6. Aplicații
7. Grafuri orientate. Memorare, parcurgere, circuite
8. Graf complet și graf turneu
9. Graf tare conex
10. Drumuri de cost minim. Algoritmii Roy-Floyd și Dijkstra
11. Aplicații
Grafuri neorientate
Definiții
Un graf este o colecție (mulțime) de entități discrete (atomice, punctuale) numite noduri sau vârfuri, dintre care unele (sau toate) se pot afla în anumite relații două câte două. Grafurile sunt deci, privite din punct de vedere matematic, abstract, duplete
G=(V, E)
unde V este o mulțime finită și nevidă, ale cărei elemente se numesc noduri, iar E este o mulțime de perechi (v1, v2) formate din elemente ale mulțimii V. Dacă perechile (v1, v2) sunt neordonate (nu contează poziția lor în pereche), graful se numește neorientat, iar perechile (v1, v2) se numesc muchii. Dacă perechile sunt ordonate (contează care e primul și care e al doilea), graful este orientat iar perechile (v1, v2) se numesc în acest caz arce.
Nodurile și relațiile dintre ele se pot figura grafic prin puncte și linii, în felul următor:
Fig. 1 graf neorientat format din 6 noduri și 4 muchii.
Din fig. 1 se vede că nodurile sunt numerotate, și în plus nu toate nodurile pot fi legate între ele prin muchii. V={1, 2, 3, 4, 5, 6}, E={(1, 2), (2, 3), (4, 5), (5, 6)}. Litera E provine de la cuvântul englezesc edge = muchie.
Numărul nodurilor se notează cu n, iar numărul muchiilor se notează cu m.
Două noduri distincte pot fi unite prin cel mult o singură muchie. Acest fapt este evident din definiția grafului, deoarece elementele mulțimii E ={(v1, v2), …} sunt distincte între ele, deci nu pot exista două perechi (v1, v2) ci numai una singură.
Noduri adiacente. Două noduri i și j sunt adiacente dacă există muchie între ele, deci dacă există muchia (vi, vj). Muchia dintre ele se numește muchie incidentă cu nodurile i și j.
Gradul unui nod v este numărul muchiilor incidente la el și se notează d(v).
Suma gradelor unui graf este dublul numărului de muchii:
d1+d2+...+dn = 2m.
2. Reprezentarea în memorie a grafurilor
De regulă, aplicațiile la grafuri pornesc de la un fișier text în care sunt scrise pe rânduri consecutive perechile de noduri care delimitează muchiile, iar pe prima linie a fișierului este trecut numărul de noduri n.
Fișierul text:
6
1 2
1 3
1 5
2 3
3 4
4 5
Matricea de adiacență
Se construiește în memorie un tablou A[i, j] unde elementele a(i,j) au semnificația: a(i, j) = 1, dacă (i, j) ∈E sau 0 dacă (i, j) ∉E. Pentru graful de mai sus, matricea arată așa:
- Elementele de pe diagonala principală sunt 0.
- Matricea este simetrică.
- Suma elementelor de pe coloana j este gradul nodului j, d(j).
Programul următor crează un fișier reprezentând lista muchiilor, apoi citește acest fișier și crează matricea de adiacență. În practica obișnuită, fișierul se crează separat cu notepad.
/*Optiunea W=programul creaza un fisier text continand pe prima linie
doua numere naturale reprezentand n=umarul nodurilor si m=numarul muchiilor
unui graf neorientat.
Urmeaza apoi m linii continand doua numere naturale intre 1 si n
separate prin spatiu reprezentand muchiile.
Optiunea R=programul citeste fisierul creat anterior si genereaza matricea
de adiacenta a grafului.
*/
#include <iostream>
#include <fstream>
#include <string.h>
#include <stdio.h>
#include <limits.h>
int A[50][50];
const int infinit=INT_MAX;
int nod,arce,nod1,nod2,pondere;
using namespace std;
void wr()
{
char optiune[1];
cout<<"w (scrie fisierul) sau w (citeste fisierul) ";
{cin>>optiune;}
while (optiune[0]!='r' && optiune[0]!='w') ;
switch (optiune[0])
{
case ('w') :{scrie(); break;}
case ('r') :{citeste(); break;}
}
}
*/
void scrie()
{
fstream ograf("graf.grf",ios::out);
cout<<endl<<"numar noduri= ";cin>>nod;
cout<<endl<<"numar muchii= "; cin>>arce;
ograf<<nod<<" "<<arce<<endl;
for(int i=1;i<=arce;i++)
{
cout<<endl<<"nod1: ";cin>>nod1;
cout<<endl<<"nod2: ";cin>>nod2;
ograf<<nod1<<" "<<nod2<<endl;
}
}
void citeste()
{
ifstream igraf("graf.grf",ios::in);
igraf>>nod>>arce;
for (int i=1;i<=nod;i++)
for(int j=1;j<=nod;j++)
A[i][j]=0;
for(int i=1;i<=arce;i++)
{
igraf>>nod1>>nod2;
A[nod1][nod2]=1;
A[nod2][nod1]=1;
}
}
Liste de adiacență alocate static.
Se crează în memorie un vector cu n componente numit start și o matrice T cu 2 linii și 2m coloane cu următoarele semnificații:
- Start[i] specifică coloana din T unde începe lista nodurilor adiacente cu i. Dacă start[i]=0, nodul i nu are noduri adiacente.
- T[0][i] reprezintă un nod al listei nodurilor adiacente
- T[1][i] reprezintă legătura către următorul nod adiacent (indicele coloanei care urmează în listă). Dacă conține 0, atunci acesta este ultimul element din lista succesorilor.
Listele sunt următoarele (pentru fiecare nod există o listă):
Nodul 1 -> lista începe în coloana 5 -> nodul adiacent 5, următorul nod adiacent se află în coloana 3 -> nodul al doilea din listă este 3, iar următorul se află în coloana 1 -> nodul al 3-lea este 2, iar acesta este ultimul din listă.
1-> 2, 3, 5
2->1, 3
3-> 1, 2, 4
4->3, 5
5->1, 4
6->
Liste de adiacență alocate dinamic
Se pornește tot de la un vector start cu n elemente, dar fiecare element i al vectorului start conține adresa de start a listei vecinilor nodului i.
Programul următor este un exemplu complet privind toate modurile de reprezentare internă a unui graf: matrice de adiacență, liste de adiacență alocate static, liste de adiacență alocate dinamic, lista muchiilor. Programul afișează apoi pentru verificare structura de date realizată.
#include <iostream>
#include <fstream>
#include <stdio.h>
using namespace std;
fstream f("graf.txt",ios::in);
void creare_la_static();
void creare_la_dinamic();
void afisare_la_static();
void afisare_la_dinamic();
void creare_mat_adiacenta();
void afisare_ma();
void creare_lista_muchii();
void afisare_lm();
int A[20][20];
int start[20];
int T[2][40];
int m,n,i,j,k,u;
struct Nod
{
int nd;
Nod* urmator;
};
struct Nod *wstart[20];
struct muchie
{
int x,y;
};
muchie V[20];
int main()
{
creare_mat_adiacenta();
afisare_ma();
f.clear();
f.seekg(0,f.beg);
creare_la_static();
afisare_la_static();
f.clear();
f.seekg(0,f.beg);
creare_la_dinamic();
afisare_la_dinamic();
f.clear();
f.seekg(0,f.beg);
creare_lista_muchii();
afisare_lm();
cin>>n;
}
void creare_mat_adiacenta()
{
f>>n;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)A[i][j]=0;
while(!f.eof())
{
f>>i>>j;
A[i][j]=1;
A[j][i]=1;
}
}
void afisare_ma()
{
for(i=1;i<=n;i++)
{
cout<<"Matricea de adiacenta: lista nodurilor adiacente cu nodul "<<i<<": ";
for(j=1;j<=n;j++)
{
if(A[i][j])cout<<j<<" ";
}
cout<<endl;
}
cout<<endl;
}
void creare_la_static()
{
k=0;
f>>n;
for(i=1;i<=n;i++)start[i]=0;
for(i=1;i<=39;i++)
{
T[0][i]=0;T[1][i]=0;
}
while(f>>i>>j)
{
k++;
T[0][k]=j;
T[1][k]=start[i];
start[i]=k;
k++;
T[0][k]=i;
T[1][k]=start[j];
start[j]=k;
}
}
void afisare_la_static()
{
for(i=1;i<=n;i++)
{
cout<<"Lista de adiacenta statica: nodurile adiacente cu nodul "<<i<<": ";
u=start[i];
do
{
cout<<T[0][u]<<" ";
u=T[1][u];
}
while(u);
cout<<endl;
}
cout<<endl;
}
void creare_la_dinamic()
{
f>>n;
for(i=1;i<=n;i++)wstart[i]=0;
Nod* u;
k=1;
while(f>>i>>j)
{
u=new Nod;
u->nd=j;
u->urmator=wstart[i];
wstart[i]=u;
u=new Nod;
u->nd=i;
u->urmator=wstart[j];
wstart[j]=u;
}
}
void afisare_la_dinamic()
{
Nod* u;
for(i=1;i<=n;i++)
{
cout<<"Lista de adiacenta dinamica: nodurile adiacente cu nodul "<<i<<": ";
u=wstart[i];
while(u)
{
cout<<u->nd<<" ";
u=u->urmator;
}
cout<<endl;
}
cout<<endl;
}
void creare_lista_muchii()
{
f>>n;
k=1;
while(f>>i>>j)
{
V[k].x=i;
V[k].y=j;
k++;
}
m=k;
}
void afisare_lm()
{
for(i=1;i<=n;i++)
{
cout<<"Lista muchiilor: nodurile adiacente cu nodul "<<i<<": ";
for(j=1;j<=m;j++)
if(V[j].x==i)cout<<V[j].y<<" ";
else
if(V[j].y==i)cout<<V[j].x<<" ";
cout<<endl;
}
cout<<endl;
}
Fig. 3 graf complet.
TEOREMĂ: Un graf neorientat conex în care m=n-1, unde n=numărul de noduri, m=numărul de muchii, nu conține niciun ciclu.
Demonstrație: Prin inducție. Un graf cu 1 nod are 0 muchii, deci respectă afirmația. Dacă adăugăm un al doilea nod, acesta se leagă printr-o muchie nouă la graful precedent, deci noul graf are 2 noduri și 1 muchie și nu conține cicluri. Dacă adăugăm al treilea nod și îl unim cu graful printr-o muchie nouă, acest nou nod are gradul 1, deci nu este parte din niciun ciclu. Dacă la un graf cu n-1 noduri și n-2 muchii care este conex și nu conține cicluri adăugăm un nod nou, unit printr-o singură muchie de graful precedent, atât numărul de noduri cât și numărul de muchii cresc cu o unitate, deci se respectă relația m=n-1.
Teoremă: un graf neorientat conex în care m>n-1 conține cel puțin un ciclu.
Demonstrație: Un graf conex cu n noduri și m=n-1 muchii nu conține niciun ciclu. Deoarece graful este conex, există un lanț între oricare două noduri, în particular și între nodurile a și b, pe care vrem să le unim printr-o muchie nouă. Dacă la acest graf adăugăm o muchie nouă între a și b, vor fi n noduri și n muchii. Cum lanțul existent înainte între a și b se închide, acesta devine ciclu.
Problemă: Fiind dat un graf, să se scrie un program care decide dacă graful conține cel puțin un ciclu.
/*algoritmul lui Lee
Matricea drumurilor unui graf orientat este o matrice nXn, care are 1 pentru MD[i][j] dacă există drum de la nodul i la nodul j, și 0 în cazul în care nu există.
Fiind dat un graf turneu, se cere să se afișeze un drum elementar care trece prin toate vârfurile grafului.
Rezolvare:
#include <iostream>
#include <fstream>
#include <conio.h>
using namespace std;
fstream f("graf.txt",ios::in);
int MA[25][25];
int n;
int sf;
int sol[25];
void shift_right(int poz) //face un loc liber in vectorul sol
// pe pozitia sol[poz], muand la dreapta cu un loc
//restul sirului cuprins intre poz si sf
{
sf++;
for(int i=sf;i>poz;i--)
sol[i]=sol[i-1];
}
int main()
{
int i,j;
f>>n;
while(f>>i>>j)
MA[i][j]=1;
sol[1]=1;
sf=1;
for(int p=2;p<=n;p++)
{
//testez situatia 1: exista arc de la nodul p la sol[1],
//nodul p se insereaza la inceputul lui sol
if(MA[p][sol[1]]==1)
{
shift_right(1);
sol[1]=p;
}
//testez situatia 2: exista arc de la ultimul nod din sol catre nodul p
//nodul p se insereaza in urma ultimului nod din sol
else if(MA[sol[sf]][p]==1)
{
sf++;
sol[sf]=p;
}
//daca nu suntem nici in situatia 1, nici in situatia 2,
//rezulta ca suntem in situatia 3, in care se va cauta o succesiune de doua noduri
//in vectorul sol, care au sagetile opuse, intre care
//se va intercala nodul p.
else
{
bool gasit=false;
for(int i=2;i<=sf&&!gasit;i++)
{
//testam sensul sagetii dintre doua noduri sucesive si nodul de inserat p
if(MA[sol[i-1]][p]==1&&MA[p][sol[i]]==1)
{
//am gasit doua noduri cu arce de sens opus
//nodul p se va insera intre ele
shift_right(i);
sol[i]=p;
gasit=true;
}
}
}
}
//afisare lant
for(int i=1;i<=n;i++)
cout<<sol[i]<<" ";
getch();
}
//determina componentele tare conexe dintr-un GO
#include <iostream>
#include <fstream>
using namespace std;
fstream f("ctc.txt",ios::in);
int A[50][50],D[50][50],S[50],suc[50],pred[50];
int n,nctc;
int i,j;
//metoda matricii drumurilor\
matricea D[i][j] are 1 daca exista drum de la nodul i la nodul j\
se completeaza prin n parcurgeri DF\
in vectorul de selectie S[n] se pune S[1]=nctc=1 apoi pt toti j pt care D[1][j]=D[j][1]=1\
se listeaza\
se increm nctc si se repeta pt primul i cu S[i]=0.\
complexitate n**3\
metoda parcurgerii inapoi\
se parcurge inainte pt primul i cu S[i]=0 marcandu-se in suc[k] nodurile atinse\
apoi se parcurge inapoi marcandu-se in pred[k] nodurile atinse\
nodurile care au suc[k]=pred[k]=1 fac parte din aceleasi ctc\
se listeaza iar celelalte se pune Suc[k]=0.\
se repeta pana cand toate elem din S sunt =0
void drum(int nod)
{
for(int k=1;k<=n;k++)
{
if(A[nod][k]==1&&S[k]==0)
{
S[k]=1;
D[i][k]=1;
drum(k);
}
}
}
void inainte(int nod)
{
for(int k=1;k<=n;k++)
{
if(A[nod][k]==1&&suc[k]==0)
{
suc[k]=nctc;
inainte(k);
}
}
}
void inapoi(int nod)
{
for(int k=1;k<=n;k++)
{
if(A[k][nod]==1&&pred[k]==0)
{
pred[k]=nctc;
inapoi(k);
}
}
}
int main()
{
f>>n;
while(f>>i>>j)
{
A[i][j]=1;
}
//metoda matricii drumurilor
cout<<"metoda matricii drumurilor"<<endl;
for(i=1;i<=n;i++)
{
//nodul de start i
for(j=1;j<=n;j++)S[j]=0;
S[i]=1;
drum(i);
}
nctc=0;
for(j=1;j<=n;j++)S[j]=0;
for(int i=1;i<=n;i++)
{
if(S[i]==0)
{
nctc++;
cout<<endl<<"componenta "<<nctc<<": "<<i<<" ";
for(int j=1;j<=n;j++)
{
if(D[i][j]==1&&D[j][i]==1)
{
cout<<j<<" ";
S[j]=1;
}
}
}
}
//metoda parcurgerilor inapoi
cout<<endl<<"metoda parcurgerilor inapoi"<<endl;
int k=1;
nctc=0;
while(k<=n)
{
if(suc[k]==0)
{
nctc++;
cout<<endl<<"componenta "<<nctc<<": ";
suc[k]=pred[k]=nctc;
inainte(k);
inapoi(k);
for(int u=1;u<=n;u++)
if(suc[u]==nctc&&pred[u]==nctc)
cout<<u<<" ";
else
if(suc[u]!=pred[u])
suc[u]=pred[u]=0;
}
k++;
}
}
SOLUȚIA 2
/* se determina componentele tare conexe dintr-un GO
noutatea este reprezentarea sub forma de matrice de adiacenta alocata dinamic si functie cu parametru pointer la tablou.
se construieste simultan si matricea transpusa
*/
#include <iostream>
#include <fstream>
#include <stdlib.h> //realloc
using namespace std;
fstream f("date.in",ios::in);
int n,nrc;
int (*A)[20],(*T)[20];
int S[20], P[20]; //vectori de selectie
void DFS(int v,int (*mat)[20],int(*vec))
{
for(int i=1;i<=n;i++)
{
if(mat[v][i]==1&&vec[i]==0)
{
vec[i]=nrc;
DFS(i,mat,vec);
}
}
}
int main()
{
f>>n;
A=new int[20][20];
T=new int[20][20] ;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
A[i][j]=T[i][j]=0;
int a,b;
while(f>>a>>b)
{
A[a][b]=1;
T[b][a]=1;
}
nrc=0;
for(int i=1;i<=n;i++)
{
if(S[i]==0)
{
nrc++;
S[i]=nrc;
DFS(i,A,S); //se parcurge DFS lista directa A completandu-se vectorul de selectie directa S
for(int j=1;j<=n;j++)P[j]=0;
P[i]=nrc;
DFS(i,T,P); //se parcurge transpusa completandu-se vectorul de selectie inversa P
for(int j=1;j<=n;j++) // se sterg selectiile care nu corespund aceleiasi componente
if(S[j]==nrc&&P[j]!=nrc)
{
S[j]=0;
}
}
}
for(int i=1;i<=nrc;i++)
{
cout<<endl<<"componenta "<<i<<": ";
for(int j=1;j<=n;j++)
if(S[j]==i)
cout<<j<<" ";
}
}
//cauta drumul optim (de cost minim) intr-un graf orientat\
reprezentat prin matricea ponderilor in forma 1
#include <iostream>
#include <fstream>
using namespace std;
fstream f("rf.txt",ios::in);
int A[10][10];
int n,i,j,k,a,b;
int nrmax=0xFFFF;
int drum(int p,int q)
{
int i=1;
bool gasit=false;
while(!gasit&&(i<=n))
{
if(i!=p&&i!=q&&A[p][i]+A[i][q]==A[p][q])
{
gasit=true;
drum(p,i);
drum(i,q);
}
i++;
}
if(!gasit)
cout<<q<<" ";
}
int main()
{
f>>n>>a>>b;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j)A[i][j]=nrmax;
else
A[i][j]=0;
}
while(f>>i>>j>>k)
A[i][j]=k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(A[i][j]>A[i][k]+A[k][j])
A[i][j]=A[i][k]+A[k][j];
}
cout<<endl<<A[a][b];
cout<<endl;
cout<<a<<" ";
drum(a,b);
// cout<<b;
}
//cauta drum optim de cost minim intre un nod si celelalte noduri\
Tipuri particulare de grafuri
Graf complet: un graf neorientat în care oricare două noduri sunt adiacente. Se notează cu simbolul K𝒏.
Proprietăți:
- Într-un graf complet, gradul oricărui nod este n-1.
- Într-un graf complet există relația m=n(n-1)2
- Există 2n(n-1)/2grafuri neorientate cu n noduri.
Graf parțial.
Un graf parțial al unui graf neorientat dat G=(V, E) este un graf G₁=(V, E₁), unde
E₁E. Un graf parțial al unui graf G este el însuși sau se obține din G prin suprimarea unor muchii.
Subgraf
Un subgraf al unui graf neorientat G=(V, E) este un graf G₁=(V₁, E₁), unde
V₁V, E₁E iar muchiile din E₁ sunt toate muchiile din E care sunt incidente numai la muchii din mulțimea V₁.
Un subgraf al unui graf G este el însuși sau se obține din el prin suspendarea anumitor noduri și a tuturor muchiilor incidente cu acestea.
Parcurgerea grafurilor
Pargurgerea grafurilor este o modalitate de vizitare a nodurilor. Algoritmii de parcurgere sunt foarte importanți, deoarece toate aplicațiile grafurilor se bazează pe o parcurgere a lor. Există două modalități diferite de parcurgere: parcurgerea în lățime (BFS - Breadth First Search) și parcurgerea în adâncime (DFS - Depth First Search).
Parcurgerea în lățime
- Se începe de la un anumit nod i, pe care îl considerăm vizitat;
- Se vizitează apoi toate nodurile adiacente cu el - fie ele j₁, j₂, … vizitate în această ordine;
- Se vizitează toate nodurile adiacente cu j₁, apoi cu j₂;
- …
- Parcurgerea continuă în acest mod până când au fost vizitate toate nodurile accesibile.
Algoritmul:
Parcurgerea BFS se efectuează prin utilizarea structurii numitî coadă (queue), având grijă ca un nod să fie utilizat o singură dată. Atunci când un nod este introdus în coadă, se marchează ca vizitat. Coada se alocă printr-un vector Q. Coada are un indice de început (start_q) și unul de sfârșit (end_q). Marcarea nodurilor vizitate se face prin setarea elementelor altui vector S (vector de selecție) pe 1.
- Nodul de pornire este introdus în coadă și este marcat ca vizitat.
- Cât timp coada este nevidă
- Se introduc în coadă toate nodurile adiacente cu el care nu au fost marcate (vizitate) și se marchează;
- Se afișează;
- Se extrage din coadă;
//parcurgere BFS a unui GrNeor reprezentat prin MA
#include <iostream>
#include <fstream>
using namespace std;
fstream f("date.in",ios::in);
int n, i, j, ic=0, sfc=1;
int A[50][50];
int Q[50], S[50];
int main()
{
//creare MA
f>>n;
while(f>>i>>j)
{
A[i][j]=A[j][i]=1;
}
//initializare coada
Q[0]=1;
S[Q[0]]=1;
cout<<"parcurgere BFS a unui GrNeor reprezentat prin MA"<<endl;
//parcurgere si afisare
while (ic<sfc)
{
int k=Q[ic++];
cout<<k<<" ";
for(int i=1;i<=n;i++)
{
if(A[k][i]==1&&S[i]==0)
{
S[i]=1;
Q[sfc++]=i;
}
}
}
}
Parcurgerea în adâncime
- Se începe cu un nod i, care se consideră vizitat;
- După ce se vizitează un nod, se vizitează primul dintre nodurile adiacente cu el care nu a mai fost vizitat, apoi următorul nod adiacent, până când se vizitează toate nodurile adiacente cu el;
- Parcurgerea continuă în acest fel până se vizitează toate nodurile accesibile.
Pentru același graf din fig. 7, parcurgerea în adâncime pornind de la nodul 1 este:
1 3 7 6 2 5 4
Programul următor realizează o parcurgere BFS a unui graf reprezentat prin liste de adiacență alocate static:
#include <iostream>
#include <fstream>
using namespace std;
fstream f("date.in",ios::in);
int start[50];
int T[2][50], S[50];
int n,i,j,k=0, nod=1;
void df(int);
int main()
{
f>>n;
while(f>>i>>j)
{
k++;
T[0][k]=start[i];
T[1][k]=j;
start[i]=k;
k++;
T[0][k]=start[j];
T[1][k]=i;
start[j]=k;
}
nod=1;
S[nod]=1;
cout<<nod<<" ";
df(nod);
}
void df(int nod)
{
int p=start[nod];
while(p)
{
int v=T[1][p];
if(S[v]==0)
{
cout<<v<<" ";
S[v]=1;
df(v);
}
p=T[0][p];
}
}
TEMĂ: scrieți programul de parcurgere BFS pentru un graf reprezentat prin matrice de adiacență.
Complexitatea algoritmilor de parcurgere.
Parcurgerea BFS sau DFS a unui graf reprezentat prin matrice de adiacență se realizează în O(n²). Dacă graful este reprezentat prin liste de adiacență, complexitatea este O(m).
Deoarece m<n², reprezentarea prin LA este mai convenabilă. Totuși, reprezentarea prin MA este mai simplă.3. Lanțuri
Lanțuri
Un lanț este o succesiune de noduri cu proprietatea că oricare două noduri vecine sunt adiacente. Dacă lanțul conține numai noduri distincte, lanțul se numește elementar.
Expresia matematică a acestei definiții este următoarea:
Dacă G=(V, E) este un graf, un lanț L=[v₁, v₂, …, v𝐧] este o succesiune de noduri adiacente, adică (v₁, v₂)∈E, (v₂ , v₃) ∈E, etc.
Altfel spus, un lanț este o succesiune de muchii care au două câte două un capăt comun.
Vârfurile v₁ și v𝐧 se numesc extremitățile lanțului.
Problemă: Fiind dat un graf și două noduri ale sale a și b, să se scrie un program care decide dacă între ele există un lanț sau nu, iar dacă există, să se afișeze lanțul.
Rezolvare: Există un lanț de la a la b dacă și numai dacă o parcurgere DFS sau BFS care pornește de la nodul a va ajunge să viziteze nodul b. Reținerea traseului de la a la b se va face cu ajutorul uui vector special, numit vectorul taților, sau vectorul referințelor ascendente T[ ]. Fiecare metodă de parcurgere, pornind de la un nod j, va selecta un nod adiacent i.
T[i]={ j, dacă i este descendent al lui j
0, dacă i este extremitatea inițială
Drumul (lanțul) se va reconstitui astfel: se afișează b, apoi T[b], apoi T[[b]] și așa mai departe, până când se obține valoarea 0. Ordinea nodurilor se poate afișa și în sensul celălalt, scriind o funcție recursivă.
Programul următor caută un lanț într-un graf neorientat reprezentat prin matricea de adiacență, prin ambele metode de parcurgere, BFS și respectiv DFS:
void lant_DF()
{
cout<<endl<<"Lant prin parcurgere DF intre nodul "<<noda<<" si nodul "<<nodb<<": ";
for(i=1;i<=n;i++){S[i]=0;Q[i]=0;}
visit_lant_ma(noda,0);
if(!Q[nodb])
cout<<endl<<"Nu exista lant intre "<<noda<<" si "<<nodb<<endl;
else
print_za(nodb);
}
void lant_BF()
{
cout<<endl<<"Lant prin parcurgere BF intre nodul "<<noda<<" si nodul "<<nodb<<": ";
for(i=1;i<=n;i++){S[i]=0;Q[i]=0;}
i_c=0;
s_c=1;
coada[i_c]=noda;
Q[noda]=0;
do
{
if(!S[coada[i_c]])
{
S[coada[i_c]]=1;
pune_vecini_in_coada_ma(coada[i_c]);
}
i_c++;
}
while(i_c<s_c);
if(!Q[nodb])
cout<<endl<<"Nu exista lant intre "<<noda<<" si "<<nodb<<endl;
else
print_za(nodb);
}
Funcțiile apelate sunt următoarele:
void visit_lant_ma(int nod,int tata)
{
if(!S[nod])
{
Q[nod]=tata;
S[nod]=1;
for(j=1;j<=n;j++)
if(A[nod][j])visit_lant_ma(j,nod);
}
}
void pune_vecini_in_coada_ma(int i)
{
for(k=1;k<=n;k++)
if(A[i][k])
{
coada[s_c]=k;
if(!S[k])Q[k]=i; //lant
s_c++;
}
}
void print_za(int k)
{
cout<<k<<" ";
if(Q[k]==0)return;
else
print_za(Q[k]);
}
Datele folosite au semnificațiile următoare:
int coada[20]; //vectorul pentru implementarea cozii - BFS.
int S[20],Q[20]; // vector de selecție și vector de tați
int i_c,s_c,noda=2,nodb=5; //indici început și sfârșit coadă
int A[20][20]; //matricea de adiacență
Observație foarte importantă:
Parcurgerea în lățime produce lanțul de lungime minimă. Parcurgerea BFS furnizează vecinii în ordinea depărtării de nodul rădăcină.
Matricea lanțurilor
Se pune întrebarea de a afla, pentru fiecare nod i, nodurile j pentru care există un lanț de la i la j.
Rezultatul acestei aplicații poate fi reținut într-o matrice pătratică nXn, pentru care fiecare element A[i][j] va fi 1 dacă există lanț de la i la j, și 0 dacă nu există.
Exercițiu:
Scrieți un program care calculează matricea lanțurilor unui graf neorientat.
4. Grafuri conexe
Grafuri conexe
Un graf neorientat G=(V, E) este conex dacă pentru orice pereche de noduri x, y aparținând la V, există un lanț în care extremitatea inițială este x și extremitatea finală este y.
Un graf alcătuit dintr-un singur nod este conex.
Problemă: Fiind dat un graf, să se scrie un program care să decidă dacă graful este conex sau nu.
Rezolvare: Se parcurge graful prin oricare din modalități, pornind de la oricare dintre noduri. Dacă în urma parcurgerii se vizitează toate nodurile, atunci graful este conex.
Întrebare: cum putem ști dacă s-au vizitat toate nodurile?
Componente conexe
Definiție
Fie G=(V, E) este un graf conex și G₁=(V₁, E₁) un subgraf al său. G₁ este o componentă conexă a lui G dacă:
- Oricare ar fi x și y din V₁, există lanț de la x la y (G₁ este conex)
- Nu există un alt subgraf al lui G, G₂=(V₂, E₂) cu V₁ inclus în V₂ care îndeplinește condiția 1 (dacă mai adăugăm un nod la G₁ acesta nu mai este conex, cu alte cuvinte G₁ este maximal în raport cu proprietatea de conexitate).
Exemplu: Graful din fig. 10 are două componente conexe.
Problemă: Fiind dat un graf oarecare, se cere să se afișeze nodurile fiecărei componente conxe.
Rezolvare: Se parcurge graful prin oricare metodă. Dacă în urma parcurgerii mai rămân noduri nevizitate, se reia parcurgerea începând cu unul din nodurile nevizitate. Procesul se reia până când nu mai rămân noduri nevizitate.
Soluția 1, cu matrice de adiacență
#include <iostream>
#include <fstream>
using namespace std;
fstream f("date.in",ios::in);
int n,i,j,nrcomp=0;
int A[20][20];
int S[20];
void df(int nod)
{
S[nod]=1;
for(int i=1;i<=n;i++)
{
if(A[nod][i]==1&&S[i]==0)
{
cout<<i<<" ";
df(i);
}
}
}
int main()
{
f>>n;
while(f>>i>>j)
{
A[i][j]=1;
}
for(i=1;i<=n;i++)
{
if(S[i]==0)
{
nrcomp++;
cout<<endl<<"componenta conexa "<<nrcomp<<": "<<i<<" ";
df(i);
}
}
}
Soluția 2, cu liste de adiacență alocate static
/* sa se determine componentele conexe ale unui graf neorientat
graful este reprezentat prin LA statice
In vectorul de selectie S se memoreaza numarul comp conexe
se parcurge in adancime DFS
*/
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
fstream f("f.txt");
int n;
int start[50];
int T[50][2];
int it=1;
int S[50];
int st[50],ps=1,vecin;
int cc=0;
void viziteaza(int);
int main()
{
//se creaza listele de adiacenta
f>>n;
int a,b;
while(f>>a>>b)
{
// se marcheaza b ca vecin al lui a
T[it][0]=b;
T[it][1]=start[a]; //pointer ->vecinul precedent in lista sau 0 daca este primul vecin
start[a]=it;
// se marcheaza a ca vecin al lui b
it++;
T[it][0]=a;
T[it][1]=start[b];
start[b]=it;
it++;
}
//incepe parcurgerea DFS de la primul nod neafiliat avand S[i]=0;
for(int i=1;i<=n;i++)
if(S[i]==0)
{
cc++;
S[i]=cc;
cout<<endl<<"componenta conexa "<<cc<<": "<<i<<" ";
viziteaza(i);
}
}
void viziteaza(int nod)
{
int it=start[nod]; indicele it nu trebuie sa fie variabila globala ci locala in functia viziteaza
while(it)
{
vecin=T[it][0];
if(S[vecin]==0)
{
cout<<vecin<<" ";
S[vecin]=cc;
viziteaza(vecin);
}
it=T[it][1];
}
}
5. Cicluri
Cicluri
Un lanț care conține numai muchii distincte și pentru care nodul inițial coincide cu nodul final se numește ciclu. Dacă, cu excepția ultimului nod, care coincide cu primul, lanțul este elementar (conține fiecare nod luat o singură dată), ciclul se numește ciclu elementar.
TEOREMĂ: Un graf neorientat conex în care m=n-1, unde n=numărul de noduri, m=numărul de muchii, nu conține niciun ciclu.
Demonstrație: Prin inducție. Un graf cu 1 nod are 0 muchii, deci respectă afirmația. Dacă adăugăm un al doilea nod, acesta se leagă printr-o muchie nouă la graful precedent, deci noul graf are 2 noduri și 1 muchie și nu conține cicluri. Dacă adăugăm al treilea nod și îl unim cu graful printr-o muchie nouă, acest nou nod are gradul 1, deci nu este parte din niciun ciclu. Dacă la un graf cu n-1 noduri și n-2 muchii care este conex și nu conține cicluri adăugăm un nod nou, unit printr-o singură muchie de graful precedent, atât numărul de noduri cât și numărul de muchii cresc cu o unitate, deci se respectă relația m=n-1.
Teoremă: un graf neorientat conex în care m>n-1 conține cel puțin un ciclu.
Demonstrație: Un graf conex cu n noduri și m=n-1 muchii nu conține niciun ciclu. Deoarece graful este conex, există un lanț între oricare două noduri, în particular și între nodurile a și b, pe care vrem să le unim printr-o muchie nouă. Dacă la acest graf adăugăm o muchie nouă între a și b, vor fi n noduri și n muchii. Cum lanțul existent înainte între a și b se închide, acesta devine ciclu.
Problemă: Fiind dat un graf, să se scrie un program care decide dacă graful conține cel puțin un ciclu.
Rezolvare: Presupunem că graful este conex (dacă nu este, o vom rezolva pentru fiecare componentă conexă în parte). Efectuăm o parcurgere DFS și, dacă algoritmul va ajunge în situația de a vizita un nod de două ori, înseamnă că am găsit un ciclu.
Observație: algoritmul de parcurgere respinge oricum tentativa de vizitare de două ori a unui nod, acesta este rolul vectorului de selecție S.
Soluție:
// decide daca un graf neorientat contine cel putin un ciclu
#include <iostream>
#include <fstream>
using namespace std;
int A[50][50];
int S[50];
int n;
fstream f("graf.txt",ios::in);
void dfs(int nod);
bool areciclu=false;
int main()
{
f>>n;
int a,b;
while(f>>a>>b)A[a][b]=A[b][a]=1;
dfs(1);
if(areciclu)cout<<"Graful are un ciclu";
}
void dfs(int nod)
{
for(int i=1;i<=n;i++)
{
if(A[nod][i]==1)
if(S[i]==0)
{
S[i]=1;
dfs(i);
}
else
areciclu=true;
}
}
Problemă: scrieți un program care afișează și ciclul găsit. Indicație: se va folosi un vector de tați (referințe ascendente).
Ciclu eulerian, graf eulerian
Un lanț L al unui graf G este eulerian dacă conține toate muchiile grafului luate o singură dată.
Dacă alest lanț este ciclu (nodul de start coincide cu nodul final), atunci ciclul se numește eulerian.
Dacă un graf conține un ciclu eulerian, grtaful se numește graf eulerian.
Teoremă: un graf fără vârfuri izolate este eulerian dacă și numai dacă este conex și gradele tuturor vârfurilor sunt pare.
Problemă: Fiind dat un graf conex care are gradele tuturor vârfurilor pare, să se găsească un ciclu eulerian.
Rezolvare: Programul va găsi un ciclu, apoi pentru fiecare nod al ciclului se va căuta un nou ciclu, iar dacă acesta este găsit se va intercala în ciclul găsit inițial, prin deplasare. Ciclurile sunt depozitate în vectorul eul, care conține inițial nodul 1 pe prima poziție. Indicele sf indică poziția ultimului nod introdus în vectorul eul.
Pentru graful din figura 12, figura de mai jos arată 3 configurații intermediare ale lui eul:
// graf eulerian = are un ciclu care trece prin toate muchiile o singură dată
#include <iostream>
#include <fstream>
using namespace std;
fstream f("date.in",ios::in);
int n,i,j,k,sf;
int eul[100];
int A[10][10];
void ciclu(int k)
{
for(int i=1;i<=n;i++)
{
if(A[eul[k]][i]==1)
{
A[eul[k]][i]=A[i][eul[k]]=0;
for(int p=sf;p>k;p--)
eul[p+1]=eul[p];
sf++;
eul[k+1]=i;
ciclu(k+1);
}
}
}
int main()
{
f>>n;
while(f>>i>>j)
{
A[i][j]=A[j][i]=1;
}
eul[1]=1;
sf=1;
for(int i=1;i<=sf;i++)ciclu(i);
for(i=1;i<=sf;i++)
cout<<eul[i]<<" ";
}
Grafuri hamiltoniene
Un ciclu care trece o singură dată prin toate nodurile unui graf se numește ciclu hamiltonian. Un graf care conține un ciclu hamiltonian se numește graf hamiltonian.
Problemă: Fiind dat un graf neorientat, se cere să se găsească, dacă există, un ciclu hamiltonian.
Rezolvare: se aplică metoda backtracking.
//un graf neorientat care are un ciclu elementar ce trece prin toate nodurile
#include <iostream>
#include <fstream>
using namespace std;
fstream f("graf.txt",ios::in);
int A[20][20],S[20];
int i,j,n;
void printsol()
{
cout<<endl;
for(int i=1;i<=n;i++)
cout<<S[i]<<" ";
cout<<S[1];
}
bool valid(int k)
{
bool ret=true;
for(int i=1;i<k;i++)
{
if(S[i]==S[k])
ret=false;
}
if(k==n&&A[S[n]][S[1]]==0)ret=false;
if(k==n&&A[S[n]][S[1]]==0)ret=false;
return ret;
}
void ham(int k)
{
if(valid(k))
{
for(int i=1;i<=n;i++)
{
if(A[S[k]][i]==1)
{
A[S[k]][i]=A[i][S[k]]=0;
S[k+1]=i;
ham(k+1);
}
}
}
}
int main()
{
f>>n;
while(f>>i>>j)
A[i][j]=A[j][i]=1;
S[1]=1;
ham(1);
printsol();
}
Grafuri bipartite
Un graf neorientat se numește bipartit dacă există o partiție (divizare) a mulțimii V în două submulțimi A și B astfel încât oricare două vârfuri din aceeași submulțime să nu fie adiacente. Altfel spus, toate arcele grafului au o extremitate în mulțimea A și cealaltă extremitate în mulțimea B.
Problemă: Să se decidă dacă un graf dat este bipartit.
Rezolvare: Vectorul de selecție S va reține 1 sau -1 pentru un nod vizitat, alternând pe 1 cu -1 de la un nod la vecinii săi. Dacă în urma parcurgerii se întâlnește un nod marcat cu aceeași valoare ca și predecesorul său, graful nu este bipartit. Dacă este bipartit, se afișează pe rând cele două partiții, parcurgând vectorul S.
#include <iostream>
#include <fstream>
using namespace std;
fstream f("date.in",ios::in);
int A[50][50];
int S[50];
int i,j,n;
bool bipartit=true;
void bip(int);
int main()
{
f>>n;
while(f>>i>>j)A[i][j]=A[j][i]=1;
S[1]=1;
bip(1);
if(bipartit)
{
cout<<endl<<"partitia 1: ";
for(int i=1;i<=n;i++)
if(S[i]==1)cout<<i<<" ";
cout<<endl<<"partitia 2: ";
for(int i=1;i<=n;i++)
if(S[i]==-1)cout<<i<<" ";
}
else
cout<<"graful nu este bipartit";
}
void bip(int nod)
{
for(int i=1;i<=n;i++)
{
if(A[nod][i]==1)
{
A[i][nod]=0;
if(S[i]==0)
{
S[i]=-S[nod];
bip(i);
}
else
{
if(S[i]==S[nod])
bipartit=false;
}
}
}
}
6. Aplicații grafuri neorientate
TESTE
- Se dă graful din figură:
- Graful este conex?
- Câte componente conexe are?
- Ce muchie ar trebui adăugată pentru a deveni conex?
- [1, 3, 6] este un lanț?
- Care este cel mai lung lanț elementar?
- Câte cicluri există?
- Care este numărul minim de muchii care trebuie eliminate pentru ca graful să nu conțină cicluri?
- Care este ciclul cu cel mai mare număr de muchii?
- Care este nodul cu gradul maxim?
- Care este matricea lui de adiacență?
- Care este lista muchiilor?
- Care este lista de adiacență?
- Scrie parcurgerea in adâncime pornind de la nodul 1
- Scrie parcurgerea în lățime pornind de la nodul 1.
2. Care este graful corespunzător urătoarei matrice de adiacență?
0 1 0 1 0
1 0 1 0 0
0 1 0 1 1
1 0 1 0 1
0 0 1 1 0
3. Cu ajutorul parcurgerii in adâncime se poate determina dacă un graf neorientat are cel puțin un ciclu?
4. Cu ajutorul parcurgerii în lățime se poate determina dacă un graf este conex?
5. Cu ajutorul BFS se poate determina dacă între două noduri există un lanț?
6. Există un graf complet cu n>=2 care nu conține cicluri?
7. Orice graf complet este alcătuit dintr-o singură componentă conexă?
8. Se dă un graf neorientat reprezentat prin matricea de adiacență. Să se afișeze toate nodurile care au gradul maxim.
9. Se dă un graf neorientat și o succesiune de noduri. Să se scrie un program care decide dacă succesiunea dată reprezintă un lanț sau nu.
10. Fiind dată matricea drumurilor unui graf, să se scrie un program care afișează componentele conexe.
11. Există un graf complet care este și bipartit?
12. Există un graf eulerian care este și hamiltonian?
13. Există un graf bipartit care este și eulerian?
14. Orice graf hamiltonian este și eulerian?
15. Să se scrie o funcție care transformă listele de adiacență în matrice de adiacență.
16. Să se scrie o funcție care transformă matricea de adiacență în liste de adiacență.
Probleme rezolvate
1. Algoritmul lui Lee
/*algoritmul lui Lee
se da o matrice/labirint cu camerele L[i,j] = -1 dacă prin camera nu se poate trece si 0 daca se poate trece.
se cer distantele minime de la camera de coordonate l, c la oricare alta camera accesibila.
datele
A[20][20] matricea labirint
n,l,c
S[400],Q[400]
algoritmul
parcurgere in latime, folosind coada Q si marcand direct in matrice departarea fata de celula data.
*/
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
fstream f("lee.txt",ios::in);
typedef struct celula
{
int linie;
int coloana;
}celula;
int A[20][20];
celula S[400],Q[400];
int n,lin,col,endq,begq,i,j;
void printa()
{
for(i=1;i<=n;i++)
{
cout<<endl;
for(j=1;j<=n;j++)
cout<<A[i][j]<<" ";
}
}
void pun_vecini_in_coada()
{
int l=Q[begq].linie;
int c=Q[begq].coloana;
int dist=A[l][c];
begq++;
if(A[l-1][c]==0)
{
A[l-1][c]=dist+1;
endq++;
Q[endq].linie=l-1;
Q[endq].coloana=c;
}
if(A[l+1][c]==0)
{
A[l+1][c]=dist+1;
endq++;
Q[endq].linie=l+1;
Q[endq].coloana=c;
}
if(A[l][c-1]==0)
{
A[l][c-1]=dist+1;
endq++;
Q[endq].linie=l;
Q[endq].coloana=c-1;
}
if(A[l][c+1]==0)
{
A[l][c+1]=dist+1;
endq++;
Q[endq].linie=l;
Q[endq].coloana=c+1;
}
}
int main()
{
f>>n>>lin>>col;
for( i=1;i<=n;i++)
for(j=1;j<=n;j++)
f>>A[i][j];
for( i=0;i<=n+1;i++)
A[0][i]=A[n+1][i]=-1;
for( i=0;i<=n+1;i++)
A[i][0]=A[i][n+1]=-1;
Q[1].linie=lin;
Q[1].coloana=col;
A[lin][col]=1;
endq=1;
begq=1;
printa();
do {pun_vecini_in_coada();}
while(begq<=endq);
cout<<endl<<endl;
printa();
}
2. Colecție de subprograme utile pentru grafuri neorientate:
- reprezentarea sub formă de matrice de adiacență
- reprezentarea sub formă de liste de adiacență
- parcurgerea BFS și DFS
- găsirea unui lanț între două noduri
- găsirea componentelor conexe
- găsirea unui ciclu eulerian
- găsirea ciclurilor hamiltoniene
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <conio.h>
using namespace std;
//fstream f("graf.txt",ios::in);
//fstream f("euler.txt",ios::in);
//fstream f("graf.grf",ios::in);
fstream f("bipartit.txt",ios::in);
void creare_la_static();
void creare_la_dinamic();
void afisare_la_static();
void afisare_la_dinamic();
void creare_mat_adiacenta();
void afisare_ma();
void creare_lista_muchii();
void afisare_lm();
void pune_vecini_in_coada_la(int k);
void pune_vecini_in_coada_ma(int k);
void visit_la(int nod);
void visit_ma(int nod);
void DF_la();
void DF_ma();
void BF_la();
void BF_ma();
void lant_DF();
void visit_lant_ma(int nod, int tata);
void comp_conexe();
void lant_BF();
void euler();
void hamilton();
bool valid_bkt(int poz,int nd);
void print_bkt();
void bkt(int nod);
void bipartit();
void bip();
int coada[20];
int S[20],Q[20];
int i_c,s_c,noda=2,nodb=5;
int A[20][20];
int start[20];
int T[2][40];
int m,n,i,j,k,u,part;
bool bp;
typedef struct Nod
{
int nd;
Nod* urmator;
}Nod;
Nod *wstart[20];
void caut_ciclu(Nod* u);
struct muchie
{
int x,y;
};
muchie V[20];
int main()
{
creare_mat_adiacenta();
afisare_ma();
/* f.clear();
f.seekg(0,f.beg);
creare_la_static();
afisare_la_static();
f.clear();
f.seekg(0,f.beg);
creare_la_dinamic();
afisare_la_dinamic();
f.clear();
f.seekg(0,f.beg);
creare_lista_muchii();
afisare_lm();
BF_la();
BF_ma();
DF_la();
DF_ma();
lant_DF();
lant_BF();
comp_conexe();*/
// euler();
// hamilton();
bipartit();
getch();
}
void bipartit()
{
// verifica daca un graf este bipartit. Vectorul Q[] va retine pt fiecare nod vizitat: valoarea 1 sau -1
// se face o parcurgere BF. Se utilizeaza vectorul coada[], vectorul de selectie S[] si indicii i_c si s_c.
// daca in parcurgere se intalneste un nod deja vizitat care nu are acelasi Q[] cu vizita precedenta, bp=false.
for(i=1;i<=n;i++){S[i]=0;Q[i]=0;}
bp=true;
part=1;
i_c=1;
s_c=2;
coada[1]=1;
Q[1]=1;
while((i_c<=s_c)&&bp)
bip();
if(bp)
{
cout<<"graful este bipartit"<<endl;
cout<<"Submultimea A: ";
for(i=1;i<=n;i++)
if(Q[i]==1)cout<<i<<" ";
cout<<endl<<"Submultimea B: ";
for(i=1;i<=n;i++)
if(Q[i]==-1)cout<<i<<" ";
}
else cout<<"graful nu este bipartit";
}
void bip()
{
if(S[coada[i_c]]==0)
{
part=Q[coada[i_c]]; //indicele partitiei se restaureaza la valoarea nodului tata
for(k=1;k<=n;k++)
{
if(A[coada[i_c]][k]==1)
{
if(Q[k]==0||Q[k]==-part) //daca nodul k nu a mai fost vizitat sau daca indicele = - indicele tatalui
{
coada[s_c]=k;
s_c++;
A[k][coada[i_c]]=0;
Q[k]=-part; //toate nodurile fiu primesc indicele de partitie = -indicele tatalui
}
else bp=false; //nod deja vizitat cu indice = indicele tatalui
}
}
}
i_c++;
}
void hamilton()
{
for(int i=0;i<=n;i++)S[i]=0;
bkt(1);
}
void bkt(int nivel)
{
for(k=1;k<=n;k++)
{
S[nivel]=k;
if(valid_bkt(nivel,k))
if(nivel==n)
{
S[nivel+1]=S[1];
print_bkt();
}
else bkt(nivel+1);
}
}
bool valid_bkt(int poz,int nd)
{
bool rezult=true;
if(poz>1)
{
if(A[S[poz-1]][S[poz]]==0)rezult=false;
for(int i=1;i<=poz-1;i++)
{
if (S[i]==S[poz]) rezult=false;
}
}
return rezult;
}
void print_bkt()
{
cout<<endl<<"Ciclu hamiltonian: ";
for(int i=1;i<=n+1;i++)
cout<<S[i]<<" ";
}
void euler()
{
Nod* u=new Nod;
u->nd=1;
u->urmator=NULL;
wstart[0]=u;
do
{
caut_ciclu(u);
u=u->urmator;
}
while(u);
cout<<endl<<"Ciclul eulerian: ";
u=wstart[0];
do
{
cout<<u->nd<<" ";
u=u->urmator;
}
while(u);
}
void caut_ciclu(Nod* u)
{
i=u->nd;
for (k=1;k<=n;k++)
{
if(A[i][k])
{
A[i][k]=0;
A[k][i]=0;
Nod* w=new Nod;
w->urmator=u->urmator;
u->urmator=w;
w->nd=k;
caut_ciclu(w);
}
}
}
void comp_conexe()
{
for(i=1;i<=n;i++)S[i]=0;
k=0;
for(i=1;i<=n;i++)
{
if(!S[i])
{
k++;
cout<<endl<<"componenta conexa numarul "<<k<<": ";
visit_ma(i);
}
}
}
void visit_lant_ma(int nod,int tata)
{
if(!S[nod])
{
Q[nod]=tata;
S[nod]=1;
for(j=1;j<=n;j++)
if(A[nod][j])visit_lant_ma(j,nod);
}
}
void print_za(int k)
{
cout<<k<<" ";
if(Q[k]==0)return;
else
print_za(Q[k]);
}
void lant_DF()
{
cout<<endl<<"Lant prin parcurgere DF intre nodul "<<noda<<" si nodul "<<nodb<<": ";
for(i=1;i<=n;i++){S[i]=0;Q[i]=0;}
visit_lant_ma(noda,0);
if(!Q[nodb])
cout<<endl<<"Nu exista lant intre "<<noda<<" si "<<nodb<<endl;
else
print_za(nodb);
}
void lant_BF()
{
cout<<endl<<"Lant prin parcurgere BF intre nodul "<<noda<<" si nodul "<<nodb<<": ";
for(i=1;i<=n;i++){S[i]=0;Q[i]=0;}
i_c=0;
s_c=1;
coada[i_c]=noda;
Q[noda]=0;
do
{
if(!S[coada[i_c]])
{
S[coada[i_c]]=1;
pune_vecini_in_coada_ma(coada[i_c]);
}
i_c++;
}
while(i_c<s_c);
if(!Q[nodb])
cout<<endl<<"Nu exista lant intre "<<noda<<" si "<<nodb<<endl;
else
print_za(nodb);
}
void DF_la()
{
cout<<endl<<"parcurgere DF cu lista de adiacenta: ";
for(i=1;i<=n;i++)S[i]=0;
visit_la(1);
}
void DF_ma()
{
cout<<endl<<"parcurgere DF cu matrice de adiacenta: ";
for(i=1;i<=n;i++)S[i]=0;
visit_ma(1);
}
void visit_la(int nod)
{
if(!S[nod])
{
cout<<nod<<" ";
S[nod]=1;
u=start[nod];
while(u)
{
visit_la(T[0][u]);
u=T[1][u];
}
}
}
void visit_ma(int nod)
{
if(!S[nod])
{
cout<<nod<<" ";
S[nod]=1;
for(j=1;j<=n;j++)
if(A[nod][j])visit_ma(j);
}
}
void BF_la()
{
cout<<endl<<"parcurgere BF cu lista de adiacenta: ";
for(i=1;i<=n;i++)S[i]=0;
i_c=0;
s_c=1;
coada[i_c]=1;
do
{
if(!S[coada[i_c]])
{
S[coada[i_c]]=1;
pune_vecini_in_coada_la(coada[i_c]);
cout<<coada[i_c]<<" ";
}
i_c++;
}
while(i_c<s_c);
cout<<endl;
}
void BF_ma()
{
cout<<endl<<"parcurgere BF cu matrice de adiacenta: ";
for(i=1;i<=n;i++)S[i]=0;
i_c=0;
s_c=1;
coada[i_c]=1;
do
{
if(!S[coada[i_c]])
{
S[coada[i_c]]=1;
pune_vecini_in_coada_ma(coada[i_c]);
cout<<coada[i_c]<<" ";
}
i_c++;
}
while(i_c<s_c);
cout<<endl;
}
void pune_vecini_in_coada_ma(int i)
{
for(k=1;k<=n;k++)
if(A[i][k])
{
coada[s_c]=k;
if(!S[k])Q[k]=i; //lant
s_c++;
}
}
void pune_vecini_in_coada_la(int k)
{
u=start[k];
while(u)
{
coada[s_c]=T[0][u];
u=T[1][u];
s_c++;
};
}
void creare_mat_adiacenta()
{
f>>n;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)A[i][j]=0;
while(!f.eof())
{
f>>i>>j;
A[i][j]=1;
A[j][i]=1;
}
}
void afisare_ma()
{
for(i=1;i<=n;i++)
{
cout<<"Matricea de adiacenta: lista nodurilor adiacente cu nodul "<<i<<": ";
for(j=1;j<=n;j++)
{
if(A[i][j])cout<<j<<" ";
}
cout<<endl;
}
cout<<endl;
}
void creare_la_static()
{
k=0;
f>>n;
for(i=1;i<=n;i++)start[i]=0;
for(i=1;i<=39;i++)
{
T[0][i]=0;T[1][i]=0;
}
while(f>>i>>j)
{
k++;
T[0][k]=j;
T[1][k]=start[i];
start[i]=k;
k++;
T[0][k]=i;
T[1][k]=start[j];
start[j]=k;
}
}
void afisare_la_static()
{
for(i=1;i<=n;i++)
{
cout<<"Lista de adiacenta statica: nodurile adiacente cu nodul "<<i<<": ";
u=start[i];
do
{
cout<<T[0][u]<<" ";
u=T[1][u];
}
while(u);
cout<<endl;
}
cout<<endl;
}
void creare_la_dinamic()
{
f>>n;
for(i=1;i<=n;i++)wstart[i]=0;
Nod* u;
k=1;
while(f>>i>>j)
{
u=new Nod;
u->nd=j;
u->urmator=wstart[i];
wstart[i]=u;
u=new Nod;
u->nd=i;
u->urmator=wstart[j];
wstart[j]=u;
}
}
void afisare_la_dinamic()
{
Nod* u;
for(i=1;i<=n;i++)
{
cout<<"Lista de adiacenta dinamica: nodurile adiacente cu nodul "<<i<<": ";
u=wstart[i];
while(u)
{
cout<<u->nd<<" ";
u=u->urmator;
}
cout<<endl;
}
cout<<endl;
}
void creare_lista_muchii()
{
f>>n;
k=1;
while(f>>i>>j)
{
V[k].x=i;
V[k].y=j;
k++;
}
m=k;
}
void afisare_lm()
{
for(i=1;i<=n;i++)
{
cout<<"Lista muchiilor: nodurile adiacente cu nodul "<<i<<": ";
for(j=1;j<=m;j++)
if(V[j].x==i)cout<<V[j].y<<" ";
else
if(V[j].y==i)cout<<V[j].x<<" ";
cout<<endl;
}
cout<<endl;
}
7. Grafuri orientate. Memorare, parcurgere, circuite
Un graf orientat este perechea ordonată G=(V, A), unde:
V={v1, v2, ...vn) este o mulțime finită de elemente numite vârfuri;
A este o mulțime de arce. Un arc este o pereche ordonată (v𝐢, v𝐣) cu i diferit de j.
Termeni și definiții:
Vârfurile distincte v𝐢, v𝐣 sunt adiacente dacă există cel puțin un arc care le unește.
Gradul exterior al unui vârf v este numărul arcelor incidente spre exterior cu v. Gradul exterior al unui nod se notează d⁺(v).
Gradul interior al unui vârf este numărul arcelor incidente spre interior cu v. Se notează d⁻(v).
Suma gradelor exterioare este egală cu suma gradelor interioare într-un graf orientat.
Memorarea grafurilor orientate
- Prin matricea de adiacență. Matricea de adiacență a grafurilor orientate nu este simetrică.
- Prin liste de adiacență alocate static
- Prin liste de adiacență alocate dinamic.
- Prin lista arcelor
- Prin matricea ponderilor.
Metodele 1- 4 sunt identice ca cele ale grafurilor neorientate. Matricea ponderilor este o matrice de adiacență modificată, care reține în locul informației 1, un număr oarecare pozitiv cu semnificație de cost atașată muchiei.
Graf.txt
5
1 2 1
1 3 9
1 5 3
2 4 3
2 3 7
4 3 2
4 1 1
5 2 4
5 4 2
Matricea ponderilor se construiește ca și matricea de adiacență, cu deosebirea că, pentru fiecare MP[i][j], în loc de 0 și 1 se vor scrie infinit (de fapt o valoare foarte mare) dacă i și j nu sunt adiacente, sau costul muchiei (i,j) dacă i și j sunt adiacente. Diagonala matricei MP va fi deasemenea nulă.
Pentru graful de mai sus, MP este următoarea:
Pentru memorarea practică a valorii infinit se pot utiliza constante mari, ca de exemplu:
const float pInfinit=1.e20;
const int infinit=0xFFFF;
const int infinit=255;
const int infinit65535;
Graf parțial, subgraf
Un graf parțial al unui graf orientat G este el însuși sau se obține din G prin suprimarea anumitor arce.
Un subgraf al unui graf orientat G este un graf care se obține din G prin eliminarea unor vârfuri și a tuturor arcelor care sunt incidente cu acestea.
Parcurgerea grafurilor. Drumuri. Circuite.
Toate noțiunile aferente grafurilor neorientate se aplică în mod corespunzător și grafurilor orientate, cu specificarea că matricea de adiacență nu este simetrică: un arc de la nodul i la nodul j nu implică arcul invers, de la j la i.
Parcurgerea grafurilor orientate se face la fel ca și a celor neorientate, prin cele două metode - în lățime și în adâncime. Parcurgerea se realizează de la un nod la vecinii săi, deci numai în sensul indicat de arce.
Un drum într-un graf orientat este o succesiune de vârfuri unite între ele prin arce. Primul și ultimul vârf se numesc extremitățile drumului. Lungimea drumului este numărul arcelor care formează drumul, deci este numărul nodurilor minus 1.
Un drum este elementar dacă conține numai vârfuri distincte.
Un circuit este un drum în care vârful inițial coincide cu vârful final.
Un lanț într-un graf orientat este o succesiune de noduri unite prin arce al căror sens nu contează. Dacă nodurile sunt distincte, lanțul este elementar.
Matricea drumurilor unui graf orientat este o matrice nXn, care are 1 pentru MD[i][j] dacă există drum de la nodul i la nodul j, și 0 în cazul în care nu există.
8. Graf complet și graf turneu
Graf complet și graf turneu
Un graf orientat este complet dacă oricare două vârfuri i și j cu i diferit de j, sunt adiacente.
Există 3^((n*(n-1))/2) grafuri complete cu n noduri.
Demonstrația prin inducție: pentru n=2, există 3 posibilități: există arcul (1,2), există arcul (2,1) sau există ambele arce. Adăugând încă un nod, acesta se poate cupla tot în 3 moduri posibile.
Un graf orientat este turneu, dacă oricare ar fi două vârfuri i și j, cu i diferit de j, între ele există un singur arc: fie arcul (i,j), fie arcul (j,i).
Proprietăți:
- Orice graf turneu este graf complet.
- Există 2 la puterea n(n-1)/2 grafuri turneu cu n noduri.
- În orice graf turneu există un drum elementar care trece prin toate vârfurile grafului. Demonstrația prin inducție: Fie un drum care trece prin k<n vârfuri distincte, [v1, v2, …,vk] și fie v un vârf care nu face parte din acest drum. Demonstrăm că acest v trebuie să facă parte din drum.
- Dacă există arcul (v, v1) atunci am găsit drumul [v, v1, v2,...vk].
- Dacă nu există arcul [v,v1] înseamnă că există arcul [v1, v]. Dacă există arcul (vk,v) atunci am găsit drumul [v1,v2,...vk,v]. Dacă nu există arcul (vk,v) înseamnă că există arcul (v,vk). Suntem în situația din figura următoare:
Dacă există arcul (vk-1,v), atunci v1, v2,...vk-1,v,vk este un drum care îl include pe v. Dacă nu, atunci există arcul (v,vk-1).
Judecăm analog, și în ultimă instanță trebuie să găsim că îl putem intercala pe v între v1 și v2.: v1,v,v2,...vk.
Existența drumului elementar care trece prin toate vârfurile conduce la faptul că putem aranja cele n noduri într-un șir ordonat.
Problemă:
Fiind dat un graf turneu, se cere să se afișeze un drum elementar care trece prin toate vârfurile grafului.
Rezolvare:
#include <iostream>
#include <fstream>
#include <conio.h>
using namespace std;
fstream f("graf.txt",ios::in);
int MA[25][25];
int n;
int sf;
int sol[25];
void shift_right(int poz) //face un loc liber in vectorul sol
// pe pozitia sol[poz], muand la dreapta cu un loc
//restul sirului cuprins intre poz si sf
{
sf++;
for(int i=sf;i>poz;i--)
sol[i]=sol[i-1];
}
int main()
{
int i,j;
f>>n;
while(f>>i>>j)
MA[i][j]=1;
sol[1]=1;
sf=1;
for(int p=2;p<=n;p++)
{
//testez situatia 1: exista arc de la nodul p la sol[1],
//nodul p se insereaza la inceputul lui sol
if(MA[p][sol[1]]==1)
{
shift_right(1);
sol[1]=p;
}
//testez situatia 2: exista arc de la ultimul nod din sol catre nodul p
//nodul p se insereaza in urma ultimului nod din sol
else if(MA[sol[sf]][p]==1)
{
sf++;
sol[sf]=p;
}
//daca nu suntem nici in situatia 1, nici in situatia 2,
//rezulta ca suntem in situatia 3, in care se va cauta o succesiune de doua noduri
//in vectorul sol, care au sagetile opuse, intre care
//se va intercala nodul p.
else
{
bool gasit=false;
for(int i=2;i<=sf&&!gasit;i++)
{
//testam sensul sagetii dintre doua noduri sucesive si nodul de inserat p
if(MA[sol[i-1]][p]==1&&MA[p][sol[i]]==1)
{
//am gasit doua noduri cu arce de sens opus
//nodul p se va insera intre ele
shift_right(i);
sol[i]=p;
gasit=true;
}
}
}
}
//afisare lant
for(int i=1;i<=n;i++)
cout<<sol[i]<<" ";
getch();
}
9. Graf tare conex, componente tare conexe
Graf tare conex. Componente tare conexe.
Noțiunea echivalentă cu conexitatea de la grafurile neorientate este tare-conexitatea.
Un graf G=(V,A) este tare conex dacă pentru oricare x,y noduri din V, există drum de la x la y ȘI drum de la y la x.
Un subgraf G1 al unui graf orientat G este o componentă tare conexă dacă are proprietatea de tare conexitate, și nu există un alt subgraf G2 al lui G, cu V1 inclus în V2, cu această proprietate. Sau, altfel spus, nu mai putem adăuga nici un nod la G1 și acesta să rămână tare conex.
Problemă: fiind dat un graf orientat, să se afișeze vârfurile fiecărei componente tare conexe.
//determina componentele tare conexe dintr-un GO
#include <iostream>
#include <fstream>
using namespace std;
fstream f("ctc.txt",ios::in);
int A[50][50],D[50][50],S[50],suc[50],pred[50];
int n,nctc;
int i,j;
//metoda matricii drumurilor\
matricea D[i][j] are 1 daca exista drum de la nodul i la nodul j\
se completeaza prin n parcurgeri DF\
in vectorul de selectie S[n] se pune S[1]=nctc=1 apoi pt toti j pt care D[1][j]=D[j][1]=1\
se listeaza\
se increm nctc si se repeta pt primul i cu S[i]=0.\
complexitate n**3\
metoda parcurgerii inapoi\
se parcurge inainte pt primul i cu S[i]=0 marcandu-se in suc[k] nodurile atinse\
apoi se parcurge inapoi marcandu-se in pred[k] nodurile atinse\
nodurile care au suc[k]=pred[k]=1 fac parte din aceleasi ctc\
se listeaza iar celelalte se pune Suc[k]=0.\
se repeta pana cand toate elem din S sunt =0
void drum(int nod)
{
for(int k=1;k<=n;k++)
{
if(A[nod][k]==1&&S[k]==0)
{
S[k]=1;
D[i][k]=1;
drum(k);
}
}
}
void inainte(int nod)
{
for(int k=1;k<=n;k++)
{
if(A[nod][k]==1&&suc[k]==0)
{
suc[k]=nctc;
inainte(k);
}
}
}
void inapoi(int nod)
{
for(int k=1;k<=n;k++)
{
if(A[k][nod]==1&&pred[k]==0)
{
pred[k]=nctc;
inapoi(k);
}
}
}
int main()
{
f>>n;
while(f>>i>>j)
{
A[i][j]=1;
}
//metoda matricii drumurilor
cout<<"metoda matricii drumurilor"<<endl;
for(i=1;i<=n;i++)
{
//nodul de start i
for(j=1;j<=n;j++)S[j]=0;
S[i]=1;
drum(i);
}
nctc=0;
for(j=1;j<=n;j++)S[j]=0;
for(int i=1;i<=n;i++)
{
if(S[i]==0)
{
nctc++;
cout<<endl<<"componenta "<<nctc<<": "<<i<<" ";
for(int j=1;j<=n;j++)
{
if(D[i][j]==1&&D[j][i]==1)
{
cout<<j<<" ";
S[j]=1;
}
}
}
}
//metoda parcurgerilor inapoi
cout<<endl<<"metoda parcurgerilor inapoi"<<endl;
int k=1;
nctc=0;
while(k<=n)
{
if(suc[k]==0)
{
nctc++;
cout<<endl<<"componenta "<<nctc<<": ";
suc[k]=pred[k]=nctc;
inainte(k);
inapoi(k);
for(int u=1;u<=n;u++)
if(suc[u]==nctc&&pred[u]==nctc)
cout<<u<<" ";
else
if(suc[u]!=pred[u])
suc[u]=pred[u]=0;
}
k++;
}
}
SOLUȚIA 2
/* se determina componentele tare conexe dintr-un GO
noutatea este reprezentarea sub forma de matrice de adiacenta alocata dinamic si functie cu parametru pointer la tablou.
se construieste simultan si matricea transpusa
*/
#include <iostream>
#include <fstream>
#include <stdlib.h> //realloc
using namespace std;
fstream f("date.in",ios::in);
int n,nrc;
int (*A)[20],(*T)[20];
int S[20], P[20]; //vectori de selectie
void DFS(int v,int (*mat)[20],int(*vec))
{
for(int i=1;i<=n;i++)
{
if(mat[v][i]==1&&vec[i]==0)
{
vec[i]=nrc;
DFS(i,mat,vec);
}
}
}
int main()
{
f>>n;
A=new int[20][20];
T=new int[20][20] ;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
A[i][j]=T[i][j]=0;
int a,b;
while(f>>a>>b)
{
A[a][b]=1;
T[b][a]=1;
}
nrc=0;
for(int i=1;i<=n;i++)
{
if(S[i]==0)
{
nrc++;
S[i]=nrc;
DFS(i,A,S); //se parcurge DFS lista directa A completandu-se vectorul de selectie directa S
for(int j=1;j<=n;j++)P[j]=0;
P[i]=nrc;
DFS(i,T,P); //se parcurge transpusa completandu-se vectorul de selectie inversa P
for(int j=1;j<=n;j++) // se sterg selectiile care nu corespund aceleiasi componente
if(S[j]==nrc&&P[j]!=nrc)
{
S[j]=0;
}
}
}
for(int i=1;i<=nrc;i++)
{
cout<<endl<<"componenta "<<i<<": ";
for(int j=1;j<=n;j++)
if(S[j]==i)
cout<<j<<" ";
}
}
10. Drumuri de cost minim. Algoritmii Roy-Floyd și Dijkstra
Drumuri de cost minim
Dându-se un graf orientat reprezentat prin matricea ponderilor, se pune problema găsirii drumului de cost minim (dcm) dintre două vârfuri A și B. Există trei variante ale problemei:
- Se cere dcm dintre un vârf unic A și un vârf unic B;
- Se cere dcm dintre un vârf unic A și oricare alte vârfuri (sursă unică, destinație multiplă)
- Se cere dcm dintre oricare vârf și oricare vârf (sursă multiplă, destinație multiplă).
Pentru rezolvarea acestor probleme, dacă între două vârfuri i nu există arc, se va presupune că există un arc de cost infinit.
Algoritmul Roy-Floyd
Acesta rezolvă problema 3 de mai sus, sursă multiplă și destinație multiplă.
Ideea este următoarea: se lucrează în interiorul matricei ponderilor MP, care este modificată în n pași succesivi (n fiind numărul de vârfuri). În pasul 1, se încearcă construirea de drumuri mai scurte între oricare 2 vârfuri i și j, cu condiția ca ele să treacă prin vârful 1. Astfel, se compară MP[i][j] cu MP[i][1]+MP[1][j]. Dacă drumul nou, care trece prin 1, este mai scurt, atunci se înlocuiește în matricea MP valoarea MP[i][j] cu suma calculată anterior.
Se procedează mai departe identic, considerând ca nod intermediar pe rând toate vârfurile de la 1 la n.
Algoritmul are complexitatea O(n^3).
Desfășurarea drumului optim de la un vârf A la un vârf B se face astfel:
Dacă există un vârf k astfel încât MP[i][j]=MP[i][k]+MP[k][j], atunci vârful k face parte dintr-unul din drumurile optime de la i la j (pot fi mai multe). Se aplică strategia Divide et impera.
//cauta drumul optim (de cost minim) intr-un graf orientat\
reprezentat prin matricea ponderilor in forma 1
#include <iostream>
#include <fstream>
using namespace std;
fstream f("rf.txt",ios::in);
int A[10][10];
int n,i,j,k,a,b;
int nrmax=0xFFFF;
int drum(int p,int q)
{
int i=1;
bool gasit=false;
while(!gasit&&(i<=n))
{
if(i!=p&&i!=q&&A[p][i]+A[i][q]==A[p][q])
{
gasit=true;
drum(p,i);
drum(i,q);
}
i++;
}
if(!gasit)
cout<<q<<" ";
}
int main()
{
f>>n>>a>>b;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j)A[i][j]=nrmax;
else
A[i][j]=0;
}
while(f>>i>>j>>k)
A[i][j]=k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(A[i][j]>A[i][k]+A[k][j])
A[i][j]=A[i][k]+A[k][j];
}
cout<<endl<<A[a][b];
cout<<endl;
cout<<a<<" ";
drum(a,b);
// cout<<b;
}
Algoritmul lui Dijkstra
Acesta rezolvă problema 2, sursa unică (vârful r) și destinația multiplă.
Se folosesct 3 vectori: vectorul de selecție S, vectorul de tați T și vectorul de distanțe D.
Se selectează vârfurile grafului, unul câte unul, în ordine crescătoare a costului de la nodul r la ele într-un vector de selecție S, care inițial conține numai vârful r selectat.
În vectorul D se scriu lungimile drumurilor de la vârful r la toate celelalte vârfuri ale grafului. Inițial, acesta este deci linia r a matricii ponderilor.
Vectorul T conține referințele ascendente, către tați.Pentru nodul r se memorează 0.
Pasul 1 inițializare: se selectează vârful r în S: S[r]=1; se copiază linia r a matricii MP în D, se pune T[i]=r pentru toate vârfurile care au distanța față de vârful r D[i] finită.
Pasul 2 se execută de n-1 ori: printre nodurile neselectate (deci pentru S[i]=0) se selectează cel aflat la distanța minimă față de r (deci cel pentru care D[i] este minim). Fie poz acest vârf. Se selectează poz (S[poz]=1). Se compară costul existent în vectorul D pentru fiecare nod j, adică D[j], cu suma dintre distanța de la r la poz + distanța de la poz la j. Distanța de la r la poz este D[poz], iar distanța de la poz la j se ia din matricea MP, MP[poz][j]. În cazul în care suma aceasta este mai mică, ea va înlocui în D vechea valoare D[j], simultan consemnând în vectorul de tați că j este descendent al lui poz: T[j]=poz.
Pasul 3 se afișează drumurile optime, cu ajutorul vectorului de tați T.
//cauta drum optim de cost minim intre un nod si celelalte noduri\
intr-un graf orientat reprezentat prin matricea ponderilor sub forma 1
#include <iostream>
#include <fstream>
using namespace std;
fstream f("dij.txt",ios::in);
int A[10][10],D[10],S[10],T[10];
int n,i,j,k,r,sel;
int nrmax=0xffff;
int valmin;
int main()
{
f>>n>>r;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j)A[i][j]=nrmax;
else
A[i][j]=0;
}
while(f>>i>>j>>k)
A[i][j]=k;
/*algoritmul:
S[r]=1
se scriu in D distantele dintre nodul r si ele, preluate din matricea A
pentru toate nodurile cu D[k] finit se pune T[k]=r
pentru toate nodurile neselectate se executa de n-1 ori:
- se alege nodul cu D[k] minim si se numeste sel
-S[sel]=1
- pentru toate elementele din D, daca A[sel][k]+D[sel]<D[k]
aunci se inlocuieste D[k] cu valoarea minima si T[k] cu sel.
*/
S[r]=1;
for(i=1;i<=n;i++)
{
if(i!=r)
{
D[i]=A[r][i];
T[i]=r;
}
}
for(j=1;j<n;j++)
{
valmin=nrmax;
sel=1;
for(k=1;k<=n;k++)
{
if(S[k]==0)
{
if(D[k]<valmin)
{
sel=k;
valmin=D[k];
}
}
}
S[sel]=1;
for(k=1;k<=n;k++)
{
if(S[k]==0&&D[sel]+A[sel][k]<D[k])
{
D[k]=D[sel]+A[sel][k];
T[k]=sel;
}
}
}
cout<<endl<<"drumul optim dintre nodul "<<r<<" si celelalte noduri";
for(i=1;i<=n;i++)
{
if(i!=r&&D[i]<nrmax)
{
cout<<endl<<"distanta la nodul "<<i<<":"<<D[i]<<" iar drumul este: ";
k=i;
do
{
cout<<k<<" ";
k=T[k];
}
while(k!=r);
cout<<k;
}
}
}
11. Aplicații
- Câte componente conexe și câte componente tare conexe are graful următor?
a) 1 1; b) 1 3; c) 1 0; d) 0 0;
2. În graful următor, care este lungimea celui mai lung lanț elementar și care este lungimea celui mai lung drum elementar?
- 3 2; b) 2 2; c) 2 3; d) 1 2;
Se dă graful următor:
.
3. Câte circuite conține?
- 3; b) 2; c) 1; d) 4.
4. Câte componente tare conexe conține?
- 4; b) 3; c) 2; d) 1.
5. Care este nodul cu grad interior maxim și care este nodul cu grad exterior minim?
- 1 1; b) 1 2; c) 2 2 d) 2 5.
6. Care este numărul minim de arce care trebuie adăugate pentru ca graful să devină tare conex?
- 1; b) 2; c) 3; d)4.
7. Se considerăun graf orientat cu 6 noduri care are următoarele proprietăti:
- suma gradelor externe ale tuturor varfurilor grafului este egală cu 6;
- sunt doar 3 vârfuri care au gradul intern egal cu 1.
Care este valoarea maximă pe care o poate avea gradul extern al unui vârf din graful dat?
Reprezentaţi prin liste de adiacenţă un graf care îndeplineşte condiţiile din enunţul problemei şi în care unul dintre vîrfuri are acest grad extern maxim.
8. Se consideră un graf orientat cu 6 noduri numerotate de la 1 la 6 şi cu mulţimea arcelor
formată doar din arcele:
- de la fiecare nod numerotat cu un număr neprim i (i>1) la toate nodurile numerotate cu numere ce aparţin mulţimii divizorilor proprii ai lui i (divizori diferiţi de 1 şi de i)
- de la nodul numerotat cu 1 la nodul numerotat cu 6
- de la fiecare nod numerotat cu un număr prim i la nodul numerotat cu i-1
Pentru graful dat, câte dintre nodurile grafului au gradul exterior strict mai mare decât gradul interior? (4p.)
a. 1 b. 2 c. 4 d. 3
9. Se consideră graful orientat G reprezentat prin listele de adiacenţă alăturate. Care este lungimea maximă a unui drum elementar din acest graf? Care sunt arcele care compun un drum cu aceste proprietăţi?
1 2,6,5
2 3
3 1
4 6
5 6
6 2
10. Se consideră graful orientat reprezentat prin matricea de adiacenţă alăturată. Care este lungimea maximă a unui drum de la vârful 4 până la vârful 6 format din vârfuri distincte două câte două?
0 1 1 0 0 0
0 0 0 0 1 1
0 0 0 0 0 0
0 0 1 0 1 0
1 1 0 0 0 1
1 0 1 0 0 0
a. 4 b. 3 c. 1 d. 5
11. Suma gradelor interne ale tuturor vârfurilor unui graf orientat este întotdeauna egală cu:
a. numărul valorilor de 1 aflate sub diagonala principală în matricea sa de adiacenţă
b. produsul gradelor externe ale tuturor vârfurilor grafului
c. suma tuturor valorilor aflate deasupra diagonalei principale în matricea sa de adiacenţă
d. suma gradelor externe ale tuturor vârfurilor grafului.
12. Într-un graf orientat cu 7 noduri suma gradelor interioare ale tuturor nodurilor este egală cu 10. Care este valoarea sumei gradelor exterioare ale tuturor nodurilor?
a. 5 b. 20 c. 10 d. 17
13. Care dintre următoarele arce trebuie adăugat unui graf orientat cu 5 noduri, numerotate de la 1 la 5, reprezentat prin matricea de adiacenţă alăturată, astfel încât în acest graf să existe cel puţin un drum între oricare două vârfuri?
0 1 0 1 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 1
1 0 0 0 0
a. (3 , 5) b. (4 , 1) c. (5 , 3) d. (3 , 2)
14. Care din următoarele proprietăţi este adevărată pentru un graf orientat cu n vârfuri şi n arce (n>3) care are un circuit de lungime n:
a. există un vârf cu gradul intern n-1
b. pentru orice vârf gradul intern şi gradul extern sunt egale
c. graful nu are drumuri de lungime strict mai mare decât 2
d. gradul intern al oricărui vârf este egal cu 2.
15. Care este numărul arcelor ce au ca extremitate iniţială vârful 4, în graful orientat cu 4 vârfuri, numerotate de la 1 la 4, reprezentat prin matricea de adiacenţă alăturată? (4p.)
0 1 0 1
0 0 0 0
0 1 0 0
1 1 1 0
a. 3 b. 2 c. 1 d. 0
16. Un graf orientat este memorat cu ajutorul listelor alăturate de adiacenţă. Suma elementelor de pe ultima linie a matricii de adiacenţă asociată grafului este egală cu:
1:(5,6); 4:(1,2);
2:(1,5); 5:(2);
3:(1,5); 6:(2, 4, 5);
a. 3 b. 0 c. 1 d. 5
17. Graful orientat G este reprezentat prin matricea de adiacenţă alăturată.
Câte vârfuri din graful dat au gradul interior egal cu gradul exterior?
0 1 0 0 1
1 0 1 0 0
0 0 0 1 1
0 1 0 0 1
1 0 0 0 0
a. 0 b. 1 c. 3 d. 2
18. Care dintre următoarele propoziţii este falsă pentru graful orientat G dat prin matricea de adiacenţă alăturată?
0 1 1 0 0
0 0 1 1 0
0 0 0 1 1
1 1 0 0 0
0 0 0 1 0
a. există cel puţin un nod în graful G care are gradul intern egal cu cel extern
b. graful G nu are circuite
c. există cel puţin un drum între oricare
două noduri ale grafului G
d. graful G are 9 arce.
19. Care sunt arcele care alcătuiesc un drum elementar de lungime maximă de la nodul 1 la nodul 5 pentru graful orientat cu şase noduri, numerotate de la 1 la 6, reprezentat prin matricea de adiacenţă alăturată?
0 1 1 1 0 0
0 0 0 0 0 1
0 1 0 1 0 0
0 0 1 0 0 1
0 1 0 0 0 0
0 0 0 0 1 0
20. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6, ale cărui arce sunt:
(2,1),(3,6),(4,1),(4,3),(4,5),(5,2), (6,4),(1,4). Două circuite sunt distincte dacă ele diferă prin cel puţin un arc.
a) Care este numărul total de circuite din acest graf?
b) Care este numărul total de circuite elementare din acest graf?
21. Fie graful orientat din figura alăturată. Care este numărul de circuite elementare distincte? Două circuite elementare sunt distincte dacă diferă prin cel puţin un arc.
a. 0 b. 1 c. 2 d. 3
22. Se consideră un graf orientat cu 5 vârfuri şi 8 arce. Care dintre următoarele şiruri de numere pot fi gradele exterioare ale vârfurilor acestui graf? (4p.)
a. 2, 3, 1, 1, 1 b. 2, 2, 6, 5, 1
c. 1, 0, 1, 1, 1, 1 d. 1, 1, 0, 2, 1
23. Se consideră graful orientat din figura alăturată. Câte dintre vârfurile grafului au
gradul intern egal cu gradul extern?
a. 3 b. 2 c. 1 d. 4
24. Variabila n memorează un număr natural nenul. Care este numărul total de grafuri orientate distincte care se pot forma cu aceste noduri? Două grafuri orientate sunt distincte dacă matricele lor de adiacenţă sunt diferite.
a. 4n*(n-1)/2 b. 3n*(n-1)/2
c. 4n*(n-1) d. 2n*(n-1)/2
25. Se consideră graful orientat G cu 6 vârfuri numerotate cu numerele de la 1 la 6, definit cu ajutorul listelor de adiacenţă alăturate. Care este numărul de circuite distincte din graful G? Două circuite sunt distincte dacă diferă prin cel puţin un arc.
1: 2 6
2: 3
3:
4: 3
5: 4 6
6: 3
26. Care dintre vârfurile grafului orientat din figura alăturată, au gradul interior un număr par?
27. Într-un graf orientat G cu 6 vârfuri numerotate cu numere distincte de la 1 la 6, există arc de la vârful i la vârful j dacă şi numai dacă i<j şi j-i>1. Care sunt vârfurile din graf ce au gradul interior mai mare decât gradul exterior?
28. Se dă graful orientat definit prin matricea de adiacenţă alăturată. Precizaţi câte noduri ale grafului au gradul interior egal cu gradul exterior.
0 1 0 1 0 0
1 0 1 0 0 0
1 1 0 0 0 1
0 0 0 0 1 0
0 0 1 0 0 1
0 0 0 0 1 0
a. 5 b. 6 c. 3 d. 4
29. Se consideră graful orientat cu 5 noduri, numerotate de la 1 la 5, definit prin matricea de adiacenţă alăturată. Indicaţi numărul minim de arce care trebuie adăugate grafului astfel încât, pentru orice două noduri x şi y ale sale, să existe cel puţin un drum de la x la y.
0 1 0 0 0
0 0 1 1 1
0 1 0 1 0
0 0 1 0 0
0 0 0 0 0
30. Se consideră graful orientat cu 6 noduri, numerotate de la 1 la 6, şi arcele (1,2), (1,5), (1,6), (2,3), (4,3), (4,5), (6,5). Care este numărul minim de arce care trebuie
adăugate grafului astfel încât acesta să conţină cel puţin un circuit elementar de lungime 4?
Pentru graful rezultat, daţi un exemplu de astfel de circuit. (6p.)
31. Se consideră graful orientat cu 7 vârfuri, numerotate de la 1 la 7, şi arcele (1,2), (2,5), (3,2), (3,4), (3,6), (5,6), (5,7), (6,1). Care este numărul minim de arce care trebuie adăugate acestui graf astfel încât, pentru orice două noduri x şi y, din mulţimea {1,2,3,4} să existe cel puţin un drum de la x la y? Enumeraţi arcele care trebuie adăugate.
32. Fie graful orientat cu 8 vârfuri, numerotate de la 1 la 8, şi arcele (1,2), (2,3), (3,1),
(4,5), (6,5), (5,7), (7,6), (7,4), (8,7). Numărul minim de arce care trebuie adăugate astfel încât, pentru oricare două vârfuri x şi y din graf să existe cel puţin un drum de la nodul x la nodul y este:
a. 2 b. 4 c. 0 d. 1
33. Fie graful orientat cu 7 vârfuri numerotate de la 1 la 7 şi arcele (1,2) (2,3) (3,1)
(4,5) (5,6) (5,7) (6,7) (7,4). Care este numărul minim de arce şi care sunt acele arce care ar trebui eliminate pentru ca graful parţial obţinut să nu mai conţină circuite?
34. Se consideră un graf orientat cu 6 vârfuri, numerotate de la 1 la 6, cu proprietatea că există un arc cu extremitea iniţială în vârful i şi extremitea finală în vârful j dacă i este divizor al lui j. Gradul interior (intern) maxim al vârfurilor din acest graf este:
a. 3 b. 5 c. 4 d. 2
35. Fie graful orientat cu 9 vârfuri numerotate de la 1 la 9 şi arcele (1,2) (2,3) (3,1)
(4,5) (5,6) (5,7) (6,7) (7,4) (8,7) (8,9) (9,8). Care sunt vârfurile cu proprietatea că gradul interior este egal cu gradul exterior ?
36. Se consideră graful orientat cu nodurile numerotate de la 1 la 5 şi arcele (1,2),
(1,5),(2,1), (2,3), (2,5), (3,4), (5,2), (5,4). Care este lungimea maximă a unui drum format din noduri distincte, de la nodul 1 la nodul 4?
a. 5 b. 6 c. 4 d. 7
37. Se consideră graful orientat cu nodurile numerotate de la 1 la 5 şi arcele (1,2), (1,4), (2,1), (2,5), (3,2), (4,3), (5,1), (5,4). Care este numărul minim de arce care poate fi adăugat pentru ca toate nodurile să aibă şi gradul extern şi gradul intern numere pare?
a. 1 b. 2 c. 3 d. 4
38. Se consideră graful orientat cu vârfurile numerotate de la 1 la 7 şi arcele (1,2),
(1,7), (2,3), (3,2), (3,4), (4,3), (5,4), (5,6), (6,4), (7,6). Câte noduri cu gradul extern par există în graful dat?
a. 3 b. 2 c. 4 d. 0
39. Un graf neorientat cu 5 noduri, numerotate de la 1 la 5, este reprezentat prin listele de adiacenţă alăturate. Transformaţi acest graf într-un graf orientat prin înlocuirea fiecărei muchii cu exact un arc, astfel încât în graful orientat care rezultă să existe cel puţin un drum de la orice nod x până la orice nod y, (x≠y). Scrieţi reprezentarea grafului orientat pe care l-aţi construit, prin liste de adiacenţă.
1: 2, 3
2: 1, 3, 5
3: 1, 2, 4, 5
4: 3, 5
5: 2, 3, 4
40. Se dă graful orientat cu 5 noduri, numerotate de la 1 la 5, definit prin matricea de adiacenţă alăturată. Determinaţi un drum de lungime maximă de la nodul 1 la nodul 5 , care să fie alcătuit din arce distincte două câte două. Scrieţi lungimea drumului
determinat precum şi arcele care îl compun (lungimea unui drum este egală cu numărul de arce care îl compun).
0 1 0 0 0
0 0 1 1 1
0 1 0 1 0
0 0 1 0 0
0 0 0 0 0
Niciun comentariu:
Trimiteți un comentariu