Tematică științifică · Capitolul 5
Teoria grafurilor
- 1 Grafuri orientate și neorientate. Terminologie Definiția grafului, graful neorientat și graful orientat, gradele nodurilor, metodele de reprezentare (matricea de adiacență, matricea de incidență, lista muchiilor, listele de adiacență), lanțul, ciclul, drumul și circuitul, graful parțial, subgraful și graful transpus, cu programe în C++. ✓ GRATUIT
- 2 Tipuri speciale de grafuri Graful complet, graful bipartit și graful bipartit complet, graful turneu: definiții, proprietăți, numărul muchiilor și al grafurilor de fiecare tip, drumul care trece prin toate nodurile unui graf turneu, cu programe de verificare în C++.
- 3 Parcurgerea grafurilor Parcurgerea în lățime și parcurgerea în adâncime: noțiunile preliminare, descrierea algoritmilor, exemplificarea etapelor pe un graf cu 10 noduri, implementarea în C++, complexitatea și aplicațiile (lanțul de lungime minimă, componentele conexe), cu baremele subiectelor date la examen.
- 4 Matricea drumurilor. Conexitate Graful conex și componentele conexe, matricea lanțurilor, graful tare conex, matricea drumurilor și algoritmul Roy-Warshall; verificarea conexității și a tare conexității, determinarea componentelor conexe și a componentelor tare conexe în C++, cu exemple desenate și cu baremul subiectului dat la examen.
- 5 Grafuri ponderate. Drumuri de cost minim Graful ponderat, costul unui drum și matricea costurilor; algoritmul Roy-Floyd, cu reconstituirea drumului, și algoritmul lui Dijkstra, cu vectorul predecesorilor, exemplificate pas cu pas pe același graf și implementate în C++; aplicații, complexitate și baremele subiectelor date la examen.
- 6 Grafuri hamiltoniene Lanțul hamiltonian, ciclul hamiltonian și graful hamiltonian; condiții necesare, teoremele lui Dirac și Ore, graful complet; verificarea unui ciclu dat, verificarea condițiilor din teoreme și determinarea ciclurilor hamiltoniene prin backtracking în C++, cu exemplificarea etapelor și baremul subiectului dat la examen.
- 7 Grafuri euleriene Lanțul eulerian, ciclul eulerian și graful eulerian; problema podurilor din Königsberg, teorema lui Euler, grafurile cu noduri izolate și graful orientat; verificarea unui ciclu dat, verificarea proprietății și determinarea unui ciclu eulerian cu stivă în C++, cu exemplificarea etapelor și baremul subiectului dat la examen.
- 8 Arbori. Arbori parțiali de cost minim Arborele ca graf conex fără cicluri, teorema de caracterizare și proprietățile arborilor; arborele parțial și arborele parțial de cost minim; algoritmii lui Kruskal și Prim, cu exemplificarea etapelor și programe în C++ pentru verificarea unui arbore, determinarea unui arbore parțial și a arborelui parțial de cost minim; subiectele date la examen.
- 9 Arbori cu rădăcină și arbori binari Arborele cu rădăcină, terminologia și reprezentarea cu referințe ascendente și descendente; arborele binar, tipurile speciale (strict, complet, aproape complet), proprietăți, reprezentări și parcurgeri; arborele binar de căutare; ansamblul heap, cu inserarea, eliminarea cheii maxime și HeapSort; programe în C++ și subiectele date la examen.