KOMBINATORIKUS ALGORITMUSOK

(Frank András)

1. GRÁFOK BEJÁRÁSA

SZÉLESSÉGI KERESÉS

Legyen D = (V, E) irányított gráf és s egy adott pontja. Jelölje S az s-ből irányított úton elérhető pontok halmazát. Ekkor S-ből nem vezet ki él és létezik olyan s gyökerű F fenyő, amelynek ponthalmaza S. Hogyan lehet S-et és F -et algoritmikusan megtalálni?

Az alábbi cimkézési technika segít. A digráf minden v pontjához tartozzék egy R-címke (Reach = elér), amely azt mutatja, hogy az algoritmus futásának egy adott pillanatában v-t már elértük s-ből egy út mentén vagy sem. Amennyiben nem, akkor az R-címke tartalma NEM ELÉRT. Ha v-t már elértük, akkor Rcímkéjének tartalma ELÉRT valamint azon útnak a legutolsó uv éle, amelyen elértük v-t. Az egyetlen kivétel maga az s pont, amelynek R-címkéje mindig ELÉRT.

Ezen kívül minden pontban fenntartunk egy S-címkét (Scan = letapogat, átvizsgál), amely azt jelzi, hogy az adott pillanatban a v pontból vajon már az összes továbbmenési lehetőséget átvizsgáltuk-e (azaz valamennyi vu ∈ E élre az u csúcs már elért), amikoris az S-címke tartalma ÁTVIZSGÁLT, vagy pedig még van át nem vizsgált vx él. Kezdetben minden S-címke tartalma NEM ÁTVIZSGÁLT.

Az algoritmus általános lépésében kiválasztunk egy már elért, de még át nem vizsgált u pontot (ami induláskor persze csak az s pont lehet) és eldöntjük, hogy van-e olyan uv éle a digráfnak, hogy v még nem elért. Amennyiben nincs, akkor az u pontot ÁTVIZSGÁLT-nak deklaráljuk és az eljárást iteráljuk. Ha viszont találunk ilyen v pontot, akkor v-t ELÉRT-nek nyilvánítjuk, az R-címkéjébe betesszük az uv élt, és ismét az eljárást iteráljuk. Az algoritmus akkor ér véget, amikor már minden elért pont átvizsgált lesz.

Egyszerű feladat annak igazolása, hogy az algoritmus lefutása után az ELÉRT pontok S halmazából nem vezet kifelé él, továbbá, hogy az elért pontok R-címkéjébe írt élek egy s gyökerű fenyőt alkotnak, melynek ponthalmaza S. Az eljárás az S meghatározása után folytatható egy tetszőleges S-ben nem szereplő s_{2} pont gyökérnek való kijelölésével. Végül egy fenyvest kapunk, melynek gyökerei s_{1} := s, s_{2}, …, és amely az összes pontot tartalmazza. (Ezen utóbbi kiterjesztés úgy is interpretálható, hogy az algoritmus futásának az elején felveszünk egy új s_{0} pontot, és onnan minden más pontba egy új élt, majd a kibővített digráfban alkalmazzuk a keresést az s_{0} gyökérre.)

Az eljárásról annyit érdemes még tudni, hogy megfelelő adatstruktúra alkalmazásával a futási idő lineáris, azaz az élek számával arányos. További megjegyzés, hogy az eljárás irányítatlan gráfokra is alkalmazható.

Az algoritmus futása során szabadságunk van az aktuális már elért, de még át nem vizsgált pont kiválasztásában. Egy lehetséges stratégia azt a még nem átvizsgált pontot kiválasztani, amelyiket leghamarabb értük el. Ebben az esetben szélességi keresésről beszélünk (breadth first search: BFS). A BFS például alkalmas arra, hogy segítségével a pontok s-től való távolságát egyszerűen meghatározzuk. Csupán azt a csekély módosítást kell a fenti algoritmusban végrehajtani, hogy minden v pontra fenntartunk egy d(v) változót is, amely a már elért pontoknál megmondja az s-től való távolságot. Kezdetben ez az s-ben 0, mindenütt másutt ∞. Amikor az algoritmus során egy v pontot az uv él mentén u-ból elérünk, akkor a d(v) értéket d(u) + 1-re állítjuk be. Valójában ez az algoritmus speciális esete Dijkstra később ismertetésre kerülő eljárásának, amely általában nem-negatív súlyozás esetén számítja ki egy v pontnak s-től való távolságát.

Gyakorlat Igazoljuk, hogy a BFS algoritmus helyesen határozza meg az s-től való távolságot.

Gyakorlat Igazoljuk, hogy irányítatlan gráfban a távolság függvény kielégíti a háromszög egyenlőtlenséget.

Az 1998 tavaszán tartott kurzus anyaga MÉLYSÉGI KERESÉS

A címkézési eljárásban egy másik lehetséges stratégia az, amikor az algoritmus azt a még át nem vizsgált pontot választja ki, amelyiket legkésőbb értük el. Ebben az esetben az eljárást mélységi keresésnek nevezzük (depth first search: DFS). A DFS-nél minden pontnak van egy elérési időpontja, amikor a pont ELÉRT lesz (tehát amikor az algoritmus először találkozik az illető ponttal), és van egy elhagyási időpontja, amikor a pont ÁTVIZSGÁLT lett (vagyis amikor a keresés utoljára találkozik a illető ponttal). Mind a kettő meghatározza a pontok egy sorrendjét: az elérési és az elhagyási sorrendet. A két sorrend összefésülésével kapjuk a pontok kezelési sorendjét. Tehát a kezelési sorrendben minden pont kétszer fordul elő, és a két előfordulás közötti ponthalmaz, amint az könnyen belátható, két különböző pontra vagy diszjunkt vagy tartalmazkodó. Az ilyen sorozatot laminárisnak nevezzük. Következik, hogy ha s-ből minden pont elérhető, akkor a sorozat első és utolsó tagja az s gyökérpont. Egyébként egy lamináris sorozat, amelynek első és utolsó tagja s, mindig egyértelműen leír egy s gyökerű fenyőt. Ezt rekurzívan definiálva úgy kaphatjuk meg, hogy veszünk a sorozatnak egy x, y, y alakú három egymást követő eleméből álló részét [ilyen van a laminaritás miatt], a két y-t kihagyjuk, a maradékhoz megkonstruáljuk a fenyőt, és végül hozzávesszük az xy élt.

Gyakorlat Igazoljuk, hogy legalább háromtagú lamináris sorozatnak (amelyben minden elem kétszer fordul elő) van x, y, y alakú három egymást követő elemből álló része.

A DFS fenyő fontos tulajdonsága, hogy minden xy élre az y elérési időpontja megelőzi az x elhagyási időpontját. Speciálisan, összefüggő irányítatlan gráf mélységi fájához nem tartozik keresztél. (Egy s gyökerű irányítatlan fa esetén egy xy nem-fa élt akkor hívjuk keresztélnek, ha a fában az x és y-t összekötő egyértelmű út s-hez (a fában) legközelebbi pontja különbözik x-től és y-tól.)

A DFS-nek számos érdekes alkalmazása van. Segítségével lehet például lineáris időben egy kétszer élösszefüggő gráf erősen összefüggő irányítását megkapni: vegyünk egy s gyökerű mélységi fát, irányítsuk a fa éleit s-től kifelé, a nem-fa éleket pedig s felé. Mivel nincs keresztél, így minden élt irányítottunk.

Feladat Igazoljuk, hogy ha a gráf 2-élösszefüggő, akkor az így kapott irányítás erősen összefüggő.

A DFS másik alkalmazása aciklikus digráfban a pontok ún. topológikus sorrendjének meghatározására szolgál (a topológikus sorrend olyan, amelyre vonatkozólag minden él visszafelé vezet.) Ennek érdekében feltehetjük, hogy a digráfnak van olyan s pontja, ahonnan minden más pont elérhető. (Valóban, mert ha nem ez a helyzet, akkor adjunk a digráfhoz egy új s pontot, és vezessünk s-ből minden eredeti pontba élt. Így aciklikus digráfot kapunk, amely pontjainak topológikus sorrendjéből az újonnan hozzáadott s-t kihagyva megkapjuk az eredeti digráf pontjainak egy topológikus sorrendjét.)

Feladat Igazoljuk, hogy az elhagyási sorrend topológikus sorrendet ad.

Gráfelméletből ismert, hogy tetszőleges G = (V, E) irányított gráf esetén, ha két pontot ekvivalensnek tekintünk amennyiben mindkettő elérhető a másikból irányított úton, úgy ekvivalencia relációt kapunk. Érvényes, hogy az ekvivalencia osztályai erősen összefüggő részgráfokat feszítenek, amelyek mindegyikét egy-egy pontra összehúzva aciklikus digráfot kapunk. Az ekvivalencia osztályok által feszített digráfokat szokás a G digráf erősen összefüggő komponenseinek nevezni.

Gyakorlat Igazoljuk, hogy egy mélységi kereséssel kapott feszítő fenyves olyan, hogy a digráf bármely C erősen összefüggő komponensére megszorítva C-nek feszítő fenyőjét adja (amelynek gyökere a C-nek a keresés által legelőször elért pontja).

A topológikus sorrend meghatározásánál kicsit ravaszabb módon lehet egy digráf erősen összefüggő komponenseit előállítani. Ismét feltehetjük, hogy egy s pontból minden pont elérhető. Az algoritmus két külön fázisból áll. Az első fázisban mélységi kereséssel határozzuk meg az elhagyási sorrendet. A második fázisban tetszőleges keresési eljárással (ami lehet a DFS is, de ezt már nem használjuk ki a bizonyításban) határozzunk meg egy fordított fenyvest úgy, hogy a soron következő gyökérpont mindig az első fázisban kapott elhagyási sorrend még nem szerepelt legutolsó tagja legyen. (Fordított fenyő alatt olyan irányított fát értünk, amelyben a gyökértől eltekintve minden pont kifoka egy, míg a gyökéré nulla. Fordított fenyves olyan irányított erdő, amelynek komponense fordított fenyő.)

Feladat Igazoljuk, hogy a második fázisban kapott fordított fenyves komponensei éppen a digráf erősen összefüggő komponensei lesznek.

A mélységi keresésnek elméleti alkalmazásai is vannak.

Feladat Bizonyítsuk be, hogy legalább két pontú összefüggő, egyszerű irányítatlan gráfban, ha minden pont foka legalább három, akkor létezik úgynevezett periférikus kör, azaz egy olyan húrmentes C kör, amelynek pontjait elhagyva összefüggő gráfot kapunk.

(Segítség: az s gyökerű mélységi fához válasszunk egy olyan xy nem-fa élt, amelynek s-hez közelebbi x pontja s-től a lehető legtávolabb van a fában, és ezen belül y a lehető legközelebb. Ekkor az xy alapköre periférikus.)

A periférikus köröknek fontos szerepük van síkba rajzolható gráfok síkba rajzolásánál. Nevezetesen, nem nehéz belátni, hogy 3-összefüggő síkgráfban egy kör akkor és csak akkor periférikus, ha a síkbaágyazásnál tartományt határol: íly módon a tartományt tisztán kombinatorikusan lehet definiálni. Tutte bebizonyította, hogy egy 3-összefüggő síkgráfnak a következő módon lehet egy síkbarajzolását meghatározni. Keressünk egy C periférikus kört. Ennek pontjait helyezzük el a síkban úgy, hogy konvex poligont feszítsenek. Tekintsük azt az egyenlet rendszert, amely azt írja le, hogy a gráf minden nem C-ben lévő csúcsa a szomszédos csúcsok súlypontjában van. Ezen egyenletrendszer megoldása, amint azt Tutte bebizonyította, a pontoknak olyan elhelyzését szolgáltatja, amelyben különböző csúcsoknak különböző pontok felelnek meg, és a gráfban szomszédos csúcsoknak megfeleltetett síkbeli pontokat szakaszokkal összekötve a gráfnak olyan síkba rajzolást kapjuk, amelyben a korlátos tartományok konvexek.

Feladat Periférikus köröket használva igazoljuk G. Dirac azon tételét, mely szerint egy gráf akkor és csak akkor soros-párhuzamos, ha nem tartalmaz részgráfként felosztott teljes négyest. (A felosztott teljes négyes a négypontú teljes gráfból áll elő úgy, hogy az éleket [a végpontoktól eltekintve] diszjunkt utakkal helyettesítjük.)

(Definíció szerint egy soros-párhuzamos gráf egy pontból kiindulva az alábbi műveletek tetszés szerinti egymás utáni alkalmazásával áll elő: (1) egy új él hozzáadása, melynek egyik vége régi pont, a másik viszont új, (2) egy meglévő élt egy osztóponttal felosztunk, (3) egy meglévő éllel párhuzamos élt behúzunk.)

Feladat Tegyük fel, hogy G = (V, E) irányított, összefüggő Euler-gráf, azaz minden pontnak ugyanannyi a befoka, mint a kifoka. Legyen s tetszőleges pont és F s-gyökerű fordított feszítő fenyő. Az s-ből kiindulva minden u pontnál tetszés szerint haladjunk tovább egy még nem használt uv élen, csak arra ügyelve, hogy u ≠ s esetén az u-ból kilépő egyetlen F -beli élt csak akkor vegyük igénybe, ha már más lehetőségünk nincsen. Az eljárás akkor ér véget, amikor egy olyan ponthoz érünk, amelynek már minden kimenő élét használtuk. Igazoljuk, hogy ez a végső pont s és az eljárás G-nek egy Euler-bejárását szolgáltatja, azaz minden élt pontosan egyszer használ.

IRÁNYÍTÁSOK

A korábbiakban megoldott elérési feladat alkalmazásaként megvizsgálunk egy gráfirányítási problémát. Legyen G = (V, E) irányítatlan gráf (amelyben lehetnek párhuzamos élek is), amelyben i(X) jelöli az X ⊆ V halmaz által feszített élek számát, míg e(X) jelöli azon élek számát, melyeknek legalább egyik vége X-ben van. Legyen f : V → Z_{+} és g : V → Z_{+} ∪ {∞} két függvény, melyekre f ≤ g.

1.1 TÉTEL G = (V, E) éleinek akkor és csak létezik olyan irányítása, amelynek ϱ befok függvényére ϱ(v) ≥ f(v) minden v csúcsra fennáll, ha

e(X) ≥ f(X) minden X ⊆ V -re,  (1.1)

ahol f(X) := ∑_{v∈X} f(v).

G = (V, E) éleinek akkor és csak létezik olyan irányítása, amelyben ϱ(v) ≤ g(v) minden v csúcsra fennáll, ha

i(X) ≤ g(X) minden X ⊆ V -re.  (1.2)

G = (V, E) éleinek akkor és csak létezik olyan irányítása, amelyben f(v) ≤ ϱ(v) ≤ g(v) minden v csúcsra fennáll, ha mind (1.1), mind (1.2) fennáll.

Biz. (1.1) szükségessége. Tegyük fel létezik jó irányítás. Ekkor f(X) ≤ ∑(ϱ(v) : (v ∈ X)) ≤ e(X).

(1.1) elegendősége. G egy irányításában nevezzünk egy s pontot hibásnak, ha ϱ(s) < f(s). Válasszunk G-nek egy olyan irányítását, amelynek a ∑(f(v) − ϱ(v)) : v hibás) összeggel definiált hibája minimális. Ha ez a hiba 0, vagyis ha nincs hibás csúcs, akkor készen vagyunk.

Legyen most az s csúcs hibás és jelöljük X-szel a megadott irányításban azon pontok halmazát, amelyek s-ből elérhetők. Ekkor X-ből nem lép ki él, és így ∑(ϱ(v) : v ∈ X) = e(X). Most X szükségképpen tartalmaz egy olyan t pontot, amelyre ϱ(t) > f(t). Valóban, ha nem létezne ilyen pont, akkor az X minden v pontjára ϱ(v) ≤ f(v) volna, ráadásul az X-ben lévő s pontra ϱ(s) < f(s) és így azt kapnánk, hogy f(X) > ∑(ϱ(v) : v ∈ X) = e(X), ellentmondásban (1.1)-vel. Egy s-ből t-be vezető út éleinek irányítását megfordítva G-nek egy olyan irányítását kapjuk, amelynek hibája kisebb, mint a meglévő irányításé. A módszer ismételt alkalmazásával legfeljebb f(V) út megfordítása után jó irányítást kapunk.

Analóg módon igazolható a tétel második része (azzal az eltéréssel, hogy most egy t pont akkor hibás, ha a meglévő irányításban ϱ(t) > g(t) és X-szel azon pontok halmazát jelöljük, amelyekből t elérhető.) Valójában a második rész formailag is ekvivalens az elsőnek azzal az alakjával, amelyben olyan irányítást keresünk, hogy minden v pont kifoka legalább f(v) := d_{G}(v) − g(v) legyen.

Végül a harmadik rész igazolásához induljunk ki egy olyan irányításból, amelyre (∗) ϱ(v) ≤ g(v) teljesül minden v pontra. Alkalmazzuk az első rész algoritmusát és figyeljük meg, hogy ennek során egy s pontnak a befoka csak akkor nő, ha ϱ(s) < f(s) ≤ g(s), vagyis (∗) automatikusan érvényben marad. •

Feladat Igazoljuk, hogy adott m : V → Z_{+} esetén G-nek akkor és csak akkor létezik olyan irányítása, amelyben ϱ(v) = m(v) minden v csúcsra fennáll, ha i(X) ≤ m(X) minden X ⊆ V -re és m(V) = |E| (amely feltétel azzal ekvivalens, hogy e(X) ≥ m(X) minden X ⊆ V -re és m(V) = |E|.)

Feladat Az előző feladat segítségével vezessük le Hall tételét. (Útmutatás: A G = (S, T; E) páros gráf éleinek [ahol |S| = |T |] keressünk olyan irányítását, amelyben minden S-beli pont befoka 1 és minden T -beli t pont befoka d_{G}(t) − 1.)

Feladat Mutassuk ki, hogy az irányítási algoritmust az előbbi feladatra adaptálva éppen a teljes párosítás meghatározására szolgáló közismert alternáló utas módszert kapjuk.

Feladat Legyen m_{1} ≤ m_{2} ≤ … ≤ m_{n} nem-negatív egészeknek egy sorozata. Akkor és csak akkor létezik olyan turnament, amelyben az i-dik pont befoka m_{i}, ha ∑_{i=1}^{n} m_{i} = n(n − 1)/2 és ∑_{i=1}^{k} m_{i} ≥ k(k − 1)/2 (k = 1, …, n).

Feladat Adott egy M = (V, A + E) vegyes gráf, amely a G = (V, E) irányítatlan és D = (V, A) irányított gráfok összetevésével keletkezett. Akkor és csak akkor lehet úgy irányítani az E elemeit, hogy az előálló irányított gráf Euler legyen (azaz minden pont befoka megegyezzék a kifokával), ha M-ben minden pont páros sok (irányított és irányítatlan) éllel szomszédos és d_{G}(X) ≥ ϱ_{D}(X) − δ_{D}(X) teljesül minden X ⊆ V - re.

Feladat Legyen D = (V, A) irányított gráfban s és t két olyan pont melyekre ϱ_{D}(s) = 0 = δ_{D}(t) és ϱ(T) ≥ k fennáll minden t ∈ T ⊆ V − s halmazra. Igazoljuk, hogy D tartalmaz egy olyan D′ részgráfot, amelyben ϱ′(v) = δ′(v) teljesül minden v ∈ V −{s, t} pontra és δ′(s) = k = ϱ′(t). (Segítség: Legyen G az az irányítatlan gráf, amelyet D-ből kapunk az élek irányításának elhagyásával. Keressünk G-nek olyan irányítását, amelyben minden v ∈ V − {s, t} pont befoka az eredeti, s befoka k és t befoka ϱ_{D}(t) − k.) Vezessük le ebből Menger tételének irányított, élidegen változatát.

2. A LOKÁLIS SZÉLESSÉGI KERESÉS ÉS A MAX-VISSZA SORREND ALKALMAZÁSAI

LOKÁLIS SZÉLESSÉGI KERESÉS

A BFS keresés általánosítása a lokális szélességi keresés (SFS: scan-first search). Ennek bevezetéséhez nézzük a BFS algoritmusnak azt a lépését, amikor a legkorábban elért, még nem átvizsgált pont az u. A következő lépések mindegyikében ugyanaz az u lesz a legkorábbi még át nem vizsgált pont egészen addig, amíg a gráfnak már valamennyi uv élére a v pont a fenyőhöz nem tartozik (azaz elért). Így ezeket a lépéseket egybe is vonhatjuk, vagyis a BFS algoritmus (∗) veszi az u pontot, és a fenyőbe teszi a gráfnak valamennyi olyan uv élét, amelynek v feje még nem volt elért. Mármost a lokális szélességi keresésnél egy tetszőleges (tehát nem feltétlenül a legkorábban) elért, de még át nem vizsgált u pontot választunk és erre alkalmazzuk (∗)-t. Ebből a szabályból természetesen következik, hogy az átvizsgálásra választott u pont szükségképpen a már meglévő fenyőnek végpontja illetőleg a legelső választáskor a gyökere.

Legyen G = (V, E) hurok-mentes irányítatlan (!) gráf, amelyben azonban lehetnek párhuzamos élek is. (A definíció irányított gráfokra is kiterjeszthető, de az alábbi alkalmazásokban csak irányítatlan gráfok szerepelnek.) Nevezzük G pontjainak egy {v_{1}, …, v_{n}} sorrendjét folytonosnak, ha G összefüggő komponensei folytonosan helyezkednek el, és G bármely komponensében a legelső pont kivételével mindegyik más pontból vezet visszafelé él. Ez tehát egyrészt azt jelenti, hogy ha C a gráf bármelyik komponensének ponthalmaza és i < j < k indexek, akkor v_{i}, v_{k} ∈ C-ből következik, hogy v_{j} ∈ C, másrészt pedig ha v_{h} ∈ C nem a legkisebb indexű pont C-ben, akkor létezik olyan j < h index, amelyre v_{j} ∈ C és v_{j}v_{h} ∈ E.

A pontok minden sorrendjéhez hozzárendelhetünk egy F erdőt úgy, hogy minden pontból, amelyből megy visszafelé él, vesszük a leginkább visszamenő (azaz a sorrendben legkorábbi ponthoz vezető) élt. [Az így kapott részgráf valóban körmentes lesz.] Az F erdőt nevezzük a sorrendhez tartozó erdőnek.

Gyakorlat Igazoljuk, hogy folytonos sorrendhez tartozó erdő maximális.

A lokális szélességi keresésnél a pontokat egymást követően vizsgáltuk. Az ezáltal meghatározott sorrendet nevezzük a pontok átvizsgálási sorrendjének.

LEMMA Az átvizsgálási sorrend folytonos. Egyszerű gráf esetén a keresés által meghatározott erdő éppen a sorrendhez tartozó erdő.

Biz. Ha a gráf komponensei K_{1}, …, K_{t}, akkor a lokális szélességi keresés csak akkor kezd egy új komponenst bejárni, ha az aktuális komponensnek már megtalált egy feszítő fáját. Tehát a gráf komponensei a sorrendben összefüggően helyezkednek el. Ha v_{1}, …, v_{l} jelöli egy komponensen belül az átvizsgálási sorrendet, akkor a v_{1} kivételével tetszőleges v_{k} pont akkor kerül átvizsgálásra, ha v_{k} végpontja a már addig felépített F részfának. Jelölje e = v_{j}v_{k} a részfában a v_{k}-ból induló egyetlen élt. Ekkor v_{j} megelőzi a sorrendben v_{k}-t, és v_{j} a legelső olyan pont, amely szomszédos a gráfban v_{k}-val. Ha ugyanis volna egy v_{j}-t megelőző v_{i} pont, amely szomszédos a gráfban v_{k}-val, akkor a lokális szélességi keresés szabálya szerint a v_{i}v_{k} él a részfába kerül, ellentmondásban e választásával. •

LEMMA Minden {v_{1}, …, v_{n}} folytonos sorrend egy lokális szélességi keresés átvizsgálási sorrendje.

Biz. Feltehetjük, hogy a gráf összefüggő. Tetszőleges pont, így v_{1} is választható egy lokális szélességi keresés első pontjául. Legyen j a legnagyobb olyan index, amelyhez van olyan lokális szélességi keresés, amelyben az első j pont átvizsgálási sorrendje {v_{1}, …, v_{j}}. Ekkor 1 ≤ j ≤ n. Készen vagyunk, ha j = n, ezért tegyük fel, hogy j < n. Miután a sorrend folytonos, v_{j+1}-ből vezet kisebb indexű ponthoz él. Legyen v_{i} a legkisebb indexű ilyen pont. Amikor a v_{i} pont átvizsgálásra került, akkor v_{j+1} is bekerült a fába, tehát van olyan a lokális szélességi keresés, amely a v_{j} pont átvizsgálása után a v_{j+1}-t vizsgálja át, ellentétben j maximális választásával. •

Pontok X, Y részhalmazára jelölje d(X, Y) az X − Y és Y − X között vezető élek számát. Legyen d(X) := d(X, V − X). G pontjainak v_{1}, …, v_{n} sorrendjére jelölje V_{i} az első i elemből álló halmazt. Azt mondjuk, hogy a sorrend max-vissza, ha

d(v_{i}, V_{i−1}) ≥ d(v_{j}, V_{i−1})  (2.0)

fennáll minden {i, j} párra (2 ≤ i < j ≤ n). Az ún. max-vissza kereséssel meghatározhatunk egy maxvissza sorrendet. A max-vissza keresés tetszőleges pontot választ v_{1}-nek. Ha már v_{1}, …, v_{i−1}-t meghatároztuk, a maradék pontok közül egy olyant vegyünk a sorrendbe i-ediknek, amelyből a legtöbb él vezet V_{i−1}- be. Alkalmas adatstruktúrát használva egy max-vissza sorrend O(|E|) időben megtalálható. Egyszerű, de hasznos megfigyelés, hogy a max-vissza sorrend mindig folytonos.

Gyakorlat Legyen v_{1}, …, v_{n} a G gráf egy max-vissza sorrendje. Igazoljuk a következőket. (a) Ha F a sorrendhez tartozó erdő, akkor v_{1}, …, v_{n} az F éleinek kihagyásával keletkező G − E(F) gráfnak is maxvissza sorrendje. (b) Ha e tetszőleges v_{n}-ből induló él, akkor v_{1}, …, v_{n} a G − e gráfnak is max-vissza sorrendje. (c) Tetszőleges i, j-re (1 ≤ i < j ≤ n) v_{1}, …, v_{i}, v_{j} az ezen pontok által feszített részgráfnak max-vissza sorrendje.

IRÁNYÍTATLAN GRÁF ÉLÖSSZEFÜGGŐSÉGÉNEK MEGHATÁROZÁSA

Az alábbiakban megvizsgáljuk a max-vissza sorrend alkalmazását egy G irányítatlan gráf minimális vágásának meghatározására. Ennek elemszámát λ(G)-vel fogjuk jelölni. Az Ibaraki és Nagamochi által 1992-ben publikált eljárásban az a meglepő, hogy a korábbi ilyen célú módszerekkel szemben egyáltalán nem használ maximális folyamot kiszámító szubrutint.

Jelölje λ(x, y) := λ(x, y; G) az x és y-t szétválasztó minimális vágás elemszámát. (Menger tétele alapján tudjuk, hogy ez egyenlő az x és y között vezető élidegen utak maximális számával, de erre a tényre nincs szükségünk.) Természetesen a λ(x, y) érték legfeljebb akkora, mint az x illetve az y fokszáma. Könnyű példát mutatni arra, amikor szigorúan kisebb. (Mutassunk!) Létezik-e vajon olyan gráf is, amelyben minden x, y pontpárra λ(x, y) < min(d(x), d(y))? W. Mader 1972-ben belátta, hogy ilyen nem létezhet, azaz tetszőleges (legalább két-pontú) hurokmentes irányítatlan gráf tartalmaz két olyan x, y pontot, amelyekre λ(x, y) = d(x). A következő tétel tartalma az, hogy a max-vissza sorrend utolsó két pontja ilyen.

2.1 TÉTEL Ha v_{1}, …, v_{n} max-vissza sorrend, akkor λ(v_{n}, v_{n−1}) = d(v_{n}).

Biz. Legyen k := d(v_{n}). Ha k = 0, akkor a tétel nyilván igaz, hiszen λ(v_{n}, v_{n−1}) = 0 = d(v_{n}). Legyen tehát k ≥ 1 és legyen F_{1} a sorrendhez tartozó erdő. Korábban láttuk, hogy F_{1} maximális erdő és a sorrend az F_{1} elhagyása után keletkező gráfra is max-vissza sorrend. Így egymás után képezhetjük az F_{1}, F_{2}, …, F_{k} maximális erdőket, ahol tehát az F_{i} erdőt úgy kapjuk, hogy minden v_{j} pontra megvizsgáljuk, hogy vezet-e vissza (azaz kisebb indexű ponthoz) belőle legalább i él, és ha igen, akkor F_{i}-be vesszük a v_{j}-ből visszamenőek közül az i-edik legkorábbit. (Párhuzamos élek esetén előre lerögzítjük az egymással párhuzamos élek egy sorrendjét.) Láttuk korábban, hogy a max-vissza sorrend folytonos. Ebből következik, hogy az utolsó két pont F_{k}-nak ugyanahhoz a komponenséhez tartozik és ezért ugyanez igaz a többi F_{i}-re is. Így minden v_{n−1}-t és v_{n}-t elválasztó vágás mindegyik F_{i}-ből tartalmaz legalább egy élt, vagyis legalább k = d(v_{n}) elemű, amiből a tétel következik. •

Nagamochi és Ibaraki algoritmusa a következő megfigyelésen alapul. Jelölje G′ azt a gráfot, amely G-ből keletkezik az x és y pontok összehúzásával. Ekkor nyilván

λ(G) = min(λ(x, y), λ(G′)),  (2.1)

hiszen G vágásait két osztályba lehet sorolni aszerint, hogy x-t és y-t elválasztják-e vagy sem. Ha tudunk valahogyan két olyan x, y pontot találni, amelyekre d(x) = λ(x, y), akkor λ(G) = min(λ(G′), d(x)), és ebből adódóan ilyenkor elegendő az összehúzott G′ gráf élösszefüggőségét kiszámítani. A fenti tétel megmondja, hogy miként lehet ilyen pontpárt találni. Ezen megfontolások igazolják az alábbi eljárás helyességét.

AZ ALGORITMUS

Legyen G_{1} := G és ismételjük meg n − 1-szer a következő eljárást. Tegyük fel, hogy a G_{i} gráfot már megkonstruáltuk i − 1 pontpár összehúzásával (i = 1, …, n − 1). Határozzuk meg a G_{i} gráf pontjainak egy max-vissza sorrendjét, és tegyük egy listára e sorrend utolsó, x_{i}-vel jelölt pontját valamint a d_{G_{i}}(x_{i}) fokszámot. Az utolsó két pont összehúzásával készítsük el G_{i}-ből a G_{i+1} gráfot. (Az összehúzásnál esetleg keletkező hurkokat kihagyjuk.)

Az n−1 iteráció elvégzése után válasszuk ki a listáról azt az x_{j} elemet, amelyre d_{G_{j}}(x_{j}) a legkisebb. Ekkor λ(G) egyenlő d_{G_{j}}(x_{j})-vel és a G_{j}-beli x_{j} pontnak a G-ben megfelelő X_{j} ⊆ V ponthalmaz olyan, hogy d(X_{j}) = λ(G), vagyis [X_{j}, V −X_{j}] a G gráfnak minimális vágása. [X_{j} tehát V azon pontjainak részhalmaza, amelyek az egymást követő összehúzások nyomán az x_{j} pontra lettek húzva. A λ(G) = d_{G_{j}}(x_{j}) egyenlőség pedig (2.1) ismételt alkalmazásával következik: λ(G) = λ(G_{1}) = min(λ(G_{2}), d_{G_{1}}(x_{1})) = min(λ(G_{3}), d_{G_{1}}(x_{1}), d_{G_{2}}(x_{2})) = … = min(d_{G_{1}}(x_{1}), d_{G_{2}}(x_{2}), …, d_{G_{n−1}}(x_{n−1})).]

Miután egy max-vissza sorrendet O(m) lépésben meg lehet határozni, a teljes algoritmus lépésszáma O(mn).

Gyakorlat Igazoljuk, hogy a fenti algoritmusnál egyszerre összehúzhatjuk az F_{k} erdő mindegyik komponensét egy-egy ponttá (ahol k az aktuális sorrend utolsó pontjának fokszámát jelöli).

Az algoritmust ki lehet terjeszteni arra az általánosabb esetre is, amikor a gráf élhalmazán adott egy w nem-negatív, egész költség-függvény és a célunk minimális össz-költségű vágást megtalálni. Csupán a max-vissza sorrend fogalmát kell a természetes módon kiterjesztenünk. Nevezetesen legyen d_{w}(X, Y) := ∑(w(xy) : xy ∈ E, x ∈ X, y ∈ Y) és akkor hívjunk egy sorrendet max-visszának (a w-re nézve), ha d_{w}(v_{i}, V_{i−1}) ≥ d_{w}(v_{j}, V_{i−1}) fennáll minden {i, j} párra (2 ≤ i < j ≤ n). (Ebben az esetben egy max-vissza sorrend megtalálása O(m log m) lépést igényel.) Ha w racionális, akkor a közös nevezővel való felszorzással a feladatot visszavezethetjük az egészértékű w esetére. Ha viszont w irracionális is lehet, akkor a 2.1 Tétel erre vonatkozó kiterjesztése bizonyítást igényel. Az alábbiakban λ(x, y) a w függvényre vonatkozó minimális vágás értékét jelöli, amely elválasztja x-t és y-t.

2.1A TÉTEL λ(v_{n}, v_{n−1}) = d_{w}(v_{n}, V_{n−1})(= d_{w}(v_{n})).

Biz. Természetesen a baloldal nem nagyobb, mint a jobb, ezért csak a ≥ irányt kell igazolnunk. Tegyük fel indirekt, hogy a tétel nem igaz, és legyen G minimális ellenpélda. Ekkor nyilvánvalóan n ≥ 3.

