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
Alții au mai descărcat și
Definitie Ofera o interfata pentru crearea unor familii de obiecte inrudite sau dependente intre ele, fara a specifica clasa lor concreta. Se mai...
1.1. CE ESTE DELPHI? Delphi este un produs program realizat de firma Borland pentru scrierea aplicaţiilor Windows. Cu Delphi se pot scrie programe...
Sistemele expert sunt produse ale inteligentei artificiale, ramura a stiintei calculatoarelor ce urmareste dezvoltarea de programe inteligente....
1. NOTIUNI GENERALE PRIVIND ROBOTII INDUSTRIALI 1.1. Definitii si notiuni uzuale utilizate Cuvântul `robot` a fost folosit pentru prima datã în...
Inteligenta artificiala 1 Concepte de baza Când s-a vorbit prima data de Inteligenta Artificiala (AI Artificial Intelligence) în 1956, totul...
Definitie: Un sistem expert este un program ce utilizeaza cunoasterea si procedurile de inferenta (deductie logica) pentru rezolvarea problemelor...
Invatare automata. Agenti care invata. Clasificarea metodelor şi tehnicilor Dupa modul de fundamentare empirică: -metode şi tehnici de calcul...
Obiectivul inteligentei artificiale - Construirea de artefacte (entitati artificiale) inteligente, pentru: - Obtinerea de avantaje prin...
Te-ar putea interesa și
INTRODUCERE IN TEORIA GRAFURILOR Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin...
A. PROBLEME DE ORDONANŢARE ŞI COORDONARE I. INTRODUCERE Se consideră două tipuri de probleme relative la ordinea în care trebuie efectuate o...
Motivaţia lucrării Structurile de date reprezintă modalitatea în care datele sunt dispuse în memoria calculatorului(sau păstrate pe disc)....
1. Introducere 1.1 Ce este un algoritm?Tipuri de algoritmi folositi pentru calcularea drumului optim Scurt istoric: “Originile teoriei...
Definitii generale Ce este un graf ? • Numim graf o pereche ordonată de mulţimi, notată G=(X,U), unde X este o mulţime finită şi nevidă de...
Scurtă prezentare a proiectului propus Analiza contingentei abstracte este importanta pentru furnizarea de informatii despre vulnerabilitatea...
Curs 1 1.Notatii.Definitii Multiset – S multime finita, S!=VID R=(S,r) r:S->N³0, r=functie multiplicitate r:S->{0,1} => def partilor lui S (R)...
8. Arbori 8.1. Arbori generalizaţi 8.1.1. Definiţii În definirea noţiunii de arbore se porneşte de la noţiunea de vector. Fie V o mulţime având...