Grafuri speciale
1. Graful hamiltonian
Definiţie. Un graf care conţine un ciclu hamiltonian se numeşte graf hamiltonian.
Propoziţie: Graful complet Kn este hamiltonian.
Exemplu: Problema comis voiajorului
Un comis-voiajor trebuie să viziteze un număr de n oraşe pentru a-şi prezenta produsele. Se cunoaşte costul deplasării între localităţi. Comis-voiajorul doreşte să treacă o singură dată prin fiecare oraş, iar la întoarcere să revină în primul oraş, astfel încât costul deplasării să fie minim.
Localităţile formează nodurile unui graf, iar traseul voiajorului trebuie să fie un ciclu hamiltonian în acest graf. Dacă există mai multe cicluri hamiltoniene, se va alege cel cu costul minim.
Putem construi un algoritm euristic de tip Greedy care furnizează o soluţie a problemelor de tip comis-voiajor într-un interval de timp polinomial.
Definiţie. Un graf care conţine un ciclu hamiltonian se numeşte graf hamiltonian.
Propoziţie: Graful complet Kn este hamiltonian.
Exemplu: Problema comis voiajorului
Un comis-voiajor trebuie să viziteze un număr de n oraşe pentru a-şi prezenta produsele. Se cunoaşte costul deplasării între localităţi. Comis-voiajorul doreşte să treacă o singură dată prin fiecare oraş, iar la întoarcere să revină în primul oraş, astfel încât costul deplasării să fie minim.
Localităţile formează nodurile unui graf, iar traseul voiajorului trebuie să fie un ciclu hamiltonian în acest graf. Dacă există mai multe cicluri hamiltoniene, se va alege cel cu costul minim.
Putem construi un algoritm euristic de tip Greedy care furnizează o soluţie a problemelor de tip comis-voiajor într-un interval de timp polinomial.
Algoritmul pentru parcurgerea unui graf hamiltonian
-Pentru generarea tuturor lanţurilor elementare se foloseşte metoda backtracking.
-Pentru generarea tuturor lanţurilor elementare se foloseşte metoda backtracking.
Teorema: (Dirac, 1951)Dacă graful G=(X,U) este un graf cu mai mult de două noduri (n≥3) şi gradul fiecărui nod x X satisface condiţia d(x)≥n/2, atunci graful G este hamiltonian.
Observaţie. Această teoremă precizează doar condiţia suficientă ca un graf să fie hamiltonian. Această condiţie nu este şi necesară.
Observaţie. Această teoremă precizează doar condiţia suficientă ca un graf să fie hamiltonian. Această condiţie nu este şi necesară.
Aplicații practice
Orice problemă la care cerinţa este de a găsi un traseu – care porneşte dintr-un anumit punct, trebuie să treacă prin puncte precizate, cu revenire la punctual de pornire – se rezolvă prin găsirea unui ciclu hamiltonian. De exemplu:
- O firmă de mesagerie trebuie să distribuie zilnic colete la mai multe adrese. Maşina care distribuie aceste colete pleacă de la sediul firmei, ajunge la mai multe puncte din oraş şi revine la sediul firmei. Legătura directă dintre două puncte este caracterizată prin distanţa măsurată în kilometric (costul asociat fiecărei muchii). Se cere să se găsească traseul de lungime minimă pe care trebuie să-l parcurgă maşina.
- O persoană doreşte să facă un circuit prin ţară şi să viziteze mai multe puncte turistice, plecând din localitatea de domiciliu. Legătura directă dintre două puncte turistice este caracterizată prin distanţa măsurată în kilometri (costul asociat fiecărei muchii). Se cere să se găsească circuitul turistic de lungime minimă.
Orice problemă la care cerinţa este de a găsi un traseu – care porneşte dintr-un anumit punct, trebuie să treacă prin puncte precizate, cu revenire la punctual de pornire – se rezolvă prin găsirea unui ciclu hamiltonian. De exemplu:
- O firmă de mesagerie trebuie să distribuie zilnic colete la mai multe adrese. Maşina care distribuie aceste colete pleacă de la sediul firmei, ajunge la mai multe puncte din oraş şi revine la sediul firmei. Legătura directă dintre două puncte este caracterizată prin distanţa măsurată în kilometric (costul asociat fiecărei muchii). Se cere să se găsească traseul de lungime minimă pe care trebuie să-l parcurgă maşina.
- O persoană doreşte să facă un circuit prin ţară şi să viziteze mai multe puncte turistice, plecând din localitatea de domiciliu. Legătura directă dintre două puncte turistice este caracterizată prin distanţa măsurată în kilometri (costul asociat fiecărei muchii). Se cere să se găsească circuitul turistic de lungime minimă.
2. Graful eulerian
Aplicaţie . Orasul Königsberg era asezat pe coasta Marii Baltice, la gurile râului Pregel. Pe râu erau două insule legate de țărmuri și între ele de șapte poduri ca în figura V.2.1.
Oamenii care cutreierau aceste insule au observat că dacă porneau de pe malul sudic al râului, nu puteau să-și planifice plimbarea astfel încât să traverseze fiecare pod o singură dată. Se părea că ori trebuia să sară un pod ori să-l traverseze de două ori.
Această problemă poate fi generalizată astfel. Fiind dată o figură geometrică construită din linii, este posibilă desenarea acesteia fără să ridicăm creionul de pe hîrtie şi fără să desenăm de mai multe ori o linie?
Această problemă poate fi generalizată astfel. Fiind dată o figură geometrică construită din linii, este posibilă desenarea acesteia fără să ridicăm creionul de pe hîrtie şi fără să desenăm de mai multe ori o linie?
Soluție: Figura geometric poate fi reprezentată printr-un graf neorientat, în care nodurile sunt vârfurile figurii, iar muchiile, laturile figurii. Problema constă în a găsi un ciclu eulerian sau, dacă nu este graf eulerian, un lanț eulerian. In cazul acesta, multigraful trebuie să conțină exact două noduri de grad impar, care vor fi nodurile de inceput și sfârșit ale lanțului.
Exemplu: Pentru graful din figura următoare avem două noduri de grad impar, respectiv nodurile 4 și 1. Pentru a găsi lanțul eulerian se pleacă din unul din aceste noduri, și anume L={1,2,5,3,2,4,3,1,4}.
Exemplu: Pentru graful din figura următoare avem două noduri de grad impar, respectiv nodurile 4 și 1. Pentru a găsi lanțul eulerian se pleacă din unul din aceste noduri, și anume L={1,2,5,3,2,4,3,1,4}.
Teorema: Un graf G=(X,U), care nu conţine noduri izolate, este eulerian dacă şi numai dacă este conex şi gradele tuturor nodurilor sunt numere pare.
Definiţie: Un graf care conţine un ciclu eulerian se numeşte graf eulerian.
Definiţie: Un graf care conţine un ciclu eulerian se numeşte graf eulerian.
Algoritmul pentru parcurgerea unui graf eulerian
Implementarea algoritmului se relizează cu ajutorul matricei de adiacenţă şi a vectorului g în care se memorează gradul fiecărui nod. Algoritmul care determină dacă un graf este eulerian verifică dacă graful îndeplineşte condiţiile precizate în teoremă:
Implementarea algoritmului se relizează cu ajutorul matricei de adiacenţă şi a vectorului g în care se memorează gradul fiecărui nod. Algoritmul care determină dacă un graf este eulerian verifică dacă graful îndeplineşte condiţiile precizate în teoremă: