Definiția și Tipuri de Grafuri

Definiția Grafurilor

• Un graf este reprezentat ca o pereche ordonată de mulțimi: G = (V, E).
• V reprezintă o mulțime finită de noduri (vârfuri).
• E reprezintă o mulțime de muchii (arce), fiecare muchie fiind o pereche de noduri din V.

Tipuri de Grafuri

• Graf neorientat: muchiile nu sunt ordonate.
• Graf orientat (digraf): muchiile sunt perechi ordonate (arce).
• Graf ponderat: muchiilor li se asociază valori numerice (ponderi).
• Graf neponderat: muchiile nu au ponderi.
• Graf complet: între oricare două noduri există o muchie.
• Graf conex: între oricare două noduri există un drum.
• Graf aciclic: nu conține cicluri.
• Arbore: graf conex aciclic.
• Graf bipartit: nodurile pot fi împărțite în două mulțimi disjuncte, fiecare muchie conectând un nod dintr-o mulțime cu unul din cealaltă.

Reprezentări ale Grafurilor

Matricea de adiacență

• Matrice A de dimensiune n x n, unde n este numărul de noduri.
• A[i][j] = 1 dacă există muchie între nodul i și nodul j; altfel, A[i][j] = 0.
• Pentru grafuri ponderate, A[i][j] poate reprezenta ponderea muchiei.

Lista de adiacență

• Un vector de liste, unde fiecare listă conține nodurile adiacente unui anumit nod.

Matricea de incidență

• Matrice B de dimensiune n x m, unde n este numărul de noduri și m este numărul de muchii.
• B[i][j] = 1 dacă nodul i este incident cu muchia j; altfel, B[i][j] = 0.

Algoritmi Importanți pentru Grafuri

• BFS (Breadth-First Search): parcurgere în lățime.
• DFS (Depth-First Search): parcurgere în adâncime.
• Sortare topologică: ordonarea nodurilor într-un graf orientat aciclic.
• Dijkstra: găsirea drumului minim de la un nod sursă la toate celelalte noduri într-un graf ponderat cu ponderi pozitive.
• Bellman-Ford: găsirea drumului minim de la un nod sursă la toate celelalte noduri într-un graf ponderat (detectează cicluri negative).
• Floyd-Warshall: găsirea drumului minim între toate perechile de noduri într-un graf ponderat.
• Arborele minim de acoperire (MST):
  • Prim: algoritm pentru găsirea MST.
  • Kruskal: algoritm pentru găsirea MST.

Proprietăți Utile ale Grafurilor

• Suma gradelor tuturor nodurilor într-un graf este egală cu de două ori numărul de muchii.
• Într-un graf bipartit, nu există cicluri de lungime impară.
• Un arbore cu n noduri are n-1 muchii.

Noțiuni Adiționale Despre Grafuri

• Ciclu Eulerian: trece prin fiecare muchie exact o dată.
• Ciclu Hamilton: trece prin fiecare nod exact o dată.
• Componente conexe: subgrafuri conexe maximale.
• Puncte de articulație: noduri a căror eliminare crește numărul de componente conexe.
• Punte: muchii a căror eliminare crește numărul de componente conexe.

Exemplu de Graf Neorientat

• Reprezentare grafică:

      A --- B
      |     |
      C --- D

Matricea de adiacență corespunzătoare

    A B C D
A  0 1 1 0
B  1 0 0 1
C  1 0 0 1
D  0 1 1 0

Lista de adiacență corespunzătoare

A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]