Téma ismertetése
1. Előadás
Gráfelméleti alapfogalmak
- irányítalan és irányított gráfok; fák
- éllista, szomszédsági lista, szomszédsági mátrix
A programozási technikák bemutatkoznak- mohó
- backtracking
- oszd-meg-és-uralkodj
- dinamikus programozás
- branch-and-bound
3. Előadás
Mélységi bejárás (DFS) és alkalmazásai
- körmentesség vizsgálata
- topologikus sorrend
- összefüggő és erősen összefüggő komponensek
4. Előadás
BFS (szélességi bejárás) és alkalmazásai
- legrövidebb utak
- elkerülhetetlen pontok
- páros gráfok
5. Előadás
Backtracking módszer
- Descartes szorzat elemei
- Permutációk generálása
- N-királynő probléma
Téma 7
13. ELŐADÁS
Az utazóügynök probléma
- Backtracking
- Mohó
- Dinamikus programozás
- Branch-and-Bound
Téma 13
Téma 14