Cuprins
- Capitolul 1 Introducere 1
- 1.1. Definiţia unui graf 1
- 1. 2. Grade 3
- 1.3. Subgrafuri 3
- 1.4. Operaţii cu grafuri 3
- 1.5. Clase de grafuri 4
- 1.6. Drumuri şi circuite 5
- 1.7. Mulţimi separatoare, transversale şi mulţimi omogene 6
- 1.8. Algoritmi şi complexitate de calcul 7
- Capitolul 2 Metode de căutare 9
- 2.1. Căutarea în lăţime 9
- 2.1.1. Algoritmul 9
- 2.1.2. Implementarea C++ 9
- 2.1.3. Complexitate şi optimalitate 10
- 2.1.4 Aplicaţii ale BFS 11
- 2.2. Căutarea în adâncime 11
- 2.3. Metoda Greedy 13
- 2.4. Metoda backtracking 14
- 2.5. Metoda divide et impera 16
- 2.6. Metoda branch and bound 17
- Capitolul 3 Structuri de date 21
- 3.1. Liste 21
- 3.1.1. Liste simplu înlănţuite 21
- 3.1.2. Parcurgerea unei liste simplu înlănţuite 22
- 3.1.3. Liste dublu înlănţuite 22
- 3.1.4. Parcurgerea unei liste dublu înlănţuite 23
- 3.2. Arbori 24
- 3.2.1. Arbori liberi 24
- 3.2.2. Arbori cu rădăcină 24
- 3.2.3. Arbori binari 25
- 3.2.4. Parcurgerea arborilor binari 25
- Capitolul 4 Parcurgeri de grafuri 29
- 4.1. Parcurgerea BF a grafurilor 29
- 4.2. Parcurgerea DF a grafurilor 35
- 4.3. Aplicaţii 38
- 4.3.1. Sortarea topologică 38
- 4.3.2. Componentele conexe ale unui graf 39
- Capitolul 5 Probleme de drum în (di)grafuri 43
- 5.1. Problema celui mai scurt drum 43
- 5.1.1. Arborele Steiner 45
- 5.1.2. Algoritmul lui Dijkstra 46
- 5.1.3. Probleme similare şi algoritmi 49
- 5.1.4. Probleme legate de drum 50
- 5.1.5. Algoritmul Bellman-Ford 50
- 5.1.6. Algoritmul de căutare A∗ 54
- 5.1.7. Algoritmul Floyd-Warshall 57
- 5.1.8. Algoritmul lui Johnson 60
- 5.2. Probleme de conexiune. Teorema lui Menger şi aplicaţii 61
- 5.3. Structura grafurilor p-conexe 62
- 5.4. Problema drumului Hamiltonian 63
- 5.5. Problema ciclului Hamiltonian 64
- 5.6. Arborele parţial de cost minim 69
- 5.7. Algoritmul lui Prim 71
- 5.8. Algoritmul lui Kruskal 77
- Capitolul 6 Probleme de fluxuri în reţele 83
- 6.1. Problema fluxului maxim 83
- 6.2. Fluxuri de cost minim 89
- 6.3. Algoritmul Ford-Fulkerson 92
- Capitolul 7 Numărul de stabilitate şi densitatea unui graf 95
- 7.1. Mulţimi stabile şi clici 95
- 7.2. Problema mulţimii independente 96
- 7.3. Problema clicii 98
- 7.4. Determinarea mulţimilor stabile maximale 100
- Capitolul 8 Probleme de descompuneri în grafuri 103
- 8.1. Tipuri de descompuneri în grafuri 103
- 8.1.1. Descompunerea de tip 2 103
- 8.1.2. Descompunerea de tip 3 104
- 8.1.3. Descompunerea în funcţie de compoziţie 105
- 8.1.4. G-descompunerea 106
- 8.1.5. Descompunerea substituţie şi partiţionarea vârfurilor 107
- 8.2. Descompunerea slabă a grafurilor 111
- 8.2.1. Introducere 111
- 8.2.2. Descompunerea slabă a unui graf 111
- 8.3. Teorema celor patru culori 115
- 8.3.1. Colorarea grafurilor 117
- 8.3.2. Colorarea vârfurilor 117
- 8.3.3. Numărul cromatic 118
- 8.3.4. Aspecte algoritmice 118
- 8.3.5. Algoritmul Welsh – Powell 119
- 8.3.6. Polinomul cromatic 119
- Bibliografie 121
Extras din curs
Capitolul 1
INTRODUCERE
Pentru noţiunile din acest paragraf am consultat Behzad, Chartrand,
Foster, Croitoru, Olaru, Tomescu. Alte completări bibliografice sunt
precizate în momentul utilizării.
1.1. Definiţia unui graf
Un graf este o pereche G = (V,E), unde V este o mulţime finită
nevidă, iar E este o mulţime de submulţimi cu două elemente distincte ale lui
V. V se numeşte mulţimea vârfurilor şi numărul său de elemente, |V| este
ordinul grafului G. E este mulţimea muchiilor grafului G şi |E| este
dimensiunea grafului G. Când facem referire la mulţimea de vârfuri şi
muchii ale grafului G folosim V(G) şi E(G), respectiv.
Un digraf (graf orientat) este o pereche D=(V(D),A(D)) unde
V(D) este o mulţime finită nevidă (mulţimea vârfurilor digrafului D), iar
A(D)⊆V(D)×V(D) este mulţimea arcelor digrafului D.
Dacă e = {x,y} este o muchie a grafului G, vom nota, pe scurt,
{x,y} = xy (yx) şi vom spune că: muchia e este incidentă cu vârfuri1e x şi y;
vârfurile x şi y sunt adiacente în G; vârfurile x şi y sunt vecine în G; vârfurile
x şi y sunt extremităţile muchiei e.
Dacă v∈V(G), atunci mulţimea
NG (v)={w | w∈V(G)−{v}, vw∈E(G)},
se numeşte vecinătatea vârfului v în G.
NG (v)={w | w∈V(G)−{v}, vw∉E(G)}
se numeşte mulţimea nevecinilor vârfului v în G.
Dacă A,B⊆V(G), A∩B = 0/ atunci :
Preview document
Conținut arhivă zip
- A1.pdf
- A2.pdf
- A3.pdf
- A4.pdf
- A5.pdf
- A6.pdf
- A7.pdf
- A8.pdf
- A9.pdf
- Cuprins.pdf