Conexitatea grafurilor
1. Lanțul: este o succesiune de noduri cu proprietatea ca oricare doua noduri vecine sunt adiacente in graf.
Clasificarea lanţurilor:
o elementare – conţin numai noduri distincte două câte două;
o neelementare – conţin noduri care se repetă;
o simple – toate muchiile (arcele) din lanţ sunt diferite între ele;
o compuse - în lanţ se pot repeta unele muchii (arce).
Algoritmul pentru determinarea tuturor lanțurilor elementare -se va folosi metoda backtracking
Clasificarea lanţurilor:
o elementare – conţin numai noduri distincte două câte două;
o neelementare – conţin noduri care se repetă;
o simple – toate muchiile (arcele) din lanţ sunt diferite între ele;
o compuse - în lanţ se pot repeta unele muchii (arce).
Algoritmul pentru determinarea tuturor lanțurilor elementare -se va folosi metoda backtracking
Graful orientat -trecerea de la nodul de
pe nivelul k-1 la nodul de pe nivelul k se face, în graf, în sensul arcului sau
în sens invers arcului.
Aplicații:
Din fișierul graf_n.in se citesc numărul de noduri și extremitățile muchiilor unui graf neorientat (sau graf_o.in pentru graful orientat). Să se verifice dacă:
a. Un șir de k numere citite de la tastaură reprezintă un lanț simplu pentru graf.
b. Caută și afișează toate lanțurile de lungime d, unde valoarea lui d se citește de la tastatură. Dacă nu există un astfel de lanț, se afișează un mesaj de informare.
c. Caută și afișează toate lanțurile elementare de lungime minimă dintre două noduri x și y. Dacă nu există un astfel de lanț, se afișează un mesaj de informare.
d. Caută și afișează toate lanțurile dintre două noduri x și y care trec prin z. Valorile pentru x, y și z se citesc de la tastatură. Dacă nu există un astfel de lanț, se afișează un mesaj de informare.
Din fișierul graf_n.in se citesc numărul de noduri și extremitățile muchiilor unui graf neorientat (sau graf_o.in pentru graful orientat). Să se verifice dacă:
a. Un șir de k numere citite de la tastaură reprezintă un lanț simplu pentru graf.
b. Caută și afișează toate lanțurile de lungime d, unde valoarea lui d se citește de la tastatură. Dacă nu există un astfel de lanț, se afișează un mesaj de informare.
c. Caută și afișează toate lanțurile elementare de lungime minimă dintre două noduri x și y. Dacă nu există un astfel de lanț, se afișează un mesaj de informare.
d. Caută și afișează toate lanțurile dintre două noduri x și y care trec prin z. Valorile pentru x, y și z se citesc de la tastatură. Dacă nu există un astfel de lanț, se afișează un mesaj de informare.
2. Ciclul este un lanţ care are
toate muchiile distincte două câte două şi extremităţile coincid.
Algoritmul pentru determinarea tuturor ciclurilor elementare -se va folosi metoda backtracking.
Algoritmul pentru determinarea tuturor ciclurilor elementare -se va folosi metoda backtracking.
Aplicații.
Din fișierul graf_n.in se citesc numărul de noduri și extremitățile muchiilor unui graf neorientat (sau graf_o.in pentru variant de graf orientat). Să se verifice dacă:
a. Un șir de k numere citite de la tastaură reprezintă un ciclu elementar pentru graf.
b. Caută și afișează toate ciclurile de lungime d și le afișează, unde valoarea lui d se citește de la tastatură. Dacă nu există un astfel de ciclu, se afișează un mesaj de informare.
c. Caută și afișează toate ciclurile elementare de lungime maximă care trec prin nodul x. Valoarea lui x se citește de la tastatură. Dacă nu există un astfel de ciclu, se afișează un mesaj de informare.
d. Caută și afișează toate ciclurile elementare care trec prin toate nodurile grafului. Dacă nu există un astfel de ciclu, se afișează un mesaj de informare.
Din fișierul graf_n.in se citesc numărul de noduri și extremitățile muchiilor unui graf neorientat (sau graf_o.in pentru variant de graf orientat). Să se verifice dacă:
a. Un șir de k numere citite de la tastaură reprezintă un ciclu elementar pentru graf.
b. Caută și afișează toate ciclurile de lungime d și le afișează, unde valoarea lui d se citește de la tastatură. Dacă nu există un astfel de ciclu, se afișează un mesaj de informare.
c. Caută și afișează toate ciclurile elementare de lungime maximă care trec prin nodul x. Valoarea lui x se citește de la tastatură. Dacă nu există un astfel de ciclu, se afișează un mesaj de informare.
d. Caută și afișează toate ciclurile elementare care trec prin toate nodurile grafului. Dacă nu există un astfel de ciclu, se afișează un mesaj de informare.
3. Drumul este un lant cu proprietatea ca oricare in care deplasarea intre doua noduri vecine se face in sensul arcelor
Definiții:
Lungimea unui drum este dată de numărul de arce care îl compun.
Subdrumul este format dintr-un şir continuu de noduri din drum.
Drumul elementar este drumul în care nodurile sunt distincte două câte două.
Drumul simplu este drumul în care arcele sunt distincte două câte două.
Algoritmi pentru determinarea drumurilor elementare -se va folosi metoda backtracking.
Definiții:
Lungimea unui drum este dată de numărul de arce care îl compun.
Subdrumul este format dintr-un şir continuu de noduri din drum.
Drumul elementar este drumul în care nodurile sunt distincte două câte două.
Drumul simplu este drumul în care arcele sunt distincte două câte două.
Algoritmi pentru determinarea drumurilor elementare -se va folosi metoda backtracking.
Algoritmul Roy-Warshall de determinare a matricei drumurilor
Dacă nu există un arc de la nodul i la nodul j, considerăm că există drum de la nodul i la nodul j dacă există un nod k (k≠i şi k≠j) care are proprietea că există un drum de la nodul i la nodul k şi un drum de la nodul k la nodul j.
Implementarea algoritmului: transforma matricea de adiacenţă în matricea drumurilor
Implementarea algoritmului: transforma matricea de adiacenţă în matricea drumurilor
4. Circuitul este un
drum care are toate arcele distincte două câte două şi extremităţi care coincid.
Definiţie: Circuitul elementar este circuitul în care toate nodurile sunt distincte două câte două.
Algoritm pentru determinarea circuitelor elementare se va folosi metoda backtracking.
Definiţie: Circuitul elementar este circuitul în care toate nodurile sunt distincte două câte două.
Algoritm pentru determinarea circuitelor elementare se va folosi metoda backtracking.
Aplicație: Într-un grup sunt n elevi, băieţi şi fete, pe care-i numerotăm 1, 2, ..., n. Fiecare elev cunoaşte o parte din ceilalţi elevi. Relaţia de cunoştinţă nu este neaparat reciprocă (dacă x îl cunoaşte pe z, nu înseamnă că şi y trebuie să-l cunoască pe x). Unul dintre elevi are un CD foarte valoros, cu multe jocuri demonstrative, pe care toţi membrii grupului vor să-l aibe fie şi pentru scurt timp, pentru a şi-l copia pe calculatorul propriu. CD-ul circulă printre membrii grupului în felul următor: fiecare elev după ce l-a primit de la altcineva îl dă mai departe, dar numai unui elev pe care îl cunoaşte, pentru că nu doreşte să ajungă în mâna unor persoane în care nu poate avea încredere. Determinaţi o modalitate (dacă există) prin care CD-ul să circule pe la fiecare elev o singură dată, transmiterea lui făcându-se numai către o cunoştinţă, iar în final CD-ul să ajungă din nou la proprietarul său.
Indicaţie: Pentru a rezolva cerinţa trebuie să construiţi un circuit elementar care să cuprindă toţi elevii grupului, pornind de la elevul care are CD-ul valoros.
Indicaţie: Pentru a rezolva cerinţa trebuie să construiţi un circuit elementar care să cuprindă toţi elevii grupului, pornind de la elevul care are CD-ul valoros.
5. Graful conex -pentru orice pereche
de noduri distincte, există un lanţ care să le lege.
Definiţie: Dacă graful G=(X,U) nu este conex, se numeşte componentă conexă a grafului un subgraf conex al său C=(X’,U’), maximal în raport cu această proprietate.
Definiţie: Dacă graful G=(X,U) nu este conex, se numeşte componentă conexă a grafului un subgraf conex al său C=(X’,U’), maximal în raport cu această proprietate.
Aplicație: Să se determine componentele conexe ale unui graf neorientat.
Soluție: Se folosește parcurgerea BF pornind de la un nod oarecare.
Soluție: Se folosește parcurgerea BF pornind de la un nod oarecare.
Aplicaţii.
1. X reprezintă o mulţime de calculatoare, şi U indică pentru fiecare calculator care sunt calculatoarele conectate direct la acesta. Evident, fiecare conexiune este în ambele sensuri. Să se determine câte reţele independente există, şi care sunt calculatoarele care compun fiecare reţea .
Soluție: Se află componentele conexe ale grafului neorientat în care nodurile sunt calculatoarele iar muchiile sunt conexiunile directe dintre acestea.
Teoremă: Numărul minim de muchii mmin necesare pentru ca un graf neorientat, cu n noduri, să fie conex este n-1.
1. X reprezintă o mulţime de calculatoare, şi U indică pentru fiecare calculator care sunt calculatoarele conectate direct la acesta. Evident, fiecare conexiune este în ambele sensuri. Să se determine câte reţele independente există, şi care sunt calculatoarele care compun fiecare reţea .
Soluție: Se află componentele conexe ale grafului neorientat în care nodurile sunt calculatoarele iar muchiile sunt conexiunile directe dintre acestea.
Teoremă: Numărul minim de muchii mmin necesare pentru ca un graf neorientat, cu n noduri, să fie conex este n-1.
Exemple de grafuri conexe cu n noduri și număr minim de muchii:
→ Fiecare nod este legat de alte două, cu excepția a două noduri terminale.
→ Un nod este legat de toate celelate n-1 noduri.
→ Fiecare nod este legat de alte două, cu excepția a două noduri terminale.
→ Un nod este legat de toate celelate n-1 noduri.
Aplicaţie. Fiind dat un graf neorientat conex G=(X,U), să se determine un vârf x∊X astfel încât subgraful indus de mulțimea de vârfuri X\{x} să fie conex.
Soluție: Pornind dintr-un nod oarecare al grafului (de exemplu nodul 1), deplasându-ne pe muchii, în noduri neparcurse încă, atât cât este posibil. Când ajungem într-un nod din care nu ne mai putem deplasa folosind noduri neparcurse, înseamnă că am găsit un un nod a cărui eliminare (împreună cu muchiile incidente lui) nu schimbă conexitatea grafului.
Soluție: Pornind dintr-un nod oarecare al grafului (de exemplu nodul 1), deplasându-ne pe muchii, în noduri neparcurse încă, atât cât este posibil. Când ajungem într-un nod din care nu ne mai putem deplasa folosind noduri neparcurse, înseamnă că am găsit un un nod a cărui eliminare (împreună cu muchiile incidente lui) nu schimbă conexitatea grafului.
Propoziţia 1: Dacă un graf cu n noduri are p componente conexe, atunci numărul minim de muchii care trebuie adăugate, ca să devină conex, este p-1.
Aplicație: Pentru un graf neconex, să se adauge un număr minim de muchii astfel încât graful să devină conex.
Soluție: Se determină mai întâi componentele conexe ale grafului folosind algoritmul de parcurgere în adâncime, BF.
Aplicație: Pentru un graf neconex, să se adauge un număr minim de muchii astfel încât graful să devină conex.
Soluție: Se determină mai întâi componentele conexe ale grafului folosind algoritmul de parcurgere în adâncime, BF.
Propoziţia 2: Dacă un graf conex cu n noduri are n-1 muchii, atunci orice pereche de noduri este legată printr-un lanţ, şi numai unul.
Aplicație: Propoziția se poate verifica cu ajutorul programului care caută toate lanțurile elementare dintre oricare două noduri.
Aplicație: Propoziția se poate verifica cu ajutorul programului care caută toate lanțurile elementare dintre oricare două noduri.
Propoziţia 3: Dacă un graf cu n noduri şi m muchii este conex,numărul maxim de muchii care se pot elimina pentru a obţine un graf parţial conex este m-n+1.
Teorema: Un graf neorientat conex cu n noduri şi n-1 muchii este aciclic şi maximal în raport cu această proprietate.
Propoziţia 4: Dacă un graf neorientat conex are n noduri și m muchii, numărul de muchii care trebuie eliminate, pentru a obține un graf parțial conex aciclic, este egal cu m-n+1.
Propoziţia 5: Dacă un graf are n noduri, m muchii şi p componente conexe, numărul de muchii care trebuie eliminate, pentru a obţine un graf parţial aciclic, este egal cu m-n+p.
Propoziţia 5 : Pentru a obţine, dintr-un graf neorientat conex, două componente conexe, numărul minim de muchii care trebuie înlăturate mmin este egal cu gradul minim din graf.
Teorema: Numărul maxim de muchii mmax dintr-un graf neorientat, cu n noduri şi p componente conexe este:
Teorema: Un graf neorientat conex cu n noduri şi n-1 muchii este aciclic şi maximal în raport cu această proprietate.
Propoziţia 4: Dacă un graf neorientat conex are n noduri și m muchii, numărul de muchii care trebuie eliminate, pentru a obține un graf parțial conex aciclic, este egal cu m-n+1.
Propoziţia 5: Dacă un graf are n noduri, m muchii şi p componente conexe, numărul de muchii care trebuie eliminate, pentru a obţine un graf parţial aciclic, este egal cu m-n+p.
Propoziţia 5 : Pentru a obţine, dintr-un graf neorientat conex, două componente conexe, numărul minim de muchii care trebuie înlăturate mmin este egal cu gradul minim din graf.
Teorema: Numărul maxim de muchii mmax dintr-un graf neorientat, cu n noduri şi p componente conexe este:
6. Graful tare conex -între orice pereche de noduri diferite între ele, există un drum care să le lege.
Definiţie: Se numeşte componentă tare conexă a grafului, un subgraf tare conex al său C=(X’,U’), maximal în raport cu această proprietate.
Algoritmi pentru determinarea conexităţii grafurilor orientate1. O soluţie în complexitate O(N3) este transformarea matricei de adiacenţă într-o matrice a drumurilor cu ajutorul algoritmului lui Roy-Warshall.
2. 2. O soluţie în complexitate O(N + M) în cazul mediu, dar O(N2) în cazul defavorabil poartă numele de algoritmul plus-minus. Algoritmul Kosaraju.
2. 2. O soluţie în complexitate O(N + M) în cazul mediu, dar O(N2) în cazul defavorabil poartă numele de algoritmul plus-minus. Algoritmul Kosaraju.
7. Aplicații practice
7.1. Rețele de telefonie.
Într-un oraș există n abonați și mai multe rețele de telefonie. Se știe că doi abonați aparțin aceleași rețele de telefonie dacă primul abonat îl poate contacta pe cel de-al doilea (direct sau prin intermediul altor abonați) și reciproc. Problema constă în determinarea tuturor rețelelor de telefonie, prin specificarea abonaților fiecarei rețele.
7.1. Rețele de telefonie.
Într-un oraș există n abonați și mai multe rețele de telefonie. Se știe că doi abonați aparțin aceleași rețele de telefonie dacă primul abonat îl poate contacta pe cel de-al doilea (direct sau prin intermediul altor abonați) și reciproc. Problema constă în determinarea tuturor rețelelor de telefonie, prin specificarea abonaților fiecarei rețele.
7.2. Algoritmul lui Kosaraju - Sharir :