2.2. 2.2. Az út és a vágás fogalma

Az alábbiakban a digráfokon két fontos fogalmat vezetünk be, az út és a vágás fogalmát, amelyeket először általánosan fogalmazunk meg, de majd mindig két kitüntetett ponttal kapcsolatban értelmezünk. Legyen adott az digráf és két kitüntetett pontja: (s=source (forrás), t=target (cél)).

Az út ( -ből -be vezető út) fogalma:

Legyen az pontsorozat olyan, hogy minden esetén. Ekkor az pontsorozat által meghatározott élhalmazt az pontból az pontba vezető útnak nevezzük. Az út tehát nem más, mint azon élek összessége, amelyeken keresztül az egyik pontból a másikba irányított éleken eljuthatunk. Az utat matematikailag legegyszerűbben egy pontsorozattal adjuk meg, de valójában az út egymásba kapcsolódó élek halmaza. Jelölésére a

szimbólumot használjuk.

Ha az pontsorozat olyan, hogy az mellett és , akkor ezen pontsorozat által meghatározott élhalmazt a két kitüntetett pont közötti útnak vagy pontosabban s-ből t-be vezető útnak nevezzük.

A minta digráfban legyen és . Az -ból az -be vezető út (három ilyen út is van) a következőképpen adható meg:

Mint említettük, amikor az utat matematikai formában írjuk le, akkor a pontjai sorozatával () adjuk meg, de konkrét esetekben megadhatjuk természetesen más módon is az utat, mint élhalmazt, az élek felsorolásával is, például az utolsó utat így is megadhatjuk:

Szokásos az utat az alábbi szemléletes módon is jelölni, ezt fogjuk alkalmazni a példamegoldások során:

A vágás (az -et a -től elválasztó vágás) fogalma :

Legyen az ponthalmaz az és diszjunkt, nem üres ponthalmazokra felbontva, azaz , , , . Azon élek összességét, amelyek kezdőpontja -ben, végpontja -ben van vágásnak nevezzük, melynek jele . Képletben megfogalmazva az vágás:

Tehát a vágás is, mint ahogy az út is élek halmazát jelenti, az éleket azonban itt nem pontsorozattal, hanem két ponthalmaz segítségével határozzuk meg.

Ha az pontok olyanok, hogy és , akkor az vágást az pontokat elválasztó vágásnak nevezzük. Ekkor tehát a két kitüntetett pont el van választva, szeparálva van egymástól.

A minta digráfban legyen és , akkor az vágás az alábbi:

Ha a két kitüntetett pont: és , akkor ezt az vágást az pontot az ponttól elválasztó vágásnak is mondjuk. Ugyanezt a vágást lehet például az pontot az ponttól elválasztó vágásnak is nevezni. Ha előre megadjuk a két kitüntetett pontot, akkor általában többféle vágás is szóba jöhet, amely az és a pontokat elválasztja. Ha például és , akkor az -et az -től elválasztó vágások közül többek között az egyik lehet az és a ponthalmazokkal megadott vágás, ekkor az vágás élhalmazai az alábbiak:

Ez utóbbi vágást szemlélteti az alábbi ábra.

A későbbi vizsgálatainkban fontos lesz az alábbi fogalom. Egy vágást üresnek mondunk, ha az élhalmaz üres, azaz nincs olyan él, amely ponthalmaz valamelyik pontjából indulna és a ponthalmaz valamelyik pontjába érkezne.

Összefoglalva tehát az út és a vágás is egy-egy élsorozat, amelyet a matematikai leírásokban pontsorozattal ill. két ponthalmazzal szoktunk megadni.

Mind az utat mind a vágást illusztrálhatjuk a struktúratáblázatban is. Az út és a vágás éleit valamilyen módon „megjelöljük”, ezt a megjelölést az alábbiakban ismertetjük.

Út illusztrálása:

Az út éleit bekeretezéssel () szokás jelölni. Ilyenkor ugyan csak az út élei vannak feltüntetve, az élek egymásra kapcsolódása közvetlenül nem látszik. A későbbi alkalmazásokban látni fogjuk, hogy ez számunkra elegendő információ az útról. A minta digráfban az út illusztrálása bekeretezéssel:

Vágás illusztrálása:

A vágás éleit is nagyon egyszerűen szemléltethetjük, mégpedig a táblázat bizonyos sorainak és oszlopainak lefedésével. Egy-egy szaggatott vonallal lefedjük a struktúratáblázat azon oszlopait, amelyekhez tartozó pontok az ponthalmaz elemei és azon sorait, amelyhez tartozó pontok a ponthalmaz elemei. Ha a struktúratáblázatban egy élhez tartozó cella nincs lefedve, ez azt jelenti, hogy az él kezdőpontja -ben van, végpontja pedig -ben van. Tehát a fedetlen helyeken éppen az vágás élei vannak. Az olvasó könnyen ellenőrizheti, hogy a kétszer fedett helyeken a típusú élek vannak, azaz olyan élek, amelyek kezdőpontja a ponthalmazból, végpontja pedig az ponthalmazból való. Az egyszer fedett helyeken pedig az vagy a típusú élek vannak, azaz vagy -beli pontból indulnak és ott végződnek, vagy -beli pontból indulnak és ott végződnek. Nyilvánvaló, hogy az üres vágás is szemléltethető ilyen módon, ekkor a fedetlen helyeken nincs él, azaz nincs * jel.

A minta digráfban az vágás illusztrálása lefedéssel, ahol , ill. .

Az vágásbeli élhalmazok mellett a , és a élhalmazok is könnyen kiolvashatók a lefedés segítségével.