13. A DFS algoritmus, DFS-erdő, az élek osztályozása, osztályzás az algoritmus futása
közben. A DFS alkalmazása az aciklikusság eldöntésére, illetve topologikus sorrend meghatározására.
10. Hálózat, hálózati folyam és s − t vágás fogalma, folyam értéke,
vágás kapacitása. Algoritmus maximális folyam és minimális vágás
keresére, Ford-Fulkerson tétel, Edmonds-Karp
tétel (biz. nélkül). Egészértékűségi lemma. A folyamprobléma
általánosításai.
11. Éldiszjunkt és pontdiszjunkt utak létezésének eldöntése utakat
lefogó élhalmazok, illetve ponthalmazok, valamint folyamok
segítségével irányított és irányítatlan gráfban. Menger pontpárok
közötti diszjunkt utakra vonatkozó tételei. Többszörös összefüggőség
és élösszefüggőség, Menger ezekre vonatkozó tételei.
Teljes párosítás létezése reguláris páros gráfban. Gráfok élszínezése, χe (G) fogalma és
viszonya ∆(G)-hez. Vizing-tétel (biz. nélkül), Kőnig tétele a páros gráfok élkromatikus
számáról.
