2.3. 2.3. Az út és a vágás dualitása. Címkézési technika

Az út és a vágás fogalmak között szoros kapcsolat van, amelyet a fontosságára való tekintettel tétel formájában mondunk ki. A tételt az út és a vágás dualitási tételének vagy a megalkotójáról MINTY-tételnek nevezzük.

MINTY tétel (Út és vágás dualitási tétele):

Legyen digráf és benne az két kitüntetett pont. Az alábbi két állítás közül egyik és csak egyik igaz:

  1. van s-ből t-be vezető út,

  2. van az s-et t-től elválasztó üres vágás.

A tételre konstruktív bizonyítást adunk, amely vagy az utat, vagy az üres vágást adja meg. A bizonyításnak ezt a konstruktív (megoldást is szolgáltató) módját a későbbi tételeinkben is használjuk, így tulajdonképpen a tételeink bizonyítása egyben a megoldási algoritmust is megadja.

Bizonyítás.

Konstruáljuk meg (állítsuk elő) az halmazt a következőképpen:

• legyen ,

• legyen akkor, ha van olyan pont, hogy .

Ez a két részből álló, látszólag bonyolult matematikai megfogalmazás tulajdonképpen azt fejezi ki, hogy az halmaz álljon az pontból és az ebből a pontból úttal elérhető pontokból. Az megkonstruálása után két egymást kizáró esetet különböztethetünk meg.

  1. Ha , akkor konstrukcióját figyelembe véve van út -ből -be.

  2. Ha , akkor jelöljük -vel az úttal el nem érhető pontok halmazát, azaz . Mivel , így az egy vágás és ez az -t a -től elválasztja. Az konstrukciója miatt az így megalkotott vágás üres.

A bizonyításban szereplő halmaz meghatározására szolgáló eljárást címkézési technikának nevezik, amelyet a következő alfejezetben ismertetünk.

Az út és vágás dualitási tétele és a címkézési technika FORD L.R. Jr. [ 4 ] és MINTY G.J. [ 11 ] munkáiban szerepel először.