Tudjuk, hogy igaz a következő megállapítás:

Tegyük fel, hogy a definíció értelmezése szerinti c

  értéket 6-nak választjuk. Adja meg a legkisebb pozitív

küszöbszámot (

Tekintsük az alábbi hálózatot és az ehhez tartozó folyamot.

Legyen egy vágása a fenti hálózati folyamnak: ({s, a, b, d, e},{c, f, t}). Azaz S ={s, a, b, d, e}, T={c, f, t}.

Mennyi az (S, T) vágás kapacitása?

Tekintsük az alábbi hálózatot és az ehhez tartozó folyamot.

Legyen egy vágása a fenti hálózati folyamnak: ({s, a, d, e, f},{b, c, t}). Azaz S ={s, a, d, e, f}, T={b, c, t}.

Mennyi az (S, T) vágáshoz tartozó folyam értéke?

Tekintsük az alábbi hálózatot és az ehhez tartozó folyamot.

Legyen egy vágása a fenti hálózati folyamnak: ({s, d, e, f},{a, b, c, t}). Azaz S ={s, d, e, f}, T={a, b, c, t}.

Mennyi az (S, T) vágáshoz tartozó folyam értéke?

Tekintsük az alábbi hálózatot és az ehhez tartozó folyamot.

Legyen egy vágása a fenti hálózati folyamnak: ({s, a, d, e, f},{b, c, t}). Azaz S ={s, a, d, e, f}, T={b, c, t}.

Mennyi az (S, T) vágás kapacitása?

Tekintsük az alábbi hálózatot és az ehhez tartozó folyamot (s: forrás, t: nyelő).

Tekintsük az alábbi hálózatot és az ehhez tartozó folyamot.

Legyen egy vágása a fenti hálózati folyamnak: ({s, d, e, f},{a, b, c, t}). Azaz S ={s, d, e, f}, T={a, b, c, t}.

Mennyi az (S, T) vágás kapacitása?

Tekintsük az alábbi hálózatot és az ehhez tartozó folyamot (s: forrás, t: nyelő).

Tekintsük az alábbi gráfot:

Tegyük fel, hogy a Mélységi keresés eljárásának 5–7. sorában szereplő for ciklus a csúcsokat ábécé szerinti sorrendben vizsgálja, továbbá, hogy a szomszédsági listák is ábécé szerint rendezettek. Add meg a mélységi keresés végén előállt csúcsok eredményül kapott zárójelezését (pl. (s(z(y(xx)y)(ww)z)s)(t(vv)(uu)t))! A megadásnál ügyelj arra, hogy sehol ne üss space-t (ld. a fent megadott példa választ)!

Tekintsük az alábbi gráfot:

Határozzuk meg a tanult algoritmussal az Erősen összefüggő komponenseket. Az eredményként kapott komponens-gráf hány élt tartalmaz?