Állítjuk, hogy d_{w}(v_{n}) = d_{w}(v_{n}, V_{n−2}), vagy ami ezzel ekvivalens, hogy v_{n} és v_{n−1} között nincsen él. Ha volna, akkor egy ilyent élt kihagyva a keletkező gráfra az adott sorrend továbbra is max-vissza maradna, így a tétel már alkalmazható, de akkor a tétel G-re is igaz volna.

A G − v_{n} gráfra a tétel már igaz, így λ(v_{n−1}, v_{n−2}) ≥ λ(v_{n−1}, v_{n−2}; G − v_{n}) ≥ d_{w}(v_{n−1}, V_{n−2}) ≥ d_{w}(v_{n}, V_{n−2}) = d_{w}(v_{n}), ahol az utolsó egyenlőtlenség a max-vissza sorrend definíciója miatt igaz. A tétel a G − v_{n−1} gráfra is igaz, így λ(v_{n}, v_{n−2}) ≥ λ(v_{n}, v_{n−2}; G − v_{n−1}) ≥ d_{w}(v_{n}, V_{n−2}) = d_{w}(v_{n}). Ebből λ(v_{n}, v_{n−1}) ≥ min(λ(v_{n}, v_{n−2}), (λ(v_{n−1}, v_{n−2})) ≥ d_{w}(v_{n}), ellentétben G ellenpélda voltával. •

Feladat Általánosítsuk a fenti eljárást hipergráf élöszefüggőségének meghatározására.

Feladat Legyen a G = (V, E) gráfban s kiválasztott csúcs. Hogyan kell módosítani a Nagamochi-Ibaraki algoritmust, ha olyan minimális vágást kell találnunk, amely különbözik az [s, V − X] vágástól?

RITKA TANÚK ÉL-ÖSSZEFÜGGŐSÉGRE

Egy gráf definíció szerint akkor összefüggő, ha bármely két pontja között vezet út. Hogyan tudunk valakit meggyőzni arról, hogy egy adott gráf összefüggő? Konkrétabban, milyen igazolványt, tanúsítványt (röviden: tanút) lehet egy gráf mellé letenni, amelyre rápillantva rögtön elhisszük, hogy a gráf összefüggő? Ilyen tanú természetesen, ha valamennyi pontpárra megadunk egy utat, amely a pár két tagját köti össze. Ez elvileg jó, csak kissé terebélyes. Az n(n − 1)/2 út helyett egyetlen feszítő fa éppúgy igazolja az összefüggőséget és csak n − 1 élből áll.

Az általánosabb kérdés mármost az, hogy magasabb él-összefüggőség igazolására mennyire kicsiny (ritka) tanút tudunk találni. Adott 2-élösszefüggő gráf legkisebb 2-élöf. részgráfját sajnos nem tudjuk polinom időben kiszámítani, mert ez a feladat tartalmazza a Hamilton kör problémát, így NP-teljes. (Hogyan tartalmazza?) Az alábbi 2.3 Tétel szerint azonban a k-szor élösszefüggőségnek mindig létezik legfeljebb k(n − 1) élből álló tanúja.

Legyen G = (V, E) hurokmentes irányítatlan gráf. Válasszunk ki egymás után k maximális erdőt, azaz először vegyünk egy F_{1} maximális erdőt (ami persze fa lesz, ha G összefüggő), hagyjuk el az éleit, majd a maradékból válasszunk ki egy F_{2} maximális erdőt, hagyjuk el az éleit, stb., végül válasszuk ki a maradékból a maximális F_{k} erdőt. (Mindegyik erdő ponthalmaza a V lesz.) Jelölje a gráf X és V −X részei között menő élek által alkotott vágást B := [X, V − X].

2.2 LEMMA E_{k} := F_{1} ∪ … ∪ F_{k} a B vágásból legalább min(k, |B|) elemet tartalmaz.

(Másszóval, ha E_{k} nem tartalmazza teljesen a B vágást, akkor B legalább k elemű és van k eleme, ami E_{k}-ban van. Még másképpen, a (V, E_{k}) gráfnak a k-nál kevesebb élű vágásai pontosan ugyanazok, mint az eredeti G gráf k-nál kevesebb élű vágásai.)

Biz. Ha E_{k} tartalmazza a teljes B vágást, akkor kész vagyunk. Tegyük most fel, hogy E_{k} nem tartalmazza a B vágás valamely e = xy elemét. Ekkor azt kell igazolnunk, hogy |B| ≥ k. Mindegyik i-re az x és y pontok az F_{i}-nek ugyanahhoz a komponenséhez tartoznak, mert ha ez valamelyik F_{i}-re nem teljesülne, úgy i-t a legkisebb ilyen indexnek választva az e élt F_{i}-hez lehetne venni, ellentétben F_{i} maximalitásával. De ez azt jelenti, hogy az F_{i}-ben az x és y között vezető egyértelmű út használ élt B-ből, azaz mind a k darab F_{i} tartalmaz B-ből élt, és így |B| ≥ k. •

2.3 TÉTEL Tetszőleges G = (V, E) k-szor élösszefüggő gráf tartalmaz olyan G_{k} = (V, E_{k}) k-élöf. részgráfot, amelynek legfeljebb k(n − 1) éle van.

Biz. Tekintsük a 2.2 Lemmában szereplő F_{1}, …, F_{k} erdőket. Ezek E_{k} uniója jó lesz. Nyilván |E_{k}| legfeljebb k(n − 1). Mivel G a feltevés szerint k-élöf., így minden vágása legalább k elemű, és ezért a 2.2 Lemmából a tétel adódik. •

Feladat Igazoljuk, hogy tetszőleges G irányítatlan gráf esetén az előbbi bizonyításban szereplő G_{k} = (V, E_{k}) gráf olyan, hogy minden x, y pontpárjára λ(x, y; G_{k}) ≥ min(k, λ(x, y; G)).

Feladat Mutassuk meg, hogy az előbbi tételben a k(n − 1) helyett nem írhatunk kisebb számot.

A 2.2 Lemmának még egy érdekes algoritmikus alkalmazása a következő. Tegyük fel, hogy egy G gráfot minimális számú új él hozzáadásával k-élösszefüggővé akarunk tenni. Ez a feladat a fentiek alapján ekvivalens azzal, hogy a legfeljebb k(n − 1) élű (V, E_{k}) gráfot tegyük k-élösszefüggővé. (Ugyanis a kiindulási G gráfnak és a fenti (V, E_{k}) részgráfnak a k-nál kevesebb élű vágásai a 2.2 lemma szerint ugyanazok. Márpedig a k-élöszefüggővé tevésnél csak ezek a vágások számítanak. A Válogatott fejezetek a komb.opt.-ban című előadásban tárgyaljuk Watanabe és Nakamura tételét, amely pontosan megmondja, hogy legkevesebb hány új él hozzáadásával lehet egy G gráfot k élösszefüggővé tenni.)

RITKA TANÚK PONT-ÖSSZEFÜGGŐSÉGRE

Kérdés, hogy a k-szor pont-összefüggőségnek létezik-e ritka tanúja. Egy gráfot akkor hívunk k-pont-összefüggőnek, ha bármely két pontja között vezet k belsőleg pont-diszjunkt út. Legyen (A, B, Z) a V ponthalmaz olyan három részes partíciója, ahol A, B nem-üres, Z viszont lehet üres. Jelölje az A és B között vezető élek halmazát Δ_{E}(A, B) és legyen d_{E}(A, B) := |Δ_{E}(A, B)|. Azt mondjuk, hogy a (Z, Δ_{E}(A, B)) pár vegyes vágást alkot, ahol Z a vegyes vágás pontjainak, Δ_{E}(A, B) pedig az éleinek a halmaza. A |Z| + d_{E}(A, B) számot nevezzük a vegyes vágás elemszámának. Menger tétele alapján könnyen látszik, hogy G akkor és csak akkor k-szor összefüggő, ha minden vegyes vágása legalább k elemű. Jelölje κ(x, y; G) a G gráfban a két pontot elválasztó minimális vegyes vágás elemszámát. (Menger tétele alapján ez egyenlő az x és y között vezető belsőleg diszjunkt utak maximális számával. Könnyű látni, hogy ha x és y nem szomszédos, akkor κ(x, y) az x-t és y-t összekötő utakat lefogó V − {x, y}-beli pontok minimális száma.)

A 2.2 Lemma pont-összefüggőségre vonatkozó ellenpárját szeretnénk megfogalmazni. Legyen G = (V, E) egyszerű irányítatlan gráf. Lokális szélességi kereséssel válasszunk ki egy maximális F_{1} erdőt és hagyjuk el Gből az éleit, majd a maradékból ugyanígy egy F_{2} maximális erdőt, stb. A kiválasztott erdőket F_{1}, F_{2}, …, F_{k}- val jelöltük és bevezettük az E_{k} := F_{1} ∪ … ∪ F_{k}, G_{k} = (V, E_{k}) jelölést is.

2.4 TÉTEL Legyen x és y két olyan pont, amely F_{k}-nak ugyanahhoz a komponenséhez tartozik. Ekkor κ(x, y; G_{k}) ≥ k.

Biz. k szerinti indukciót alkalmazunk. Ha k = 1, akkor az állítás triviális. Legyen k ≥ 2 és tekintsünk egy (A, B, Z) által definiált vegyes vágást, amelyre x ∈ A, y ∈ B. Az F_{i}-k konstrukciója miatt (éspedig amiatt, hogy mindegyik F_{i} maximális) mindegyik F_{i}-re az x, y pontok az F_{i}-nek ugyanahhoz a komponenséhez tartoznak. Legyen G′ := G − F_{1} és J := F_{2} ∪ … ∪ F_{k}.

Amennyiben F_{1} tartalmazza Δ_{E_{k}}(A, B) egy elemét, úgy alkalmazzuk az indukciós feltevést a G′-re valamint az F_{2}, …, F_{k} erdőkre. Ennek alapján |Z| + d_{E_{k}}(A, B) ≥ |Z| + d_{J}(A, B) + 1 ≥ (k − 1) + 1 = k és így κ(x, y; G_{k}) ≥ k.

Tegyük most fel, hogy F_{1} nem tartalmazza Δ_{E_{k}}(A, B) egyik elemét sem. Jelölje C_{1} az F_{1} azon komponensét, amely tartalmazza x-t és y-t. Az A és B nevének esetleges felcserélésével elérhetjük, hogy C_{1} gyökere ne B-ben legyen. Legyen z_{1} a Z ∩ V (C_{1})-nek az a pontja, amely F_{1} építésekor a legkorábban került átvizsgálásra. (Ilyen z_{1} azért van, mert F_{1}-ben nincs él A és B között.) Mivel F_{1} nem tartalmaz A-t és B-t összekötő élt, a lokális szélességi keresés szabálya és a z_{1} választása miatt J-ben nincs él z_{1} és B között. Ez azt jelenti, hogy Δ_{J}(A, B) = Δ_{J}(A′, B), ahol A′ := A + z_{1}. Legyen Z′ := Z − z_{1} és alkalmazzuk az indukciós feltevést a G′ gráfra, és az F_{2}, …, F_{k} erdőkre. Ennek alapján |Z| + d_{E_{k}}(A, B) = 1 + |Z′| + d_{J}(A, B) = 1 + |Z′| + d_{J}(A′, B) ≥ 1 + (k − 1) = k.

Gyakorlat Példával mutassuk meg, hogy nem érvényes a következő: ”Legyen x és y két olyan pont, amely F_{k}-nak ugyanahhoz a komponenséhez tartozik. Ekkor az F_{1}, …, F_{k} erdők által meghatározott k darab x és y közötti út belsőleg pontdiszjunkt”.

2.4A. KÖVETKEZMÉNY Amennyiben E_{k} nem tartalmazza a (Z, Δ_{E}(A, B)) vegyes vágás minden élét, úgy |Z| + d_{E_{k}}(A, B) ≥ k, azaz a (Z, Δ_{E_{k}}(A, B)) vegyes vágásnak legalább k eleme van.

Biz. Legyen egy nem tartalmazott él e = xy. Az F_{k} maximalitása folytán x és y az F_{k}-nak ugyanahhoz a komponenséhez tartozik, így a 2.4 tételből a következmény adódik. •

A 2.4A Következmény segítségével kapjuk az alábbi k-összefüggőséget igazoló ritka tanút.

2.5 TÉTEL (W. Mader) Minden G = (V, E) k-összefüggő gráf tartalmaz egy G_{k} = (V, E_{k}) k-összefüggő részgráfot, amelyre |E_{k}| ≤ (k − 1)k/2 + (n − k)k, ahol n = |V |.

Biz. Feltehető, hogy G egyszerű. Tekintsük a 2.4 tétel előtt definiált F_{1}, F_{2}, …, F_{k} maximális lokális BFS erdőket és legyen E_{k} := F_{1} ∪ … ∪ F_{k}. A 2.4A Következmény alapján G_{k} = (V, E_{k}) k-szor összefüggő. Jelölje s_{i} az F_{i} erdő legelső olyan gyökérpontját, amelyből indul ki F_{i}-nek éle. A lokális BFS szabálya szerint ha j > i, akkor F_{j} nem tartalmaz az s_{i}-vel szomszédos élt, és ezért F_{j}-nek legfeljebb n − j éle lehet, vagyis |E_{k}| ≤ (n − 1) + (n − 2) + … + (n − k) = (k − 1)k/2 + (n − k)k éle van. •

Feladat Minden G = (V, E) k-összefüggő páros gráf tartalmaz egy G′ = (V, E′) k-összefüggő részgráfot, amelyre |E′| ≤ k(n − k). Érvényes-e ugyanez háromszög-mentes k-összefüggő gráfokra? Mutassuk meg, hogy a korlát éles!

Feladat Tetszőleges G esetén a fent definiált G_{k} olyan, hogy κ(x, y; G_{k}) ≥ min(k, κ(x, y; G)) fennáll minden x, y pontpárra.

Érvényes a 2.1 Tétel ellenpárja is.

2.6 TÉTEL Minden legalább kétpontú egyszerű gráfnak van két olyan x, y pontja, amelyekre κ(x, y) = d(x), éspedig egy max-vissza sorrend utolsó két pontja, y = v_{n−1} és x = v_{n}, ilyen.

Biz. Legyen k := d(v_{n}) és tekintsük a sorrendhez tartozó F_{1}, …, F_{k} erdőket. A G_{k} = (V, E_{k}) gráfban (ahol E_{k} := F_{1} ∪ … ∪ F_{k}) a 4A Következmény szerint az utolsó két pont mindegyik erdőben egy komponenshez tartozik. •

Feladat Igazoljuk, hogy a 2.6 Tételben x és y választható szomszédosnak is. (Ezt is Mader bizonyította).

2.7 KÖVETKEZMÉNY Legyen a G gráfnak legalább két pontja. Ha G élelhagyásra nézve minimális k-élösszefüggő vagy k-pontösszefüggő, akkor létezik k fokú pontja.

Biz. Egy max-vissza sorrend utolsó pontja mindkét esetben jó lesz. Valóban, a feltevés miatt minden pont foka legalább k. Ha most indirekt v_{n} foka k-nál nagyobb lenne, akkor a v_{n}-ben végződő utolsó e él (azaz a lehető legnagyobb indexű ponthoz vezető él) nem tartozna F_{k}-hoz, márpedig korábban láttuk, hogy (V, F_{1} ∪ … ∪ F_{k}) k-összefüggő (k-élösszefüggő), ha a kiindulási G az, ami viszont ellentmondásban volna a gráf minimalitására tett feltevéssel, hiszen ezek szerint G − e is k-összefüggő (k-élösszefüggő). •

Nem ismeretes az élösszefüggőség meghatározására szolgáló Nagamochi-Ibaraki algoritmushoz hasonló olyan eljárás, amely a gráf pont-összefüggőségét határozza meg. Ugyanakkor a fenti eljárás kiterjeszthető hipergráfok összefüggőségének meghatározására. Legújabban M. Queyranne ilyen alapon adott hatékony algoritmust szimmetrikus szubmoduláris függvény minimum helyének meghatározására.

MEREVKÖRŰ GRÁFOK

Egy G = (V, E) irányítatlan gráfot akkor nevezünk merevkörűnek vagy húrosnak (chordal), ha minden legalább 4 élű körében van húr. (Egy xy élt akkor mondunk egy C kör vagy út húrjának, ha x és y nem követi egymást a C mentén.)

Feladat Igazoljuk, hogy egy intervallum rendszer metszetgráfja merevkörű. Mutassunk olyn merevkörű gráfot, amely nem áll elő ilyen alakban. (A metszetgráfban minden intervallumnak megfelel egy pont és kettőt akkor kötünk össze, ha az általuk reprezentált intervallumok metszik egymást.)

Egy gráf pontjainak valamely sorrendjét nevezzük szimpliciálisnak, ha minden pont és a sorrendben utána következő szomszédjai klikket (teljes részgráfot) alkotnak. A gráf egy pontját szimpliciálisnak nevezzük, ha a szomszédai klikket alkotnak.

Feladat Igazoljuk, hogy ha egy gráf pontjainak van szimpliciális sorrendje, akkor merevkörű.

2.8 TÉTEL (G. Dirac) G akkor és csak akkor merevkörű, ha a pontjainak létezik szimpliciális sorrendje.

A nem-triviális irány, vagyis a szimpliciális sorrend létezése következik az alábbiból.

2.9 TÉTEL (Yannakakis és Tarjan) Merevkörű gráf max-vissza sorrendje fordított szimpliciális sorrend.

Biz. Mivel merevkörű gráf feszített részgráfja is merevkörű, elég azt bebizonyítani, hogy egy v_{1}, …, v_{n} max-vissza sorrend utolsó pontja szimpliciális. Feltehetjük, hogy G egyszerű. Legyen v_{i} a v_{n} akármelyik szomszédja és jelölje α a v_{n} azon szomszédainak számát, melyek a fenti sorrendben (szigorúan) megelőzik v_{i}-t. Jelölje G_{in} a v_{1}, v_{2}, …, v_{i}, v_{n} pontok által feszített részgráfot. Tudjuk, hogy v_{1}, v_{2}, …, v_{i}, v_{n} a G_{in}-nek max-vissza sorrendje. Ezért a 2.6 Tétel alapján κ(v_{n}, v_{i}; G_{in}) = d(v_{n}, V_{i}) = α + 1, ahol V_{i} = {v_{1}, …, v_{i}}. A Menger tétel szerint létezik a G_{in} gráfban α + 1 belsőleg diszjunkt út v_{n} és v_{i} között. Válasszuk ezeket a legrövidebbnek abban az értelemben, hogy húrmentesek legyenek. Mivel G merevkörű, a v_{n}v_{i} él jelenléte miatt ezen utak mind legfeljebb 2 élűek, ami azt jelenti, hogy v_{i} szomszédos a v_{n} minden olyan v_{h} szomszédjával, amelyre h < i. Ezzel bebizonyítottuk, hogy v_{n} bármely két szomszédja egymással is szomszédos, azaz v_{n} szimpliciális. •

A fentiek alapján egy merevkörű gráf pontjainak szimpliciális sorrendjét lineáris időben meg lehet határozni. A szimpliciális sorrend pedig arra jó, hogy segítségével polinom időben ki lehet számítani egy pontsúlyozott merevkörű gráf maximális súlyú klikkjét, illetve stabil részhalmazát. (Lásd a 4. fejezet végét).

Feladat Legyen F fa és F_{1}, F_{2}, …, F_{n} az F részfáinak egy rendszere. Legyen G olyan n pontú egyszerű gráf, amelynek pontjai az F_{i} részfáknak felelnek meg, és amelyben két pont akkor szomszédos, ha a nekik megfelelő részfáknak van közös pontja. Igazoljuk, hogy az így kapott gráf merevkörű, továbbá hogy minden merevkörű gráf megkapható ilyen alakban.

3. LEGRÖVIDEBB SÉTÁK ÉS UTAK

Adott a D = (V, A) n pontú, m élű irányított gráf élein egy c : E → R költség- (vagy másnéven súly-) függvény. Sétán egy olyan v_{0}, e_{1}, v_{1}, e_{2}, …, e_{k}, v_{k} sorozatot értünk, amelyben felváltva következnek pontok és élek, és mindegyik e_{i} él a v_{i−1} pontból vezet a v_{i} pontba. A séta zárt, ha v_{0} = v_{k}. A szereplő élek száma a séta hossza. Azt mondjuk, hogy v_{0} a séta kezdőpontja, v_{k} a séta végpontja. Amenyiben nincs ismétlődés, útról beszélünk. Rövidség kedvéért egy s-ből v-be vezető utat sv-útnak fogunk hívni.

Fő célunk minimális össz-költségű, másnéven legolcsóbb sv-utat találni. Ha a költség negatív is lehet, akkor a feladat már az azonosan −1 súlyozás esetén is NP-teljes, ugyanis ekkor a legrövidebb út feladat magában foglalja a Hamilton út problémának az előírt végpontú változatát, ami a tetszőleges végpontú Hamilton út problémához hasonlóan NP-teljes.

A legolcsóbb út problémája viszonylag egyszerűen megoldható, ha a költségek nemnegatívok, de létezik egy még mindig jól kezelhető közbenső eset is, amikor negatív élek ugyan előfordulhatnak, de nincsen olyan irányított kör, amelynek össz-költsége negatív (röviden: negatív kör). Az ilyen súlyozást konzervatívnak nevezzük. Egy nemnegatív költség-függvény például nyilvánvalóan konzervatív, éppúgy mint egy aciklikus digráf tetszőleges költség-függvénye.

Hogyan lehet hatékonyan eldönteni, hogy egy adott súlyozás konzervatív-e? És egyáltalán, a negatív kör létezésének problémája co-NP-ben van-e, azaz létezik-e egyszerű mód valakinek a meggyőzésére arról, hogy egy adott konzervatív súlyozás valóban az? (Az, hogy a probléma NP-ben van, világos: egy konkrét körről rögtön ellenőrizhető, hogy a súlya negatív-e vagy sem.) Az alábbi tétel ezen második kérdésre ad igenlő választ, de segítségünkre lesz az algoritmusnál is.

3.1 TÉTEL Egy c súlyozás akkor és csak akkor konzervatív, ha létezik olyan π : V → R megengedett potenciálnak nevezett függvény a pontokon, amelyre

π(v) − π(u) ≤ c(uv) fennáll minden uv élre.  (3.1)

Továbbá, ha c egészértékű, akkor π is választható annak.

Biz. Ha létezik megengedett potenciál, akkor bármely C irányított körre fennáll, hogy c(C) = ∑_{i=1}^{k} c(v_{i}v_{i+1}) ≥ ∑(π(v_{i+1}) − π(v_{i})) = 0, ami azt jelenti, hogy c konzervatív. (Itt v_{1}, …, v_{k} a kör pontjait jelöli, és a v_{k+1} = v_{1} jelölési konvencióval éltünk.)

Megfordítva, tegyük fel, hogy c konzervatív. Be akarjuk látni, hogy létezik megengedett potenciál. Feltehetjük, hogy a digráfnak van olyan s pontja, ahonnan minden pont elérhető irányított úton, mert ha nem ez a helyzet, akkor vegyünk a gráfhoz egy új s pontot, vezessünk s-ből minden más pontba egy új élt, melynek költségét definiáljuk 0-nak. Ez a növelés nem hoz létre új irányított kört, így a súlyozás továbbra is konzervatív, és a megnövelt digráf egy megengedett potenciálját az eredeti ponthalmazra megszorítva megengedett potenciált kapunk.

Jelöljön most W_{n}(u) az s-ből u-ba vezető legfeljebb n élű (n := |V |) séták közül egy minimális költségűt és w_{n}(u) ennek a költségét. Mivel nincs negatív kör, feltehető, hogy a W_{n}(u) séta út, azaz nem tartalmaz kört, és így legfeljebb n − 1 élből áll. De ekkor bármely uv élre W_{n}(u) + uv egy legfeljebb n élű séta s-ből v-be, így azt kapjuk, hogy w_{n}(v) ≤ w_{n}(u) + c(uv), azaz w_{n} megengedett potenciál, amely ráadásul egészértékű, amennyiben a c költség-függvény egészértékű volt. •

Egy uv élt a továbbiakban pontosnak fogunk hívni (π-re nézve), ha (3.1)-et egyenlőséggel teljesíti. Tetszőleges π potenciál által definiált t(uv) := π(v) − π(u) költségfüggvényt potenciál-különbségnek vagy tenziónak nevezünk.

Bizonyítás Farkas Lemmával. (Ezt inkább csak a tétel könnyebb ”elhelyezése” miatt említjük, hiszen a fenti bizonyítás egyszerű, sőt az alábbiakban az is kiderül, hogy könnyen algoritmikussá tehető.) Tekintsük a digráf A incidencia mátrixát. Amennyiben az

Ax = 0, x ≥ 0, cx ≤ −1  (3.2)

rendszernek van megoldása, úgy van racionális és ezért egész megoldása is. Ha z ilyen egész megoldás, akkor z előáll irányított körök nemnegatív egész kombinációjaként. Így azután az előállításban szereplő egyik kör költsége szükségképpen negatív. Tegyük most fel, hogy (3.1)-nek nincs megoldása. A Farkas lemma szerint létezik olyan y : V → R (amely az A sorainak megfelelő duális változókat tartalmazza) és egy α ≥ 0 szám (a cx ≤ −1 feltételnek megfelelő duális változó), amelyekre yA + αc ≥ 0 és α(−1) < 0. Vagyis α > 0. Ekkor a π := −y/α vektorra fennáll, hogy c ≥ πA, ami pontosan (3.1). •

(Ez a bizonyítás nem adja ki, a tétel második részét!)

Feladat Adjunk a 3.1 Tételre még egy bizonyítást, amely pontszám szerinti indukciót használ az alábbi vázlat alapján. Válasszunk ki egy tetszőleges z pontot, minden uz és zv élpárra vegyünk egy új élt u-ból z-be, amelynek költsége legyen c(uz)+c(zu), majd töröljük a z pontot. A keletkező kisebb pontszámú gráfra alkalmazzunk indukciót.

Feladat Igazoljuk, hogy egy éleken értelmezett költségfüggvény akkor és csak akkor tenzió, ha minden kör összköltsége 0.

Megjegyzés Irányítatlan gráfban is vizsgálható, hogy egy megadott súlyozás konzervatív-e vagy sem. Meglepő módon ez a kérdés nagyságrendekkel nehezebb, mint az irányított eset. A szokásos trükk, hogy minden élt két ellentétesen irányított éllel helyettesítünk nem segít, mert ez a művelet egy negatív irányítatlan él helyébe rögtön behoz egy kétélű negatív kört. A feladat a súlyozott párosítás probléma segítségével oldható meg, valójában azzal ekvivalens.

Figyeljük meg, hogy a fenti bizonyításban c konzervativitását csak annyiban használtuk, hogy a szóbanforgó séták nem tartalmaznak negatív kört. Ezért érvényes az alábbi:

KÖVETKEZMÉNY Ha mindegyik v ∈ V -re létezik olyan s-ből v-be vezető legfeljebb n élű séta, amely az ilyenek közül a legolcsóbb és amely nem tartalmaz negatív kört, akkor a digráfban egyáltalán nem létezik negatív kör, azaz a költség-függvény konzervatív.

Konzervatív c esetén a 3.1 Tétel bizonyításában definiált w_{n} potenciált (s-re vonatkozó) kanonikus potenciálnak nevezzük. (Ilyenkor tehát w_{n}(u) az s-ből u-ba vezető utak költségének minimuma). Az alábbiakban mindenütt feltesszük, hogy s-ből a digráf minden pontja elérhető.

3.2 TÉTEL Konzervatív c súlyozás esetén az s-ből t-be vezető utak súlyának minimuma egyenlő π(t)−π(s) maximumával, ahol a maximum az összes megengedett potenciálon veendő.

Biz. Legyen π megengedett potenciál és P tetszőleges út s-ből t-be, melynek pontjai v_{1} = s, v_{2}, …, v_{k} = t. Ekkor c(P) = ∑ c(v_{i+1}v_{i}) ≥ ∑(π(v_{i+1}) − π(v_{i})) = π(t) − π(s), vagyis a tételben a min ≥ max irány következik.

A fordított irányú egyenlőtlenség igazolásához kell találnunk egy P st-utat és egy π megengedett potenciált, amelyekre

c(P) = π(t) − π(s).  (∗)

E célra viszont egy tetszőleges P legolcsóbb st-út és a w_{n} kanonikus potenciál megfelel, hiszen w_{n} definíciója miatt (∗) fennáll, és már láttuk, hogy a kanonikus potenciál megengedett. •

Az alábbi következmény mutatja, hogy miért tekintettük w_{n}-et kanonikusnak, kitüntetettnek a megengedett potenciálok közül.

1. KÖVETKEZMÉNY Tetszőleges π megengedett potenciálra, amelyre π(s) = 0, fennáll w_{n} ≥ π. •

2. KÖVETKEZMÉNY Ha P olyan st-út, amely valamely megengedett π potenciálra nézve pontos élekből áll, akkor P egy legolcsóbb st-út. •

3. KÖVETKEZMÉNY Konzervatív súlyozás esetén létezik olyan F s-gyökerű feszítő fenyő, hogy valamennyi v pontra az F által meghatározott egyértelmű sv út a digráfban egy legolcsóbb sv út. •

A következményben leírt fenyőt nevezzük a legolcsóbb utak fenyőjének. (Persze ez nem feltétlenül egyértelmű.) Hogyan lehet algoritmikusan eldönteni, hogy egy megadott súlyozás konzervatív-e, és ha az, meghatározni a legolcsóbb utak fenyőjét?

A fenti meggondolások elvezetnek egy ilyen algoritmushoz, feltéve, hogy képesek vagyunk a legolcsóbb legfeljebb n élű séták kiszámítására. Ezt pedig úgy fogjuk megtenni, hogy minden k-ra (k = 1, 2, …, n) és minden v ∈ V -re rekurzív módon kiszámítjuk az s-ből v-be vezető legfeljebb k-élű séták közül a legkisebb költségűt. Megjegyezzük, hogy ehhez az algoritmushoz nem kell feltételeznünk, hogy a súlyozás konzervatív.

Jelölje w_{k}(v) ezt a minimális költséget. Azzal a technikai feltevéssel élünk, hogy s-ből minden pontba vezet él, hogy w_{k}(v) jól definiált legyen. Ha valamely pontba nem vezetne él s-ből, akkor adjunk egy ilyen élt a gráfhoz végtelen költséggel.

Az algoritmus kulcsa a következő triviális észrevétel: egy v-be vezető legfeljebb k + 1 élből álló séta vagy pontosan k + 1 élből áll vagypedig legfeljebb k élből. Ebből adódik, hogy ha már kiszámoltuk valamennyi pontra az s-ből az odavezető legfeljebb k élű séták közül a legolcsóbbat, akkor a legfeljebb k + 1 elű séták közül is meg tudjuk határozni a legolcsóbbat az alábbi rekurzió szerint:

3.3 LEMMA

w_{k+1}(v) = min(w_{k}(v), min(w_{k}(u) + c(uv) : uv ∈ E))  (3.3)

minden v ∈ V -re. •

Ennek alapján a w_{k}(v) értékeket k = 1-től kezdve, a k egyenkénti növelésével sorra ki tudjuk számolni. Ezzel párhuzamosan minden k-ra meg tudjuk határozni a szóbanforgó minimális sétákat is. Az algoritmus O(|V ||A|) lépésszámú. Konzervatív súlyozás esetén még egyszerűbb a dolog, ha menetközben nem törődünk a séták konstruálásával, csak a w_{n}(v) értékeket számoljuk ki. Ezek ismeretében a w_{n}-re nézve pontos élekből felépítünk egy feszítő fenyőt. Ez legolcsóbb utak fenyője lesz.

Feladat Tegyük fel, hogy c konzervatív súlyozás és valaki megadott egy π megengedett potenciált. Miként lehet a π segítségével a c-re vonatkozó legolcsóbb út problémáját egy nemnegatív költségfüggvényre vonatkozó út problémára visszavezetni?

Feladat Adott az éleken egy tetszőleges költség-függvény. Határozzunk meg egy olyan s-ből t-be vezető utat, amelyen a legnagyobb súly a lehető legkisebb.

Feladat Tegyük fel, hogy az éleken két (konzervatív) költségfüggvényünk adott: c_{1} és c_{2}. Készítsünk algoritmust olyan st út megkeresésére, amely a c_{1}-re nézve minimális költségű és ezen belül c_{2}-re nézve minimális költségű.

Feladat Igazoljuk, hogy ha egy s-ből t-be vezető P út minden éle benne van egy legolcsóbb útban, akkor P maga egy legolcsóbb út.

MINIMÁLIS ÁTLAGÚ KÖRÖK

Amennyiben a c súlyozás nem konzervatív, a fenti eljárás megtalál egy negatív kört. Több alkalmazásban is felvetődik a kérdés, hogy mi az a legkisebb ε szám, amellyel minden él költségét egységesen megnövelve, a súlyozás konzervatívvá válik. Az ε nyilván a minimális körátlag negatívja. (A körátlag a kör költsége osztva az éleinek számával.) Jelöljük a minimális körátlagot μ-vel. Egy 0 költségű kört nevezzünk röviden 0-körnek.

A fenti eljárás alábbi módosításával a minimális körátlag kiszámítható. Jelölje p_{k}(v)(k = 0, 1, …, n) a pontosan (!) k élű v-be vezető séták minimális költségét. (Ha nincs pontosan k élű séta, akkor p_{k}(v) := ∞.) Ez az alábbi rekurzióval számolható ki: p_{k+1}(v) = min(p_{k}(u) + c(uv) : uv ∈ E).

3.4 LEMMA Ha c konzervatív, akkor minden v csúcsra max_{k}(p_{n}(v) − p_{k}(v) : 0 ≤ k ≤ n − 1) ≥ 0.

Biz. Valóban, a maximum ott vétetik fel, ahol p_{k}(v) a legkisebb, ami c konzervativitása miatt, éppen w_{n}(v), ez pedig definíció szerint legfeljebb p_{n}(v). •

3.5 LEMMA Ha c konzervatív és létezik C 0-kör, akkor van olyan v csúcs, amelyre

max_{k}(p_{n}(v) − p_{k}(v) : 0 ≤ k ≤ n − 1) = 0.

Biz. A 3.4 Lemma szerint max ≥ 0, így csak azt kell kimutatnunk, hogy valamely v pontba létezik s-ből egy n élű P_{n} séta, amelynek költsége a v-be vezető utak minimális költségével egyenlő.

Legyen P egy s-ből C-hez vezető minimális költségű út. A c̄(uv) := c(uv)−(w_{n}(v)−w_{n}(u)) eltolt költségfüggvény nemnegatív és egy tetszőleges s-ből induló séta akkor és csak akkor minimális, ha minden uv élére c̄(uv) = 0 (azaz uv pontos.) Nyilván egy 0-kör minden élének az eltolt költsége 0 lesz, így a P utat a C körön addig folytatva, amíg egy n élből álló sétát kapunk, a keletkező P_{n} séta v végpontja teljesíti a lemma kívánságát. (Elképzelhető, hogy a körön a P_{n} többször is körbehalad.) •

3.6 TÉTEL (R. Karp)

μ = min_{v∈V} max_{k=0}^{n−1}(p_{n}(v) − p_{k}(v))/(n − k).  (3.4)

Biz. Amennyiben μ = 0, úgy (3.4) épp a 3.5 Lemmával ekvivalens. Nézzük a μ ≠ 0 esetet. Tetszőleges ε számra, ha minden él költségét egységesen ε-nal megnöveljük, akkor (3.4) baloldala ε-nal nő. Mivel ekkor p_{k}(v) értéke εk-val nő, a jobboldali hányados ε-nal nő. Vagyis, minden él költségét ugyanazzal a számmal eltolva, (3.4) mindkét oldala ugyanúgy változik, így a tétel következik a μ = 0 esetből. •

A 3.6 Tétel segítségével a minimális körátlag O(mn) lépésben kiszámítható. Egy minimális átlagú kör a következőképp határozható meg. A fenti eltolási meggondolás miatt feltehetjük, hogy μ = 0, amikoris a célunk egy 0-kör megkeresése.

Legyen v az a pont, amelyre (3.4) a minimumát felveszi. Ekkor tehát p_{n}(v) a v-be vezető pontosan n élű P_{n} séta költsége ugyanakkora, mint a v-be vezető utak minimális költsége, ezért a P_{n} által tartalmazott (bármely) kör 0-kör. • •

(Az utolsó bekezdés helyett úgy is eljárhatunk, hogy kiszámítunk egy megengedett potenciált, a különbségével eltoljuk a költségeket, és megkeresünk egy csupa nulla eltolt költségű élből álló kört.)

Feladat Példán mutassuk meg, hogy a következő kézenfekvő algoritmus minimális átlagkör kiszámítására nem biztosan polinomiális. Az algoritmus az alábbi lépések iterálásából áll: keressünk egy tetszőleges negatív kört, súlyának átlágának −1-szeresével növeljük meg az összes él súlyát. Az algoritmus akkor ér véget, amikor már nincs negatív kör. A legutoljára talált negatív kör lesz a minimális átlagú. (Segítség: az irányított gráf egy irányított körből keletkezzék úgy, hogy annak éleit párhuzamosan megduplázzuk.)

A fenti eljárás kicsit talán ad hocnak tűnhet. Egy egyszerű észrevétel segítségével azonban magunk is könnyen rájöhetünk egy algoritmusra. Az észrevétel pedig az, hogy körök helyett zárt sétákat tekintsünk. Mivel minden kör speciális zárt séta, a zárt séták súlyátlagának minimuma legfeljebb a minimális körátlag. Másrészt viszont egy zárt séta incidencia vektora (ami azt mutatja, hogy a séta az egyes éleket a séta hányszor használta) előáll irányított körök nemnegatív egészegyütthatós lineáris kombinációjaként. Ezért a zárt séták minimális súlyátlaga valójában egyenlő a minimális körátlaggal. Ugyanez érvényes a legfeljebb n élből álló zárt sétákra is, hiszen már ezek is magukban foglalják az összes irányított kört. Az algoritmus mármost minden i = n, n − 1, …, 1 értékre iterálja a következőt. Az i élű zárt séták közül válasszuk ki a minimális súlyút, és ha ez negatív, akkor a súlyátlag −1-szeresével növeljük meg minden él súlyát. Az utolsónak talált negatív zárt séta bármely köre a keresett minimális átlagú kört adja.

Feladat Igazoljuk az algoritmus korrektségét. Hogyan lehet adott i-re minimális súlyú i élű zárt sétát meghatározni polinom időben?

KONZERVATÍV KÖLTSÉGEK

Két fontos speciális esetben a legolcsóbb utak fenyője direkt módon, élek egyenkénti hozzávételével felépíthető. Tegyük fel először, hogy a c súlyozás nemnegatív.

3.7 LEMMA Legyen T egy legolcsóbb utak (nem feltétlenül feszítő) s-fenyője és tegyük fel, hogy az m_{T} := min(w_{n}(u) + c(uv) : uv kilép T -ből) minimum valamely a = u_{a}v_{a} élen vétetik fel. Ekkor T′ := T + a is legolcsóbb utak fenyője.

Biz. Nyilván csak az s-ből v_{a}-ba vezető T′ beli P′ útról kell belátnunk, hogy D-ben legolcsóbb. Legyen P tetszőleges sv út D-ben, és jelölje ennek első V (T)-ből kilépő élét e = u_{e}v_{e}. P -nek az s-től u_{e}-ig tartó P′′ részútjára érvényes, hogy c(P′′) ≤ c(P), hiszen c nemnegatív. Az a minimális választása miatt, c(P′) ≤ c(P′′) és a lemma következik. •

A 3.7 lemmán alapuló Dijkstra módszer n − 1 fázisból áll. s-ből kiindulva, élek egyenkénti hozzávételével felépítünk legolcsóbb utaknak egy T s-fenyőjét. Ennek érdekében fenntartunk egy k_{T} címkét, amely azt mondja meg, hogy az aktuális T -hez tartozó m_{T} érték mely v ∈ V − V (T) pontban vétetik fel. Minden fenyőn kívüli v ∈ V −V (T) pontra fenntartunk egy l(v) := min(w_{n}(u)+c(uv) : uv kilép T -ből) címkét. Ezen kívül fenntartunk még egy a(v) címkét is, amely azt mondja meg, hogy az l(v)-t meghatározó minimum mely uv élen vétetik fel.

l(v) szemléletesen azt jelenti, hogy mekkora az s-ből v-be vezető, csak V (T) pontjait használó utak költségének minimuma. Evvel a jelöléssel tehát k_{T} az l(v) minimum helye.

Ezen címkék segítségével meg tudjuk mondani, hogy melyik a élt kell a soron következő lépésben T -hez venni. Nevezetesen, vesszük a k_{T} ban lévő a_{v} pontot és az a(a_{v})-ben lévő a = a_{u}a_{v} élt vesszük az aktuális T fenyőhöz.

Az alábbi egyszerű módosításokkal kapjuk meg a keletkező T′ fenyőhöz tartozó címkéket.

Az l(v) értékeket a következő szabály szerint módosítjuk. l(v) := min(l(v), l(v_{a}) + c(v_{a}v)). Amennyiben a minimum a második tagon éretik el, az a(v) címke tartalmát v_{a}v-re cseréljük. Ebben az esetben még azt is megnézzük, hogy a csökkentett l(v) nem kisebb-e m_{T} -nél, és ha igen, akkor k_{T} tartalmát az aktuális v pontra cseréljük, m_{T} -t pedig l(v)-re.

Így az összes módosítás kiszámítása O(n) lépést igényel, és a teljes algoritmus bonyolultsága O(n^{2}). •

ACIKLIKUS DIGRÁFOK, A KRITIKUS ÚT MÓDSZERE

Még egyszerűbb a helyzet, ha a D digráf aciklikus és a c súlyozás tetszőleges. Aciklikus digráfnak mindig van olyan pontja, amelyből nem vezet ki él és ezért a pontokat sorba lehet úgy rendezni, hogy minden él korábbi pontból későbbibe vezessen (topologikus sorrend megfordítva). Ráadásul egy ilyen sorrendet, amint már említettük, mélységi kereséssel lineáris időben meg tudunk találni.

A megadott sorrendben tekintjük a pontokat: a fenti lemma nyilván most is érvényes. Valójában most még kicsit egyszerűbb a helyzet, mint a Dijkstra algoritmusnál, mivel ott az aktuális fenyőhöz hozzáveendő új pontot menet közben határozzuk meg, annak megfelelően, hogy az l(v) hol a legkisebb, míg az aciklikus esetben a pontok sorrendje már eleve meghatározott. Ezen egyszerűsítésnek köszönhetően az algoritmus bonyolultsága O(m). •

Alkalmazásokban gyakori, hogy aciklikus digráfban maximális súlyú utat kell keresni. Az is előfordul, hogy nem annyira az optimális útra vagyunk kiváncsiak, mint inkább az optimális potenciálra. Tekintsük páldául a következő feladatot. Egy projekt elvégzése különféle részfeladatokból áll, melyeknek előre adott az végrehajtási ideje. Tudjuk továbbá, hogy bizonyos részfeladatoknak meg kell előzni másokat (házépítésnél az alapozás megelőzi a fürdőszoba csempézést), azaz a részfeladatok halmazán adott egy részbenrendezés. Kérdés, hogy mi az a legrövidebb idő, amely alatt a teljes project elvégezhető, továbba adjuk meg az egyes részfeladatok kezdési időpontját úgy, hogy minden feladat kezdésére az őt a részbenrendezésben megelőzők már elkészüljenek.

A megoldáshoz készítsünk el egy G irányított gráfot a következőképpen. Reprezentáljunk mindegyik z részfeladatot egy u_{z}v_{z} irányított éllel, amelynek súlya legyen a z végrehajtási ideje. Amennyiben a z feladat megelőzi az y feladatot, úgy vegyünk be G-be egy v_{z}u_{y} élt 0 súllyal. Végül adjunk a digráfhoz egy s forráspontot, amelyből minden u_{x} pontba vezessünk 0 súlyú élt, és adjunk egy t pontot, amelybe minden v_{x} pontból vezessünk 0 súlyú élt. Feladatunk olyan π időpontok kijelölésével ekvivalens, amely π(s) = 0, π(t) minimális és minden élre az időpontkülönbség legalább akkora, mint az él súlya. Ha most mindent negálunk, akkor, aciklikus irányított gráfról lévén szó konzervatív súlyozást kapunk. Így a 3.2 tétel alkalmazásával rögtön kapjuk, hogy a projekt végrehajtásának minimális ideje egyenlő a legsúlyosabb út súlyával. Egy ilyen utat szoktak néha kritikus útnak nevezni, és az előzőekben leírt minimális út problémának az itteni feladatra adaptált változatát kritikus út módszernek (angolul PERT: project evaluation and review technique.).

Tudunk tehát részbenrendezett halmazban maximális súlyú láncot keresni. Ezt alkalmazhatjuk a következő feladatokban.

Gyakorlat Adott egy út bizonyos részútjainak F rendszere. Válasszunk ki F-nek diszjunkt tagjait úgy, hogy az összhosszúk maximális legyen.

Feladat Adott két betűkből álló sorozat. Válasszunk ki egy maximális sok tagból álló közös részsorozatot. A feladat még akkor is megoldható, ha az egyes betűknek különböző súlya van és a kiválasztott közös részsorozatban lévő betűk súlyösszegét akarjuk maximalizálni.

4A. MINIMÁLIS KÖLTSÉGŰ FÁK

A kombinatorikus optimalizálás legkorábbi feladata egy G = (V, E) összefüggő irányítatlan gráf minimális költségű feszítő fájának megkeresését célozza. Ez a mohó algoritmussal történik és valójában a matroidokra vonatkozó mohó algoritmus speciális esetének tekinthető. A fákra vonatkozó mohó algoritmusnak számos változata ismert: az alábbiakban ezek egységes leírását adjuk meg. Jelölje c : E → R a költségfüggvényt. A következő lemma a fák egy fontos kicserélési tulajdonságát írja le. (A megfelelő állítás matroidok bázisaira is érvényes.)

4A.1 LEMMA Jelölje T_{1} és T_{2} két V -t feszítő fa élhalmazát. Ekkor bármely e ∈ T_{1} élre van olyan f ∈ T_{2} él, amelyre mind T_{1} − e + f, mind T_{2} − f + e fa.

Biz. Ha e ∈ T_{2}, akkor f := e jó lesz. Tegyük fel, hogy e = st ∉ T_{2}. T_{1} − e-nek két komponense van, C_{1} és C_{2}. T_{2}-ben van egy egyértelmű P út, amely összeköti az s és t pontokat. Legyen f a P útnak egy olyan éle, amely C_{1} és C_{2} között vezet. Ezen f él kielégíti a lemma kívánalmait. •

Legyen T a G = (V, E) egy feszítő fája. Az e ∈ F élhez tartozó alapvágáson a G azon vágását értjük, amelyet a T − e két komponense határoz meg. Egy f = uv ∈ E − T élhez tartozó alapkörön azt a kört értjük, amely az f élből és az u és v pontokat a T fában összekötő egyértelmű útnak az éleiből áll.

A 4A.1 Lemmából rögtön következik:

4A.2 TÉTEL A G gráf valamely T feszítő fájára az alábbiak ekvivalensek:

(a) T minimális költségű,

(b) c(e) ≤ c(f) fennáll minden e ∈ T élre, ahol f az e alapvágásának egy eleme,

(c) c(e) ≥ c(f) fennáll minden e ∉ T élre, ahol e az f alapkörének egy eleme. •

MOHÓ ALGORITMUS [Boruvka, 1926], [Kruskal, 1956] Az eljárás egy feszítő erdőt épít élek egyenkénti hozzávételével. Az V ponthalmazú élt nem tartalmazó erdővel indul, és akkor ér véget, amikor az aktuális feszítő erdő már fa. Az általános lépés abból áll, hogy az aktuális erdőhöz adjuk a legolcsóbb olyan élt, amely két komponensét köti össze.

Ismeretes a mohó algoritmusnak másik változata is.

DIJKSTRA-PRIM ALGORITMUSA [Dijkstra 1959], [Prim 1957] Egy tetszőleges x_{0} pontból indulva élek egyenkénti hozzávételével fát építünk, egészen addig, amíg feszítő fát nem kapunk. Az általános lépésben a legolcsóbb olyan éllel növelünk, amelynek pontosan az egyik végpontja tartozik a már megkonstruált fához.

A következő algoritmus óvatosnak nevezhető; ahelyett, hogy olcsó élekből próbálna fát vagy erdőt építeni, megszabadul a drága élektől.

FORDÍTOTT MOHÓ ALGORITMUS Az eljárás során éleket hagyunk ki a gráfból arra ügyelve, hogy a visszamaradó részgráf összefüggő legyen. Az általános lépésben kiválasztjuk a maximális költségű élt, amely nem elvágó él, és ezt elhagyjuk a gráfból.

Ezen algoritmusok egy közös általános keretbe foglalhatók.

Gyakorlat Mutassuk meg, hogy az előbbi algoritmusok mindegyike az alábbi speciális esetének tekinthető.

ÁLTALÁNOS ALGORITMUS Az eljárás az alábbi két művelet tetszőleges sorrendben történő egymás utáni alkalmazásából áll. Az első művelet egy F feszítő erdőt épít élek egyenkénti hozzávételével. Kezdetben F := ∅.

1. LÉPÉS Ha F már feszítő fa, az algoritmus befejeződik. Ha F még nem feszíti V -t, akkor válasszunk G-nek egy tetszőleges olyan B vágását, amelyben nincs F -nek éle és legyen e a B vágás legolcsóbb eleme. Adjuk e-t F -hez.

2. LÉPÉS Válasszunk ki egy tetszőleges C kört (ha már nincs kör, akkor a 2. lépés nem alkalmazható.) Legyen e ∈ C a legdrágább éle C − F -nek. Töröljük e-t G-ből.

4A.3 TÉTEL Az algoritmus által talált végső feszítő F fa minimális költségű.

Biz. Az algoritmus futásának tetszőleges közbenső állapota egy (F, D) párral jellemezhető, ahol F az eddig megkonstruált erdőt, D pedig az eddig eltörölt élek halmazát jelöli. Azt igazoljuk indukcióval, hogy létezik olyan T minimális költségű feszítő fája G-nek, amelyre F ⊆ T ⊆ E − D. Világos, hogy bármelyik minimális költséges fa jó lesz, amikor F = D = ∅. Tegyük most fel, hogy az állítást már beláttuk valamely (F, D) párra, vagyis hogy van egy olyan T minimális költségű feszítő fa, amelyre F ⊆ T ⊆ E − D.

Tegyük fel először, hogy az 1. lépést alkalmaztuk, és legyen e ∈ B az újonnan F -hez vett él. Legyen F′ := F + e. Ha e ∈ T, akkor készen vagyunk, mert a változatlan T jó lesz az (F′, D) párra nézve is. Ha e ∉ T, akkor legyen C_{e} az e alapköre a T -re nézve. Az e él a szabály szerint a B vágásban van, így C_{e}-nek kell lennie egy másik f élének B-ben. Miután e, f ∈ B, az 1. lépés szabálya szerint c(e) ≤ c(f). Mivel e, f ∈ C_{e} és T minimális költségű, azt kapjuk, hogy c(f) ≥ c(e). Ezekből c(e) = c(f), és T′ := T − f + e is egy minimális költségű feszítő fa, amelyre F′ ⊆ T′ ⊆ E − D.

Másodszor, tegyük fel, hogy a 2. lépést alkalmazzuk, és legyen e ∈ C a frissen eltörölt él. Ha T nem tartalmazza e-t, készen vagyunk, mert a változatlan T jó lesz az (F, D + e) párra nézve is. Tegyük fel tehát, hogy T tartalmazza e-t, és legyen B_{e} az e-nek T -re vonatkozó alapvágása. Ekkor létezik egy f ≠ e él, amelyre f ∈ C ∩ B_{e}. Mivel e, f ∈ C, a 2. lépés szabály szerint c(e) ≥ c(f). Mivel e, f ∈ B_{e} és T minimális költségű, következik, hogy c(e) ≤ c(f). Ezekből c(e) = c(f), és T′ := T − f + e is egy minimális költségű feszítő fa, amelyre F ⊆ T′ ⊆ E − (D + e). •

Feladatok

1. Ha minden költség különböző, akkor a min. költségű feszítő fa egyértelmű.

2. Tegyük fel, hogy két költségfüggvény adott az éleken: c_{1}, c_{2}. Adjunk algoritmust olyan feszítő fa megkeresésére, amely a c_{1}-re nézve minimális költségű és ezen belül c_{2}-re nézve minimális költségű. Hogyan általánosítható az eljárás több költségfüggvényre.

3. G(V, E) összefüggő gráf egy F feszitő fája akkor és csak akkor minimális költségű, ha a fa bármely e élének a költsége nem nagyobb, mint az F − e két komponense között vezető bármely él költsége. Továbbá F akkor és csak akkor minimális költségű, ha bármely uv ∈ E − E(F) él költsége legalább akkora, mint a fában az u és v között vezető egyértelmű út bármely élének a költsége.

4B. KÉTFÁZISÚ MOHÓ ALGORITMUSOK

MOHÓ ALGORITMUSOK

Mohó algoritmuson olyasféle eljárást szoktak érteni, amelyben az algoritmus során valamiféle szabályt követve teszünk választásokat, és ezeket a későbbiek során már nem változtatjuk meg. (Ez persze nem matematikai defínició!) Láttuk már, hogy mohó algoritmus segítségével hogyan lehet meghatározni egy összefüggő irányítatlan gráf minimális költségű feszítő fáját (vagy általánosaban egy matroid minimális költségű bázisát). Matroidelméletben azt is láttuk, hogy a mohó algoritmus egyfajta értelemben jellemzi is a matroidokat. Vannak azonban egyéb (helyes eredményt adó) mohó algoritmusok is. Például, ha adott egy P irányított út bizonyos részútjainak F rendszere, kiváncsiak lehetünk arra, hogy miként lehet maximálisan sok élidegen utat kiválasztani F-ből. Válasszuk ki először F-nek a leghamarabb befejeződő tagját, majd az általános lépésben, ameddig csak lehetséges, válasszuk ki F-nek a leghamarabb befejeződő olyan tagját, amely élidegen a már eddig kiválasztottaktól.

Gyakorlat Igazoljuk, hogy ezzel az algoritmussal F-nek maximálisan sok élidegen útból álló részrendszerét kapjuk! Igazoljuk, hogy a kiválasztott utak utolsó élei F valamennyi tagját lefogják!

Feladat Készítsünk algoritmust, amely az F maximális sok tagját kiválasztja úgy, hogy a P alapút minden éle legfeljebb k kiválasztott útban van benne, ahol k előre adott pozitív egész. (A k = 1 felel meg az előbbi élidegen esetnek.)

Feladat Tegyük fel, hogy F tagjait minimális számú osztályba akarjuk besorolni úgy, hogy minden osztály élidegen utakat tartalmaz. Tegyük fel, hogy az osztályok egy adott sorrendben vannak elrendezve. Legyenek ezek kezdetben üresek. Tekintsük az F tagjait a kezdőpontjaik sorrendjében, és egymás után soroljuk be őket az osztályokba úgy, hogy a soron következő utat tegyük a legkorábbi olyan osztályba, amelybe élidegen módon belefér. Igazoljuk, hogy ez a mohó algoritmus minimális számú osztályt fog megadni (éspedig pontosan a maximumát annak a számnak, ahány F-beli útban a P egy éle benne lehet.)

A következő mohó algoritmus egy P részbenrendezett halmaz minimális számú antiláncra történő felbontására szolgál. Jelölje A_{i} a P minimális elemeinek halmazát. Az általános lépésben, amikor már meghatároztuk az A_{1}, …, A_{i} antiláncokat, legyen A_{i+1} a maradék elemek közül a minimálisak halmaza. Az eljárás akkor ér végét, amikor P -nek már minden eleme sorra került.

Gyakorlat Igazoljuk, hogy a kapott antilánc felbontás minimális sok antiláncot használ.

Vannak esetek azonban, amikor a mohó algoritmus nem segít. Például mit csináljunk, ha egy irányított gráfban minimális költségű adott gyökerű feszítő fenyőt kell meghatározni? Kézenfekvőnek tűnhet kiindulni az s gyökérből, majd mindig a lehetséges legolcsóbb olyan élt hozzávenni a már megkonstruált fenyőhöz, amely annak a ponthalmazából kilép.

Gyakorlat Példán mutassuk meg, hogy ez a mohó algoritmus nem feltétlenül ad minimális költségű fenyőt.

Vagy tekinthetjük a fentebbi élidegen út probléma azon általánosítását, amikor minden F-beli útnak adott egy nemnegatív súlya és a célunk egy olyan élidegen utakból álló részrendszert kiválasztani, amelynek összsúlya maximális. Ismét könnyű példán megmutatni, hogy a súlyozatlan esetre előbb leírt mohó algoritmus a súlyozott esetben nem biztosan ad optimumot.

Gyakorlat Mutassuk meg, hogy ez a súlyozott útpakolós probléma miként vezethető vissza egy alkalmas aciklikus digráfban leghosszabb út feladatra.

Feladat Az A zárt szakasz az A_{i} zárt szakaszok (i = 1, …, t) egyesítése. Ekkor ki lehet választani az A_{i} szakaszok közül néhány diszjunktat úgy, hogy az össz-hosszúságok legalább A hosszának a fele.

Hasonlóképp, nem ismert direkt mohó algoritmus egy P részbenrendezett halmaz maximális hosszú láncának meghatározására. Azonban az ismert, hogy a P -nek az előbb mohó módon meghatározott {A_{1}, …, A_{t}} antilánc felbontását miképp lehet segítségül hívni. Legyen ugyanis p_{t} az A_{t} egy tetszőleges eleme. Ez nem került bele A_{t−1}-be, így van olyan p_{t−1} ∈ A_{t−1} elem, amely kisebb mint p_{t}. Ugyanilyan okoskodással van olyan p_{t−2} ∈ A_{t−2} elem, amely kisebb, mint p_{t−1}. Az eljárást folytatva, mindegyik A_{i} antiláncból kiválaszthatunk egy elemet, amely elemek egy t tagú láncot alkotnak, rögtön bizonyítva, hogy ez a lánc maximális elemszámú és azt is, hogy az antilánc felbontás minimális sok tagból áll. (Így az egyik megelőző gyakorlat megoldását is megkaptuk.)

Ez az eljárás egy kétfázisú mohó eljárásnak tekinthető. Az első fázisban mohó módon meghatározzuk az antilánc felbontást, majd ezt felhasználva a második fázisban mohó módon megoldjuk a duális problémát, a leghosszabb lánc meghatározását.

Feladat Tegyük fel, hogy a P részbenrendezett halmaz elemein adott egy w nemnegatív súlyfüggvény. Az előző megközelítést kiterjesztve fejlesszünk ki egy kétfázisú mohó algoritmust maximális össz-súlyú lánc meghatározására. Fogalmazzuk meg a duális problémát és az algoritmus találja meg annak megoldását is.

Kétfázisú mohó algoritmusok más helyeken is felbukkannak. Az alábbiakban két ilyen módszert írunk le.

T -METSZŐ HALMAZRENDSZEREK LEFOGÁSA ÉLEKKEL

Az első algoritmus eredetileg D.R. Fulkersontól való és irányított gráf minimális költségű feszítő fenyőjének meghatározására szolgál. Az algoritmust kicsit általánosabban fogalmazzuk meg, mert így egyéb érdekes speciális eseteket is nyerhetünk.

Legyen G = (V, E) irányított gráf, s ∈ V speciális csúcs, T ⊆ V − s megadott csúcshalmaz. Legyen F a V −s nemüres részhalmazainak egy olyan rendszere, amelyre X, Y ∈ F, X∩Y ∩T ≠ ∅ esetén X∩Y, X∪Y ∈ F. Az X és Y halmazokat T -metszőnek mondjuk, ha nem tartalmazák egymást és X ∩ Y ∩ T ≠ ∅. Az F′ részhalmazát F-nek T -laminárisnak nevezzük, ha F′ nem tartalmaz két T -metsző tagot.

Adott még egy nemnegatív c : E → R költségfüggvény. Azt mondjuk, hogy az F élhalmaz lefogja a Z csúcshalmazt, ha tartalmaz Z-be lépő élt, azaz ϱ_{F} (Z) ≥ 1. F lefogja az F halmaz családot, ha lefogja minden tagját. Célunk, minimális összköltségű F ⊆ E élhalmazt találni, amely lefogja F-t.

Ilyen általános megfogalmazásban a probláma NP-teljes feladatokat is magában foglal (lásd alább), ezért indokolt valamiféle többlet feltétel kikötése. A következőt fogjuk feltenni.

G minden élének a feje T -ben van.  (4A.1)

Megjegyezzük, hogy az élek töveire nincs megszorítás. Figyeljük meg, hogy a T := V − s esetben (4A.1) lényegében semmiféle megkötést nem jelent, hiszen az s-be lépő élek úgysem játszanak szerepet, így azok létét automatikusan kizárhatjuk.

SPECIÁLIS ESETEK.

1. Minimális költségű fenyők. Legyen T = V − s és F álljon a V − s összes nemüres részhalmazából. Ekkor egy minimális költségű F-t lefogó élhalmaz, amint az könnyen ellenőrizhető, s gyökerű feszítő fenyőt alkot. Vagyis az általános feladat magában foglalja a minimális költségű feszítő fenyő problémáját.

2. Minimális költségű utak. Legyen t egy másik rögzített csúcs, legyen T = V − s és F álljon a V − s összes t-t tartalmazó részhalmazából. Ekkor egy minimális költségű F-t lefogó élhalmaz, amint az könnyen ellenőrizhető, egy s-ből t-be vezető utat alkot. Vagyis az általános feladat magában foglalja a minimális költségű út problémáját (legalábbis nemnegatív költségek esetén).

3. Gyökeres élösszefüggőség minimális költségű növelése. Legyen D = (V, A) irányított gráf, s kijelölt gyökér, T ⊆ V − s kijelölt csúcshalmaz. Tegyük fel, hogy (∗) s-ből T minden pontjába vezet k − 1 élidegen út, de vannak olyan pontjai T -nek, amibe nem vezet k élidegen út s-ből. Legyen adva egy G = (V, E) (4A.1)-t kielégítő digráf ugyanazon a csúcshalmazon, együtt egy c nemnegatív költségfüggvénnyel az E élhalmazon. Célunk G éleinek olyan minimális költségű F ⊆ E részhalmazát megkeresni, amelyet D-hez adva a keletkező D^{+} := (V, A + F) digráfban s-ből a T minden pontjába vezet k élidegen út.

Legyen F := {Z ⊆ V − s, Z ∩ T ≠ ∅, ϱ_{D}(Z) = k − 1}. Felhasználva (∗)-t és a befok függvény szubmodularitását, könnyen beláthatjuk, hogy F T -metsző. A Menger tétel irányított él-változata alapján F pontosan akkor fogja le F-t, ha D^{+} := (V, A+F)-ben s-ből a T minden pontjába van k élidegen út. Tehát az általános feladat magában foglalja az s-ből T pontjaiba való élösszefüggőség eggyel való minimális költségű növelésének a problémáját, legalábbis abban az esetben, amikor a felhasználható új élek mindegyikének a feje T -ben van. Megjegyzendő, hogy ez a kikötés automatikusan teljesül, ha T = V −s. Ha viszont a kikötést elhagyjuk, akkor már k = 1 esetben is általános T -re NP-teljes feladatot kapunk (a Steiner fa problémájának irányított változatát.)

4. Gyökeres pontösszefüggőség minimális költségű növelése. Legyen most a kiindulási digráf D′ = (V′, A′) és legyen T′ a V′ − s′ egy részhalmaza. A felhasználható új élek gráfját jelölje G′ = (V′, E′) és tegyük fel, hogy G′ minden élének a feje T′-ben van. (∗) helyett most azt tegyük fel, hogy D′-ben s-ből T′ minden pontjába vezet k − 1 (belsőleg) pontidegen út, de vannak olyan pontjai T′-nek, amikbe nem vezet k pontidegen út s′-ből. Célunk a G′ éleinek olyan minimális költségű F részhalmazát meghatározni, amelyet D′-hez véve a keletkező digráfban s′-ből T′ minden pontjába vezet k pontidegen út.

Ezt a problémát az alábbi szokásos fogással visszavezethetjük az élidegen esetre. Minden v ∈ V′ pontot helyettesítsünk két új ponttal, melyek jele v_{t} és v_{f}. Legyen s := s_{f}. Álljon V az új pontokból és legyen T := {v_{t} : v ∈ T′}. Jelölje D = (V, A) azt a digráfot, amelyben minden eredeti uv ∈ A′ él definiál egy u_{f}v_{t} élt, továbbá minden v ∈ V pont definiál egy u_{t}u_{f} élt. A G = (V, E) digráfban minden eredeti uv ∈ E′ élnek megfeleltetünk egy u_{f}v_{t} élt (de G-be a u_{t}u_{f} típusú éleket nem vesszük be.)

Mármost könnyen látszik, hogy D′-ben akkor és csak akkor van k −1 pontidegen út s′-ből valamely v ∈ T′ pontba, ha D-ben van k − 1 élidegen út s-ből v_{t}-ben. Továbbá valamely F′ ⊆ E′ élhalmazra, amennyiben az F′-nek a G-ben megfelelő élek halmazát F -fel jelöljük, (V, A′ +F′)-ben akkor és csak akkor van k pontidegen út s′-ből v-be, ha (V, A + F)-ben van k élidegen út s-ből v_{t}-be. Vagyis a pontösszefüggőség növelése valóban visszavezethető az élösszefüggőség növelésre.

Megjegyzés A pontösszefüggőségre vonatkozó T = V − s speciális esetet nem lehet visszavezetni az élösszefüggőségre vonatkozó T = V − s speciális esetre (legalábbis a fenti egyszerű pontduplázás nem látszik működni).

OPTIMALITÁSI FELTÉTELEK

Egy x ∈ R^{E} vektor és Z ∈ F halmazra legyen ϱ_{x}(Z) := ∑(x(e) : e belép Z-be). Valamely y : F → R_{+} vektorra és e ∈ E élre legyen m(y, e) := ∑(y(X) : e belép X-be.) Tekintsük a következő (primál) lineáris programot: min cx, feltéve, hogy

ϱ_{x}(Z) ≥ 1 minden Z ∈ F-re, x ≥ 0.  (4A.2)

The duális lineáris program max ∑(y(X) : X ∈ F, y : F → R_{+}), feltéve, hogy

c(e) ≥ m(y, e) minden e ∈ E élre.  (4A.3)

Annak érdekében, hogy (4A.2)-nek legyen egyáltalán megoldása, feltesszük, hogy minden Z ∈ F halmazba lép be él. Célunk egy olyan kombinatorikus algoritmus megadása, amely megoldja a fenti duális lineáris programokat. A primálnak mindig egész optimális megoldását szolgáltatja, a duálisnak pedig azon feltételezés mellett, hogy c egészértékű. Az algoritmus melléktermékként arra fog konstruktív bizonyítást szolgáltatni, hogy (4A.2) TDI.

Miután a primálban egész értékű optimumot keresünk, az x vektort x := χ_{F} alakban fogjuk előállítani, ahol F ⊆ E és χ_{F} az F karakterisztikus (vagy incidencia) vektora. Ennek megfelelően x := χ_{F} pontosan akkor primál megengedett, ha F lefogja F − t.

A (4A.3)-t kielégtő y vektort duál megengedettnek nevezzük. Azt mondjuk, hogy az e ∈ E él y-pontos vagy pontos, ha c(e) = m(y, e). Egy Z ∈ F halmaz F -pontos vagy pontos, ha ϱ_{F} (Z) = 1. Az optimalitási feltételek a következők.

(O1) F elemei y-pontosak. (O2) Ha y(Z) > 0, akkor ϱ_{F} (Z) = 1.

AZ ALGORITMUS

Az algoritmus két fázisból áll. Az elsőben mohó módon megkonstruálunk egy y megengedett duál megoldást. A másodikban csak y-pontos éleket használva mohó módon megkonstruálunk egy olyan F ⊆ E halmazt, amely kielégíti az (O2) optimalitási feltételt.

Vagyis a konstrukció során vigyázunk az optimalitási feltételek fennállására és a duális megengedettségre, és az algoritmus helyességének bizonyítása azáltal válik majd teljessé, hogy majd kimutatjuk a végül kapott F élhalmaz primál megengedettségét (azaz hogy F lefogása F-nek).

1 FÁZIS A fázis lépésekből áll. Minden egyes lépésben meghatározzuk az F egy Z tagját egy belelépő e éllel együtt, valamint a végleges y(Z) értéket. Kezdetben legyen y ≡ 0. Tegyük fel, hogy Z_{j} ∈ F, e_{j} ∈ E és y(Z_{j}) már minden j ≤ i − 1 indexre meg lett határozva. Az i-dik lépésben (i = 1, 2, …) ellenőrizzük, vajon van-e F-nek olyan Z tagja, amelybe nem lép be az eddig kiválasztott {e_{1}, …, e_{i−1}} élek egyike sem. Ha nincs ilyen Z, akkor az első rész végetér. Legyen t := i−1, Z := {Z_{1}, …, Z_{t}} és térjünk a második fázisra. Amennyiben van ilyen Z, úgy válasszuk Z_{i}-nek F legszűkebb ilyen tagját. Legyen μ_{i} := min(c(e)−m(y, e) : e belép Z_{i}-be) és módosítsuk y-t úgy, hogy az aktuális y(Z_{i}) = 0-t változtassuk y(Z_{i}) := μ_{i}-re. (Előfordulhat, hogy μ_{i} = 0). Legyen továbbá e_{i} az egyik olyan Z_{i}-be lépő él, amelyen a minimum felvétetik.

2. FÁZIS Az üres halmazból indulva egyre bővítjuk F -t az alábbi szabály szerint. Tekintsük az 1. fázisban kiválasztott e_{i} éleket fordított sorrendben és a sorra következő e_{i} élt akkor válasszuk F -be, ha az Z_{i} még nincsen lefogva.

Megjegyzés Az algoritmus konkrét esetben akkor használható, ha rendelkezésünkre áll egy olyan szubrutin, amely eldönti, hogy adott J ⊆ E élhalmaz lefogja-e F-t, és ha nem, akkor meghatározza F-nek egy legszűkebb lefogatlan elemét. A fentebb említett speciális esetek mindegyikében ez a szubrutin legyártható. A minimális költségű fenyők esetén a következő szakaszban ezt részletesebben tárgyaljuk is. A gyökeres élösszefüggőeség növelés esetén (amelyre, mint láttuk a gyökeres pontösszefüggőség esete is visszamegy) a szükséges szubrutin előlállításához a maximális folyam algoritmus alkalmazására van szükség: a részleteket itt nem tárgyaljuk.

AZ ALGORITMUS HELYESSÉGÉNEK BIZONYÍTÁSA

Az 1. fázisban megkonstruált y a szabály miatt nyilván duál megengedett lesz. Továbbá mindegyik e_{i} él pontos. Ebből adódik, hogy F y-pontos élekből áll, azaz (O1) teljesül.

Az 1. fázis szabálya miatt érvényes a következő:

A ÁLLÍTÁS Ha X ⊂ Z_{j} valamely j = 1, …, t indexre és X ∈ F, akkor van olyan i index, amelyre i < j és e_{i} belép X-be. •

B ÁLLÍTÁS Z T -lamináris.

Biz. Indirekt tegyük fel, hogy Z_{j}, Z_{h} két T -metsző halmaz, melyekre j < h. Az A állítást X := Z_{j} ∩ Z_{h}-ra alkalmazva kapjuk, hogy van olyan e_{i} él, amelyre i < j és e_{i} belép X-be. Ekkor e_{i} belép Z_{j} és Z_{h} egyikébe legalább, ami ellentmond az 1. fázis választási szabályának miután i < j < h. •

C ÁLLÍTÁS Mindegyik Z_{i} F -pontos.

Biz. A konstrukció miatt ϱ_{F} (Z_{i}) ≥ 1. Indirekt tegyük fel, hogy valamely Z_{i}-be az F -nek legalább két éle lép be és tegyük fel, hogy Z_{i} maximális ilyen. Legyen a két él e_{j} és e_{k}. A választási szabályok és (4A.1) miatt i < j < k. Mivel Z T -lamináris, kapjuk, hogy Z_{i} ⊂ Z_{j} ⊂ Z_{k}, de ekkor mind az e_{j} mind az e_{k} él belép Z_{j}-be, ellentétben Z_{i} maximális választásával. •

A C állítás alapján (O2) teljesül.

D ÁLLÍTÁS Tetszőleges Z ∈ F halmazhoz van olyan j index, amelyre e_{j} belép Z-be és Z_{j} ⊆ Z.

Biz. Az első fázis végén van Z-be lépő e_{j} él. Tegyük fel, hogy j a legkisebb olyan index, amelyre e_{j} belép Z-be. Belátjuk, hogy ekkor Z_{j} ⊆ Z. Ha nem ez volna a helyzet, akkor X := Z_{j} ∩ Z valódi részhalmaza lenne Z_{j}-nek. Ekkor az A állítás szerint van olyan i < j index, amelyre e_{i} belép X-be. Ekkor viszont e_{i} szükségképpen belép Z_{j} és Z közül legalább az egyikbe. Ugyanakkor az e_{i} nem léphet be Z_{j}-be az 1. fázis szabály szerint, és nem léphet be Z-be sem a j minimális választása szerint, amely ellentmondás igazolja az állítást. •

E ÁLLÍTÁS F lefogja F-t.

Biz. Tegyük fel indirekt, hogy F-nek van F által lefogatlan tagja és legyen Z egy legbővebb ilyen. A D állítás szerint van olyan j index, amelyre e_{j} belép Z-be és Z_{j} ⊂ Z. Emiatt e_{j} nincs F -ben, és így (a 2. fázis szabály szerint) van olyan Z_{k}, amelyre Z_{k} ⊃ Z_{j} és e_{k} belép Z_{j}-be, de Z-be nem. Következik, hogy Z_{k} és Z T -metszők. Z maximális választása miatt ϱ_{F} (Z_{k} ∪ Z) ≥ 1, ezért van olyan e_{l} ∈ F él, amely belép Z_{k} ∪ Z-be. De ekkor e_{l} belép Z_{k} és Z egyikébe legalább, ami viszont lehetetlen, hiszen Z-be nem lép be F -beli, ha viszont e_{l} az Z_{k}-ba lép, akkor Z_{k}-ba belép e_{k} és e_{l} is, ellentétben a C állítással. •

MAXIMÁLIS SÚLYÚ STABIL HALMAZ KERESÉSE MEREVKÖRŰ GRÁFBAN

Legyen G = (V, E) irányítatlan gráf. V pontjainak egy részhalmazát akkor nevezik stabilnak, ha nem feszít élt. Közismert, hogy maximális stabil halmaz meghatározása NP-teljes. Perfekt gráfok esetén viszont tudjuk, hogy a maximális stabil halmaz α(G) mérete megegyezik a klikk-fedési számmal, sőt ennek érvényes a súlyozott változata is, amely szerint ha adott a V -n egy w egészértékű súlyfüggvény, akkor (perfekt gráfban) a maximális súlyú stabil halmaz α_{w}(G) súlya egyenlő azon (nem feltétlenül különböző) klikkek minimális számával, amelyek minden v csúcsot legalább w(v)-szer tartalmaznak. Az első feladatra primál, a másodikra duál problémaként fogunk hivatkozni. Az alábbiakban leírunk egy algoritmust, amely merevkörű gráf esetén kiszámolja ezen extrémumokat, és egyúttal erre a gráfosztályra a tételnek konstruktív bizonyítását szolgáltatja.

A második fejezetben láttuk, hogy G = (V, E) merevkörű gráf esetén egy max-vissza sorrend fordított szimpliciális sorrendet alkot, vagyis a csúcsoknak egy u_{1}, …, u_{n} szimpliciális sorrendjét gyorsan ki lehet számolni. Mindegyik i-re álljon K_{i} az u_{i} pontból valamint az u_{i}-nek i-nél nagyobb indexű szomszédaiból. A szimpliciális sorrend definíciója folytán K_{i} klikk.

1. FÁZIS Növekvő sorrend szerint végigmegyünk a csúcsokon, és mindegyik K_{j} klikkhez meghatározunk egy y_{j} := y(K_{j}) nemnegatív egészet, amely azt jelzi, hogy a K_{j} klikket hány példányban választjuk be a keresett klikk-fedésbe. Az első lépésben legyen y_{1} := w_{1}. A j-dik lépésben feltesszük, hogy az y_{1}, …, y_{j−1} értékeket már meghatároztuk. Amennyiben az u_{j} pont már benne van w_{j} klikkben (azaz az u_{j}-t tartalmazó klikkek változóinak összege eléri a w_{j} értéket), úgy legyen y_{j} := 0 és j értékét eggyel növelve iteráljuk az eljárást. Ellenkező esetben legyen y_{j} := w_{j} − ∑(y_{i} : K_{i} tartalmazza u_{j}-t).

2. FÁZIS Tekintsük azokat az i indexeket, amelyekre y_{i} > 0. Legyenek ezek i_{1}, …, i_{t}. Az ezeknek megfelelő pontokon fordított sorrendben végighaladva, u_{i_{t}}-nél kezdve, egymás után válasszunk ki pontokat csak arra ügyelve, hogy a kiválasztott csúcsok stabil halmazt alkossanak. Jelölje S az eljárás végére előálló halmazt.

Az algoritmus szabályaiból következik, hogy y duális megengedett megoldás és S stabil halmaz. Az optimalitáshoz azt kell igazolni, hogy az alábbi optimalitási feltételek teljesülnek. Azt mondjuk, hogy egy u_{j} csúcs pontos, ha w_{j} = ∑(y_{i} : K_{i} tartalmazza u_{j}-t). Az optimalitási feltételek a következők.

(O1) Az S elemei pontosak.

(O2) Ha y(K_{i}) > 0, akkor K_{i} ∩ S ≠ ∅.

Mármost (O1) teljesül a 2. fázis szabálya miatt. (O2) igazolásához tekintsünk egy K_{i} klikket, amelyre y_{i} pozitív. Amennyiben u_{i} benne van S-ben, úgy (O2) teljesül. Tegyük fel tehát, hogy u_{i} nem lett S-be választva. Ennek a 2. fázis szabálya szerint az volt az oka, hogy létezik egy olyan j index, amelyre j > i, u_{j} ∈ S és u_{i}u_{j} ∈ E. De ekkor K_{i} definíciója folytán u_{j} ∈ K_{i}, azaz (O2) valóban fennáll. •

Feladat Dolgozzunk ki algoritmust merevkörű gráf maximális klikkjének meghatározására valamint pontjainak minimális számú színnel történő kiszinezésére. Általánosítsuk az eljárást a súlyozott esetre!

A fejezet elején említett maximális összsúlyú élidegen utak kiválasztásának feladata ezáltal megoldhatóvá válik, ha megfigyeljük, hogy egy irányított alapút bizonyos részújainak rendszeréből álló hipergráf élgráfja merevkörű.

Feladat Adott az F fa részfáinak egy F rendszere. Tegyük fel, hogy F mindegyik tagjának adott a súlya. Határozzunk meg F-nek egy maximális összsúlyú páronként pont-diszjunkt fákból álló részrendszerét.

Tájékoztatásul megjegyezzük, hogy ha a fenti feladatban pont-idegen helyett élidegen fákat keresünk, akkor sokkal nehezebb feladathoz jutunk. Ez a probléma ugyanis még w ≡ 1 súlyozás esetén is magában foglalja a a maximális párosítás problémáját tetszőleges gráfban. (Hogyan?) A feladat azonban a párosítás problémára egy ügyes fogás révén visszavezethető és így megoldható.

4C. MINIMÁLIS KÖLTSÉGŰ FENYŐK

Az előzőekben megadott kétfázisú mohó algoritmusok tanulmányozása közben az a bizonytalan érzése támadhat az olvasónak, hogy az algoritmusok során megadott választási szabályok némileg misztikusak vagy legalábbis légbőlkapottak, és utána az algoritmus helyességének igazolása valahogy a dolgok váratlanul szerencsés körülállása miatt lehetséges. Valójában egy ilyen algoritmus kitalálásakor számos választási szabállyal kisérletezhetünk, és párhuzamosan figyeljük a bizonyítási lehetőségeket.

Példaképp megemlítjük, hogy irányított gráf minimális költségű feszítő fenyőjének meghatározására az előzőekben már megadtunk egy algoritmust. Most ugyanezen problémára egy kicsit másként vezetett kétfázisú mohó algoritmust is leírunk. Tehát az itt közölt algoritmus NEM a korábbinak specializációja, bár hasonlít rá. Ennek kapcsán részletesebben kielemezzük, hogy a szükséges szubrutin miért is áll rendelkezésre. Azt is megvizsgáljuk majd, hogy hogyan lehetett volna kitalálni az algoritmust, ha nem ismernénk a lineáris programozási hátteret.

Legyen tehát G = (V, E) újfent egy irányított gráf, amelynek egy adott s pontjából minden más pontja elérhető irányított úton, ami azzal ekvivalens, hogy G tartalmaz feszítő s-fenyőt. Adott az éleken egy nemnegatív c : E → R_{+} költség- (vagy másnéven súly-) függvény. Keressünk minimális összköltségű feszítő s-fenyőt.

Egy z : 2^{V −s} → R_{+} halmazfüggvényt c-megengedettnek nevezünk, ha

c(e) ≥ ∑(z(X) : e belép X-be) minden e ∈ E élre.  (4C.1)

4C.1 TÉTEL [Fulkerson, 1974] Az s-fenyők minimális költsége egyenlő max(∑(z(X) : X ⊆ V − s) : z c-megengedett). Továbbá, ha c egészértékű, akkor az optimális z választható egészértékűnek.

Megjegyzés. Tömören megfogalmazva a tétel azzal ekvivalens, hogy az Ax ≥ 1, x ≥ 0 egyenlőtlenségrendszer teljesen duálisan egészértékű (TDI), ahol az A egy olyan 0 − 1 mátrixot jelöl, amelynek a sorai a G éleinek felelnek meg, az oszlopai a V − s nemüres részhalmazainak, és a mátrix egy e élnek és X részhalmaznak megfelelő eleme pontosan akkor 1, ha e belép X-be.

Biz. Legyen F feszítő s-fenyő és z egy c-megengedett vektor. Ekkor

c(F) = ∑(c(a) : e ∈ F) ≥ ∑(∑(z(X) : e belép X − be): e ∈ F) ≥ ∑(z(X) : X ⊆ V − s) (4C.2)

amiből max ≤ min következik. (4C.2)-ben akkor van végig egyenlőség, ha a következő optimalitási feltételek teljesülnek.

c(e) = ∑(z(X) : e belép X-be) minden e ∈ F élre ,  (4C.3a)

z(X) > 0 esetén ϱ_{F} (X) = 1.  (4C.3b)

Az alábbi algoritmus egy olyan F feszítő s-fenyőt és megengedett z-t konstruál, amelyre (4C.3a-b) teljesül. Két fázisból áll. Az elsőben z-t konstruáljuk meg, míg a másodikban F -t. Mindkét rész egyfajta értelemben mohó lesz. Az első fázis minden lépésében módoítjuk a költségfüggvényt, és az aktuális költségfüggvényt c′-vel fogjuk jelölni. Egy e élt a c′ aktuális költségfüggvényre nézve 0-élnek nevezzük, ha c′(e) = 0.

1. FÁZIS Amíg van V −s-nek olyan nemüres részhalmaza, amelybe nem lép be 0-él, ismételjük a következő lépést. Válasszunk egy olyan minimális nemüres X ⊆ V − s részhalmazt, amelybe nem lép 0-él. Legyen z(X) := min(c′(e) : e belép X-be) és csökkentsük c′(e)-t a z(X) értékkel az összes X-be lépő e élen.

A módosított c′ továbbra is nemnegatív, és mindazokon az X-be belépő éleken 0-vá vált, amelyeken az előbbi minimum eléretik. Az 1. fázis tehát akkor fejeződik be, amikor már minden X ⊆ V − s részhalmazba lép be 0-él, vagyis amikor már létezik 0-élekből álló feszítő s-fenyő.

2. FÁZIS Az s pontból kiindulva, 0-élek egymás utáni hozzávételével felépítünk egy F s-fenyőt. Ha az építési eljárás egy lépésében több, mint egy olyan 0-él van, amely a már megkonstruált részfenyő ponthalmazából kilép, akkor azt az élt adjuk a részfenyőhöz, amely az 1 fázis során a leghamarabb vált 0-éllé.

Az előállítás szabályai miatt világos, hogy a megkonstruált z vektor c-megengedett, továbbá, hogy (4C.3a) fennáll.

LEMMA z és F kielégítit (4C.3b)-t.

Biz. Legyen X olyan halmaz, amelyre z(X) > 0 és tegyük fel indirekt, hogy ϱ_{F} (X) > 1. Ekkor a 2. fázisnak van egy olyan pillanata, amikor az aktuális F′ részfenyő olyan, hogy ϱ_{F′}(X) = 1 és az F′-höz éppen hozzáadásra kerülő e él belép X-be.

Tekintsük most az 1. fázisnak azt a pillanatát, amikor z(X) pozitív lett. Ekkor az X-be még nem lépett 0-él, ugyanakkor az X-nek már minden valódi nemüres részhalmazába lépett. Speciálisan, az X − V (F′) halmazba is lépett egy f 0-él, és mivel ez X-be nem léphetett, így f töve X ∩ V (F′)-ben van. Az f tehát már z(X) pozitívvá válásának pillanatában 0-él volt, amikor még e nem volt az. Miután az f éllel is lehetne növelni az F′ részfenyőt, ellentmondásra jutottunk a 2. fázis választási szabályával, amely szerint a legkorábban 0-éllé vált éllel kell növelni az aktuális részfenyőt. •

A lemmából következik, hogy az algoritmus által megtalált F feszítő s-fenyő és z megengedett duális megoldás kielégítik az optimalitási feltételeket, amiből az algoritmus helyessége, valamint Fulkerson tétel is következik. • •

Az előbbihez kapcsolódik a következő probléma. Legyen G = (V, E) ismét egy irányított gráf éleinek halmazán egy w súlyfüggvénnyel. Keressünk maximális súlyú fenyvest!

Egy (p, y) párt fedésnek nevezünk, ha p : V → R_{+} és y : 2^{V} → R_{+} nemnegatív függvények melyekre w(u, v) ≤ p(v) + ∑(y(B) : u, v ∈ B ⊆ V) teljesül minden uv ∈ E élre. A fedés értéke ∑(p(v) : v ∈ V) + ∑(y(B)(|B| − 1) : B ⊆ V).

4C.2 TÉTEL [Edmonds 1967], [Chu and Liu, 1965] Egy fenyves súlyának maximuma a fedések minimális értékével egyenlő. Ha w egészértékű, akkor az optimális fedés is választható annak.

Biz. Könnyen látszik, hogy max ≤ min. A fordított irány belátásához egészítsük ki G-t egy új s ponttal és vezessünk s-ből minden v ∈ V pontba egy új sv élt. A megnövelt G′ digráfon definiáljunk egy c költségfüggvényt a következőképpen. Az új élek költsége legyen M := max(w(e) : e ∈ E), míg minden eredeti e ∈ E élre legyen c(e) = M − w(e).

A 4C.1 tétel szerint létezik z : 2^{V} → R_{+} c-megengedett vektor és egy G′-nek egy F feszítő s-fenyője amelyek kielégítik (4C.3)-t. Legyen p(v) := M − ∑(z(B) : v ∈ B), és |B| > 1 esetén legyen y(B) := z(B) (B ⊆ V). Könnyen látható, hogy az így kapott (p, y) fedést alkot, továbbá, hogy az értéke egyenlő a G digráf F ∩ A fenyvesének súlyával. •

Feladat Legyen T ⊆ V − s adott halmaz olyan, hogy a digráf minden pozitív költségű élének a feje T -ben van (a költségfüggvény nemnegatív). Olyan minimális költségű s gyökerű fenyő keresése, amely T minden pontját tartalmazza (de nem feltétlenül feszítő) speciális esete a T -metsző halmazrendszerek korábban tárgyalt lefogási problémájának. Mutassuk meg, hogy a feladat visszavezethető a minimális költségű fesztő fenyő problémájára.

Feladat Igazoljuk hogy egy G = (V, E) digráfban éleknek egy adott F ⊆ E részhalmaza akkor és csak akkor egészíthető ki s gyökerű feszítő fenyővé, ha nem lehet úgy megadni a V − s halmaznak |V | − |F | darab nemüres részhalmazát, hogy ezek egyikébe sem lép F -beli él és E − F minden eleme legfeljebb egybe lép.

(Útmutatás. Alkalmazzuk a 4C.1 tétel alkalmas költségfüggvényre.)

Feladat Tegyük fel, hogy adott V − s részhalmazainak egy {A_{1}, …, A_{t}} rendszere. Hogyan lehetne algoritmikusan eldönteni, hogy a digráf tartalmaz-e olyan feszítő fenyőt, amely mindegyik A_{i} halmazba pontosan egyszer lép bele?

(Útmutatás. Keressünk minimális költségű fenyőt okosan választott költségfüggvényre.)

Feladat Tegyük most fel, hogy létezik olyan s-gyökerű feszítő fenyő, amely az {A_{1}, …, A_{t}} halmazok mindegyikébe egyetlen éllel lép bele. Készítsünk algoritmust, amely az ilyen fenyők közül egy megadott költségfüggvényre vonatkozó minimális költségűt talál.

A minimális költségű fenyő megkeresésére vonatkozó Fulkerson-féle tétel és algoritmus hátterében lineáris programozási meggondolások állnak. Az alábbiakban ugyanennek az algoritmusnak egy másik lehetséges tárgyalásmódját vizsgáljuk meg, amely nem támaszkodik lin.prog. gondolatokra, és azt is mutatja, hogy hogyan lehet kitalálni egy ilyen algoritmust. Megvizsgáljuk továbbá azt is, hogy miként is lehet a fenti 1. fázisnak azt a kissé elnagyoltan leírt lépését végrehajtani, amelyben egy ”minimális olyan X halmazt keresünk, amelybe nem lép 0-él”.

GYAKORLATOK

1. Mutassuk meg, hogy a minimális költségű s-fenyő problémája általánosítja az irányítatlan gráfra vonatkozó minimális költségű feszítő fa problémáját.

2. Hogyan lehet minimális költségű s-fenyő segítségével irányított gráfban egy s-ből t−be vezető legkisebb költségű utat megkeresni? (Emlékeztetőül: ezen utóbbi feladatra Dijkstra algoritmusa szolgáltat O(n^{2}) bonyolultságú algoritmust.)

3. Mutassunk példát arra, hogy a következő fordított mohó (”óvatos”) eljárás NEM feltétlenül ad optimális s-fenyőt: Minden lépésben dobjuk ki a maximális súlyú élt csak arra ügyelve, hogy a maradékban még minden pont elérhető legyen s-ből.

4. Miként lehet az általános költség-függvényre vonatkozó feladatot visszavezetni a nemnegatív költség esetére?

5. Tetszőleges él összehúzásakor az s-fenyők minimális költsége nem nő.

6. Ha egy s-től különböző v pontba belépő valamennyi él költségét ugyanazzal az α számmal csökkentjük, akkor minden s-fenyő költsége α-val csökken.

Ezen utolsó gyakorlat alapján feltehetjük, hogy minden s-től különböző pontba lép be 0 súlyú él. Amenynyiben a 0 súlyú élek G_{0} részgráfja tartalmaz s-fenyőt, akkor ennek 0 összköltsége nyilván minimális, hiszen a c költség-függvényről feltettük, hogy nemnegatív. A megoldandó eset tehát az, amikor G_{0} nem tartalmaz s-fenyőt.

1. ÁLLÍTÁS G_{0} tartalmaz olyan C irányított kört, amelyben s nincs benne.

Biz. Legyen S az s-ből G_{0}-ban elérhető pontok halmaza. Ekkor S-ből nem vezet ki 0 súlyú él, és a feltevés szerint V − S nem üres. Most tetszőleges v ∈ V − S pontba lép be uv 0 súlyú él és tudjuk, hogy u nem S-ben van. Következésképpen V − S tartalmaz 0 súlyú élekből álló kört. •

A döntő észrevétel az alábbi:

2. ÁLLÍTÁS A C 0-súlyú kört összehúzva az s-fenyők súlyának minimuma nem változik.

Biz. A 3. gyakorlat alapján tudjuk, hogy az összehúzással a minimum nem nő. Annak belátásához, hogy nem is csökken, válasszunk egy minimális súlyú F′ s-fenyőt az összehúzott G′ digráfban. Ennek egyetlen e′ éle lép be a C kör összehúzásával keletkezett v_{C} pontba. Jelölje e = uv az e′ élnek megfelelő eredeti élt, ahol v a C körnek pontja, míg u nem. A C-beli élek közül ha kihagyjuk a v-be lépőt, akkor egy olyan v-ből induló P utat kapunk, amelynek minden éle 0 súlyú.

Most F′-t és P -t összetéve az eredeti G digráfnak kapunk egy s-fenyőjét, amelynek súlya ugyanannyi, mint F′ súlya. •

A 2. Állítás alapján elegendő meghatározni az összehúzott G′ digráfnak egy minimális költségű s-fenyőjét, és e meggondolásokat rekurzívan alkalmazva G egy minimális költségű s-fenyője kiszámítható. Ez tehát a következő algoritmust jelenti. Az eljárás két fázisból áll. Az elsőben váltakozva súlyokat csökkentünk és köröket húzunk össze, míg a másodikban megkeressük a kívánt s-fenyőt.

1. FÁZIS (A) Minden s-től különböző v pontra csökkentsük a v-be lépő élek súlyát ezen súlyok minimumával.

(B) Döntsük el, hogy minden pont elérhető-e s-ből 0 súlyú éleket használva. Ha igen, menjünk a 2. fázisra. Ha nem, keressünk egy 0 súlyú élekből álló irányított kört, húzzuk össze, és az összehúzott gráffal menjünk vissza az (A) pontba.

2. FÁZIS Határozzunk meg az aktuális (összehúzások után keletkezett) digráfban egy 0 súlyú élekből álló s-fenyőt. Az összehúzott köröket az összehúzás sorrendjében visszafelé haladva egymás után egyenként ”fújjuk vissza”, és a 2. állítás bizonyításában leírt módon a meglévő s-fenyőből határozzuk meg a visszafújt digráfnak egy s-fenyőjét.

A fenti eljárásról könnyen kimutatható, hogy polinomiális futásidejű. Ezen belül azonban nem túlságosan ökonomikus. Az 1. fázis (B) lépésében például, amikor egy C kört összehúzunk, lehet hogy az összehúzott pontba lép be 0 súlyú él, és ilyenkor az (A) lépésre való visszatéréskor ott semmi sem történik, hanem a súlyok változtatása nélkül ismét a (B) lépésre kerül a sor. Hogyan lehetne ezeket az üres (A) lépéseket kiiktatni? Úgy, hogy egyszerre nem csak egyetlen kört húzunk össze, hanem a 0 súlyú élek G_{0} digráfjának egy olyan s-et nem tartalmazó erős komponensét, amelybe nem vezet 0 súlyú él. Nevezzünk egy ilyen halmazt forrás-komponensnek.

LEMMA Az 1. fázis folyamán az aktuális G_{0}-nak mindig van s-et nem tartalmazó forrás-komponense.

Biz. Tudjuk, hogy egy tetszőleges G′ digráf erősen összefüggő komponenseit összehúzva aciklikus digráfot kapunk, amelyben biztosan van forráspont, ami az összehúzás előtti digráf egy forrás-komponensének felel meg. Mármost legyen G′ az a digráf, amely G_{0}-ból keletkezik úgy, hogy minden v pontból behúzunk egy s-be menő új élt. Mivel az 1. fázisban vagyunk, G_{0}-ban az s-ből elérhető pontok S halmaza szűkebb V -nél és az S a G′-nek egy erősen öszefüggő komponense lesz, amely nem forrás-komponens. Tehát G′ bármely forrás-komponense jó lesz, mert nem tartalmazza s-et. •

MÓDOSÍTOTT 1. FÁZIS A lemma alapján módosítsuk úgy az 1. fázist, hogy a 2. lépésben nem csupán egyetlen irányított kört húzunk össze, hanem egy teljes s-et nem tartalmazó K forrás-komponenst.

Figyeljük meg, hogy K nem egyetlen pontból áll, hiszen az (A) lépés miatt minden s-től különböző pontba vezet 0 súlyú él, tehát egyetlen pont nem lehet forrás-komponens.

Ezen lépés összevonásnak nagy előnye, hogy egy-egy mélységi keresés segítségével lineáris időben mind egy digráf erős komponenseit, mind egy aciklikus digráf forrás-pontjait meg tudjuk határozni, vagyis G_{0}-nak az s-et nem tartalmazó forrás-komponense lineáris időben megtalálható.

Kellemetlenség azonban, hogy a 2. fázis fenyőépítési eljárása áttekinthetetlenné válik. Ezt a nehézséget leküzdendő, először is figyeljük meg, hogy a 2. Állítás érvényben marad akkor is, ha kör helyett forráskomponensről beszélünk. Ebből következik, hogy a 2. fázisban a G digráfnak egy olyan s-fenyőjét kell megkeresni, amelynek minden élének módosított súlya nulla, és amely

minden valamikor is összehúzásra került halmazba egyetlen egy éllel lép be.  (∗)

Ezt a célt éri el a következő:

MÓDOSÍTOTT 2. FÁZIS s-ből kiindulva 0 (módosított) súlyú élek egyenkénti hozzávételével G-ben építsünk fel egy F s-fenyőt, mindig olyan élt véve a már meglévő rész-fenyőhöz, amelynek súlya az első fázis során leghamarabb vált nullává.

LEMMA A megkonstruált F s-fenyő kielégiti a fenti (∗) tulajdonságot és így optimális.

Biz. Legyen K az 1. fázis során valamikor összehúzott forrás-komponens és tegyük fel indirekt, hogy F több mint egyszer lép be K-ba. Legyen e = uv az F -nek a K-ba belépő második éle (a 2. fázis fenyő-építésének sorrendjében) és jelölje K′ a K-nak azt a részhalmazát, amely az e bevétele előtti pillanatban a meglévő rész-fenyőhöz tartozik . Tekintsük az 1. fázisnak a K összehúzása előtti pillanatot. Ekkor K-ba nem lép 0 súlyú él, de a K által feszített 0 súlyú élek erősen összefüggő digráfot alkotnak. Tehát e súlya később vált nullává, mint ezen éleké. Ily módon a módosított 2. fázis előírása szerint az e helyett egy K′-ből K − K′-be vezető 0 súlyú élt kellett volna a meglévő rész-fenyőhöz venni. Ez az ellentmondás bizonyítja a lemmát. • •

(Ez a bizonyítás ugyanaz, mint a Fulkerson tételben szereplő lemma bizonyítása, és csak a teljesség kedvéért ismételtük meg.)

Feladat Adott egy erősen összefüggő digráf, élein súlyokkal. Mutassuk meg (valamely közismert NP-teljes feladatra történő visszavezetéssel) hogy minimális költségű erősen összefüggő feszítő részgráf keresésének problémája NP-teljes. Készítsünk olyan polinom idejű eljárást, amely az optimumnak legfeljebb kétszeresét adja.

Feladat Igazoljuk, hogy egy digráf akkor és csak akkor erősen összefüggő, ha irányított körök egymás utáni összehúzásával egyetlen pontra húzható.

4D. DINAMIKUS PROGRAMOZÁS

A dinamikus programozás egy lehetséges algoritmikus megközelítési mód kombinatorikus optimalizálási feladatok megoldására. Az általános ideát néhány feladaton mutatjuk be.

1. Adott egy G = (V, E) irányított gráf, élein egy c konzervatív súlyozás, határozzunk meg egy s-ből t-be vezető minimális súlyú utat.

Ezt a problémát már korábban tárgyaltuk. A megoldás egyik kulcs észrevétele az a megfigyelés, hogy ha P egy s-ből t-be vezető legrövidebb út és v ennek belső pontja, akkor P -nek az s-től v-ig vezető kezdő szakasza egy s-ből v-be vezető legrövidebb út. (Ez az állítás csak konzervatív súlyozás esetén áll fenn és ekkor is csak irányított gráfra.)

A másik fontos ötlet az volt, hogy nem csupán a t-be vezető legrövidebb utat határoztuk meg, hanem az összes többi pontba vezetőt, sőt még ennél is többet: Meghatároztuk az összes v pontra és az összes 0 ≤ k ≤ n egészre az s-ből v-be vezető legfeljebb k élt használó utak közül a legkisebb költségűt.

Tegyük fel, hogy már ismertek a legfeljebb k élt használó legrövidebb utak w_{k}(v) költségei. Tekintsünk egy v be menő legfeljebb k + 1 élű utat, amelynek költsége minimális. Amennyiben ez legfeljebb k élből áll, akkor w_{k+1}(v) = w_{k}(v). Ha viszont pontosan k + 1 élből áll, akkor az utolsó előtti v′ pontjáig tartó részút k élű és így költsége éppen w_{k}(v′). Ennek alapján w_{k+1}(v) = min(w_{k}(v), min(w_{k}(u)+c(uv) : uv ∈ E)) minden v ∈ V -re.

Ennek alapján az algoritmus n fázisból áll: a (k + 1)-dikben a fenti rekurzió alapján határozhatjuk meg a w_{k+1}(v) értékeket minden v pontra.

Általában is, dinamikus programozási algoritmus kidolgozására három jelenség egyidejű fennállásakor van lehetőségünk. Egyrészt a keresett optimális struktúra olyan legyen, hogy valamely része egy alkalmas részprobléma optimális megoldását adja, másrészt a szóbajövő részproblémák teljes száma ne legyen túl nagy (azaz az input méretének polinomjával legyen korlátozható), és végül a részproblémák optimális megoldásaiból az eredeti probléma optimális megoldása hatékonyan kiszámítható legyen. Nézzünk további példákat ezen gondolat megvalósítására.

2. Adott m mátrix, A_{1}, A_{2}, …, A_{m}, és ki akarjuk számítani a szorzatukat. Határozzuk meg a szorzásoknak azt a sorrendjét, amelyre az elemi szorzások össz-száma a lehető legkisebb lesz!

Természetesen az összeszorozhatóság érdekében feltesszük, hogy a mátrixok méretei stimmelnek, azaz álljon az A_{i} mátrix p_{i−1} sorból és p_{i} oszlopból. Egy ab-s és egy bc-s mátrix szorzata ac-s. Ennek egy elemének kiszámításához b szorzásra van szükség, így a szorzások teljes száma abc. Ezt tekintjük két mátrix összeszorzási költségének.

Az A_{i} mátrixok összeszorzási sorrendjét egy zárójelezés határozza meg. Tegyük fel például, hogy m = 4. Három lehetőség (összesen 5 van) és a hozzájuk tartozó szorzási költségek:

(A_{1}A_{2})(A_{3}A_{4}); p_{0}p_{1}p_{2} + p_{2}p_{3}p_{4} + p_{0}p_{2}p_{4},

(((A_{1}A_{2})A_{3})A_{4}); p_{0}p_{1}p_{2} + p_{0}p_{2}p_{3} + p_{0}p_{3}p_{4},

((A_{1}(A_{2}A_{3}))A_{4}); p_{1}p_{2}p_{3} + p_{0}p_{1}p_{3} + p_{0}p_{3}p_{4}.

Jelölje A_{i..k} az A_{i} … A_{k} mátrixok szorzatát (1 ≤ i ≤ k ≤ m) és c_{i..k} a kiszámítás minimális költségét. Tehát mi a c_{1..m}-re vagyunk kiváncsiak.

Tegyük fel, hogy egy optimális zárójelezés olyan, hogy az A_{j}-t követően bezáródik egy maximális zárójel és elkezdődik egy másik maximális (egy összetartozó zárójel-pár ”maximális”, ha nincs nagyobban benne). Ekkor nyilvánvalóan a zárójelezést akár az A_{1}, …, A_{j}, akár az A_{j+1}, …, A_{m} részsorozatra megszorítva optimális zárójelezést kapunk, vagyis teljesül a fenti két elv közül az első.

Az összes lehetséges A_{i}, …, A_{k} részsorozatra (1 ≤ i ≤ k ≤ m) meg fogjuk határozni az optimális zárójelezés c_{i..k} költségét. Szerencsére ilyen részsorozatból csak kevés van (m(m + 1)/2), így a fentebb megfogalmazott elvek közül a második is teljesül.

Nyilvánvalóan az egy-tagú részsorozatokra c_{i..i} = 0. Tegyük fel, hogy már meghatároztuk az összes legfeljebb t tagú részsorozatra az optimális zárójelezés költségét és most a t + 1 tagú részsorozatokra akarjuk ugyanezt kiszámítani. Ennek érdekében tekintsük az A_{i}, … A_{k} t + 1 tagú részsorozatot, ahol k = i + t.

Ekkor c_{i..k} = min(c_{i..j} + c_{j+1..k} + p_{i−1}p_{j}p_{k} : j = i, …, k − 1). Vagyis a legfeljebb t tagú részsorozatok összeszorzásának minimális költségéból egyszerűen ki tudjuk számítani a t + 1 taguakét is.

A most következő feladat tulajdonképpen könnyen visszavezethető az elsőre, de érdemes külön is megfogalmazni, mert érdekes alkalmazásai vannak.

3. Egy P n elemű részbenrendezett halmaz elemein adott egy c súlyozás, keressünk maximális súlyú láncot (:teljesen rendezett részhalmazt.)!

Figyeljük meg, hogy ha C maximális súlyú lánc és p egy eleme, akkor C-ből a p-nél nagyobb elemeket elhagyva olyan láncot kapunk, amely maximális súlyú azon láncok közül, melyek maximális eleme p.

P minden p elemére meghatározzuk a legnagyobb súlyú olyan láncot, melynek maximális eleme p. A maximumot jelölje m(p). Az így adódó n lánc közül a legnagyobb súlyú lesz a keresett.

Jelölje P_{1} a P legkisebb elemeinek halmazát, illetve általában P_{i+1} a P −P_{1} −…−P_{i} legkisebb elemeinek halmazát. Nyilván P_{1} tagjaira m(p) = c(p). Tegyük fel, hogy már meghatároztuk m(p)-t a P_{1} ∪ … ∪ P_{i} elemeire és most p ∈ P_{i+1}. Ekkor nyilván m(v) = c(v) + min m(u), ahol a minimum azon u ∈ P_{i} elemekre megy, melyek a részbenrendezésben kisebbek v-nél.

Két speciális esetet említünk.

3.1 Különböző számokból álló a_{1}, …, a_{m} sorozatból válasszunk ki egy maximális monoton növő részsorozatot.

Definiáljunk egy P részbenrendezést a p_{1}, …, p_{m} elemeken úgy, hogy p_{i} kisebb, mint p_{j}, ha i < j és a_{i} < a_{j}. (Ez nyilván részbenrendezés, hiszen két lánc szorzata.) Akalmazható az előző eljárás az azonosan 1 súlyozás esetére.

3.2 Adott egy G = (A, B; E) páros gráf, ahol A = {a_{1}, …, a_{k}} és B = {b_{1}, …, b_{l}}, keressünk maximális párosítást, amely nem tartalmaz ”keresztező élt”, azaz ha a_{i}b_{j} és a_{i′}b_{j′} a párosításhoz tartozik és i < i′, akkor j < j′.

Definiáljunk az éleken egy részbenrendezést: Az a_{i}b_{j} él megelőzi az a_{i′}b_{j′} élt, ha i < i′ és j < j′. A feladat éppen azt kivánja, hogy ebben a részbenrendezésben keressünk maximális elemszámú láncot.

További érdekes speciális eset a következő. Azt mondjuk, hogy a nem feltétlenül különböző betűkből készített X = {x_{1}, …, x_{k}} sorozatnak a Z = {z_{1}, … z_{j}} sorozat részsorozata, ha léteznek olyan i_{1} < … < i_{j} indexek, melyekre x_{i_{1}} = z_{1}, …, x_{i_{j}} = z_{j}.

3.2.1 Határozzuk meg az X = {x_{1}, …, x_{k}} és Y = {y_{1}, …, u_{l}} sorozatoknak egy maximális közös részsorozatát.

Készítsük el a G = (A, B; E) páros gráf, ahol A = {a_{1}, …, a_{k}}, B = {b_{1}, …, b_{l}} és az a_{i} illetve b_{j} pontokat akkor kössük össze éllel, ha x_{i} = y_{j}. A feladat éppen egy maximális nem-keresztező párosítás megtalálásával ekvivalens, így alkalmazható 3.2.

A következő példa ismét irányított gráfok legrövidebb útjaival foglalkozik.

4. G = (V, E) irányított gráf élein adott egy c nemnegatív súlyozás, határozzuk meg minden s, t pontpárra az s-ből t-be vezető legrövidebb út hosszát.

Elvileg itt nincs nehézség, hiszen n(n − 1) pontpár van és ezek mindegyikére a Dijkstra algoritmus segítségével például meg tudjuk a legrövidebb utat határozni. A következő Floyd és Warshalltól származó algoritmus egyszerre számolja ki a kivánt minimumokat. Jelölje C a költség mátrixot: c_{ij} az v_{i} pontból a v_{j}-be menő él költsége. Az eljárás n fázisból áll. A k-dik fázisban meghatározzuk minden v_{i}, v_{j} pontpárra a v_{i}-ből v_{j}-be menő legkisebb költségű olyan utat, amely belső pontot csak a V_{k} := {v_{1}, …, v_{k}} halmazból használ. Jelölje w_{k}(i, j) ezt a minimumot illetve W_{k} az ezen értékekből alkotott mátrixot. Ekkor W_{1} = C.

Jelölje P a v_{i}-ből v_{j}-be vezető minimális utat, amelynek minden belső pontja V_{k}-hoz tartozik. Amennyiben P nem tartalmazza v_{k}-t, azaz P minden belső pontja V_{k−1}-hez is már hozzá tartozik, akkor w_{k}(v_{i}, v_{j}) = w_{k−1}(v_{i}, v_{j}).

Amennyiben v_{k} rajta van P -n, úgy a P -nek mind a v_{i}-től v_{k}-ig, mind a v_{k}-tól v_{j}-ig terjedő szakasza olyan út, amelynek minden belső pontja már V_{k−1}-ben van. Ezek hossza tehát w_{k−1}(v_{i}, v_{k}) illetve w_{k−1}(v_{k}, v_{j}). Ebből adódik, hogy érvényes a következő rekurzió:

w_{k}(v_{i}, v_{j}) = min(w_{k−1}(v_{i}, v_{j}), w_{k−1}(v_{i}, v_{k}) + w_{k−1}(v_{k}, v_{j})).

Vagyis a W_{k} mátrixot O(n^{2}) lépésben ki tudjuk számítani W_{k−1}-ből.

Végezetül bemutatjuk a dinamikus programozásnak egy eddigieknél bonyolultabb helyzetben történő alkalmazását.

5. Legyen G = (V, E) irányítatlan gráf és T a pontjainak egy részhalmaza, mely pontokat termináloknak nevezünk. Adott még az éleken egy nem-negatív c költség-függvény. Keressünk minimális össz-súlyú összefüggő részgráfot, amely T minden pontját tartalmazza!

Világos, hogy a minimum egy részfán vétetik fel, mely részfát Steiner fának nevezik. A minimális súlyú Steiner fa feladata közös általánosítása a legrövidebb út problémának (amikor T kételemű) és a minimális költségű feszítő fa problémájának (amikor T = V). Bár ez a két szélső eset polinom időben megoldható, R. Karp bebizonyította, hogy a Steiner fa probléma NP-teljes, még azonosan 1 súlyok esetén is.

Dinamikus programozás segítségével azonban megadható olyan algoritmus, amely n-ben (a gráf pontszámában) polinomiális és csak |T |-ben exponenciális. Vagyis ha T kicsi, pontosabban rögzített, akkor ez az algoritmus polinomiális futásidejű. Például, ha T három elemű, akkor minden v pontból meghatározunk mindhárom terminálba egy-egy legrövidebb utat. Amelyik v-re a legkisebb ezen utak össz-hosszúsága, a három út úniója, amint az egyszerűen látható, az optimális Steiner fát adja.

Az általános eset tárgyalásához először is feltesszük, hogy a költség-függvény kielégíti a háromszög egyenlőtlenséget. Ha nem ez a helyzet, akkor minden u, v pontpárra helyettesítjük a költségüket a köztük vezető legkisebb kölségű út költségével. Jelölje s(T′ + v) az olyan Steiner fa minimális költségét, melynek terminál halmaza T′ ∪{v} ahol T′ a T -nek valódi részhalmaza míg v tetszőleges pont (tehát lehet T -n belül is és kívül is). Jelölje s_{b}(T′ + v) az olyan Steiner fa minimális költségét, amelynek terminál halmaza ismét T′ ∪ {v}, de megköveteljük, hogy v a Steiner-fának belső, azaz legalább 2 fokú pontja legyen. (Ha ilyen fa nem létezik, a költséget végtelennek definiáljuk.) T minden T′ részhalmazára és G minden v pontjára ki fogjuk számítani mind az s(T′ + v), mind az s_{b}(T′ + v) értéket. Ezek száma csak T méretétől függ exponenciálisan, |V |-ben polinomiális.

Legyen K a termináloknak egy részhalmaza és tekintsünk egy ezekre vonatkozó F minimális Steiner fát, melynek valamely v pontja a fában legalább 2 fokú. Osszuk tetszőlegesen a v-ből kiinduló fa-éleket két nemüres osztályba. Ez meghatározza a fának is egy olyan két részre osztását, amely részeknek csak v a közös pontjuk. Jelölje F′ és F′′ a két részfát továbbá K′ és K′′ a hozzájuk tartozó terminál halmazt. Világos, hogy F′ (illetve F′′) minimális Steiner fa a K′ + v (K′′ + v) terminál halmazra nézve. Ebből adódik, hogy érvényes a következő rekurzió:

s_{b}(K + v) = min(s(K′ + v) + s(K − K′ + v) : ∅ ⊂ K′ ⊂ K).  (4D.1)

Tekintsünk most egy K + v terminálhalmazhoz tartozó F minimális Steiner fát. Három eset lehetséges.

(i) v az F belső pontja. Ekkor nyilván s(K + v) = s_{b}(K + v).

(ii) v a fának első fokú csúcsa, és az egyetlen fabeli szomszédja, u nincs K-ban. Ekkor a háromszög egyenlőtlenség miatt feltehető, hogy u legalább harmadfokú a fában, azaz v elhagyása után legalább 2 fokú. Ezért ilyenkor s(K + v) = s_{b}(K + u) + c(uv).

(iii) v a fának első fokú csúcsa, és az egyetlen fabeli szomszédja, u a K-ban van. Ekkor s(K + v) = s(K) + c(uv).

Ezen megfigyelésekből adódik a következő rekurzió.

s(K + v) = min(min(s(K) + c(uv) : u ∈ K), min(s_{b}(K + v) + c(uv : u ∉ K).  (4D.2)

Figyeljük meg, hogy mind az (i), mind az (iii) lehetőségeket a belső minimumok közül az elsőnél vettük számításba.

Az algoritmus k-adik fázisában (k = 1, 2, …, |T | − 1) feltesszük, hogy minden v csúcsra és T -nek minden legfeljebb k elemű K részhalmazára már kiszámítottuk s(K + v)-t és s_{b}(K + v)-t. Ekkor (4D.1) segítségével először kiszámítjuk s_{b}(K + v)-t a T -nek minden k + 1 elemű részhalmazára, majd ezek ismeretében (4D.2) segítségével s(K + v)-t is. •

A következő érdekes speciális esetben a fenti algoritmus nem csak n-ben lesz polinomiális, hanem |T |-ben is. Tegyük fel, hogy a gráf síkba-rajzolható és a terminálok mindegyike a végtelen tartomány határán van. Vegyünk egy tetszőleges F Steiner fát. Ha ennek bármely élét kihagyjuk, akkor a fa két komponensre esik. Mármost a döntő megfigyelés az, hogy a két komponens a terminálpontokat egymást követően tartalmazza, azaz nem létezhet négy terminál pont t_{1}, …, t_{4}, melyek ebben a sorrendben következnek a külső ablakon és t_{1}, t_{3} az egyik fa-komponenshez tartozik, míg t_{2}, t_{4} a másikhoz. Valóban, ha indirekt ez volna a helyzet, akkor a két komponensben vegyük az egyértelmű t_{1}-t t_{3}-mal illetve a t_{2}-t t_{4}-gyel összekötő utat. A síkbeliség miatt ezen utaknak szükségképpen van közös pontja ellentmondásban a szóbanforgó két fa-komponens diszjunktságával.

Ezen ”folytonossági” tulajdonságból következik, hogy az egész algoritmus során a T -nek csak olyan K részhalmazaira kell kiszámítani (4D.1) és (4D.2)-t, melyek a külső ablakon folytonosak (azaz K és T − K nem ”keresztezi” egymást.) Ilyen K kevesebb mint |T |^{2} van, tehát (4D.1) és (4D.2) kiszámítása is polinom időben történhet. •

5. ÁRAMOK ÉS FOLYAMOK

A hálózati folyamok elméletében különféle egymással ekvivalens modelleket dolgoztak ki, melyek közül a két legfontosabb a folyamokra (flows) illetve az áramokra (circulations) vonatkozó model.

Jelöljön D = (V, A) egy irányított gráfot. Legyen f : A → R ∪ {−∞} alsó kapacitás, g : A → R ∪ {+∞} felső kapacitás úgy, hogy f ≤ g. Valamely x : A → R vektorra és S ⊆ V részhalmazra legyen ϱ_{x}(S) := ∑(x(uv) : uv ∈ A, uv belép S-be) és legyen δ_{x}(S) := ϱ_{x}(V −S). Az x vektort áramnak nevezzük, ha teljesül a megmaradási szabály, azaz ϱ_{x}(v) = δ_{x}(v) fennáll minden v csúcsra.

Gyakorlat Igazoljuk, hogy x áram esetén ϱ_{x}(X) = δ_{x}(X) minden X ⊆ V részhalmazra is fennáll.

Feladat Igazoljuk, hogy a tenziók is és az áramok is alteret alkotnak R^{A}-ban, melyek egymás ortogonális kiegészítő alterei.

Az x áramot megengedettnek (feasible) mondjuk, ha f ≤ x ≤ g.

5.1 TÉTEL [A. Hoffman, 1960] Akkor és csak akkor létezik megengedett áram, ha

ϱ_{f}(X) ≤ δ_{g}(X) minden X ⊆ V halmazra.  (5.1)

Továbbá, ha f és g egészértékűek és (5.1) fennáll, akkor létezik egészértékű megengedett áram is.

Biz. A szükségesség igazolásához legyen x megengedett áram. Ekkor δ_{g}(X) − ϱ_{f}(X) ≥ δ_{x}(X) − ϱ_{x}(X) = 0, amiből (5.1) következik.

Az elegendőség bizonyításához tekintsük a következő függvényt. γ(X) := δ_{g}(X)−ϱ_{f}(X). Most (5.1) azzal ekvivalens, hogy γ nem-negatív. X, Y ⊆ V halmazokra d_{x}(X, Y) jelölje az x(e) értékek összegét mindazon e élekre, melyek X − Y és Y − X egy-egy pontját kötik össze (mindegy melyik irányban).

5.2 LEMMA γ(X) + γ(Y) = γ(X ∩ Y) + γ(X ∪ Y) + d_{g−f}(X, Y).

Biz. Csupán azt kell ellenőrizni, hogy minden lehetséges él hozzájárulása a két oldalhoz ugyanannyi. •

A tétel bizonyításához visszatérve válasszunk egy olyan ellenpéldát, amelyben azon a élek q száma, melyekre f(a) < g(a), a lehető legkisebb. Ez a szám pozitív, mert különben x := f(= g), (5.1) miatt, megengedett áram. Legyen a = st olyan él, amelyre f(a) < g(a).

Növeljük f(a)-t amennyire csak lehetséges (5.1) megsértése nélkül. q minimalitása miatt még a megnövelt f(a) érték is kisebb, mint g(a). Létezik továbbá egy T ts̄-halmaz (azaz t-t tartalmazó, de s-et nem), amelyre ϱ_{f}(T) = δ_{g}(T), vagyis γ(T) = 0.

Hasonlóképp, csökkentsük g(a)-t amennyire csak lehetséges (5.1) megsértése nélkül. Ismét, a csökkentett g(a) érték is még nagyobb mint (az előbb megnövelt) f(a), és létezik egy S st̄-halmaz, amelyre γ(S) = 0.

Az a él létezése folytán tudjuk, hogy a d_{f−g}(S, T) érték szigorúan pozitív. Az 5.2 Lemmát és (5.1)-t alkalmazva kapjuk, hogy 0 + 0 = γ(S) + γ(T) > γ(S ∩ T) + γ(S ∪ T) ≥ 0 + 0, amely ellentmondás mutatja, hogy nem létezhet ellenpélda, és így a tétel első része következik.

Ugyanez a bizonyítás azt is mutatja, hogy ha f és g egészértékű, akkor van egészértékű megengedett áram is. • •

Legyen s és t a D digráfnak két kijelölt csúcsa, s-t hívjuk forrásnak, t-t pedig nyelőnek. Feltesszük, hogy s-be nem lép be él és t-ből nem lép ki él. Legyen g → R_{+} mindenütt pozitív kapacitás függvény. Egy x : A → R_{+} vektort s-ből t-be menő folyamnak nevezünk, vagy röviden st-folyamnak, ha ϱ_{x}(v) = δ_{x}(v) fennáll minden v ∈ V − {s, t} csúcsra. Az x folyamot megengedettnek mondjuk, ha 0 ≤ x ≤ g.

Könnyen látható (hogyan?), hogy adott x folyam esetén minden S st̄-halmazra az δ_{x}(S) − ϱ_{x}(S) értékkel definiált nettó kiáramlás független S választásától. Ezt a közös, δ_{x}(s)-sel egyenlő értéket nevezzük a folyam nagyságának.

Az x(uv) szám a folyam értéke az uv ∈ A élen. Az x folyamot út-folyamnak (kör-folyamnak) nevezzük, ha x csak egy s-ből t-be vezető út (irányított kör) mentén pozitív.

Gyakorlat Igazoljuk, hogy minden nem-negatív folyam kör- és út-folyamok nem-negatív kombinációja.

Alapvető az alábbi, L.R. Fordtól és D.R. Fulkersontól származó Maximális-Folyam Minimális-Vágás tétel (Max Flow Min Cut; MFMC).

5.3 TÉTEL Az st folyamok maximális nagysága egyenlő a δ_{g}(S) értékek minimumával, ahol a minimum az összes st̄-halmazra megy. Ha g egészértékű, úgy a maximum egészértékű folyamon is felvétetik.

Biz. Legyen x megengedett st-folyam és S st̄-halmaz. Ekkor δ_{x}(s) = δ_{x}(S) − ϱ_{x}(S) ≤ δ_{g}(S), amiből max ≤ min következik.

A fordított irány igazolásához jelölje m_{g} a szóbanforgó minimum értékét. (Ez a minimum nyilvánvalóan létezik, merthogy véges sok szám minimumáról van szó. Az viszont még ezen a ponton nem világos, hogy létezik maximális nagyságú folyam.) Adjunk D-hez egy új e = ts élt és definiáljuk f(e) = m_{g}, g(e) := {∞}. Az eredeti éleken legyen f mindenhol nulla.

Könnyen látszik, hogy most (5.1) fennáll, és így az 5.1 Tétel szerint létezik megengedett áram (amely ráadásul egészértékű, ha g az). Kihagyva a hozzávett e élt, m_{g} nagyságú folyamot kapunk. •

A fenti bizonyítás előnye, hogy nem csupán egész vagy racionális kapacitásokra működik. Hátránya viszont, hogy nem konstruktív.

Nemcsak a folyam feladat vezethető vissza megengedett áramokra, hanem megfordítva is. Magyarán, a Hoffman tétel is levezethető az MFMC tételből. Ennek érdekében minden v ∈ V csúcsra legyen λ(v) := ϱ_{f}(v) − δ_{f}(v). (Az itt következő levezetésben feltesszük, hogy f, g végesértékű: kis gyakorló feladat az általános eset kezelése.) Ha λ mindenhol nulla, akkor f megengedett áram, és készen vagyunk.

Ha λ nem azonosan nulla, akkor az S = (v : λ(v) > 0) és T = (v : λ(v) < 0) halmazok nem-üresek. Készítsük el a D′ = (V′, A′) digráfot úgy, hogy V′ = V ∪ {s, t} és A′ = A ∪ (s, v) : v ∈ S ∪ ((v, t) : v ∈ T). Definiáljuk a g′ kapacitás függvényt a következőképpen. g′(sv) := λ(v) ha v ∈ S, g′(vt) := −λ(v) ha v ∈ T és g′(a) := g(a) − f(a) ha a ∈ A. Legyen M = ∑(λ(v) : v ∈ S). A következő lemma a kapcsolatot írja le egyrészt D megengedett áramai és D′ megengedett st folyamai között, másrészt D′ M-nél kisebb vágásai és D (5.1)-et megsértő halmazai között.

LEMMA (a) Ha x M-nagyságú megengedett st-folyam D′-ben (a g′ kapacitásra vonatkozóan), akkor f + x (az eredeti A-ra megszorítva) megengedett áram.

(b) Ha δ_{g′}(X + s) < M valamely X ⊆ V halmazra, akkor X megsérti a Hoffman féle (5.1) feltételt. •

Biz. (a) A megengedettség, azaz f ≤ f +x ≤ g, következik a konstrukcióból. A megmaradási szabály nyilván fennáll V − (S ∪ T) pontjaiban. Mivel x nagysága M, minden s-ből kilépő él telített. Így S-nek bármely v pontjára az eredeti gráfban érvényes, hogy x(sv) + ϱ_{x}(v) = δ_{x}(v), azaz ϱ_{f}(v) − δ_{f}(v) + ϱ_{x}(v) = δ_{x}(v), és így ϱ_{f+x}(v) = δ_{f+x}(v), vagyis a megmaradási szabály érvényes S pontjaiban is. A bizonyítás T pontjaira analóg módon végezhető el.

(b) ϱ_{f}(S) − δ_{f}(S) = M > δ_{g′}(X + s) = δ_{g−f}(X) + λ(S − X) − λ(T ∩ X), amiből kapjuk, hogy 0 > δ_{g−f}(X)−λ(S ∩X)−λ(T ∩X) = δ_{g−f}(X)−λ(X) = δ_{g−f}(X)+δ_{f}(X)−ϱ_{f}(X), vagyis vagyis δ_{g}(X) < ϱ_{f}(X). •

Feladat Vezessük le Hoffman tételét az MFMC tételből, ha f-nek lehetnek {−∞}, g-nek pedig {+∞} komponensei.

A fenti redukció azt is mutatja, hogy a maximális folyam meghatározására szolgáló algoritmus segítségével el lehet dönteni, hogy teljesül-e (5.1), és ha igen, akkor tudunk találni megengedett áramot.

A NÖVELŐ UTAK MÓDSZERE

A fenti bizonyítás első feléből kiolvasható, hogy x akkor és csak akkor maximális nagyságú folyam, ha teljesülnek az alábbi optimalitási feltételek.

(a) x(a) = g(a) minden a élre, amely kilép S-ből, és

(b) x(a) = 0 minden a élre, amely belép S-be.

A Ford és Fulkersontól származó algoritmus tetszőleges x megengedett st-folyamból indul ki (például x ≡ 0), és azt iteratívan javítja. Készítsünk el egy D_{x} = (V, A_{x}) digráfot a következőképp. Egy uv él A_{x}-hez tartozik, ha vagy (i) uv ∈ A és x(uv) < g(uv), és ekkor ezen élét D_{x}-nek előre élnek hívjuk, vagy (ii) vu ∈ A és x(vu) > 0, és ekkor uv vissza él. Jelölje S az s-ből D_{x}-ben elérhető pontok halmazát.

1. ESET t ∉ S, azaz t nem érhető el s-ből. Mivel D_{x} semelyik éle sem lép ki S-ből, az (a) és (b) optimalitási feltételek teljesülnek és az algoritmus végetér: az adott x folyam nagysága egyenlő δ_{g}(S)-sel.

2. ESET t ∈ S, azaz t elérhető. Legyen P tetszőleges s-ből t-be vezető út D_{x}-ben.

Legyen Δ_{1} := min(g(uv) − x(uv) : uv előre éle P -nek) és Δ_{2} = min(x(v, u) : uv vissza éle P -nek). Legyen Δ = min(Δ_{1}, Δ_{2}). Ekkor Δ pozitív. Nevezzük P egy élét kritikusnak, ha Δ ezen az élen éretik el.

Módosítsuk x-t a következőképp. Ha uv előre éle P -nek, növeljük x(uv)-t Δ-val. Ha uv vissza éle P - nek, csökkentsük x(vu)-t Δ-val. Könnyen látható, hogy a módosított x′ megengedett folyam lesz, amelynek nagysága Δ-val nagyobb mint x-é. Következésképp, ha g egészértékű, akkor a 2. eset csak véges sokszor fordulhat elő. Ebben az esetben tehát új bizonyítást kaptunk az MFMC tételre. •

Amennyiben g racionális, a nevezők legkisebb közös többszörösével a kapacitásokat végigszorozva visszajutunk az egész kapacitású esethez. Ha viszont g irracionális, akkor a fenti eljárás nem biztosan ér véget véges sok lépésben. Másik hátrány, hogy még egész kapacitások esetén is az iterációk száma arányos lehet a legnagyobb előforduló kapacitás nagyságával. Így az algoritmus bonyolultsága az input méretének exponenciális függvényével arányos, azaz nem polinomiális. (Egy szám nagysága a jegyei számának exponenciális függvénye.)

SKÁLÁZÁSI TECHNIKA

Az alábbi technika olyan általános eszköz, amelynek segítségével bizonyos eljárásokat polinomiális futásidejűvé lehet tenni. Használatát a maximális folyam problémán szemléltetjük, mert ott igen egyszerű.

Tételezzük fel, hogy a kapacitások egész számok és kettes számrendszerben vannak megadva. A legnagyobb kapacitás álljon M jegyből. Összesen M folyam problémát fogunk megoldani. Jelölje g_{i} azt a kapcitás függvényt, amely úgy áll elő, hogy minden élen az eredeti kapacitásnak (balról) az első i jegyét tekintjük. Tegyük fel, hogy a g_{i} kapacitás függvényre nézve már meghatároztuk az x_{i} maximális folyamot. Ekkor 2x_{i} megengedett folyam a g_{i+1}-re nézve. A 2x_{i}-ből kiindulva alkalmazzuk a fent leírt növelő út módszert a g_{i+1} kapacitás függvényre vonatkozólag.

Miután minden e élre g_{i+1}(e) értéke vagy 2g_{i}(e) vagy 2g_{i}(e) + 1, legfeljebb élszámnyi növelés után megkapjuk az x_{i+1} maximális folyamot. Összesen tehát legfeljebb M|A| növelés segítségével megkonstruáltunk egy eredeti kapacitásokra vonatkozó maximális folyamot.

LEGRÖVIDEBB NÖVELŐ UTAK

A fenti eljárás hátránya, hogy csak egész (és így racionális) kapacitásokra működik. Vagyis általános kapacitások esetén még mindig nincs konstruktív bizonyításunk az MFMC tételre. Ezen nehézség leküzdésére J. Edmonds and R. Karp [1972] és E.A. Dinitz [1970] javasolták, hogy minden iterációban a legkisebb élszámú növelő utat válasszuk. Ez az egyszerű megszorítás lehetővé teszi, hogy a Ford-Fulkerson algoritmus bonyolultságát |V | és |A| polinomjával korlátozzuk, függetlenül a kapacitások nagyságától. (Ezt persze úgy értve, hogy a számokkal végzett alapműveleteket egyetlen lépésnek tekintjük.)

Jelölje σ_{x}(v) a v távolságát D_{x}-ben s-től. (Ha nincs egyáltalán s-ből v-be út, akkor σ_{x}(v) = ∞). Legyen P egy legrövidebb út D_{x}-ben s-ből t-be. Ekkor P mindegyik uv élére, σ_{x}(v) = σ_{x}(u) + 1.

LEMMA Amikor P mentén végrehajtunk egy növelést, a σ_{x}(v) érték semmilyen v-re sem csökken.

Biz. Nézzük meg milyen hatással van a növelés a D_{x} segédgráfra. Mivel a folyamot D-nek csak olyan élein változtattuk, melyek P éleinek felelnek meg, D_{x} csupán P éleinél változhat. Éspedig, D′_{x} lehetséges új élei P élei megfordítva, ugyanakkor P kritikus élei (ahol Δ felvétetik) eltűnnek D_{x}-ből. A v pont s-től való távolsága csak akkor csökkenhetne, ha olyan uw éleket adnánk a segédgráfhoz, melyekre σ_{x}(w) > σ_{x}(u) + 1, amiből a lemma következik. •

A növelések sorozatát fázisokra bontjuk. Egy fázis során σ_{x}(t) ugyanaz marad. A Lemma szerint legfeljebb |V | − 1 fázis lehetséges.

LEMMA Egy fázison belül legfeljebb |A| növelésre kerülhet sor.

Biz. Jelölje σ_{i}(v) a v pont távolságát s-től az i fázis kezdetén az aktuális segédgráfban. Nevezzünk egy uv élt i-szorosnak, ha σ_{i}(v) = σ_{i}(u) + 1. Az i-dik fázis során csupán i-szoros éleket használunk. Tudjuk, hogy egy növelés legalább egy i-szoros élt eltüntet az aktuális segédgráfból és nem hoz be új i-szoros élt. Mivel a segédgráfnak legfeljebb |A| darab i-szoros éle van, a lemma következik. •

Mindezeket összetéve kapjuk, hogy legfeljebb |V ||A| növelésre van szükségünk. Egyetlen növelés O(|A|) lépést igényel, így az algoritmus össz-bonyolultsága O(|V ||A|^{2}).

Miután a fenti algoritmusban választási lehetőségünk lehet a legrövidebb növelő út meghatározásában, a végül kapott maximális folyam függhet ezen választásoktól. Nem így a végső S!

Feladat (a) A végül kapott minimális δ^{+}(S) vágás független az algoritmus futásától. (b) Ha X és Y minimalizálja az δ_{g}(Z) értéket az összes st̄-halmazra, akkor X ∩ Y és X ∪ Y is minimalizáló st̄-halmazok.

(c) A minimalizáló halmazok metszete S.

Feladat Adott e élre hogyan lehet eldönteni, hogy (a) létezik-e olyan maximális folyam, amely telíti e-t, (b) minden maximális folyam telíti e-t.

Feladat Algoritmikusan határozzuk meg az összes {x, y} rendezett csúcspárt, amelyre létezik olyan X halmaz, hogy s, x ∈ X, y ∈ V − X és X minimális vágást határoz meg.

6. GOMORY-HU FÁK

Alkalmazásokban két pontot elválasztó minimális vágás kiszámítása gyakran még fontosabb, mint a maximális nagyságú folyam meghatározása. Néha szükségünk van az összes pontpárra meghatározni egy őket elválasztó minimális vágást. Irányítatlan gráfokban egy ilyen vágás rendszer nagyon szép struktúrával rendelkezik.

Legyen G = (V, E) n pontú irányítatlan gráf és g → R_{+} nem-negatív kapacitás függvény. Jelölje λ(u, v) az u és v közötti maximális folyam nagyságát (azaz az u és v-t elválasztó minimális vágás értékét.) Azt mondjuk, hogy az u és v pontokat a Z pont-halmaz szeparálja, ha pontosan az egyiküket tartalmazza. Z-t uvminimálisnak mondjuk, ha d_{g}(Z) minimális az u és v-t elválasztó halmazok között, azaz, d_{g}(Z) = λ(u, v).

Az X halmazt kritikusnak mondjuk, ha X uv-minimális valamely {u, v} pontpárra. Fő célunk kritikus halmazoknak egy olyan, lehetőség szerint minél kevesebb tagból álló rendszerét meghatározni, amely minden u, v pontpárra tartalmaz elválasztó uv-minimális halmazt. Kiderül majd, hogy mindig létezik n − 1 tagból álló ilyen rendszer, amely ráadásul keresztezés-mentes, azaz egy fa segítségével jól le lehet írni.

Legyen G_{T} = (V, F) tetszőleges fa a V ponthalmazon (nem feltétlenül a G részgráfja.) F minden e élére legyen m(e) := d_{g}(X_{e}), ahol X_{e} és V − X_{e} a G_{T} − e két komponensét jelöli. Azt mondjuk, hogy G_{T} a G-nek Gomory-Hu fája (a megadott kapacitás függvényre vonatkozóan), ha (a) minden {s, t} pont párra λ(s, t) egyenlő az m értékek minimumával, ahol a minimum az s és t-t G_{T} -ben összekötő út éleire megy és (b) amennyiben e egy olyan él, amelyen a minimum eléretik, akkor X_{e} st-minimális.

Például, ha G = K_{3,3} és g ≡ 1, akkor bármely ötélű csillag Gomory-Hu fát alkot, és ilyenkor könnyen ellenőrizhetően nincs is más Gomory-Hu fa (jelezve egyúttal, hogy a Gomory-Hu fa nem feltétlenül választható a G gráf részgráfjának.)

6.1 TÉTEL [Gomory és Hu, 1961] Minden gráfnak van Gomory-Hu fája.

Biz. Csak a g ≡ 1 esetet tekintjük, az általános eset ugyanígy megy. Pontok részhalmazainak egy F családját laminárisnak nevezzük, ha F bármely két tagja vagy diszjunkt vagy az egyik tartalmazza a másikat. Azt mondjuk, hogy F szeparálja az u és v pontokat, ha F-nek legalább az egyik tagja szeparálja u-t és v-t.

Legyen F lamináris család, amely nem szeparálja az {u, v} pontpárt. Azt mondjuk, hogy az u és v-t szeparáló X halmaz uv-minimális az F-re nézve, ha F∪{X} lamináris és d(X) a lehető legkisebb. Ilyen X-t könnyen kiszámíthatunk az MFMC algoritmus segítségével a következőképpen. Feltehetjük, hogy az alaphalmaz V F-hez tartozik. Legyen Z az F legszűkebb olyan tagja, amely tartalmazza u és v-t. A Z komplementerét húzzuk össze egy ponttá, majd F-nek Z-ben fekvő maximális olyan tagjait is, melyek nem tartalmazzák u és v-t. A keletkező gráfban egy X halmaz pontosan akkor minimális uv-szeparáló, ha az eredeti G-ben F-re nézve minimális uv-szeparáló.

Konstruáljunk most meg egy F lamináris családot a következőképpen. Kezdetben legyen F_{0} üres és tegyük fel, hogy már megkonstruáltunk valamilyen k ≥ 1-ra egy lamináris F_{k−1} = {A_{1}, …, A_{k−1}} családot. Legyen {u_{k}, v_{k}} olyan pontpár, amelyet F_{k−1} nem szeparál. Határozzuk meg az A_{k} halmazt, amely u_{k}v_{k}- minimális az F_{k−1}-re nézve és legyen F_{k} := F_{k−1} ∪ {A_{k}}. Az eljárás akkor ér véget, amikor az aktuális F := F_{k} már minden pontpárt elválaszt.

1. LEMMA F n − 1 tagból áll, azaz k = n − 1, és az E_{1} := {u_{i}v_{i} : i = 1, …, k} élhalmaz nem tartalmaz kört, azaz T_{1} := (V, E_{1}) feszítő fa.

Biz. Indukcióval könnyen ellenőrizhető, hogy tetszőleges olyan lamináris halmazrendszernek, amely minden pontpárt elválaszt, legalább n−1 tagja van. Így az egész lemma következik, ha belátjuk, hogy E_{1} körmentes, hiszen akkor k ≤ n − 1, vagyis k = n − 1.

Ha az E_{1} konstruálása folyamán valamelyik e_{j} hozzávétele kört hozna létre, akkor ezen kör egyéb, azaz korábban bevett e_{i} éleit elválasztó A_{i} halmazok egyike szükségképpen e_{j}-t is elválasztaná, ellentétben e_{j} választásával. •

Hangsúlyozzuk, hogy a T_{1} := (V, E_{1}) fa csupán egy segédfa, amely a bizonyításhoz kell. Legyen A_{0} := V és F′ := F ∪ {V }.

2. LEMMA F′ minden A_{i} tagjának pontosan egy olyan t_{i}-vel jelölt eleme van, amely nincs benne A_{i}-ben fekvő A_{j}-ben.

Biz. Nyilván két ilyen elem nem létezhet, mert akkor azokat F nem választaná el. Ha viszont egy sem létezne, azaz A_{i} a benne fekvő A_{j} halmazok partíciója volna, akkor ezen halmazok közül a legnagyobb indexű jogtalanul került az F-be, mert nem választ el olyan pontpárt, amelyet a többiek nem választanak el. •

Most már definiálni tudunk egy Gomory-Hu fát: Mindegyik A_{i}-re, i = 1, …, n − 1 tekintsük az A_{i}-t magában foglaló legszűkebb A_{j} ∈ F′ halmazt és vegyük a fához a f_{i} := t_{j}t_{i} élt. Így egy n − 1 élű F fát kapunk (amit például úgy lehet jól látni, hogy az f_{i} éleket egy pillanatra t_{i} felé irányítottnak tekintjük, amikoris egy kivétellel minden pontba egy él megy be és nincs irányított kör, mert semelyik A_{i} halmazból nem vezet ki f_{j} él.) Célunk annak igazolása, hogy F valóban Gomory-Hu fa.

3. LEMMA Legyen az X halmaz xx′-minimális, az Y halmaz pedig kritikus. Ha Y nem tartalmazza x és x′-t, akkor X − Y vagy X ∪ Y xx′-minimális. Ha Y tartalmazza x és x′-t, akkor X ∩ Y vagy Y − X xx′-minimális.

Biz. Először tegyük fel, hogy Y yy′-minimális. Ekkor vagy Y −X vagy Y ∩X elválasztja {y, y′}−t. Az első esetben λ(x, x′)+λ(y, y′) = d(X)+d(Y) ≥ d(X−Y)+d(Y −X) ≥ λ(x, x′)+λ(y, y′). Így mindenütt egyenlőség áll, tehát X −Y xx′-minimális. A második esetben λ(x, x′)+λ(y, y′) = d(X)+d(Y) ≥ d(X ∪Y)+d(X ∩Y) ≥ λ(x, x′) + λ(y, y′). Ismét egyenlőség van mindenütt és így X ∪ Y xx′-minimális, ami a lemma első részét bizonyítja. A második rész következik az elsőből, ha Y -t a komplementerével helyettesítjük. •

4. LEMMA A_{i} ∈ F u_{i}v_{i}-minimális minden i = 1, …, n − 1-re.

Biz. i = 1-re az állítás nyilván igaz. Tegyük fel, hogy már beláttuk 1, 2, …, i−1-re és most x := u_{i}, x′ := v_{i}. Indukcióval belátjuk j = 0, 1, …, i − 1-re, hogy (∗) létezik olyan X xx′-minimális halmaz, amelyre F_{j} ∪ {X} lamináris. Ebből már a lemma következik.

A (∗) állítás igaz, ha j = 0, és tegyük fel, hogy már beláttuk valamilyen 0 ≤ j < i−1-re. Alkalmazzuk a 3. lemmát X és Y := A_{j}-re. Kapjuk, hogy létezik egy X′ xx′-minimális halmaz, amelyre F_{j} ∪ {X′} lamináris. •

5. LEMMA Minden {s, t} pontpárra létezik F-nek st-minimális tagja.

Biz. Legyen P a T_{1} segédfában az s és t pontokat összekötő egyértelmű út és legyen μ := min(λ(u_{i}, v_{i}): u_{i}v_{i} a P -nek éle). Ezek szerint P egyik élét sem választja el μ-nél kisebb értékű vágás, és így az s, t pontpárt sem, vagyis λ(s, t) ≥ μ.

Legyen j a legkisebb index, amelyre u_{j}v_{j} a P -nek éle és λ(u_{j}, v_{j}) = μ. Azt állítjuk, hogy A_{j} nem választja el P -nek semelyik más élét sem. Valóban, ha A_{j} elválasztaná P -nek az u_{i}v_{i} élét, akkor az F konstrukciója szerint i < j. Másrészt μ ≤ λ(u_{i}, v_{i}) ≤ d(A_{j}) = μ és innen λ(u_{i}, v_{i}) = μ, ellentmondásban j minimális választásával.

Azt kaptuk, hogy A_{j}-nek el kell választania az {s, t} pontpárt és ebből μ ≥ λ(u_{j}, v_{j}) = d(A_{j}) ≥ λ(s, t) ≥ μ. Így végig egyenlőség áll, azaz A_{j} st-minimális halmaz. •

Az F fa konstrukciójából és az 5. lemmából közvetlenül adódik hogy F Gomory-Hu fa. • •

Párosítások elméletében érdekes szerepet játszanak a T -vágások. Legyen G = (V, E) irányítatlan gráf és T a G pontjainak egy páros elemszámú részhalmaza. Egy vágást akkor nevezünk T-vágásnak, ha T -t páratlan-páratlan részre osztja. Keressünk minimális elemszámú T -vágást! Például, ha T a páratlan fokú pontokból áll, akkor a T -vágás éppen a páratlan elemszámú vágással ekvivalens. (Miért?) Vagy ha T két elemből áll, akkor a T -vágás a két elemet elválasztó vágásnak felel meg.

6.2 TÉTEL [Padberg és Rao, 1982] Legyen F a G-nek Gomory-Hu fája. Ekkor egy minimális T -vágást úgy kaphatunk meg, hogy F -nek kiválasztunk egy olyan e élét, amelynek elhagyásával keletkező két komponens mindegyike T -t páratlan sok elemben metszi és m(e) a lehető legkisebb.

Biz. Legyen C = [X, V − X] minimális T -vágás és J az F azon e éleinek halmaza, amelyekre az F − e által meghatározott C_{e} vágás T -vágás. Könnyen belátható, hogy d_{J}(v) akkor és csak akkor páratlan, ha v ∈ T. Mivel |X ∩ T | páratlan, egyszerű paritási megfontolás mutatja, hogy d_{J}(X) páratlan, és ezért létezik egy e = uv ∈ J él, amely X és V − X között megy. Emiatt λ(u, v) ≤ d(C). Ekkor λ(u, v) = d(C_{e}) a Gomory-Hu fa definíciója miatt. Azt kaptuk, hogy |C| ≥ λ(u, v) = m(u, v) = |C_{e}| ≥ |C|, és ezért C_{e} is minimális T -vágás. •

Feladat Igazoljuk, hogy hurokmentes gráfban van két pont, melyekre λ(x, y) = d(x).

Feladat Legyen F a V alaphalmaz részhalmazainak egy olyan rendszere, amelyre igaz, hogy ha két diszjunkt halmaz nincs F-ben, úgy az úniójuk sincs, továbbá ha egy halmaz benne van F-ben, úgy a komplementere is benne van. (Például , ha |V | osztható valamely k számmal, úgy a k-val nem osztható elemszámú részhalmazok rendszere ilyen.) A 6.2 tétel általánosításaként mutassuk meg, hogy a Gomory-Hu fa segítségével hogyan lehet egy minimális olyan vágást kiszámítani, amelynek a két oldala F-ben van.

7. MINIMÁLIS KÖLTSÉGŰ FOLYAMOK

Legyen adva D = (V, A) irányított gráf az s forrás- és a t nyelőponttal. Adott még az éleken a g nemnegatív kapacitás függvény és a c nemnegatív költségfüggvény. Feltesszük, hogy g és c is egészértékű. Korábban már láttuk, hogy miként lehet egy maximális M nagyságú s-ből t-be vezető folyamot polinom időben kiszámítani.

Most minden 0 és M közé eső k egészre szeretnénk találni egy olyan k nagyságú folyamot, melynek költsége minimális. Egy z folyam költségét a cz = ∑(c(e)z(e) : e ∈ A) skaláris szorzattal definiáljuk. Azt mondjuk, hogy a z st-folyam minimális költségű folyam, ha z a legkisebb költségű a megengedett, val(z) nagyságú st-folyamok közül.

Az alábbiakban ismertetjük Ford és Fulkerson [1962] algoritmusát. Legyen π : V → Z_{+} olyan függvény a V -n, amelyre π(s) = 0 ≤ π(v) ≤ π(t) minden v ∈ V -re. Ilyen függvényt potenciálnak hívunk. Használni fogjuk a következő jelölést. c̄(uv) = c(uv) − π(v) + π(u), ahol uv ∈ A. Potenciálok segítségével egy z folyam cz költségére az alábbi alsó korlátot nyerhetjük.

∑ c(uv)z(uv) = ∑(π(v) − π(u))z(uv) + ∑ c̄(uv)z(uv) = π(t)k + ∑(c̄(uv)z(uv) : c̄(uv) < 0) + ∑ c̄(uv)z(uv) : c̄(uv) > 0) ≥ π(t)k + ∑ c̄(uv)g(uv) + 0.

Ebből következik, hogy egy z folyam bizonyosan minimális költségű, amennyiben létezik olyan π potenciál, amelyre az egyenlőtlenség egyenlőséggel teljesül. Ez pontosan akkor van így, ha fennáll a következő két optimalitási feltétel.

π(v) − π(u) < c(uv) ⇒ z(uv) = 0,  (i)

π(v) − π(u) > c(uv) ⇒ z(uv) = g(uv).  (ii)

Ford és Fulkerson módszere a maximális folyam kiszámítására vonatkozó Ford-Fulkerson algoritmus finomításának tekinthető. Minden lehetséges egész k értékre megkonstruálunk egy minimális költségű k nagyságú folyamot. Az eljárás az azonosan nulla folyammal és az azonosan nulla potenciállal indul. Ezután a folyam nagyságát növeljük egyenként, illetve menetközben néha a potenciált növeljük úgy, hogy az optimalitási feltételek végig fennállnak. Az algoritmus akkor ér véget, amikor maximális nagyságú folyamot illetve egy minimális vágást kaptunk.

ITERATÍV LÉPÉS Az általános helyzetben adott a z folyam és a π potenciál, és ezek kielégítik az (i) és (ii) feltételeket. Megkonstruálunk egy D′ = (V, A′) segédgráfot a következőképpen. D′-nek kétféle éle van: előre és vissza. Egy uv él előre él, ha uv ∈ A, c̄(uv) = 0 és z(uv) < g(uv). Egy uv él hátra él, ha vu ∈ A, c̄(vu) = 0 és z(vu) > 0.

Legyen S az s-ből D′-ben irányított úton elérhető pontok halmaza. Két eset lehet.

1. ESET. t ∉ S, azaz t elérhető s-ből.

Legyen ε_{1} = min(c̄(uv) : uv ∈ δ^{+}(S), z(uv) < g(uv)) és ε_{2} = min(−c̄(uv) : uv ∈ δ^{+}(V − S), z(uv) > 0), ahol az üres halmazon vett minimumot ∞-nek definiáljuk. Legyen ε = min(ε_{1}, ε_{2}). Az optimalitási feltételek és az S definiciója miatt ε pozitiv.

Amennyiben ε = ∞, akkor az algoritmus végetér. Ebben az esetben az S-ből kilépő eredeti élek mind telítettek, míg az S-be belépő eredeti élek mindegyikén a folyam nulla. Így tehát δ_{g}^{+}(S) = val(z), az aktuális z folyam maximális nagyságú és az S-ből kilépő élek halmaza minimális vágást határoz meg.

Legyen most ε < ∞, és módosítsuk π-t úgy, hogy minden v ∈ V − S-re növeljük π(v)-t ε-nal. Az S és az ε definíciójából rögtön kapjuk:

ÁLLÍTÁS A módosított potenciál és a változatlanul hagyott z folyam kielégíti az optimalitási feltételeket.

Készítsük el az új segédgráfot és ismételjük meg az eljárást. Figyeljük meg, hogy a segédgráfban a régi S által feszített élek változatlanok maradnak és ezért az s-ből elért pontok halmaza szigorúan bővebb lesz, mint S. Ezért az 1. eset legfeljebb |V | − 1-szeri előfordulása után biztosan vagy az ε = ∞ következik be, vagypedig az alábbi 2. eset.

2. ESET t ∈ S, vagyis t elérhető s-ből. Legyen P a D′-ben egy s-ből t-be vezető irányított út. Módosítsuk z-t a következőképpen. Legyen z′(uv) = z(uv) + 1, ha uv a P -nek előre éle és legyen z′(uv) = z(uv) − 1, vu a P -nek hátra éle.

A módosításból adódik:

ÁLLÍTÁS A módosított folyam és változatlanul hagyott potenciál kielégíti az optimalitási feltételeket.

Ezzel az algoritmus leírását be is fejeztük. Mi mondható az eljárás futásidejéről? Lényegében M növelésre van szükségünk (2. eset), így az eljárás polinomimális, amennyiben mind az M minimális költségű folyamot meg kell határoznunk.

Elképzelhető persze olyan helyzet is, amikor például csak egy maximális nagyságú minimális költségű folyamot kell kiszámítanunk. Ebben az esetben az algoritmus természetesen nem biztosan polinomiális, hiszen lépésszáma az M nagyságával arányos. De még ebben az esetben is két fontos speciális eset kezelhető.

Ha a legnagyobb kapacitás nem túlságosan nagy (nevezetesen, ha |V | polinomjával korlátozható), akkor a fenti eljárás nyilván polinomiális, függetlenül attól, hogy a c költség-függvény egészértékű-e vagy sem.

Tegyük most fel, hogy a kapacitások tetszőlegesek, a költség-függvény egészértékű és ”kicsi”. Ekkor az algoritmus következő módosítása erősen polinomiális algoritmust eredményez. Tekintsük az algoritmus egy közbenső helyzetét, amikor egy π potenciál rendelkezésre áll. A szoros élek digráfjában (egy uv él szoros, ha c̄(uv) = 0) számítsunk ki (a Max-flow Min-cut algoritmusssal) egy maximális nagyságú z folyamot és egy S minimális ki-kapacitású st̄-halmazt. Ha D-ben minden S-be belépő és S-ből kilépő él szoros, akkor S minimális vágást határoz meg és az aktuális z folyam maximális nagyságú, amely kielégíti az optimalitási feltételeket. Ebben az esetben az algoritmus véget ér.

Amennyiben D-nek létezik nem-szoros éle, amely S-be be- vagy kilép, akkor ε, ahogy azt fentebb az 1. esetnél kiszámítottuk, véges lesz. Módosítsuk π-t úgy, mint az előbb, azaz minden v ∈ V − S-re növeljük π(v)-t ε-nal.

Azt állítjuk, hogy a π(t) érték a D digráf valamely (irányítatlan értelemben vett) s-ből t-be vezető útjának a költsége. Valóban, minden folyam-növeléskor a segédgráfban van olyan st út, amely szoros élekből áll.

Következik, hogy a különböző π(t) értékek száma (vagyis az 1. eset előfordulásainak száma) felülről korlátozható az élek össz-költségével. Tehát az eljárás polinomiális, ha a c egészértékű és legnagyobb értéke |V | polinomjával korlátozható.

Van olyan példa (sorozat), amely azt mutatja, hogy ha c-nek csak az egészértékűségét tesszük fel, akkor az algoritmus nem polinomiális.

Feladat Igazoljuk, hogy tetszőleges c esetén a fenti algoritmus véges sok lépésben véget ér.

Feladat Tegyük fel, hogy x minimimális költségű folyam (a val(x) nagyságúak között). Tekintsük a MFMC algoritmusban definiált G_{x} segédgráfot, és definiáljuk egy uv ∈ A_{x} előre él kötségét c(uv)-nek, míg egy uv ∈ A_{x} hátra él kéltségét −c(vu)-nak. Igazoljuk, hogy ha P a segédgráf egy legolcsóbb útja, akkor az x folyam P mentén történő növelésével kapott folyam minimális költségű.

8. LÁNCOK ÉS ANTILÁNCOK

Legyen P = {p_{1}, …, p_{n}} részbenrendezett halmaz. Egy lánc elemszámát néha a lánc hosszának nevezik. A leghosszabb lánc hossza a részbenrendezett halmaz magassága. A legnagyobb antilánc elemszáma részbenrendezett halmaz szélessége. Először a magasságra és a szélességre vonatkozó két fontos tételt bizonyítunk. Az első meglehetősen egyszerű (néha a Dilworth tétel polárisának hívják):

8.0A TÉTEL A P -t fedő antiláncok minimális c száma egyenlő a leghosszabb lánc hosszával, vagyis P magasságával.

Biz. Világos, hogy max ≤ min. Az egyenlőség igazolásához megkonstruálunk egy antilánc felbontást és egy láncot, melyekre egyenlőség áll.

Legyen A_{1} a P minimális elemeinek halmaza. Ez nyilván antilánc. Legyen A_{2} az A_{1} elhagyása után a minimális elemek halmaza. Ezt folytatva megkonstruáljuk az A_{1}, …, A_{c} antiláncokból álló felbontását P -nek. Most visszafelé haladva előállítunk egy c elemből álló láncot. Legyen a_{c} az A_{c} antilánc tetszőleges eleme. Az a_{c} elem nem került bele A_{c−1}-be, ezért van A_{c−1}-nek egy a_{c}-nél kisebb a_{c−1} eleme. Ez az elem nem került A_{c−2}-be, tehát van A_{c−2}-ben egy a_{c−2} elem, amely kisebb, mint a_{c−1}. Ezt az eljárást folytatva, megkapunk egy c elemű láncot. •

Feladat Igazoljuk, hogy egy legalább kl + 1 tagú számsorozatban vagy van k + 1 tagú monoton növő részsorozat, vagy van l + 1 tagú szigorúan monoton csökkenő rész-sorozat. Előfordulhat-e, hogy mind a két rész-sorozat létezik?

Érvényes tételt kapunk, ha a 8.0A tételben a lánc és antilánc szavakat felcseréljük:

8.0B TÉTEL (Dilworth) A P -t fedő láncok minimális a száma egyenlő a legnagyobb antilánc elemszámával, vagyis P szélességével.

Biz. A max ≤ min egyenlőtlenség ismét nyilvánvaló. A fordított egyenlőtlenség igazolásához készítsünk el egy G = (X, Y; E) páros gráfot, melynek mindkét osztálya a P halmaznak felel meg és valamely x_{i} elem y_{j}-vel akkor van összekötve, ha p_{i} > p_{j}. (x_{i} NINCS összekötve y_{i}-vel.)

1. LEMMA G tetszőleges M párosításának megfelel P -nek egy n − |M| láncból álló felbontása.

Biz. Tekintsük a B halmaz M által fedetlen pontjait. Ezek száma n − |M|. Legyen x_{i} olyan pont, amelyet M nem fed. Mindegyik ilyen x_{i} elemhez megkonstruálunk egy C_{i} láncot, a következőképpen. Ha y_{i} fedetlen, akkor C_{i} álljon az egyetlen p_{i} elemből. Ha y_{i}-t fedi valamely M-beli x_{j}y_{i} él, akkor p_{j} > p_{i}, és legyen p_{j} a lánc következő eleme. Ha y_{j}-t fedi valamely M-beli x_{k}y_{j} él, akkor legyen p_{k} a lánc következő eleme. Így folytatva, a láncot addig növeljük, amig a lánchoz utolsónak vett p_{m} elemhez tartozó y_{m} csúcsot már nem fedi M-beli él.

Íly módon az M által nem fedett n−|M| darab X-beli csúcs mindegyikéhez definiáltunk egy láncot P -ben. A lemma következik abból, hogy az így kapott láncok páronként diszjunktak és lefedik P -t. •

2. LEMMA Legyen S ⊆ X ∪ Y a páros gráf éleinek minimális lefogása. Ekkor P -ben van olyan A antilánc, ameyre |S| + |T | = n.

Biz. Először belátjuk, hogy ha x_{i} ∈ S, akkor y_{i} ∉ S. Ha indirekt mindkét csúcs S-ben volna, akkor S minimalitása miatt a gráfnak létezne olyan x_{i}y_{j} illetve x_{k}y_{i} éle, melyekre y_{j}, x_{k} ∉ S. Ekkor tehát p_{k} > p_{i} > p_{j}, amiből p_{k} > p_{j}, és így x_{k}y_{j} éle a gráfnak. Ezt az élt viszont nem fogja le S, amely ellentmondás azt bizonyítja, hogy valóban nem lehet x_{i} és y_{i} mindegyike S-ben.

Legyen most A := {p_{i} : x_{i} ∉ S, y_{i} ∉ S}. Rögtön látszik, hogy az A halmaz kielégíti a lemma követelményeit. •

A két lemmát felhasználva Dilworth tétele rögtön következik a Kőnig tételből, ami szerint egy páros gráfban a független élek maximális száma egyenlő az éleket lefogó pontok minimális számával. • •

Most leírunk a fenti két tételnek egy közös általánosítását. Valamely B= {B_{1}, B_{2}, …, B_{k}} családra használjuk az ∪B = ∪(B_{i} : i = 1, …, k) jelölést. Az C_{γ} = {C_{1}, C_{2}, …, C_{γ}} lánc-családon γ darab diszjunkt nemüres láncból álló családot értünk. Jelölje C_{γ} a γ láncból álló lánc-családok halmazát, míg C az összes lánc-családot magába foglaló halmazt. Legyen c_{γ} = max(| ∪ C_{γ}| : C∈ C_{γ}), vagyis c_{γ} a legnagyobb halmaz elemszáma, amely előáll γ lánc egyesítéseként (azaz a Dilworth tétel alapján nem tartalmaz γ-nál nagyobb elemszámú antiláncot).

Az A_{α} = {A_{1}, A_{2}, …, A_{α}} antilánc-családon α darab diszjunkt nemüres antiláncból álló családot értünk. Jelölje A_{α} az α antiláncból álló antilánc-családok halmazát, míg A az összes antilánc-családot magában foglaló halmazt. Legyen a_{α} = max(| ∪ A_{α}| : A_{α} ∈ A_{α}), vagyis a_{α} a legnagyobb halmaz elemszáma, amely előáll α antilánc egyesíteseként (azaz a poláris Dilworth tétel alapján nem tartalmaz α-nál nagyobb elemszámú láncot).

Dilworth tétele szerint c_{a} = n, a poláris tétel szerint a_{c} = n. Mi mondható c_{γ}-ról (1 ≤ γ ≤ a) és a_{α}-ról (1 ≤ α ≤ c)?

8.1A TÉTEL [Greene és Kleitman, 1976] a_{α} = min(qα + |P − ∪C_{q}| : C_{q} ∈ C).

8.2A TÉTEL [Greene, 1976]) c_{γ} = min(qγ + |P − ∪A_{q}| : A_{q} ∈ A).

Miután egy láncnak és egy antiláncnak legfeljebb egy közös eleme lehet, a_{α} és c_{γ} legfeljebb akkora, mint a szóbanforgó minimumok.

DEFINÍCIÓ Az A_{α} = {A_{1}, A_{2}, …, A_{α}) antilánc-család és az C_{γ} = {C_{1}, C_{2}, …, C_{γ}} lánc-család ortogonális, ha

P = (∪A_{α}) ∪ (∪C_{γ})  (1a)

és

A_{i} ∩ C_{j} ≠ ∅ for 1 ≤ i ≤ α, 1 ≤ j ≤ γ,  (1b)

azaz a lánc-család és az antilánc-család együttesen lefedi P -t és mindegyik A_{i} antilánc metszi az összes C_{j} láncot.

A 8.1A és 8.2A tételek nemtriviális részeit átfogalmazhatjuk az alábbiak szerint.

8.1B TÉTEL Minden α-ra, 1 ≤ α ≤ c, létezik A_{α} ∈ A_{α} és C_{γ} ∈ C, valamely γ-ra, amelyek ortognálisak.

8.2B TÉTEL Minden γ-ra, 1 ≤ γ ≤ a, létezik C_{γ} ∈ C_{γ} és A_{α} ∈ A, valamely α-ra, melyek ortogonálisak.

A két tétel közös általánosítása így hangzik.

8.3 TÉTEL Létezik egy olyan C_{a}|A_{1}, A_{2}, …, A_{i_{1}}| C_{a−1},C_{a−2},…, C_{a−j_{1}}|A_{i_{1}+1}, …, A_{i_{2}}| C_{a−j_{1}−1}, …, C_{a−j_{2}}| … sorozat, amely a C_{a}, C_{a−1}, …, C_{1} és A_{1}, A_{2}, …, A_{c} sorozatok összefésülésével keletkezik, ahol C_{j} ∈ C_{j} és A_{i} ∈ A_{i}, és fennáll, hogy a sorozat bármely tagja (akár C_{j} akár A_{i}) ortogonális az utolsó őt megelőző ellentétes típusú tagra. (Vagyis, A_{1}, A_{2}, …, A_{i_{1}} ortogonális C_{a}-ra, C_{a−1}, C_{a−2}, …, C_{a−j_{1}} mindegyike ortogonális A_{i_{1}}-re, stb.).

Biz. Feleltessünk meg P -nek egy D = (V, A) irányított gráfot, ahol V := {s, t, x_{1}, x_{2}, …, x_{n}, y_{1}, y_{2}, … y_{n}}, és A := {(s, x_{i}) : i = 1, 2, …, n} ∪ {(y_{i}, t) : i = 1, 2, …, n} ∪ {x_{i}y_{j} : ha p_{i} ≥ p_{j}}. Legyen minden e él kapacitása g(e) ≡ 1, míg a költsége c(e) = 1, ha e = x_{i}y_{i} és 0 különben.

Alkalmazzuk a Ford és Fulkerson féle minimális költségű folyam algoritmust. Legyen z és π az algoritmus egy közbenső állapotához tartozó folyam illetve potenciál. Ekkor z 0 − 1-értékű, π nemnegatív, π(s) = 0 és kielégítik a következő optimalitási feltételeket.

π(v) − π(u) < c(uv) ⇒ z(uv) = 0,  (i)

π(v) − π(u) > c(uv) ⇒ z(uv) = g(uv).  (ii)

Írjuk fel, hogy a különféle élekre mit jelentenek az optimalitási feltételek.

x_{i}y_{i} típusú élre:

π(y_{i}) − π(x_{i}) < 1 ⇒ z(x_{i}y_{i}) = 0,  (i)

π(y_{i}) − π(x_{i}) > 1 ⇒ z(x_{i}y_{i}) = 1.  (ii)

x_{i}y_{j} típusú élre (tehát amikor p_{i} > p_{j}):

π(y_{j}) − π(x_{i}) < 0 ⇒ z(x_{i}y_{j}) = 0,  (i)

π(y_{j}) − π(x_{i}) > 0 ⇒ z(x_{i}y_{j}) = 1.  (ii)

sx_{i} típusú élre:

π(x_{i}) < 0 ⇒ z(sx_{i}) = 0,  (i)

π(x_{i}) > 0 ⇒ z(sx_{i}) = 1.  (ii)

y_{i}t típusú élre:

π(y_{i}) > π(t) ⇒ z(y_{i}t) = 0,  (i)

π(y_{i}) < π(t) ⇒ z(y_{i}t) = 1.  (ii)

8.4 LEMMA (A) Minden i = 1, …, n-re π(y_{i}) ≤ π(x_{i}) + 1. (B) Ha p_{i} > p_{j} és z(x_{i}y_{j}) = 1, akkor π(x_{i}) = π(y_{j}).

Biz. (A) fennáll az algoritmus kezdetén. A folyamnövelési lépés nem befolyásolja (A)-t. Potenciálcsere csak akkor ronthatja el (A)-t, ha a csere előtt π(y_{i}) = π(x_{i}) + 1 állt és x_{i} elérhető volt a G′ segédgráfban, miközben y_{i} nem. Ebben az esetben π′(y_{i}) = π′(x_{i}) + 2 érvényes a módosított π′ potenciálra. Az (ii) feltétel (ha π′-re alkalmazzuk) maga után vonja, hogy z(x_{i}y_{i}) = 1. Ezért z(sx_{i}) = 1 és a G′ segédgráfnak az egyetlen x_{i}-be lépő éle y_{i}x_{i}. De ez ellentmond az indirekt feltevésnek, hogy x_{i} elérhető, míg y_{i} nem.

(B) fennáll az algoritmus elején. Az (i) feltétel alapján a π(y_{j}) ≥ π(x_{i}) egyenlőtlenség fennáll. Ha egy potenciál csere elrontaná a (B) tulajdonságot, akkor π′(y_{j}) = π′(x_{i}) + 1 állna a módosított π′ potenciálra, és x_{i} elérhető volna G′-ben az s-ből, miközben y_{j} nem volna elérhető. De ez nem lehetséges, mivel y_{j}x_{i} az egyedüli él G′-ben, amely belép x_{i}-be.

Egy folyam csere csak akkor ronthatja el (B)-t, ha az aktuális (:= 0) folyamérték az x_{i}y_{j} élen 1-gyel megnőtt. Ekkor x_{i}y_{j} éle G′-nek és emiatt π(y_{i}) − π(x_{j}) = c(x_{i}y_{j}) = 0. •

Jelölje P′ azon p_{h} elemek halmazát, melyekre z(x_{h}y_{h}) = 0. Ekkor a Dilworth tétel bizonyításában látottakhoz hasonlóan azon x_{i}y_{j} (i < j) élek halmaza, melyekre z(x_{i}y_{j}) = 1, megfelel egy C_{γ} lánc-családnak, ahol γ = n − val(z), és ez a lánc-család a P′ partícióját adja. α := π(t)-re definiáljunk egy A_{α} = {A_{1}, A_{2}, …, A_{α}} családot, ahol A_{i} = {p_{j} : π(x_{j}) + 1 = π(y_{j}) = i}.

8.5 LEMMA A_{α} antilánc-családot alkot, amely ortogonális C_{γ}-ra.

Biz. Először mutassuk meg, hogy mindegyik A_{i} antilánc. Valóban, ha indirekt p_{m}, p_{j} ∈ A_{i} valamely p_{m} > p_{j} elemekre, akkor π(y_{j}) − π(x_{m}) = 1, és ezért (ii) alapján, z(x_{m}, y_{j}) = 1, ellentétben (B)-vel.

(1a) igazolása érdekében legyen p_{m} olyan elem, amely nincs P′ = ∪C_{γ}-ban, ami azzal ekvivalens, hogy z(x_{m}, y_{m}) = 1. Ekkor (i) miatt π(y_{m}) − π(x_{m}) ≥ 1, így a 8.4A lemma miatt π(y_{m}) − π(x_{m}) = 1. Vagyis π(y_{m})-t i-vel jelölve p_{m} ∈ A_{i}, tehát (1a) fennáll.

Igazoljuk végül, hogy A_{i} ∩ C_{j} ≠ ∅ (1 ≤ i ≤ α, 1 ≤ j ≤ γ). Álljon a C_{j} lánc mondjuk a p_{1} > … > p_{k} elemekből (k ≥ 1). Ekkor z(y_{1}t) = 0, így (ii) miatt π(y_{1}) ≥ π(t), amiből persze π(y_{1}) = π(t) = α. Hasonlóan z(sx_{k}) = 0, így (i) miatt π(x_{k}) ≤ 0, amiből π(x_{k}) = 0. A 8.4B lemmából kapjuk, hogy π(x_{1}) = π(y_{2}), π(x_{2}) = π(y_{3}), … π(x_{k−1}) = π(y_{k}). Ezt a 4.8A lemmával összevetve kapjuk, hogy a 0 = π(x_{k}), π(y_{k}), π(y_{k−1}), π(y_{k−2}), …, π(y_{1}) = α egész számokból álló sorozat olyan, hogy minden tagja legfeljebb eggyel nagyobb a megelőzőnél. Íly módon minden i-re (1 ≤ i ≤ α) kell olyan m indexnek lennie, amelyre π(x_{m}) = π(y_{m})+1 = i. Vagyis p_{m} ∈ C_{j} ∩ A_{i}.

Tegyük most fel, hogy a minimális költségű folyamot kiszámító algoritmus a következőképpen futott le. Kiindulva a π azonosan nulla potenciálból és a z azonosan nulla folyamból, a folyam nagysága egyenként k_{0}-ig nő, a potenciál nagysága (ami definíció szerint a π(t) érték) egyenként i_{1}-ig, azután ismét a folyam nagysága k_{1}-ig, …, stb. Végül a folyam nagysága k_{s}-re, a potenciál nagysága i_{s}-re nő. Az algoritmus a maximális nagyságú folyam elérésekor ér véget, amely nagyság esetünkben n, azaz k_{s} = n.

Legyen a := n − k_{0} és j_{i} := k_{i} − k_{0}(i = 1, 2, …, s). Az utolsó lemma alapján az algoritmus (k_{0}, 1) paraméterekkel jellemzett fázisához az C_{a} a tagú lánc-család és az A_{1} egytagú antilánc-család tartozik, melyek ortogonálisak egymásra. Ezután a potenciál nagysága, mint már említettük, egyenként i_{1}-re nő. A közbenső helyzetekhez tartozó A_{2}, A_{3}, …, A_{i_{1}} antilánc-családok ortogonálisak a változatlan C_{a}-ra. Ezután a folyam értéke egyenként k_{1}-re nő. A közbenső helyzetekhez tartozó C_{a−1}, C_{a−2}, …, C_{a−j_{1}} lánc-családok ortogonálisak a változatlan A_{i_{1}}-re, és így tovább. Ezzel a tétel bizonyítását és az algoritmus ismertetését befejeztük. • •

Feladat Dilworth után nevezzünk egy maximális (azaz a elemszámú) antiláncot D-antiláncnak. Igazoljuk, hogy a diszjunkt D-antiláncok maximális száma egyenlő a D-antiláncokat lefogó elemek minimális számával. (Segítség: Tekintsük a 8.3 tételben leírt sorozat A_{i_{1}}| C_{a−1} tagjait.)

9. MINIMÁLIS KÖLTSÉGŰ ÁRAMOK

Legyen G = (V, E) irányított gráf, az élein f : E → R, g : E → R alsó és felső kapacitások, melyekre f ≤ g. A kapacitásokon kívül adott még egy c : E → R költség-függvény is. Egy x áram költségén a cx skaláris szorzatot értjük. Határozzuk meg a legkisebb költségű megengedett áramot!

Definiáljuk a G_{x} = (V, E_{x}) segédgráfot és a c_{x} módosított költség-függvényt a következőképpen. Egy uv él akkor tartozzék E_{x}-hez, ha vagy (i) uv ∈ E, x(uv) < g(uv) és ekkor legyen c_{x}(uv) = c(uv) (E_{x} előre éle), vagy ha (ii) vu ∈ E, x(vu) > f(vu) és akkor legyen c_{x}(uv) = −c(vu) (E_{x} hátra éle).

9.0 TÉTEL x megengedett áramra a következők ekvivalensek. (a) x minimális költségű, (b) G_{x}-ben nincs negatív kör, (c) létezik egy π : V → R potenciál, melyre

π(v) − π(u) ≤ c(uv), ha x(uv) < g(uv) (uv ∈ E),  (i)

és

π(v) − π(u) ≥ c(uv), ha x(uv) > f(uv) (uv ∈ E).  (ii)

Biz. (a)=>(b). Ha G_{x}-ben létezik C negatív kör, akkor annak előre élein növeljük, hátra élein pedig csökkentsük x-t ε-nal. Amennyiben ε kicsiny pozitív szám, a keletkező x′ megengedett áram lesz, amelynek költsége (C negativitása miatt) kisebb, mint x költsége.

(b)=>(c). Használjuk azt a korábban megismert tételt, hogy ha egy irányított gráfban nincsen negatív kör, akkor létezik megengedett potenciál. A G_{x} gráfban egy π potenciálnak a c_{x}-re vonatkozó megengedettsége pontosan az (i) és (ii) feltételekkel ekvivalens! (Ez tehát valójában a (b) és (c) ekvivalenciáját bizonyítja.)

(c)=>(a). Tegyük fel π teljesíti az (i) és (ii) feltételeket. Legyen c̄(uv) := c(uv) − π(v) + π(u). Ekkor tetszőleges z megengedett áramra cz = c̄z = ∑(c̄(uv)z(uv) : c̄(uv) > 0) + ∑(c̄(uv)z(uv) : c̄(uv) < 0) ≥ ∑(c̄(uv)f(uv) : c̄(uv) > 0) + ∑(c̄(uv)g(uv) : c̄(uv) < 0) = ∑(c̄(uv)x(uv) : c̄(uv) > 0) + ∑(c̄(uv)x(uv) : c̄(uv) < 0) = c̄x = cx. •

Az (i) és (ii) feltételeket hívják optimalitási kritériumoknak. A tétel a következő algoritmust sugallja. Induljunk ki egy x megengedett áramból. Ha G_{x}-ben nincs negatív kör, akkor készen vagyunk: a tétel szerint az adott x áram minimális költségű. Ha van negatív kör, akkor ezen C kör mentén cseréljük ki x-et úgy, hogy az előre éleken Δ-val növeljük, a hátra éleken Δ-val csökkentjük, ahol Δ = min(m_{1}, m_{2}) és m_{1} a C előre élein a g(uv)−x(uv) minimuma, m_{2} pedig a C hátra élein az x(uv)−f(uv) minimuma. Nevezzünk egy ilyen változtatást a C kör mentén való javításnak. Iteráljuk az eljárást a létrejött új áramra vonatkozólag.

Ez az algoritmus, amint egy példasorozattal megmutatható, általában nem polinomiális futásidejű. Goldberg és Tarjan azonban igazolták, hogy ha mindig a minimális átlagú kör mentén javítunk, akkor az algoritmus erősen polinomiális. Ennek bizonyítása érdekében készítsük el G segítségével a következő H = (V, A) gráfot. A G minden uv éléhez, amelyre f(uv) < g(uv), tegyük A-ba az uv élt d(uv) := c(uv) költséggel és a vu élt d(vu) := −c(uv) költséggel. A G_{x} segédgráf tehát mindig a H részgráfja.

Amikor a G_{x} egy C köre mentén javítva az y áramot kapjuk, a G_{y} úgy áll elő a G_{x}-ből, hogy a C kör minden élét fordítva betesszük, ha még nem volt benn, és a C kör bizonyos éleit (éspedig azokat, ahol a Δ felvétetik) kitöröljük.

Legyen π : V → R tetszőleges potenciál. Definiáljuk H-nak mindegyik uv élére a d_{π}(uv) := d(uv) − π(v) + π(u) eltolt költséget. Nyilván tetszőleges áramnak, speciálisan minden körnek, az eltolt költsége ugyanannyi, mint az eredeti. A fenti optimalitási kritérium azzal ekvivalens, hogy a G_{x} minden e élére d_{π}(e) ≥ 0. (Miért?!) Amennyiben tehát x nem optimális, úgy bármely π potenciálra lesz olyan e él G_{x}-ben, amelyre d_{π}(e) negatív. A szemlélet azt diktálja, hogy minél közelebb vannak ezek a negatív számok a 0-hoz, annál közelebb vagyunk az optimalitási kritériumok teljesüléséhez.

Definíció. Az x áram és π potenciálból álló (x, π) pár hibája az ε(x, π) = − min(d_{π}(e) : e ∈ E_{x}) szám. Egy x áram ε(x) hibája ε(x) := min(ε(x, π) : π potenciál).

9.1 Lemma x hibája egyenlő a d-re vonatkozóan a G_{x}-ben vett minimális körátlag −1-szeresével.

Biz. Ha x hibája ε, akkor létezik π, melyre G_{x} minden e élére d_{π}(e) ≥ −ε, vagyis G_{x}-ben a körátlag legalább −ε. Megfordítva, ha G_{x}-ben a minimális körátlag −ε′, akkor a d′(e) := d(e) + ε′ (e ∈ E_{x}) költségre nézve G_{x}-ben nincs negatív kör. Így létezik π potenciál, melyre π(v) − π(u) ≤ d′(uv), minden uv ∈ E_{x} élre. Ez épp azt jelenti, hogy az (x, π) pár hibája legfeljebb ε′, és így x hibája is csak legfeljebb ε′. •

Figyeljük meg, hogy ha az x áram hibája ε, akkor létezik olyan π potenciál, amelyre az (x, π) pár hibája ε, továbbá a G_{x} digráfban minden él d_{π}-költsége legalább −ε, és a minimális átlagú kör minden élének a d_{π}-költsége −ε.

9.2 Lemma Minimális d-átlagú kör mentén javítva az áram hibája nem nő.

Biz. A 9.1 Lemma szerint azt kell bizonyítani, hogy javításnál a minimális körátlag nem csökken. Tegyük fel, hogy x hibája ε, azaz G_{x}-ben a minimális körátlag −ε, és legyen π olyan, hogy d_{π}(uv) ≥ −ε minden uv ∈ E_{x} élre. Ekkor egy minimális átlagú C kör minden e élére d_{π}(e) = −ε. C mentén javítva a keletkező G_{y} segédgráfban csak a C néhány élének megfordítottja lehet új él. Ezek d_{π}-költsége +ε, vagyis G_{y}-ban minden él d_{π}-költsége legalább −ε, és így y hibája legfeljebb ε. •

9.3 Lemma. Tetszőleges G_{x}-ből indulva nem több, mint m := |E| javítás után olyan z áram keletkezik, amelynek hibája legfeljebb az x hibájának az (1 − 1/n)-szerese lesz.

Biz. Legyen ε := ε(x) és legyen π olyan, amelyre (x, π) hibája ε. Amint már említettük, G_{x}-ben a javító kör minden élének d_{π}-költsége −ε, egy negatív szám. Tekintsük x-től kezdve az egymást követő olyan javításokat, amelyekben az egymást követő javító körök valamennyi élének d_{π}-költsége negatív. Mivel ilyen javításkor a segédgráfból legalább egy negatív él kiesik és negatív él nem jön be, az ilyen javítások k száma legfeljebb m.

Tehát k javítás után olyan z áram áll elő, amely vagy már kielégíti az optimalitási feltételeket, vagy ha még nem, akkor a G_{z}-ben olyan C kör mentén történik a javítás, amelynek valamely e élére d_{π}(e) ≥ 0. A k definíciója miatt a megelőző javítások során a segédgráfhoz csak olyan f élek jöttek, melyekre d_{π}(f) > 0, ezért a C minden olyan h éle, melyre d_{π}(h) < 0, benne van G_{x}-ben. Így d_{π}(C) ≥ 0 + (|C| − 1)(−ε). Vagyis a k ≤ m javítás után előálló G_{z}-ben a minimális körátlag legalább (1 − 1/n)(−ε), azaz z hibája az x hibájának legfeljebb (1 − 1/n)-szerese. • (MEGJEGYZÉS. Ha c egészértékű és valamely egészértékű π-re ε(x, π) < 1/n, akkor x optimális. Valóban, ellenkező esetben ugyanis létezik G_{x}-ben egy C negatív d-költségű kör. Mivel d is egészértékű, ezért d(C) ≤ −1. Vagyis ekkor a minimális körátlag legfeljebb −1/n, így ε(x, π) ≥ 1/n volna. Ez a megjegyzés a 9.3 Lemmával karöltve azt már bizonyítja, hogy egész költségek esetén az algoritmus polinomiális).

9.4 Lemma Legyen x és y megengedett áram, melyekre x(uv) < y(uv) valamely uv élre. Ekkor létezik G_{x}-ben olyan C irányított kör, amelynek megfordítása benne van G_{y}-ban és átmegy uv-n.

Biz. z := y − x áram G azon éleire megszorítva, melyeken x(e) − y(e) ≠ 0. Fordítsuk meg G azon éleinek irányítását, melyeken z negatív és ezen éleken negáljuk z-t. A keletkező z′ függvény a keletkező G′ digráf élein áramot alkot, amely mindenütt pozitív. Mivel egy pozitív áram előáll irányított körök (karakterisztikus vektorainak) pozitív lineáris kombinációjaként, van olyan C irányított kör a G′-ben, amely átmegy az uv élen. C benne van G_{x}-ben és C megfordítása benne van G_{y}-ban, ezért eleget tesz a lemma követelményének. •

Definíció. H egy uv élét ε-fixnek mondjuk, ha minden legfeljebb ε hibájú áramnak az uv-nek a G-ben megfelelő (uv vagy vu) élen ugyanaz az értéke.

(Figyelem, ha egy él ε-fix, akkor minden ε-nál kisebb ε′-re is ε′-fix.)

9.5 Lemma Legyen ε := ε(x, π), és tegyük fel, hogy G_{x} valamely uv élére d_{π}(uv) ≥ 2nε. Ekkor uv ε-fix.

Biz. Tegyük fel, hogy az uv-nek G_{x}-ben az uv él felel meg (analóg az az eset, ha a vu él). Mivel d_{π}(vu) ≤ −2nε < −ε, így vu nem lehet G_{x}-ben, azaz x(uv) = f(uv). Indirekt, tegyük fel, hogy létezik olyan legfeljebb ε hibájú y áram, amelyre y(uv) > x(uv). Tekintsük a 9.4 lemma C körét. Ennek megfordítottját jelölje C′. C benne van G_{x}-ben, C′ pedig G_{y}-ban. De ekkor −d(C′) = d_{π}(C) ≥ 2nε + (n − 1)(−ε) = (n + 1)ε, azaz d(C′) < −nε, vagyis C′ átlaga kisebb, mint −ε, ellentmondásban a feltevéssel, hogy y hibája legfeljebb ε. •

A következő egyszerű megfigyelésre az algoritmus futásidejének becslésekor lesz szükség.

9.6 Lemma Legyen N pozitív egész és y_{1}, y_{2}, … pozitív valós számok, melyekre fennáll, hogy y_{k+1} ≤ (1 − 1/N)y_{k} minden k-ra. Ekkor minden k-ra y_{k+N} ≤ y_{k}/2.

Biz. A feltételt átírva: y_{k} ≥ y_{k+1} + y_{k+1}/(N − 1). Ezt k helyén k + t-re alkalmazva t szerinti indukcióval kapjuk, hogy y_{k} ≥ y_{k+t} + ty_{k+t}/(N − 1), amiből t = N-re a lemma következik. •

9.7 TÉTEL Tetszőleges költségek esetén az algoritmus O(nm^{2} log n) javítás után véget ér.

Biz. Legyen k = mn(1 + ⌈log n⌉ ). Tekintsük a G_{x} segédgráfot, amikor ennek egy C köre mentén javítunk és legyen ε = ε(x). k javítás után a kapott áram legyen x′. A 9.3 és 9.6 lemma miatt x′ hibája legfeljebb ε′ := ε/2n. Legyen π′ olyan, hogy (x′, π′) hibája ε(x′). A C kör átlaga −ε(x), ezért valamelyik vu élére d_{π′}(vu) ≤ −ε = −2nε′, és így d_{π′}(uv) ≥ 2nε′. Alkalmazva a 9.5 lemmát az (x′, π′) és ε′-re, kapjuk, hogy a H digráf vu éle ε′-fix.

Vagyis k iteráció után egy új él fixálódik, így legfeljebb mk iteráció után az eljárás véget ér. • •

Feladat. Mutassuk meg, hogy a maximális folyam meghatározására szolgáló Edmonds-Karp-Dinitz algoritmus a fent leírt eljárás speciális esetének tekinthető.

10. OPTIMÁLIS PÁROSÍTÁSOK

A MAGYAR MÓDSZER

10.1 TÉTEL (Kőnig Dénes) G = (A, B; E) páros gráfban a független élek maximális ν száma egyenlő az éleket lefogó pontok minimális τ számával.

Biz. Minden gráfra érvényes, hogy ν ≤ τ, hiszen k darab független élt nem lehet k-nál kevesebb ponttal lefogni. (A háromszög mutatja, hogy általában az egyenlőség nem érvényes.)

Páros gráf esetén az egyenlőség igazolásához olyan M párosítást és L lefogást konstruálunk, melyek elemszáma ugyanaz. Az eljárás tetszőleges M párosításból indul ki, ami kezdetben az üres halmaz is lehet. Az általános lépésben vagy találunk egy nagyobb párosítást és ekkor a nagyobb párosításra vonatkozóan újra kezdjük az eljárást, vagypedig egy |M|-mel megegyező elemszámú lefogást, amikoris az algoritmus végetér.

Irányítsuk meg M éleit A-ból B felé, míg az összes többi élt fordítva. Jelölje S illetve T a B-ben illetve az A-ban az M által fedetlen pontok halmazát. Jelölje továbbá Z az S pontjaiból a kapott irányított gráfban elérhető pontok halmazát. Amennyiben T -nek esik pontja Z-be, akkor megkaptunk egy olyan S-t és T -t összekötő P utat, amely M-ben alternál. Most M és P szimmetrikus differenciája egy M-nél eggyel több élből álló párosítás.

Tegyük fel most, hogy T diszjunkt Z-től. Z definíciója folytán Z-ből nem vezet ki irányított él. Érvényes továbbá, hogy Z-be nem lép be megirányított uv ∈ M párosítás él, mert hiszen v csak u-n keresztül érhető el, így v csak akkor lehet elérhető, ha u is az. Következik, hogy az L := (A ∩ Z) ∪ (B − Z) halmaz az éleknek lefogása és minden M-beli élnek pontosan az egyik végpontját tartalmazza, tehát |M| = |L|. •

A fenti bizonyítás olyan algoritmushoz vezet, amely legfeljebb n darab útkeresési eljárást igényel, így az össz-lépésszám nem nagyobb, mint O(nm).

10.2 TÉTEL (M. Hall) G = (A, B, E) páros gráfban akkor és csak akkor létezik A-t fedő párosítás, ha minden X ⊆ A részhalmazra teljesül a Hall féle |Γ(X)| ≥ |X| feltétel, ahol Γ(X) jelöli azon B-beli pontok halmazát, melyeknek van szomszédja X-ben.

Biz. Nyilván ν ≤ |A|. Ha ν = |A|, akkor egy ν elemű párosítás fedi A minden pontját. Ha ν < |A|, akkor Kőnig tétele nyomán létezik olyan L lefogás, melynek |A|-nál kevesebb eleme van. De ekkor X := A − L-nek minden szomszédja B ∩ L-ben van, és |A − L| < |B ∩ L|, vagyis X megsérti a Hall feltételt. •

Tételezzük most fel, hogy a páros gráf élein adott egy d ≥ 0 súly-függvény és G-nek van teljes (azaz minden pontot fedő) párosítása. Célunk maximális súlyú teljes párosítás keresése. A lefogás általánosításaként nevezzünk egy pontokon értelmezett nem-negatív π függvényt súlyozott lefogásnak, ha minden uv élre π(u) + π(v) ≥ d(uv). Egy élt pontosnak fogunk nevezni (π-re nézve) ha itt egyenlőség áll. π súlyozott lefogás π(V) súlyán a ∑(π(v) : vA ∪ B) összeget értjük. (Itt V = A ∪ B).

10.3 TÉTEL (Kőnig – Egerváry) A teljes párosítások maximális ν_{d} súlya egyenlő a súlyozott lefogások minimális τ_{d} súlyával. Amennyiben d egészértékű, az optimális π is választható egészértékűnek.

Legyen u_{1}v_{1}, u_{2}v_{2}, …, u_{n}v_{n} tetszőleges M párosítás G-ben, és π egy súlyozott lefogás. Ekkor d(M) := ∑ d(u_{i}v_{i}) ≤ ∑(π(u_{i}) + π(v_{i}) : i = 1, …, n) = π(V), amiből ν_{d} ≤ π_{d} következik. Itt egyenlőség pontosan akkor áll, ha M minden éle pontos.

A fordított irányú egyenlőtlenség bizonyításához tehát kell találnunk egy π súlyozott lefogást úgy, hogy a π-re vonatkozó pontos élek gráfja tartalmazzon teljes párosítást. Ennek érdekében kiindulunk egy tetszőleges π súlyozott lefogásból (amely egeszértékű, amennyiben d az.) Például legyen π a B pontjaiban 0, míg bármely A-ban levő v pontra π(v) legyen a v-be futó élek súlyának maximuma.

Az általános lépésben tekintjük a pontos élek által alkotott G_{π} részgráfot és az előzőekben leírt algoritmus segítségével meghatározunk egy maximális M párosítást valamint a Kőnig tétel bizonyításában leírt Z halmazt, (amely tehát a megfelelő irányított gráfban az elérhető pontok halmazát jelölte).

Amennyiben M teljes párosítás, úgy az algoritmus végetér és a tétel bizonyítása is. Ha viszont nincs teljes párosítás G_{π}-ben, akkor az X := A − Z halmaz G_{π}-ben megsérti a Hall feltételt. A π értékeit csökkentsük X elemein egy bizonyos Δ pozitív számmal, és növeljük Γ_{π}(X) elemein ugyanazzal a Δ-val, ahol Δ := min(π(u) + π(v) − d(uv) : uvE, u ∈ X, v ∈ B − Γ(X)). A konstrukció miatt Δ pozitív és a módosított π′ is súlyozott lefogás. Érvényes továbbá, hogy a G_{π′} és M-hez tartozó irányított gráfban (:Mbeli élek B felé irányítva, a többi A felé) Z minden eleme továbbra is elérhető és még legalább egy új pont A-ban, nevezetesen annak az élnek a végpontja, amelyen a Δ-t definiáló minimum felvétetik (merthogy ez az él a módosított π′-re nézve már pontos lesz.

Ezen meggondolásból következik, hogy π-nek legfeljebb n változtatása után az aktuális pontos élek gráfjában a ν megnő. Legfeljebb n ilyen növekedés után kapunk egy pontos élekből álló teljes párosítást, ami a célunk volt. •

MAXIMÁLIS ELEMSZÁMÚ PÁROSÍTÁSOK ÁLTALÁNOS GRÁFOKBAN

Valamely G irányítatlan gráfra jelölje ν = ν(G) a független élek maximális számát vagyis a legnagyobb párosítás elemszámát. Láttuk, hogy az alternáló utak módszerével miként lehet páros gráfban maximális elemszámú párosítást megkonstruálni. Az eljárás egyúttal bizonyította a Kőnig tételt is, amely szerint a szóbanforgó maximum egyenlő a pontokat lefogó élek minimális τ számával. Nem páros gráfokban a ν = τ min-max reláció már nem feltétlenül igaz, amint ezt a háromszög példája mutatja. Itt ν = 1, τ = 2. Az általános gráfokra vonatkozó jellemzés W.T. Tutte-tól származik.

10.4 TUTTE TÉTELE A G = (V, E) irányítatlan gráfban akkor és csak akkor létezik teljes párosítás, ha a pontok tetszőleges X részhalmazára az X elhagyásával keletkező páratlan (pontszámú) komponensek száma legfeljebb |X|.

Az X elhagyásával keletkező páratlan komponensek számát jelölje q(X). Tetszőleges M teljes párosítás egy páratlan pontszámú halmazból páratlan sok éllel lép ki, így speciálisan legalább eggyel. Ebből látszik, hogy ha létezik teljes párosítás, akkor q(X) legfeljebb |X|, azaz a Tutte-féle feltétel szükséges.

Az elegendőséget kicsit általánosabb alakban igazoljuk. Amennyiben teljes párosítás nem létezik, megkérdezhetjük, hogy milyen nagy létezik, azaz mekkora ν. Jelöljük a q(X)−|X| különbséget γ(X)-szel. (A Tutte féle feltétel azt jelenti, hogy γ(X) ≤ 0.) Tegyük most fel, hogy valamely X ponthalmazra γ(X) > 0. Ekkor tetszőleges M párosítás legalább γ(X) pontot nem fed le, vagy másszóval M legfeljebb |V | − γ(X) pontot fedhet le, azaz

|M| ≤ (|V | − γ(X))/2.  (10.1)

Itt egyenlőség akkor és csak akkor áll, ha

(a) Az X elhagyásával keletkező bármely C komponensre az M-nek a C-be eső része legfeljebb egy pont híján fedi C-t.

(b) X nem feszít M-beli élt.

(c) M fedi X minden pontját.

Egy ilyen X halmazt gátnak nevezünk. A Tutte tétel általánosítása mármost a következő.

10.5 BERGE-TUTTE formula: G-ben a független élek maximális ν száma egyenlő max(|V | − γ(X))/2vel, ahol a maximum V összes X részhalmazára megy.

A fenti meggondolás alapján a max ≤ min egyenlőtlenség következik. A fordított egyenlőtlenség ekvivalens a következővel:

Létezik olyan M párosítás és pontoknak olyan X részhalmaza, melyekre (a), (b) és (c) fennáll.

Az alábbi J. Edmondstól származó algoritmus ilyen M-et és X-et konstruál meg. Az eljárás fázisokból áll. Egy fázisban valamely korábban megtalált M párosításból indulunk ki és keresünk egy olyan P M-alternáló utat, amely két szabad (azaz, M által nem fedett) pontot köt össze. Nevezzük az ilyen utat növelő útnak.

Amennyiben találunk egy P növelő utat, úgy az M′ := M ⊗ P szimmetrikus differencia olyan párosítás lesz, amelynek eggyel több éle van, mint M-nek, és ekkor a következő fázisra térünk. Amikor az algoritmus már nem talál M-alternáló utat, akkor megad majd egy X részhalmazt, amely az aktuális M párosítással együtt kielégíti a három optimalitási feltételt.

Legyen tehát M valamilyen párosítás, S a szabad pontok halmaza és v ∈ V − S-re jelöljük μ(v)-vel a v párosításbeli szomszédját. Az S pontjaira pedig definiáljuk μ(v) = v. Az eljárás egy F M-alternáló erdőt épít fel, amely a következő tulajdonságú erdő.

(i) F -nek |S| darab komponense van, mindegyike egyetlen szabad pontot tartalmaz, amely a komponens gyökere.

(ii) F bármely pontjából a gyökérhez vezető út M-alternáló.

(iii) Ha valamely fedett v pont F -ben van, akkor a vμ(v) él is F -hez tartozik.

Az F erdőben nem lévő pontok halmazát tisztásnak hívjuk és C := C(F)-fel jelöljük. Nyilván az Mnek C-ben levő élei C-t párosítják. Külső pontnak hívjuk az F azon pontjait, melyek a gyökértől páros

távolságban vannak. F többi pontja belső pont. (Az elnevezés arra utal, hogy a végül kapott külső pontok, amint majd az Edmonds-Gallai tétel nyomán kiderül, olyanok, hogy mindegyikhez van egy őt nem lefedő maximális párosítás, míg a belső pontok mindegyikét valamennyi maximális párosítás fedi.)

Kiinduláskor F a szabad pontokból áll és élt nem tartalmaz. Az általános lépés leírásához legyen F M-alternáló erdő. Három esetet különböztetünk meg.

1. eset. Az F -nek létezik olyan u és v külső pontja, melyek az F különböző komponenséhez tartoznak és amelyek között vezet él a gráfban. Ekkor az u és v komponensében a gyökerekhez vezető két alternáló utat az uv él mentén összekapcsolva egy P növelő utat kapunk, és ekkor az adott fázis végetér.

2. eset. F -nek létezik olyan u külső pontja, amely szomszédos egy v tisztáson lévő v ponttal. Ekkor az uv élt és a vμ(v) párosító élt F -hez véve nagyobb M-alternáló erdőt kapunk.

3. eset. F -nek egy komponensében létezik u és v külső pont, melyek szomszédosak. Ekkor az F -ben az u-t és v-t összekötő egyértelmű út az uv éllel együtt egy páratlan kört alkot. Húzzuk össze ezt a kört egy ponttá. Ekkor F -ből egy másik alternáló erdő keletkezik, melynek az összehúzott pont külső pontja.

Nevezzünk valamely K páratlan kört M-alternálónak, ha valamely r pontjából a körön akármelyik irányba elindulva minden második él M-beli. Az r pontot a kör bázisának hívjuk. Az M-alternáló kör legfontosabb tulajdonsága, hogy

(∗) K bármely pontjából vezet a bázisba párosítás éllel kezdődő alternáló út.

A fenti 3. esetben egy M-alternáló páratlan kört húztunk össze. A (∗) tulajdonságból látjuk, hogy ha az összehúzott gráfban létezik növelő út, akkor ebből előállíthatjuk az eredeti gráf egy növelő útját. Ebből az is következik, hogy ha az 1. eset olyankor fordul elő, amikor már bizonyos összehúzásokat végrehajtottunk, akkor az eredeti gráfnak is elő tudunk állítani egy növelő útját. Azt is megfigyelhetjük, hogy (esetleg többszöri) összehúzással keletkezett pont ősképe olyan halmaz, amelyet a beleeső M-beli élek egy pont híján kipárosítanak.

TEHÁT: Ameddig a 2. vagy 3. eset fordul elő, járjunk el az ott leírtak szerint. Amennyiben az 1. eset következik be, azaz az összehúzott gráfban van növelő út, akkor keressünk az eredeti gráfban növelő utat és egy nagyobb párosítást, majd térjünk a következő fázisra.

Vizsgáljuk most meg azt az esetet, amikor a fenti három eset egyike sem áll fenn. Jelölje X a belső pontok halmazát, C a tisztást és D a külső pontok ősképeinek halmazát. Emlékezzünk rá, hogy belső pont sohasem összehúzott pont. Külső pontból csak belső pontba vezet él, ezért G-ben az X elhagyásakor a külső pontok ősképei páratlan komponensek lesznek. Így M és X kielégítik az optimalitási feltételeket. Evvel az algoritmus leírását és egyúttal a Berge-Tutte formula igazolását befejeztük. •

Feladatok Vezessük le Tutte tételéből: (a) Petersen tételét (amely szerint 2-élösszefüggő 3-reguláris gráfban létezik teljes párosítás), (b) a Berge-Tutte formulát, (c) Hall tételét.

KRITIKUS GRÁFOK

A párosítások elméletében a következő fogalom alapvető fontosságú. Egy gráfot faktor-kritikusnak vagy röviden kritikusnak nevezünk, ha bármely pontját elhagyva létezik teljes párosítása.

(A matroidelmélet előadásban bebizonyítottuk Gallai Lemmáját, amely szerint, ha G olyan összefüggő gráf, amelynek bármely pontját elhagyva ν(G) csökken, akkor G faktor-kritikus. A bizonyítás azon múlt, hogy a feltevés szerint G párosítás matroidjának M^{∗} duálisában nincsen hurok és bármely két szomszédos pont kételemű matroidbeli kört alkot. Ebből a G összefüggőségét felhasználva következik, hogy a V alaphalmaz M^{∗}-beli rangja kettő, ami viszont azt jelenti, hogy G faktor-kritikus.)

Egy Q ⊆ V páratlan pontszámú részhalmaz által feszített gráfot valamely M párosításra nézve Mkritikusnak mondunk, ha az M Q-ba eső élei egyetlen r pont, az ún bázispont kivételével lefedik Q-t és Q minden pontjából vezet r-be páros élszámú alternáló út (azaz olyan, amelynek első éle párosítás él.)

10.6 TÉTEL Legyen adott a G gráf egy M párosítása, amely az r pontot nem fedi le, a többit lefedi. A következők ekvivalensek:

(a) G M-kritikus,

(b) G felépíthető a bázispontjából kiindulva M-alternáló utak illetve körök egymás utáni hozzávételével,

(c) G felépíthető bármely pontjából kiindulva páratlan élszámú utak és körök hozzávételével,

(d) G faktor-kritikus.

Biz. (a → b) Tegyük fel, hogy r-ből kiindulva már felépítettünk G-nek egy részgráfját a megadott módon. Jelölje a részgráf ponthalmazát T. (A kezdetben T az egyetlen r pontból áll.) Akkor vagyunk készen, ha T = V, ekkor ugyanis a még G-ből esetleg hiányzó éleket egyélű M-alternáló utakként bevéve, megkapjuk G-t. Ha még T ≠ V, akkor létezik olyan uv él, amelyre u ∈ T, v ∉ T. (Miután a definícióból adódóan Mkritikus gráf összefüggő, ilyen él létezik.) A gráf M-kritikus, így v-ből létezik r-be vezető páros M-alternáló út. Legyen ennek p az első T -be eső pontja és jelölje P′ az útnak v-ből p-be vezető szegmensét. Most az uv él a P′-vel együtt egy M-alternáló utat vagy kört alkot, amellyel T tovább építhető.

(b → c) Triviális, mert egy M-alternáló út páratlan élszámú.

(c → d) Fülek száma szerinti indukció. Két esetet kell különválasztani, annak megfelelően, hogy a kihagyandó pont az utolsó fülön van vagy sem.

(d → a) Legyen v a gráf tetszőleges pontja. Mivel G faktor-kritikus, G − v-nek létezik egy M_{v} teljes párosítása. Két párosítás szimmetrikus differenciája mindig diszjunkt alternáló körökből és utakból áll. Mivel mind M mind M_{v} a G-nek egyetlen pontját nem fedi le, így szimmetrikus differenciájuk egyetlen alternáló utat tartalmaz, és az a v és r pontokat köti össze. Így tehát létezik v-ből r-be páros élszámú M-alternáló út. •

Az alábbiakban megadunk egy kicsit bonyolultabb konstrukciót, amely M-kritikus gráfot eredményez. A tétel szemléletesen azt mondja, hogy ha egy páratlan kör pontjaiba M-kritikus gráfokat ”fújunk be”, akkor M-kritikus gráfot kapunk.

10.7 TÉTEL Tegyük fel, hogy a G gráfban az M párosítás egy r pont kivételével mindent lefed, továbbá, hogy a ponthalmaz fel van osztva páratlan sok diszjunkt M-kritikus részgráfra, melyek mindegyikét egyetlen pontra húzva M-kritikus (azaz M-alternáló) C páratlan kört kapunk. Ekkor G maga is M-kritikus.

Biz. Vegyünk a gráfnak egy tetszőleges v_{1} = v pontját és mutassuk meg, hogy létezik v-ből r-be páros élszámú M-alternáló út. Amennyiben v és r ugyanabban a P_{r} partíció részben van, akkor P_{r} M-kritikussága miatt a kívánt út létezik.

Tegyük most fel, hogy a P_{v} és P_{r} partíció részek különbözők. Jelölje P_{1} := P_{v}, P_{2}, …, P_{t} := P_{r} azokat a partíció részeket, amelyeket a C körben a P_{v}-ből a P_{r}-be menve kapunk, ha a P_{1}-ből kilépő r_{1}r_{2} párosítás él felé indulunk el. (Tehát t páratlan!)

Először P_{1}-ben a v-ből indulva elmegyünk egy páros élszámú M-alternáló úton a P_{1} gyökeréig, az ebbe jövő M-élen átmegyünk P_{2}-be. Legyen a P_{2}-ből kilépő nem-párosítás él u_{2}v_{2} ahol u_{2} ∈ P_{2}, v_{2} ∈ P_{3}. Használjuk fordítva az u_{2}-ből r_{2}-be vezető páros élszámú M-alternáló utat, így már eljutottunk u_{2}-be. Most tovább lépünk az u_{2}v_{2} élen a P_{3}-részbe, ahonnan a v_{2} ponttal kezdve iteráljuk az eljárást. •

Amint láttuk, Edmonds algoritmusa megkonstruál egy gátat és egy párosítást, melyekre fennállnak az optimalitási kritériumok. A kapott gát és párosítás elvileg függhet az algoritmus futásától és a párosítás vonatkozásában ténylegesen ez is a helyzet; egy háromszög esetén páldául akármelyik maximális (:egy-élű) párosítást megadhatja. Annál meglepőbb, hogy az algoritmus által megtalált gát kizárólag a gráftól függ és független azoktól a választásoktól, amelyeket az algoritmus futása során tettünk. (Tehát például, ha az aktuális alternáló erdőt többféleképpen lehetett növelni, akkor a végül kapott gát nem függ attól, hogy melyik növelést választottuk.) Az algoritmus által talált gát éppen a Gallai-Edmonds tételben definiált kanonikus gáttal egyezik meg.

10.8 EDMONDS ÉS GALLAI TÉTELE Jelölje D(G) azon pontok halmazát, amelyeket G-nek valamely maximális párosítása nem fed le. Álljon A(G) a V − D(G) azon pontjaiból, melyeknek van D(G)-beli szomszédja, és legyen C(G) a maradék pontok halmaza. Ekkor A(G) gátja G-nek, éspedig éppen az, amelyet az algoritmus megtalál, D(G) a V − A(G) páratlan komponenseinek egyesítése, C(G) pedig a V − A(G) páros komponenseinek egyesítése. D(G) komponensei faktor-kritikus gráfok. Végül, ha eltöröljük a páros komponenseket és az A-ban lévő éleket, és a páratlan komponensek mindegyikét összehúzzuk egy-egy pontra, akkor olyan páros gráfot kapunk, amelyben az A minden X nemüres részhalmazának legalább |X| + 1 szomszédja van.

Biz. Tetszőleges A′ gáthoz jelölje D′ a G − A′ páratlan komponenseinek únióját, C′ pedig a párosakét. Tetszőleges maximális M′ párosítás esetén az M′ lefedi a X′-t és C′-t. Ezért D(G) biztosan része D′-nek.

Legyen most A′ az algoritmus által talált gát. Csak azt kell kimutatnunk, hogy a külső pontok ősképének (ami D′) minden v elemét fedetlenül hagyja valamely maximális elemszámú párosítás. Az előző tétel szerint tudjuk, hogy egy külső pont ősképe M-kritikus, ezért létezik v-ből az alternáló fa gyökerébe egy P páros élszámú M-alternáló út. Ekkor P és M szimmetrikus differenciája egy maximális párosítás, amely elkerüli v-t.

A tétel utolsó részéhez azt figyeljük meg, hogy az algoritmus által talált alternáló erdőben a belső pontok akármely X részhalmazának legalább |X +1| külső pont szomszédja van. Ez pedig azért van így, mert a belső pontok másodfokúak, és ha mindegyik z belső pontra a belőle kiinduló uz, vz élt az uv éllel helyettesítjük, akkor egy erdőt kapunk, amelyre az állítás azt jelenti, hogy egy erdő tetszőleges X élhalmaza legalább |X| ponttal érintkezik. Ez pedig közismert és egyszerű. •

Feladat Tekintsünk egy olyan gátat, amelyre az elhagyásával keletkező páratlan komponensek úniója minimális. Igazoljuk, hogy ez éppen a Gallai-Edmonds tételében lévő gát.

MINIMÁLIS SÚLYÚ TELJES PÁROSÍTÁS KERESÉSE

Legyen adva a G = (V, E) gráf élein c nemnegatív költség-függvény, és tegyük fel G-nek létezik teljes párosítása. Az alábbiakban páratlan vágáson olyan vágást értünk, melynek két partja páratlan sok pontot tartalmaz.

A duális probléma: rendeljünk páratlan vágásokhoz változókat, melyek nemtriviális vágáson nemnegatívak és minden e élre az élt tartalmazó páratlan vágások változóinak összege legfeljebb c(e), az él költsége. Az így hozzárendelt változókat megengedettnek hívjuk. (Egy páratlan vágás triviális, ha egyik oldala egypontú.)

Azaz,

∑(y_{B} : e ∈ B) ≤ c(e) minden e élre,  (∗)

ahol az összegzés a B páratlan vágásokra megy.

Az élhalmazon egy súlyozást páros körösszegűnek nevezünk, ha egészértékű és minden kör súlya páros szám. Ha y egészértékű, akkor a (∗) baloldalán szereplő érték az élhalmazon páros körösszegű súlyozást definiál.

Legyen c_{y}(e) := c(e) − ∑(y_{B} : e ∈ B). y megengedettsége azt jelenti, hogy c_{y} nemnegatív. Egy e élt, amelyre c_{y}(e) = 0 telítettnek vagy pontosnak fogunk hívni.

10.9 TÉTEL Teljes párosítás minimális költsége egyenlő max ∑(y_{B} : y megengedett duális megoldás). Amennyiben c páros körösszegű, úgy az optimális y választható egészértékűnek.

Biz. Egyszerű becslés mutatja, hogy tetszőleges teljes párosítás költsége legalább akkora, mint a duális változók összege. Az egyenlőség kimutatásához megkonstruálunk egy M teljes párosítást és egy y megengedett duális megoldást, melyekre egyenlőség áll. Ez pedig pontosan akkor áll fenn, ha teljesül a következő két optimalitási kritérium.

1. M minden éle telített.

2. Minden B páratlan vágásra, amelyre y_{B} > 0, fennáll, hogy |B ∩ M| = 1.

Az azonosan 0 duális megoldásból indulunk ki, ami nyilván megengedett. Az általános lépésben adott a következő alakú megoldás. Legyen F a csúcsok részhalmazainak olyan lamináris rendszer, melynek minden tagja páratlan elemszámú, és bármely tagjára az abban lévő maximális tagokat összehúzva a telített élek faktor-kritikus gráfot alkotnak. Egy B nemtriviális páratlan vágásra y_{B} akkor és csak akkor pozitív, ha B-t az F nem egyelemű tagja definiálja.

Jelölje G′_{0} az F maximális tagjai összehúzásával keletkező és csak telített éleket tartalmazó gráfot. Legyen adva G′_{0}-nek egy M′ párosítása.

1. ESET Amennyiben M′ a G′_{0}-nek teljes párosítása, akkor az F tagjain kintről befelé haladva egyenként végigmegyünk, és M′-t kiegészítjük a G telített élekből álló teljes párosításává, amely F minden tagjába pontosan egy éllel lép be.

2. ESET Ha M′ nem teljes, akkor G′_{0}-ban valamely szabad pontból építünk egy F alternáló fát. (Ez egy apró különbség a ”nem-súlyozott” algoritmushoz képest, ahol alternáló erdőt építettünk.) A következő esetek lehetnek.

1. M′ növelése. F külső pontjából vezet G′_{0}-beli él szabad pontba. Ez meghatároz egy növelő utat. E mentén cserélve egy M′-nél eggyel nagyobb párosítást kapunk és erre nézve iteráljuk az eljárást.

A maximális elemszámú párosítást kereső algoritmushoz képest van egy fontos különbség. Ott, amikor alternáló utat találtunk, végrehajtjuk a növelést és az új, megnövelt párosítással mindent előlről kezdünk. Tehát eldobjuk a régi M-re felépített alternáló erdőt, az összehúzásokat, stb. Most, ha egy növelést végrehajtunk, akkor az eddigi alternáló fát ugyan eldobjuk, de a korábbi összehúzásokat megtartjuk. Ez azt jelenti, hogy az M′ vizsgálatakor már vannak G′_{0}-ban olyan pontok, melyek az M′ előtt lettek összehúzva. Így most előfordulhat, hogy az F alternáló fának belső pontja is (korábban) összehúzott pont.

2. Fa növelés. F egy külső u pontjából egy tisztáson lévő v pontba vezet G′_{0}-nek éle. Ekkor az uv élt és a vμ(v) élt a fához vesszük.

3. F két külső pontja között vezet él G′_{0}-ben. A keletkező páratlan kört összehúzzuk. Az új pont F külső pontja lesz.

4. Amennyiben az 1-2-3 lépések egyike sem hajtható végre, akkor megváltoztatjuk az y-t a következőképpen. A külső pontok ősképének duál-változóját növeljük, a belső pontok ősképének duál-változóját csökkentjük ugyanazzal az alább meghatározandó Δ értékkel. Minden külső pont ősképét F-hez vesszük.

Legyen z belső pont korábban összehúzott pont, legyen zv a z-vel szomszédos M-beli él, és zu a z-vel szomszédos másik fabeli él. Amennyiben z ősképének a duál-változója nullává válik, akkor a z pont Z-vel jelölt ősképét kihagyjuk F-ből. Ezenkívül z-t visszafújjuk abban az értelemben, hogy helyettesítjük azzal a C gráffal, amely a Z-ben lévő 0 módosított költségű élek gráfjából keletkezik az F maximális Z-ben fekvő tagjainak összehúzásával. F definíciója miatt a C gráf faktor-kritikus. Legyen v′ a C-nek olyan pontja, melyre vv′ telített él (vagyis az az él, mely a zv élt definiálta) és legyen M_{C} a C − v′ egy teljes párosítása. Vegyük M-hez az M_{C} elemeit. Ezenkívül a C-ben vegyünk egy M_{C}-ben alternáló P utat a v′ pont és az u′ pont között (ilyen van, mert C faktor-kritikus). Most a G′_{0}-ben lévő alternáló fa a P úttal együtt a z felfújásával keletkezett gráfban alternáló fát alkot.

Mekkora legyen Δ? Az alábbi m_{1}, m_{2}, m_{3} mennyiségek minimuma. Legyen m_{1} a külső pontokból a fán kívüli pontokba (azaz tisztás plusz többi szabad pont) menő G-beli (!) élek módosított költségeinek minimuma. Mivel a 2. lépés nem volt alkalmazható, m_{1} pozitív. Legyen m_{2} a fában szereplő összehúzott belső pontok duálváltozóinak minimuma. Végül legyen m_{3} az F fa külső pontjait összekötő G-beli élek módosított költségének minimumának a fele. Mivel a 3. lépés nem volt alkalmazható, az m_{3} pozitív.

Alapvető megfigyelés, hogy bármely uv élnek, amelyik a fában két külső pontot köt össze, a módosított költsége páros. Ez azért van így, mert uv a fában egy olyan G′_{0}-beli C kört definiál, melynek minden más éle telített, azaz 0 módosított költségű. Mármost bármely összehúzott pont ősképe a telített éleken összefüggő, így a C körből előállítható az eredeti G gráf egy köre, melynek minden éle, az uv él (ősképének) kivételével, telített. De a páros körösszeg tulajdonság miatt ebből következik, hogy c_{y}(uv) páros.

Ezen megfontolásból alapján m_{3} is egész szám. Könnyen látszik, hogy az új duális megoldás is megengedett. Az algoritmust az új párosításra, az új alternáló fára és az új duál-változókra iteráljuk.

Milyen lépés-szám becslés adható a fenti algoritmusra? A szabad pontok száma sohasem növekszik és párosítás növeléskor csökken. Nevezzük az algoritmus két párosítás növelés közötti részét fázisnak. Nyilván legfeljebb n/2 fázis lehetséges.

Egy fázison belül minden összehúzás külső pontot eredményez. Mivel mindig csak belső pontot fújunk fel, csak olyan pont felfújására kerülhet sor, amelyet korábbi fázisban húztunk össze. Ezért egy fázis O(m) lépést igényel.

Feladat Igazoljuk, hogy az algoritmus során a páratlan kör összehúzása a páros körösszeg tulajdonságot nem rontja el.

11. A LUCCHESI-YOUNGER TÉTEL ALGORITMIKUSAN

A poliéderes kombinatorika előadásban már megismertünk az alábbi tételre egy nem-algoritmikus bizonyítást, amely a kikeresztezési technikára épült. Jelen célunk egy algoritmikus bizonyítás leírása, amelynek segítségével polinom időben kiszámítható a szóbanforgó minimum illetve maximum. Az alábbiakban irányított vágások egy lefogását irányított kötésnek vagy röviden kötésnek fogjuk hívni.

11.1 LUCCHESI ÉS YOUNGER TÉTEL Legyen G = (V, E) irányított gráf. Az élidegen irányított vágások maximális száma egyenlő a minimális kötés elemszámával.

Biz. Feltehetjük, hogy G irányítatlan értelemben összefüggő. (Ekkor egy F élhalmaz pontosan akkor kötés, ha elemeinek összehúzása erősen összefüggő gráfot eredményez, tehát τ azon élek minimális száma, amelyeket összehúzva, vagy ekvivalensen fordítva is behúzva, eöf. digráfot kapunk.)

Nevezzük pontok egy X részhalmazát magnak, ha nem lép bele él. Az X-ből kilépő élek Δ(X) halmazát (ha nemüres) neveztük irányított vágásnak. Egyszerűen látszik, hogy a magok metszetre-únióra zárt rendszert alkotnak. Valamely X magra jelölje c(X) az X elhagyásával keletkező komponensek számát. Nyilván c(V) = 0 és c(∅) = 1.

11.2 LEMMA A magokon értelmezett c függvény szupermoduláris.

Biz. Legyen ĉ(X) := c(V − X). Elegendő azt belátni, hogy d(X, Y) = 0 esetén a szupermodularitási egyenlőtlenség fennáll ĉ-re. Tekintsük az X és Y halmazok által feszített élek E(X) és E(Y) halmazát. Miután d(X, Y) = 0,

E(X ∪ Y) = E(X) ∪ E(Y) és E(X ∩ Y) = E(X) ∩ E(Y)  (11.1)

. Jelölje r a irányítatlan értelemben vett gráf körmatroidjának rangfüggvényét. Ez persze szubmoduláris és r(X) = |X| − ĉ(X). Ezt (11.1)-gyel összevetve ĉ szupermodularitása következik. •

Legyen c′(X) ugyanaz, mint c(X), azzal az eltéréssel, hogy c′(∅) = 0. Ekkor c′ metsző szupermoduláris. Rögtön látszik, hogy egy F ⊆ E kötésre és X magra δ_{F} (X) ≥ c′(X), ahol δ_{F} (X) az X-ből kilépő F -beli élek számát jelöli. (Azért kell a c helyett a c′-vel dolgoznunk, hogy ez a kijelentés érvényes legyen.)

Egy X magot illetve a hozzá tartozó Δ(X) irányított vágást pontosnak hívunk (F -re nézve), ha c′(X) = δ_{F} (X). Amennyiben δ_{F} (X) = 1, 1-pontos magról ill. vágásról beszélünk. Látható, hogy minden pontos vágás felbomlik diszjunkt 1-pontos vágások úniójára (éspedig a G − X komponensei által meghatározott vágásokra). A definícióból adódóan V mindig pontos. A szokásos technikával igazolható, hogy:

11.3 LEMMA Metsző pontos magok metszete és úniója pontos.

Ebből rögtön következik, hogy egy v pontot tartalmazó pontos halmazok B(v) metszete pontos. A B(v) halmaz tehát a v-t tartalmazó egyértelmű legszűkebb pontos halmaz.

Feladat Igazoljuk, hogy B(u) egyenlő a u-t tartalmazó 1-pontos magok metszetével. Adjunk algoritmust B(u) meghatározására.

(A 11.3 lemmából az is rögtön következik, hogy egy pontos halmazokból álló összefüggő hipergráf ponthalmaza is pontos.)

Az algoritmus egy egy teszőleges F kötésből indul ki (ami kezdetben lehet egy feszítő fa). Az általános lépésben vagy talál egy kisebb kötést, vagypedig |F | élidegen irányított vágást. Készítsünk el egy G′ = (V, E′) segédgráfot, az élein egy d költség-függvénnyel, a következőképpen. E minden éle E′-höz tartozik és a költsége +1. Az F elemeit megfordítva tegyük E′-be és ezen fordított élek költsége legyen −1. Végül minden v pontból vezessünk B(v) minden pontjába egy 0 költségű ún. ugró élt. (Ebből következik, hogy minden eredeti él megfordítottja ugró él lesz.)

A közismert algoritmussal, döntsük el, hogy létezik-e G′-ben a d költség-függvényre nézve negatív kör. Keressünk egyet, ha van, illetve keressünk egy π megengedett (egészértékű) potenciált, ha nincs.

1. ESET G′-ben nincs negatív kör, azaz létezik π megengedett potenciál.

Mivel a π konstanssal történő eltolása a megengedettséget nem befolyásolja, feltehető, hogy π minimális értéke 0. Legyen V_{i} := {v : π(v) ≤ i}. Ekkor V_{i}-ből nem lép ki ugró él, mert ha uv ilyen volna, akkor π(v) > π(u), azaz π(v)−π(u) > 0 = d(uv), ellentétben a π megengedettségével. Miután eredeti él fordítottja mindig ugró él, következik, hogy eredeti él nem lép be V_{i}-be, azaz V_{i} mag.

Tetszőleges uv ∈ E él legfeljebb egy V_{i} halmazból léphet ki, hiszen uv benne van E′-ben +1 költséggel, tehát π(v) − π(u) ≤ 1. Tehát a V_{i} halmazok páronként élidegen vágásokat határoznak meg.

Bármely uv ∈ F él pontosan egy V_{i} halmazból lép ki, hiszen vu benne van E′-ben -1 költséggel, és így π(u) − π(v) ≤ d(vu) = −1, vagyis π(v) − π(u) ≥ 1, a másik irányú egyenlőtlenséget pedig már az előbb minden uv ∈ E élre láttuk.

11.4 LEMMA A V_{i} maghoz tartozó Δ(V_{i}) vágás felbontható 1-pontos diszjunkt irányított vágások úniójára.

Biz. Miután V_{i}-ből nem lép ki ugró él, minden v ∈ V_{i} pontra B(v) ⊆ V_{i}, és ezért a {B(v) : v ∈ V_{i}} hipergráf komponenseinek A_{1}, …, A_{l} ponthalmazai a V_{i} partícióját alkotják. Amint feljebb megjegyeztük, mindegyik A_{j} pontos, továbbá az Δ(A_{j}) vágások particionálják a Δ(V_{i}) vágást. Miután minden pontos vágás diszjunkt 1-pontos vágások úniója, a lemma következik. •

Ha tehát az első eset áll fenn, akkor megtaláltunk pontosan |F | darab páronként élidegen irányított vágást.

2. ESET A G′ segédgráfban létezik negatív kör.

Legyen C olyan negatív kör, amelynek a legkevesebb éle van. Itt a minimalitást csak annyiban fogjuk használni, hogy nincs C-nek két olyan nem egymást követő a, b pontja, amelyekre a-ból b-be vezet ugró él és a körön a b-től a-ig vezető P ív költsége negatív. Ilyen ugró él létezése esetén ugyanis P + ab egy kisebb élszámú negatív kört adna.

11.5 LEMMA A C ugró élei elrendezhetők egy olyan e_{1} = u_{1}v_{1}, e_{2} = u_{2}v_{2}, …, e_{k} = u_{k}v_{k} sorba, hogy semelyik u_{i}-ből nem vezet ugró él v_{j}-be ahol i < j.

Biz. C minden ugró élének feleltessünk meg egy pontot és valamely x pontból egy másik y-ba vezessünk élt, ha az x-hez tartozó ugró él tövéből vezet ugró él az y-hoz tartozó ugró él fejébe. Amennyiben az így kapott digráf aciklikus, úgy pontjai sorba rendezhetők hogy minden él a sorrendben visszefelé mutat, és egy ilyen sorrend éppen a lemma által előírt sorrendet adja.

Ha a digráf tartalmaz irányított kört, az azt jelenti, hogy C bizonyos ugró élei ciklikusan sorbarendezhetők: f_{1} = s_{1}t_{1}, f_{2} = s_{2}t_{2}, …, f_{m} = s_{m}t_{m} úgy, hogy s_{i}t_{j+1} ugró él (ahol t_{m+1} = t_{1}). Legyen C_{i} a C körnek az az íve amely t_{i+1}-ből vezet s_{i}-be. A C-re tett minimalitási feltevés alapján C_{i} költsége nemnegatív.

Könnyen látható , hogy a C minden nem-ugró éle ugyanannyi C_{i} ívhez tartozik. Jelöljük ezt a számot t-vel (t > 0). Ebből következik, hogy a C költségének t-szerese a C_{i} ívek költségének összege, ami nemnegatív, ellentétben a C kör negatív voltával. •

Módosítsuk F -t a következőképpen. Hagyjuk ki belőle a C ∩ F elemeit és vegyük hozzá C − F -nek az eredeti gráfhoz tartozó éleit. A keletkezett halmazt jelölje F′. Miután C negatív kör volt, |F′| < |F |.

11.6 LEMMA Az előbb definiált F′ élhalmaz kötést alkot. .

Biz. Egy X mag többlete legyen γ(X) := δ_{F} (X) − c′(X). Ez mindig nemnegatív, hiszen F kötés, és éppen akkor 0, ha X pontos. Jelölje δ^{u}(X) a C kör azon ugró éleinek a számát melyek X-ből kilépnek. δ^{u}(X) szerinti indukcióval belátjuk, hogy

γ(X) ≥ δ^{u}(X).

Az állítás δ^{u}(X) = 0 semmitmondó, így legyen δ^{u}(X) > 0 és legyen e_{i} = u_{i}v_{i} a C-nek az az ugró éle, amely kilép X-ből és a 11.5 lemmában megadott sorrendben a legkisebb indexű. Legyen B := B(u_{i}). Ha most u_{j}v_{j} egy másik ugró éle C-nek, amely kilép X-ből, akkor j > i, és állítjuk, hogy v_{j} ∉ B. Ha ugyanis v_{j} B-ben volna, akkor u_{i}v_{j} is ugró él lenne, ellentétben a sorrendezés tualajdonságával. Így tehát δ^{u}(X ∪ B) = δ^{u}(X) − 1. Most γ(X) + 0 = γ(X) + γ(B) ≥ γ(X ∩ B) + γ(X ∪ B) ≥ 1 + γ(X ∪ B) ≥ 1 + δ^{u}(X ∪ B) = δ^{u}(X), ahol az utolsó egyenlőtlenség az indukciós feltevésből adódik. Ebből kapjuk, hogy δ_{F′}(X) ≥ δ_{F} (X) − δ^{u}(X) ≥ c′(X). • •

12. ÚTRENDSZER GENERÁLÁSA: GYŐRI TÉTELE

Az alábbiakban algoritmikus bizonyítást adunk Győri tételére, amelyre a Válogatott fejezetek c. előadáshoz írott jegyzet 6. részében már adtunk nem konstruktív bizonyítást. A szükséges jelölések is ott találhatók meg, a tétel kimondását megismételjük.

12.1 TÉTEL [Győri Ervin] A P út részútjainak bármely F családjára fennáll σ(F) = γ(F).

Biz. Csak a nem-triviális σ ≥ γ egyenlőtlenséget igazoljuk.

Az algoritmus három fázisból áll. Az elsőben az L_{F}-nek kiválasztunk egy keresztezés-mentes K részrendszerét. A második fázisban Dilworth tételt alkalmazzuk K-ra és az ismert algoritmus segítségével (amely a Dilworth tételnek Kőnig tételre való visszavezetésén és ezáltal az alternáló utas módszeren alapul) K-nak meghatározunk egy maximális I független részét valamint egy minimális lánc-felbontását. A láncfelbontás irányított élek egy olyan F rendszerének felel meg, amelyek lefogják az K-ban szereplő valamennyi halmazpárt. Az algoritmus harmadik fázisában F -t átalakítjuk úgy, hogy elemszáma ne változzék és L_{F}-nek minden tagját lefogja.

1. FÁZIS Végigmegyünk a P út élein az e_{1}, …, e_{n} sorrendben és az L_{F} tagjait két csoportba soroljuk, K-ba és T -be. Kezdetben mindkét csoport üres. Az T tagjaira a későbbiek során, mint tiltott párokra hivatkozunk.

Az általános lépésben tekintjük az e_{i} élt és az összes (I_{1}, e_{i}), (I_{2}, e_{i}), …, (I_{k}, e_{i}) lényeges párt. Mivel ezen párok lényegesek, az I_{j} utak élhalmazai egymást nem tartalmazzák és a végpontjaik páronként különbözőek. Következésképp feltehető, hogy ezen utak úgy vannak indexelve, hogy b(I_{1}) < … < b(I_{k}) és j(I_{1}) < … < j(I_{k}). Mindegyik (I_{j}, e_{i}) nem tiltott párt bevesszük K-ba, és egy ilyen bevételkor letiltjuk (azaz T -be tesszük) az összes olyan (I_{h}, e_{l}) lényeges párt, amelyre j < h ≤ k, l > i és e_{l} ∈ I_{j}.

A konstrukcióból könnyen látszik, hogy az 1. fázis végén kapott K rendszer keresztezés-mentes lesz.

2. FÁZIS Alkalmazzuk a Dilworth tételt K-ra és számítsunk ki egy I ⊆ K független rész-rendszert és K-nak egy minimális lánc-felbontását, amely egy olyan F élrendszernek felel meg, amely K minden tagját lefogja, és amelyre |F | = |I|.

3. FÁZIS Amennyiben F lefogja L_{F} valamennyi tagját, akkor készen vagyunk. Tegyük fel tehát, hogy van olyan (I, f) lényeges pár, amelyet F nem fog le. Válasszuk (I, f)-t úgy, hogy (I, f)^{−} minimális legyen. Mivel (I, f)-t F nem fogja le, így (I, f) tiltva lett (azaz T -be került), vagyis van a K-nak olyan (J, e) tagja, amelyre {e, f} ⊆ I ∩ J, e megelőzi f-t és J megelőzi I-t. Válasszunk egy ilyen (J, e) párt úgy, hogy (J, e)^{+} minimális legyen.

Az (I, f) és (J, e) párok lényegesek, így mind az (I, e), mind a (J, f) pár lényeges. Az (I, f)^{−} minimalitásából következik, hogy F lefogja az ((I, e)^{−}, (I, e)^{+}) párt.

12.2 LEMMA (J, f) ∈ K.

Biz. Amennyiben (J, f) tiltott volna, úgy az algoritmus előírása miatt volna egy (J′, e′) tagja K-nak úgy, hogy J′ megelőzi J-t és {e′, f} ⊆ J′ ∩ J. Nem lehet, hogy e′ megelőzi e-t, mert akkor (J, e) is tiltott lett volna, holott (J, e) ∈ K. Ezek szerint e′ vagy egyenlő e-vel, vagy követi e-t. De ekkor (J′, e′)^{+} ⊂ (J, e)^{+}, ellentétben (J, e)^{+} minimális választásával. •

Ezek alapján F lefogja mind (I, e)-t, mind (J, f)-t. Jelölje az (I, e)-t lefogó élt f_{1} = x_{1}y_{1} és a (J, f)-t lefogó élt f_{2} = x_{2}y_{2}. Legyen f′_{1} := x_{1}y_{2}, f′_{2} := x_{2}y_{1} és legyen F′ := F − {f_{1}, f_{2}} ∪ {f′_{1}, f′_{2}}. Mivel f_{1} és f_{2} sem fogja le (I, f)-t, a szóbanforgó pontok az alábbi sorrendben követik egymást.

b(J) ≤ x_{2} < b(I) ≤ x_{1} ≤ b(e) < y_{1} ≤ b(f) < y_{2} ≤ j(J) < j(I).  (12.1)

Ebből rögtön adódik, hogy az f′_{1} él lefogja az eddig lefogatlan (I, f) párt.

12.3 LEMMA Ha F lefogott egy (I′, f′) lényeges párt, akkor F′ is lefogja.

Biz. Ez nyilván így van, ha (I′, f′)-t az F -nek egy f_{1}-től és f_{2}-től különböző tagja fogta le. Az is rögtön látszik, hogy minden f_{2} által legfogott párt f′_{1} és f′_{2} valamelyike lefogja. Tehát az egyetlen problematikus eset az, amikor (I′, f′)-t az F -ből egyedül az f_{1} él fogja le.

Tegyük fel indirekt, hogy f′_{1} és f′_{2} egyike sem fogja le (I′, f′)-t. Abból hogy f′_{1} nem fogja le (I′, f′)-t, következik, hogy j(I′) < y_{2}. Abból hogy f′_{2} nem fogja le (I′, f′)-t, következik, hogy b(I′) > x_{2}. Ezért e ∈ I′ ⊆ J, ami ellentmond annak, hogy (J, e) lényeges pár. •

A lemmából kapjuk, hogy F′ szigorúan több lényeges párt fog le, mint amennyit F lefogott. Így a fenti átcserélési műveletet legfeljebb annyiszor alkalmazva, mint ahány tagja az input útcsaládnak van, L_{F}-nek egy olyan lefogását kapjuk, amelynek elemszáma megegyezik az I független rész-rendszer elemszámával. • •

Megjegyzés A fenti algoritmusnak és bizonyításnak egy másik változata hangzott el az előadáson. Eltérés a harmadik fázisban van. A módosított 3. fázisban csupán a K-val és annak F lefogásával foglalkozunk. Amennyiben van F -nek két olyan f_{1} = x_{1}y_{1} és f_{2} = x_{2}y_{2} éle, amelyekre

x_{2} < x_{1} < y_{1} < y_{2}

és F′ := F − {f_{1}, f_{2}} ∪ {f′_{1}, f′_{2}} is lefogja K-t, úgy cseréljük ki F -t F′-re. Könnyen látszik hogy legfeljebb n^{3} ilyen egymás utáni csere létezhet.

Tegyük most fel, hogy F olyan lefogása K-nak, amelyben már ilyen csere nem hajtható végre.

LEMMA Ha F olyan fedése K-nak, amelyre nézve a fenti csere már nem hajtható végre, akkor F lefogja az összes lényeges párt.

Biz. Tegyük fel indirekt, hogy F nem fogja le az (I, i) lényeges párt. Válasszuk ezt úgy, hogy |(I, i)^{−}| minimimális. Mivel (I, i) nincs lefogva, így nem tartozik K-hoz, azaz létezik az 1. Fázis szabálya szerint egy olyan (J, j) tagja K-nak amelyre j megelőzi i-t és (J, j) keresztezi (I, i)-t. Válasszunk egy ilyen (J, j) párt úgy, hogy |(J, j)^{+}| minimális. Miután (I, i) és (J, j) lényegesek, a (I, j) és (J, i) párok is azok. Az |(I, i)^{−}| minimalitásából következik, hogy F lefogja (I, j)-t, azaz van olyan e_{1} = x_{1}y_{1} ∈ F él, amely lefogja (I, j)-t.

ÁLLÍTÁS (J, i) ∈ K.

Biz. Ha indirekt (J, i) a T -hez tartozna, akkor az 1. Fázis szabálya szerint létezik egy olyan (J′, j′) tagja K-nak, amelyre j′ megelőzi i-t és (J′, j′) keresztezi (J, i)-t. A j′ él nem előzheti meg j-t, mert különben (J′, j′) keresztezné (J, j)-t és emiatt (J, j) is T -hez tartozna. emiatt vagy j′ = j vagy pedig j megelőzi j′-t. Mindkét esetben (J′, j′) keresztezi (I, i)-t és (J′, j′)^{+} ⊂ (J, j)^{+}, ellentmondásban a |(J, j)^{+}|. minimális választásával. •

Mivel F lefogja K-t és (J, i) ∈ K, az előbbi állítás miatt van olyan e_{2} = x_{2}y_{2} eleme C-nek, amely lefogja (J, i)-t. Mivel sem e_{1} sem nor e_{2} nem foogja le (I, i)-t, azt kapjuk, hogy we have

b(J) ≤ x_{2} < b(I) ≤ x_{1} ≤ b(j) < y_{1} ≤ b(i) < y_{2} ≤ j(J) < j(I).

A lemma feltétele alapján F -ben nincsen két átcserélhető elem, így kell léteznie olyan (K, k) tagnak Kban, amelyet F′ nem fog le, ekkor (K, k)-t szükségképpen e_{1} lefogja, míg e′_{1} és e′_{2} nem. Ezért b(J) ≤ x_{2} < b(K) ≤ x_{1} < y_{1} ≤ j(K) < y_{2} ≤ j(J), azaz, j ∈ K ⊂ J, ellentmondásban a feltevéssel, hogy (J, j) lényeges.

• •