Cuprins

Laborator 06: Introducere în teoria grafurilor


1 Obiectivele laboratorului

2 Grafuri neorientate

2.1 Definiție

Un graf neorientat este o pereche ordonată de multimi(X,U),unde:

2.2 Structură

Un graf are următoarele elemente:

Ce relaţie există între suma gradelor tuturor vârfurilor dintr-un graf neorientat şi numărul de muchii?
Într-un graf complet, oricare două noduri sunt adiacente. Câte muchii are un astfel de graf?



2.3 Reprezentare

Având lista de adiacentă:

Un graf parțial este un graf obținut din graful inițial prin eliminarea uneia sau mai multor muchii
Un subgraf este un graf obținut din graful inițial prin eliminarea unui număr de noduri impreună cu muchiile formate cu acele noduri
Se numește lanț într-un graf,o succesiune de vârfuri L={v1,v2,…,vk},cu proprietatea că oricare două vârfuri consecutive sunt adiacente,adică există o muchie între acestea.

Se numeşte lanţ elementar un lanţ în care nu se repetă vârfuri.

Se numeşte lanţ simplu un lanţ în care nu se repetă muchii.

Se numeşte ciclu un lanţ simplu pentru care primul şi ultimul vârf coincid.

Se numeşte ciclu elementar un ciclu în care nu se repetă vârfuri(excepţie primul şi ultimul).

3 Grafuri orientate

3.1 Definiție

Un graf orientat este o pereche ordonată de mulțimi G={X,U},unde:

3.2 Structură

Într-un graf orientat, distingem:

Ce relaţie există între suma gradelor exterioare, suma gradelor interioare şi numărul de arce?

3.3 Reprezentare

Matricea de adiacență - este o matrice a cu n linii și n coloane,în care elementele a[i,j] se definesc astfel:


Matricea vârfuri-arce este o matrice B cu n = |X| linii și m = |U| coloane,în care fiecare element b[i,j] este:

4 Parcurgerea grafurilor

4.1 Parcurgerea în lățime

Parcurgerea în lățime (Breadth-First-Search -BFS) este o metodă ce presupune vizitarea nodurilor în următoarea ordine:

4.1.1 Implementare

Pe masură ce algoritmul avansează,se colorează nodurile în felul următor:

Se păstrează informațiile despre distanța până la nodul sursă. Se obține arborele BFS


Pentru implementarea BFS se utilizează o coadă (Q) în care inițial se află doar nodul sursă.Se vizitează pe rând vecinii acestui nod și se pun și ei în coadă.În momentul în care nu mai există vecini nevizitați,nodul sursă este scos din coadă. 

Pentru fiecare nod u din graf
{
     culoare[u]=alb
     d[u] = infinit    //in d se retine distanta pana la nodul sursa
     p[u] = null       //
}
 
culoare[sursă]=gri
d[sursă]=0
enqueue(Q,sursă)     //punem nodul sursă în coada Q
 
Cât timp coada Q nu este vidă
{
     v=dequeue(Q)   //extragem nodul v din coadă
     pentru fiecare u dintre vecinii lui v
          dacă culoare[u] == alb
          {
               culoare[u] = gri
               p[u] = v
               d[u] = d[v] + 1
               enqueue(Q,u)   //adăugăm nodul u în coadă
          }
     culoare[v] = negru   //am terminat explorarea vecinilor lui v
}


Exemplu

4.2 Parcurgerea în adâncime

Parcurgea în adâncime (Depth-First-Search -DFS) presupune explorarea nodurilor în următoarea ordine:

Această metoda de parcurgere pune prioritate pe explorarea în adâncime (pe distanțe tot mai mari față de nodul sursă).

4.2.1 Implementare

Spre deosebire de BFS, DFS utilizează o stivă în loc de o coadă. Putem defini o stivă sau ne putem folosi de stiva compilatorului, prin apeluri recursive. 

funcţie pasDFS(curent)
{
	pentru fiecare u dintre vecinii nodului curent
          dacă culoare[u] == alb
          {
               culoare[u] = gri
               p[u] = curent
               d[u] = d[curent] + 1
               pasDFS(u);   //adăugăm nodul u în "stivă" şi începem explorarea
          }
	culoare[curent] = negru   //am terminat explorarea vecinilor nodului curent
	//ieşirea din funcţie este echivalentă cu eliminarea unui element din stivă
}
Pentru fiecare nod u din graf
{
     culoare[u]=alb
     d[u] = infinit    //in d se retine distanta pana la nodul sursa
     p[u] = null
}
culoare[sursă] = gri;
d[sursă] = 0;
 
//se apelează iniţial pasDFS(sursă)

5. Exerciţii

Implementaţi, pentru fiecare cerinţă, câte o funcţie care:

  1. creează matricea de adiacenţă pentru un graf neorientat cu N noduri, folosindu-se de o listă(sau o matrice cu 2 coloane) de muchii(la alegere - muchiile citite în funcţie sau primite printr-un parametru).
  2. calculează gradul fiecărui nod. Afişaţi numărul de noduri izolate şi numărul de noduri terminale.
  3. primeşte un şir de noduri şi verifică dacă acesta poate reprezenta un lanţ.
  4. primeşte un şir de noduri şi afişează matricea de adiacenţă a subgrafului format cu nodurile respective
  5. afişează matricea de adiacenţă a unui graf orientat construit astfel:
    • graful orientat are atâtea arce câte muchii are graful neorientat
    • există arc în graful orientat între două noduri daca şi numai dacă există muchie între aceleaşi noduri în graful neorientat.
    • Extra - câte astfel de grafuri orientate pot fi formate?

Cerinţele 2, 3, 4 şi 5 se vor folosi de matricea de adiacenţă a grafului de la cerinţa 1.

5.1. Exerciții - schelet de laborator

Pentru acest laborator puteți descărca scheletul de cod de aici. Descărcați arhiva și dezarhivați-o.

Linux

Puteti folosi utilitarul wget pentru descarcare si utilitarul unzip pentru dezarhivare.

Pentru compilare folositi comanda make. Pentru rulare puteti folosi comanda make run sau ./graph.

De interviu

Un lanţ hamiltonian este un lanţ elementar(nu se repetă nodurile) care trece prin fiecare nod.

Un lanţ eulerian este un lanţ simplu(nu se repetă muchiile) care trece prin fiecare muchie.

Spunem că muchia (A, B) este pod pentru drumul de la S la D dacă orice lanţ care duce de la S la D trece prin muchia (A, B).