Algoritmica Grafurilor

Imagine preview
(8/10 din 6 voturi)

Acest curs prezinta Algoritmica Grafurilor.
Mai jos poate fi vizualizat cuprinsul si un extras din document (aprox. 2 pagini).

Arhiva contine 10 fisiere pdf de 124 de pagini (in total).

Profesor: Talmaciu

Iti recomandam sa te uiti bine pe extras, cuprins si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, il poti descarca.

Fratele cel mare te iubeste, acest download este gratuit. Yupyy!

Domeniu: Inteligenta Artificiala

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 document

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 :

Fisiere in arhiva (10):

  • A1.pdf
  • A2.pdf
  • A3.pdf
  • A4.pdf
  • A5.pdf
  • A6.pdf
  • A7.pdf
  • A8.pdf
  • A9.pdf
  • Cuprins.pdf