Szélességi keresés, legrövidebb utak 0-1 élhosszakkal,
editálási távolság (diff)


Két hasonló algoritmus: Dijkstra és Prim.
Helyességük bizonyítása.


Legrövidebb utak mátrixszorzással n^4 és n^3 log n időben.
Floyd-Warshall és a Gauss-elimináció.


További legrövidebb út algoritmusok:
Bellman-Ford;  Johnson algoritmusa és az átidőzítés módszere.  


Egyéb dinamikus programozás alkalmazások:
Mátrixlánc szorzás;
Optimális háromszögelés;
Maximális konvex részhalmaz.



Feszítőfák és vágások legkönnyebb illetve körök legnehezebb élei.
Prim, Kruskal algoritmusai.


Matroidok és a mohó algoritmus működésének szükséges feltétele.
Matroid = mohó algoritmus alkalmazható.
Bázis, kör, vágás, rang és a matroidmetszet fogalma.


Óvatos algoritmus és duális matroid.
Síkgráf dualitás és az Euler formula.


Bináris számláló növelése, potenciálfüggvények.


Folyamok.  A max_folyam=min_vágás tétel és a Ford-Fulkerson algoritmus.
A folyamfelbontási tétel.


A távolságcímkéző folyamalgoritmus 1: O (nm) legrövidebb javító út elég.


A távolságcímkéző folyamalgoritmus 2: O (n^2 m) futási idő.


Az előfolyam (preflow-push) algoritmus helyessége.


Az előfolyam (preflow-push) algoritmus O (n^2 m) futási ideje.


Páros gráf párosítása mint a folyam speciális esete.
König és Hall tételei.

A közelítő algoritmus fogalma.
2 és 1/2-közelítések párosítások és pont-fedés esetén.


A párosítás és pont-fedés mint egészértékű program (IP); gyenge dualitás.  
A mohó párosítás vizsgálata kerekítéssel és primál-duál módszerrel.


A halmazfedés-probléma; (log k)-közelítés primál-duál módszerrel.


A páros gráf párosításához tartozó poliéder minden csúcsa egész.
Totális unimodularitás.