Szubmoduláris függvények és poliédereik

Maróti Gábor

Témavezető: Frank András egyetemi tanár

Tartalomjegyzék

1. Bevezetés 2 1.1. Előszó . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2. Jelölések . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Szubmoduláris függvények 5 2.1. Halmazrendszerek . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2. Szubmoduláris függvények . . . . . . . . . . . . . . . . . . . . . 6

3. Polimatroidok és rokonaik 8 3.1. (Poli)matriodok . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2. Mohó algoritmus részbenrendezéseken . . . . . . . . . . . . . . . 12

4. Gráfok és poliéderek 17 4.1. Szubmoduláris áram poliéderek . . . . . . . . . . . . . . . . . . 17 4.2. Háló-mátrixok . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.3. Lefogási poliéderek . . . . . . . . . . . . . . . . . . . . . . . . . 22

5. Háló-poliéderek 27 5.1. Háló-poliéderek alapvető tulajdonságai . . . . . . . . . . . . . . 27 5.2. Greene és Greene – Kleitman tételei . . . . . . . . . . . . . . . . 32

6. Háló-mátrixok 35 6.1. Példák . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.2. Gyűrű-családok metszetei . . . . . . . . . . . . . . . . . . . . . 36

1. fejezet

Bevezetés

1.1. Előszó

Kombinatorikus problémák megfogalmazásánál és vizsgálatánál gyakran bukkannak fel szubmoduláris függvények. A V véges halmaz részhalmazain értelmezett b függvényt szubmodulárisnak nevezzük, ha X, Y ⊆ V esetén

b(X) + b(Y) ≥ b(X ∩ Y) + b(X ∪ Y).  (1.1)

A szubmoduláris függvények −1-szereseit szupermodulárisnak mondjuk. Ilyen függvényekre tehát az (1.1)-beli egyenlőtlenség fordítottját követeljük meg.

Szubmoduláris függvények segítségével számos egész koordinátájú csúcsokkal rendelkező (röviden egész) poliéder definiálható. Az egész tulajdonság igazolásakor legtöbbször a lineáris programozás dualitás-tétele és a teljes duális egészértékűség fogalma alkalmazható. Legyen A egész mátrix, b egész vektor. Az Ax ≤ b egyenlőtlenség-rendszer teljesen duálisan egészértékű (TDI), ha tetszőleges egész c vektort választva, amire a max cx, Ax ≤ b LP-feladat célfüggvénye korlátos, a min by, yA = c y ≥ 0 duális feladatnak van egész optimumhelye. J. Edmonds és R. Giles tétele szerint ha Ax ≤ b TDI, akkor a {x : Ax ≤ b} poliéder egész ([3]). Az egész poliéderek azért hasznosak, mert a kombinatorikus optimalizálási problémát a lineáris programozás nyelvére lefordítva , és az LP-feladatot megoldva (vagy az egész megoldás létezésének tényét felhasználva) a kapott egész optimum közvetlen kombinatorikai tartalommal bír. Ilyen gondolatmenetekkel találkozhatuunk a 3. fejezetben és az 5.2 szakaszban.

Szubmodularitás nem csak a halmazelméleti ∩, ∪ műveletekre értelmezhető. Ha az A halmazon adott két kétváltozós művelet, amelyeket ∧, ∨ vagy ⊓, ⊔ jelölhet, akkor (1.1) mintájára b: A → ℝ ∪ {±∞} szubmoduláris, ha pl. tetszőleges x, y ∈ A esetén

b(x) + b(y) ≥ b(x ∧ y) + b(x ∨ y).

Ezen absztrakt megfogalmazás nyújt lehetőséget részbenrendezések láncaival és antiláncaival kapcsolatos vizsgálatokra (3.2, 5.2 szakaszok) ill. háló-poliéderek definiálására.

A jelölések rögzítése után a dolgozat második fejezete a szubmodularitás különböző változatainak pontos definícióit tartalmazza. A további fejezetek egy-egy poliéder-osztályt tekintenek át.

A 3. fejezetben a matroidok ismert példáján keresztül megismerjük a kikeresztezési technikát, majd algoritmikus bizonyítást keresünk polimatroidok egyfajta általánosítására. U. Faigle és W. Kern [4] cikkükben leírnak egy kétfázisú mohó módszert. A 3.2 szakaszban megmutatjuk, hogy az algoritmmus más, hasonló feladatra is optimális megoldást szolgáltat, és néhány példával illusztráljuk a tételek bizonyos feltételeinek fontosságát.

A 4. fejezet a Gráfok és poliéderek címet viseli. Ezen dolgozatban nem vállalkozhatunk a számtalan felvetülő kérdéskör vizsgálatára. Ehelyett két, a dolgozat többi fogalmához jól kapcsolódó poliéder-osztályról látjuk be, hogy szubmoduláris áram poliéderek. A háló-poliéderekre vonatkozó eredmény lényegében A. Schrijvertől származik ([9]), itt kissé általánosabban igazoljuk majd. A lefogási poliéderekhez kapcsolódó tétel A. Schrijver és Frank András egyegy ötletén alapszik, és újfajta algoritmus lehetőségét veti fel irányított gráfok gyökeres összefüggőségének növelésére.

A további fejezetek már nem tartalmaznak új eredményt, a vonatkozó irodalom összefoglalását nyújtják. Az 5. fejezetben A. J. Hoffman és D. E. Schwarz [8] ill. H. Gröflin és A. J. Hoffman [7] cikkei alpján a háló-poliédereket és a szervesen kapcsolódó konzekutív függvényeket tekintjük át. Alkalmazásként levezetjük Greene és Greene – Kleitman tételeit.

A 6. fejezetben M. Cochand, A. Gaillard és H. Gröflin [1] és [2] munkáinak felhasználásával háló-mátrixok legfontosabb tulajdonságaival ismerkedünk meg. Először háló-mátrixok egyfajta reprezentációját igazoljuk, majd megadjuk a sorok konvex burkának poliéderes leírását.

Ezúton szeretnék köszönetet mondani témavezetőmnek, Frank Andrásnak, aki előadásival felkeltette érdeklődésemet a terület iránt, és feladataival, tanácsaival irányt mutatott a szakdolgozat elkészítéséhez.

1.2. Jelölések

A dolgozatban a alábbi jelöléseket fogjuk használni. Ha a további fejezetekben egy-egy szimbólumot nem definiálunk, akkor az itt megadott jelentés az irányadó.

V ≠ ∅ véges alaphalmaz, |V | = n, hatványhalmazát 2^{V} jelöli, V részhalmazai általában X, Y, Z, … lesznek, V elemeire az u, v, … betűket használjuk. χ_{X} az X halmaz karakterisztikus függvényét jelenti. Az X és Y halmazok diszjunkt unióját X ∪^{∗} Y, halmazelméleti különbségét X − Y, az X ∪ {v} halmazt pedig a rövidség kedvéért X + v jelöli. Az f: V → ℝ ∪ {±∞} ill. f: 2^{V} → ℝ ∪ {±∞} függvényekről feltesszük, hogy csak egyféle végtelen értéket vesznek fel. Az x betű x: V → ℝ (gráfoknál x: E → ℝ) függvényt takar, a nemnegatív értékkészletet röviden x ≥ 0 jelzi. 1: V → ℝ, 1(v) = 1 az azonosan 1 függvényt jelenti. Az f: V → ℝ függvény és az f ∈ ℝ^{V} vektor jelölést egyenértékűnek fogjuk tekinteni, az értékekre az f(v) ill. f_{v} szimbólumokkal hivatkozunk. x, y ∈ ℝ^{V} vektorokra x ≤ y legyen a szokásos részbenrendezés: minden komponensben x(v) ≤ y(v), xy pedig jelentse a két vektor skaláris szorzatát. A dolgozatban a sor-, és oszlopvektorokat nem jelezzük külön, egyedül vektorok és márixok szorzásánál adódhat zavar. Konvenciónk szerint az Ax szorzatokban x oszlopvektor, az yA szorzatokban y sorvektor lesz. (Ez összhangban van a skalárszorzat xy jelével is.) Az A mátrix i-dik sorát ill. j-dik oszlopát rendre iA ill. A_{j} jelöli. A mátrix elemeire a szokásos A_{i,j} jelölést használjuk. A b, p, m betűk rendre (valamilyen értelemben) szubmoduláris, szupermoduláris, illetve moduláris függvényt jelentenek majd.

Tetszőleges f: V → ℝ ∪ {±∞} függvény kiterjeszthető 2^{V} → ℝ ∪ {±∞} halmazfüggvénnyé az alábbi természetes definícióval:

f(Z) = ∑ (f(v) : v ∈ Z).

A kiterjesztésre tehát nem alkalmazunk új jelölést.

A G = (V, E) irányítatlan gráfban d(Z) a fokszámfüggvény, azaz a Z és V − Z közti élek száma; az x élsúlyozás mellett

d_{x}(Z) = ∑ (x(e) : a Z és V − Z közti éleken).

Irányított gráfban ϱ(Z) a befok-függvény: a V − Z-ből Z-be futó élek száma, és hasonlóan értelmezhető a súlyozott változat:

ϱ_{x}(Z) = ∑ (x(e) : e = uv, u ∈ V − Z, v ∈ Z).

Az analóg kifok-függvényt δ ill. δ_{x} jelöli.

Szubmoduláris függvények

Ebben a fejezetben ismert fogalmak és tételek szerepelnek. A 2.2 szakaszbeli tulajdonságokat csak egészértékű függvényekre definiáljuk. Ebben a fejezetben akár valósak is lehetnének. Később azonban egésznek szánt poliéderek leíró rendszereiben szerepelnek majd, ott fontos lesz az ”egészség”.

2.1. Halmazrendszerek

2.1 Definíció. Az X, Y ⊆ V halmazok metszők, ha X ⊈ Y, Y ⊈ X, és X ∩ Y ≠ ∅.

X és Y keresztezők, ha metszők, és X ∪ Y ≠ V.

2.2 Definíció. Az ℱ ⊆ 2^{V} halmazrendszer keresztező, ha bármely két X, Y ∈ ℱ keresztező halmazra X ∩ Y, X ∪ Y ∈ ℱ.

Az ℱ ⊆ 2^{V} halmazrendszer metsző, ha bármely két X, Y ∈ ℱ metsző halmazra X ∩ Y, X ∪ Y ∈ ℱ.

ℱ lamináris, ha nincs két metsző tagja.

ℱ keresztezésmentes, ha nincs két keresztező tagja.

2.3 Tétel. [J. Edmonds – R. Giles] Minden ℱ lamináris halmazrendszerhez létezik F = (V^{∗}, E^{∗}) fenyő, továbbá φ: V → V^{∗} leképezés és ψ: ℱ → E^{∗} bijekció úgy, hogy minden e ∈ E^{∗} esetén ψ^{−1}(e) = φ^{−1}(V_{e}), ahol V_{e} az e él elhagyásakor keletkező azon komponens, ahová e belép.

2.4 Következmény. Legyen ℱ lamináris rendszer a G = (V, E) irányított gráf csúcshalmazán. Ekkor az A ∈ {0, 1}^{ℱ×E},

A_{Z,e} = 1 ⟺ e belép Z-be

mátrix hálózati mártix, tehát teljesen unimoduláris. Speciálisan, ℱ incidenciamátrixa teljesen unimoduláris.

2.2. Szubmoduláris függvények

2.5 Definíció. A b: 2^{V} → ℤ ∪ {+∞} halmazfüggvény szubmoduláris, ha tetszőleges X, Y ⊆ V esetén

b(X) + b(Y) ≥ b(X ∩ Y) + b(X ∪ Y).  (2.1)

A p függvény szupermoduláris, ha −p szubmoduláris.

Az m függvényt modulárisnak nevezzük, ha szubmoduláris és szupermoduláris.

Akkor is értelmes definícióhoz jutunk, ha a fenti egyenlőtlenségeket csak egy ℱ ⊆ 2^{V} ∩, ∪-zárt halmazrendszerre követeljük meg. Szóhasználatunk ekkor: szubmoduláris az ℱ-en. ℱ-en szubmoduláris függvény kiterjeszthető 2^{V} -re szubmoduláris függvényként: az ℱ-en kívüli halmazokra legyen a függvényérték +∞.

Egyszerűen látható, hogy moduláris függvényt meghatároznak az egyelemű halmazokon felvett értékei:

m(Z) = ∑ (m(v) : v ∈ Z) + m(∅) ∀Z ⊆ V.

Szubmoduláris függvényekkel gyakran találkozhatunk kombinatorikus struktúrákban.

2.6 Példa. Tetszőleges irányítatlan gráfban, x nemnegatív élsúlyozás mellett d ill. d_{x} szubmoduláris. Irányított gráfokban ugyanez igaz ϱ, ϱ_{x}, δ, δ_{x}-re.

Bizonyítás. Mivel d = d_{1}, ϱ = ϱ_{1}, δ = δ_{1}, ezért elég a súlyozott esetet igazolni. Jelölje d_{x}(X, Y) az X − Y és Y − X között vezető irányítatlan vagy (valamelyik irányban) irányított élekhez rendelt x értékek összegét. Könnyű belátni, hogy

d_{x}(X) + d_{x}(Y) = d_{x}(X ∩ Y) + d_{x}(X ∪ Y) + 2d_{x}(X, Y)
ϱ_{x}(X) + ϱ_{x}(Y) = ϱ_{x}(X ∩ Y) + ϱ_{x}(X ∪ Y) + d_{x}(X, Y)
δ_{x}(X) + δ_{x}(Y) = δ_{x}(X ∩ Y) + δ_{x}(X ∪ Y) + 2d_{x}(X, Y)

Ebből már következik az állítás. ■

2.7 Példa. Közismert, hogy egy független halmazaival adott M = (V, ℱ) matroid

r: 2^{V} → ℤ, r(Z) = max (|X| : X ⊆ Z, X ∈ ℱ)

rangfüggvénye szubmoduláris.

Az 2.5 Definíció-ban leírt tulajdonságú függvényeket teljesen szubmodulárisnak stb. is nevezzük, utalva arra, hogy ezekeből az erős feltételekből engedve is hasznos fogalmakat kapunk.

2.8 Definíció. Az ℱ metsző ill. keresztező rendszeren adott b: ℱ → ℤ∪{+∞} metszőn ill. keresztezően szubmoduláris, ha (2.1) fennáll minden metsző ill. keresztező ℱ-beli halmazpárra.

p: ℱ → ℤ∪{−∞} metszőn ill. keresztezően szupermoduláris, ha −p metszőn ill. keresztezően szubmoduláris.

Metszőn ill. keresztezően szubmoduláris függvény is kiterjeszthető 2^{V} -re metszőn ill. keresztezően szubmoduláris függvénnyé a már látott módon, a külső elemekre +∞ értékkel.

2.9 Definíció. Jelölje f^{∨}(Z) := min {∑ (f(X_{i})) : Z = ∪X_{i} partíció} az f függvény alsó reszletjét, f^{∧}(Z) := max {∑ (f(X_{i})) : Z = ∪X_{i} partíció} pedig az f függvény felső reszletjét.

2.10 Állítás. Ha b metszőn szubmoduláris 2^{V} -n, akkor b^{∨} teljesen szubmoduláris, és

{x : x(Z) ≤ b(Z) ∀Z ⊆ V } = {x : x(Z) ≤ b^{∨}(Z) ∀Z ⊆ V } .

Ha p metszőn szupermoduláris 2^{V} -n, akkor p^{∧} teljesen szupermoduláris, és

{x : x(Z) ≥ p(Z) ∀Z ⊆ V } = {x : x(Z) ≥ p^{∧}(Z) ∀Z ⊆ V } .

Bizonyítás nélkül megemlítjük a keresztezően szubmoduláris/szupermoduláris függvényekre vonatkozó eredményt. Ehhez megelőlegezzük a 3.6 Definíció jelölését: legyen f: 2^{V} → ℤ ∪ {±∞} esetén

B(f) := {x ∈ ℝ^{V} : x(V) = f(V), x(Z) ≤ f(Z) ∀Z ⊆ V } .

2.11 Tétel. Ha b keresztezően szubmoduláris 2^{V} -n, és B(b) ≠ ∅, akkor létezik b^{↓} teljesen szubmoduláris függvény, amelyre B(b) = B(b^{↓}).

A szubmodularitás fogalmának egy további általánosítására a 4.2 szakaszban tárgyaljuk.

Végül emlékeztetünk a bevezetőben tett megjegyzésünkre, hogy a szubmodularitás tetszőleges alaphalmazra és rajta értelmezett bináris műveletpárra definiálható.

Polimatroidok és rokonaik

3.1. (Poli)matroidok

A dogozat címében és a bevezetőben tett ígéretünkhöz híven poliédereket fogunk definiálni szubmoduláris függvények segítségével. Kiindulásképpen bebizonyítjuk a 3.1 Tétel-t. A bizonyítás sokkal általánosabb poliéder-osztály, pl. a háló-poliéderek esetére is átvihető. A későbbiekben a hasonló tételek igazolásakor csak utalunk az alább részletezettekre. Sőt, az ezen dolgozatban vizsgált poliéderek valamennyien háló-poliéderek, így megtehetnénk, hogy rögtön az általános esetben bizonyítjuk a tételt, és ezután haladunk a speciális esetek felé. Ebben a dolgozatban a másik utat választottuk: előbb a speciális osztályokat tekintjük át.

3.1 Tétel. Legyen M = (V, ℱ) martoid r rangfüggvénnyel. Ekkor a

P = {x ∈ ℝ^{V} : x ≥ 0, x(Z) ≤ r(Z) ∀Z ⊆ V }

poliéder egész, csúcsai éppen V független részhalmazai.

Bizonyítás. Az egyelemű halmazok feltételeiből

P ⊆ {x ∈ ℝ^{V} : 0 ≤ x ≤ 1} .

A független halmazok karakterisztikus vektorai mind elemei lesznek P -nek, hiszen F ∈ ℱ, x = χ_{F}, Z ⊆ V esetén

x(Z) = |F ∩ Z| ≤ r(Z).

Ezek a karakterisztikus vektorok extremális pontjai (csúcsai) P -nek, hiszen még egységkockának is extremális pontjai. Azt kell tehát még megmutatni, hogy a poliéder minden csúcsa egész, és hogy éppen a függelten halmazok karakterisztikus vektorai.

Először azt látjuk be, hogy a leíró egyenlőtlenségrendszer TDI. Legyen a rendszer mátrixa A, és tekintsük adott c egész célfüggvény mellett a alábbi primál-duál feladatpárt:

max cx, Ax ≤ r, x ≥ 0,  (P)
min ry, yA ≥ c, y ≥ 0.  (D)

A célfüggvények most mindig korlátosak, legyen y duális optimum. Ha van olyan X és Y, amire y(X) > 0, y(Y) > 0, és egyik sem tartalmazza a másikat, akkor változtassuk meg y-t a következő módon.

Δ := min (y(X), y(Y)) ,
y(X) := y(X) − Δ, y(Y) := y(Y) − Δ,
y(X ∩ Y) := y(X ∩ Y) + Δ, y(X ∪ Y) := y(X ∪ Y) + Δ,

a többi halmazra y(Z) := y(Z). Ekkor y ≥ 0 továbbra is fennáll. Mivel a részhalmazok karakterisztikus függvényeire χ_{X} + χ_{Y} = χ_{X∩Y} + χ_{X∪Y}, így

(yA)_{v} = ∑ (y(Z) : v ∈ Z) = ∑ (y(Z) : v ∈ Z) +

+ Δ · (χ_{X∩Y} (v) + χ_{X∪Y} (v) − χ_{X}(v) − χ_{Y} (v)) = ∑ (y(Z) : v ∈ Z) =

= (yA)_{v} ≥ c(v)

szerint y is duál megengedett megoldás. Másrészt r szubmodularitásából

ry − ry = Δ · (r(X ∩ Y) + r(X ∪ Y) − r(X) − r(Y)) ≤ 0

alapján y is optimális.

Ezután az y szerinti pozitív halmazokra próbáljuk alkalmazni a fenti ”kikeresztezési” lépést, és így tovább, amíg csak találunk megfelelő X és Y halmazokat.

Az eljárás végességének bizonyításához tekintsük 2^{V} lexikografikus rendezését. Tegyük fel indirekt, hogy az eljárás nem áll meg. Ekkor van olyan lexikografikusan legnagyobb Z ⊆ V halmaz, amelyik végtelen sokszor változtat y-értéket. Mivel egymást nem tartalmazó X, Y esetén X ∪Y lexikografikusan nagyobb Xnél és Y -nál, ezért a Z-hez rendelt duális változó értéke egy időtől kezdve csak növekedhet. A (D) lineáris program mártixa és jobboldala egész elemekből áll, így feltehető, hogy a kiindulási y minden komponense racionális, \frac{1}{N} egész számú többszöröse. Ekkor minden Δ és minden további y koordinátái \frac{k}{N} alakú. Tehát y(Z) értéke végtelen sok alkalommal növekszik egyenként legalább \frac{1}{N} -nel, azaz y(Z) → ∞. Csakhogy a kikeresztezési lépések során ∑ (y(Z) : Z ⊆ V ) változatlan marad, és y ≥ 0, ami ellentmond y(Z) → ∞-nek.

Véges sok lépés után tehát {Z : y(Z) > 0} lamináris halmazrendszer lesz, másszóval a (D) feladat optimális megoldását kereshetjük olyan alakban, hogy y egy rögzített ℒ lamináris rendszeren kívül eltűnik. Az ℒ-en kívüli halmazokhoz tartozó sorokat törölhetjük a mátrixból. A visszamaradó A′ mátrix éppen ℒ incidencia-mátrixa, erről pedig tudjuk, hogy hálózati mátrix, következésképpen teljesen unimoduláris. Ezért az r′ = r|_{ℒ}, y′ ∈ ℝ^{ℒ} jelölések mellett a

min r′y, y′A′ ≥ c, y′ ≥ 0

feladatnak van egész optimumhelye, amiből nullákkal kiegészítve (D) egy egész optimumhelyét kapjuk. Ezzel beláttuk, hogy a tételbeli P poliéder egész.

Legyen végül x ∈ {0, 1}^{V} a P poliéder csúcsa, Z := {v ∈ V : x(V) = 1}. A Z halmazra vonatkozó (primál) feltételt használva:

r(Z) ≤ |Z| = ∑ (x(v) : v ∈ Z) = (Ax)_{Z} ≤ r(Z),

tehát Z független. ■

A 3.1 Tétel bizonyítása nem volt algoritmikus. Létezik azonban a tételt is bizonyító algoritmus: a maximális súlyú független részhalmaz keresésére szolgáló ”klasszikus” mohó algoritmus. A maximalizálandó célfüggvényről feltehető, hogy c_{1} ≤ c_{2} ≤ ⋯ ≤ c_{n}, V megfelelő elemei v_{1}, …, v_{n}. A módszer alapgondolata: a nagy súlyú elemeket próbáljuk meg beválasztani.

3.2 Algoritmus.

Mohó algoritmus matroidokon Z := ∅ Ciklus i := n-től 1-ig

Ha Z + v_{i} ∈ ℱ, akkor Z := Z + v_{i} Ciklus vége Algoritmus vége

Könnyen látható, hogy a végeredményként adódó Z maximális súlyú független halmaz lesz a matroidban, x = χ_{F} pedig a (P) feladat egész optimális megoldása, egyben a P poliéder csúcsa.

A matroidok mohó algoritmusát J. Edmonds általánosította polimatroidokra és szubmoduláris poliéderekre.

3.3 Definíció. A b: 2^{V} → ℤ ∪ {+∞} függvényt polimatroid-fu^{..}ggvénynek nevezzük, ha teljesen szubmoduláris, nemnegatív, és monoton növő: X ⊆ Y ⟹ b(X) ≤ b(Y).

Megjegyzés. Közismert, hogy az r: 2^{V} → ℤ pontosan akkor rangfüggvénye valamilyen matroidnak, ha polimatroid-függvény, és r(X) ≤ |X| ∀X ⊆ V.

3.4 Definíció. 1. Legyen b polimatroid-függvény. Ekkor a

P (b) = {x ∈ ℝ^{V} : x ≥ 0, x(Z) ≤ b(Z) ∀Z ⊆ V }

poliédert polimatroidnak nevezzük.

2. Legyen b szubmoduláris. Ekkor az

S(b) = {x ∈ ℝ^{V} : x(Z) ≤ b(Z) ∀Z ⊆ V }

poliédert szubmoduláris poliédernek nevezzük.

Egyszerűen látható, hogy a

max cx, x ∈ P (b) ill. x ∈ S(b)  (3.1)

fealdatokban c ≥ 0 feltehető (x ∈ S(b), c ≱ 0 esetén a célfüggvény nem korlátos, az x ∈ P (b) esetén pedig az optimális megoldásban c(v) < 0 ⟹ x(v) = 0).

Legyen most is c_{1} ≤ c_{2} ≤ ⋯ ≤ c_{n}, a pontok megfelelő sorrendje v_{1}, …, v_{n}. Ekkor a következő algoritmus megoldja a (3.1) feladatot:

3.5 Algoritmus.

Mohó algoritmus polimatroidokon y: 2^{V} → ℝ y := 0, c_{0} := 0, Z_{1} := V Ciklus i := 2-től n-ig Z_{i} := Z_{i−1} − v_{i−1} y(Z_{i}) := c_{i} − c_{i−1}

Ciklus vége

Ciklus i := n-től 1-ig

x(v_{i}) := b(Z_{i}) − ∑ (x(v_{j}) : j > i) Ciklus vége Algoritmus vége

Ekkor x primál megoldás, y duál megoldás, és teljesülnek az optimalitási feltételek. A bizonyítást – általánosabb feltételek mellett – a következő szakaszban részletezzük.

Azt kapjuk tehát, hogy a fent definiát poliéderek egészek. Ha a b-ről nem követelünk egészértékűséget, a 3.5 Algoritmus akkor is optimalizálja a megfelelő poliédert.

A polimatroidok ill. szubmoduláris poliéderek egész volta természetesen a 3.1 Tétel-beli eszközökkel is belátható. A 2.11 Tétel-lel egybevetve az is látható, hogy a 3.4 Definíció poliéderei akkor is egészek, ha b csak keresztezően szubmoduláris.

A 4. fejezetben, a szubmoduláris áram poliéderek vizsgálatához szükségünk lesz a bázispoliéder fogalmára.

3.6 Definíció. Legyen b: 2^{V} → ℤ szubmoduláris. Ekkor a

B(b) = {x ∈ ℝ^{V} : x(V) = b(V), x(Z) ≤ b(V) ∀Z ⊆ V }

poliédert bázispoliédernek nevezzük.

A 3.5 Algoritmus bizonyításából kiolvasható, hogy megoldja a

max cx, x ∈ B(b)

feladatot is, speciálisan B(b) egész.

3.2. Mohó algoritmus részbenrendezéseken

U. Faigle és W. Kern [4] munkájának tárgya az alább ismertetendő algoritmus. A cikkben ugyanez az algoritmus szerepel, helyességét a szerzők az alább leírt négy eset (3.12 és 3.13 Tétel állításai) közül csak egyre (3.13 Tétel 1. állítása) igazolták. Először néhány fogalmat vezetünk be.

Legyen P = (V, ≤) részbenrendezett halmaz. A Z ⊆ V halmaz lánc, ha bármely két eleme összehasonlítható, antilánc, ha semelyik két eleme sem hasonlítható össze. Az összes antiláncok családját 𝒜 jelöli. Az I ⊆ V halmaz ideál, ha u ∈ I, v ≤ u ⟹ v ∈ I, azaz ha ”lefelé zárt”. Ideálok halmazelméleti metszete és uniója is ideál, így az ideálok disztributív hálót alkotnak. Z ⊆ V esetén Z^{+} := {v ∈ Z : v maximális Z-ben}, ez antilánc lesz. Z ⊆ V esetén I(Z) := {v ∈ Z : ∃z ∈ Z v ≤ z} a Z által generált ideál.

3.7 Definíció. Legyen A, B ∈ 𝒜. Ekkor

A ≤ B ⟺^{def} I(A) ⊆ I(B)

A ∨ B := (I(A) ∪ I(B))^{+} A ∧ B := (I(A) ∩ I(B))^{+} A ⊔ B := A ∨ B A ⊓ B := (A ∧ B) ∩ (A ∪ B)

Megjegyzés. A ⊔ B = {v ∈ A ∪ B : v maximális A ∪ B-ben} A ⊓ B = {v ∈ A ∪ B : ∃a ∈ A, ∃b ∈ B v ≤ a, v ≤ b}

Egyszerűen igazolható, hogy az antiláncok és az ideálok az

I ↦ I^{+}, A ↦ I(A)

hozzárendelésekkel kölcsönösen egyértelműen megfeleltethetőek egymásnak, és (𝒜, ∧, ∨) izomorf az ideálhálóval.

3.8 Definíció. A P = (V, ≤) részbenrendezett halmaz \underline{lefelé erdő}, ha minden v ∈ V -re az {u ∈ V : u ≥ v} halmaz lánc. Ez azzal ekvivalens, hogy minden elemnek legfeljebb egy felső szomszédja lehet.

3.9 Lemma. Tetszőleges A, B ∈ 𝒜 esetén:

1. χ_{A} + χ_{B} = χ_{A⊔B} + χ_{A⊓B}

2. χ_{A} + χ_{B} ≤ χ_{A∨B} + χ_{A∧B}

3. P pontosan akkor lefelé erdő, ha A ∧ B = A ⊓ B minden A, B antiláncra.

4. P pontosan akkor lefelé erdő, ha (𝒜, ⊓, ⊔) háló, és ha háló, akkor disztributív is.

Bizonyítás. A műveletek tulajdonságaiból egyszerűen következik 1., 2., továbbá 3. és 4. ⟹ iránya. Tegyük most fel, hogy P nem lefelé erdő, azaz létezik v, u_{1}, u_{2} ∈ V, hogy u_{1} ≠ u_{2} egyaránt felső szomszédai v-nek. Ekkor az X = {v}, Y = {u_{1}}, Z = {u_{2}} választással. Ekkor

(X ⊓ Y) ⊓ Z = X ⊓ Z = X,
X ⊓ (Y ⊓ Z) = X ⊓ ∅ = ∅.

Tehát a ⊓ művelet nem asszociatív, így (𝒜, ⊓, ⊔) nem lehet háló, és ekkor a kétféle metszet sem egyezhet meg (hiszen ∧ asszociatív). ■

Az optimalizálási feladatok legyenek a következőek:

max cx, x(A) ≤ b(A) ∀A ∈ 𝒜,  (3.2 P)
max cx, x ≥ 0, x(A) ≤ b(A) ∀A ∈ 𝒜,  (3.3 P)

a megfelelő duális problémák:

min by, y ≥ 0, ∑ (y(A) : A ∈ 𝒜, v ∈ Z) = c(v) ∀v ∈ V,  (3.2 D)
min by, y ≥ 0, ∑ (y(A) : A ∈ 𝒜, v ∈ Z) ≥ c(v) ∀v ∈ V.  (3.3 D)

Ugyancsak (3.2 P) stb. jelöléssel hivatkozunk majd a feladatok megoldáshalmazára mint poliéderekre. A b függvény ezúttal tetszőleges valós értéket is felvehet.

3.10 Algoritmus.

Kétfázisú mohó algoritmus y := 0, Z := V, i := 1 Ciklus amíg Z ≠ ∅ A_{i} := Z^{+} y(A_{i}) := min (c(v) : v ∈ A_{i}) v_{i} ∈ A_{i} legyen olyan, hogy c(v_{i}) = y(A_{i}) A_{i} elemein legyen c(v) := c(v) − y(A_{i}) Z := Z − v_{i} i := i + 1 Ciklus vége Ciklus i := n-től 1-ig

x(v_{i}) := b(A_{i}) − ∑ (x(v_{j} : j > i, v_{j} ∈ A_{i}) Ciklus vége Algoritmus vége

Még egy fogalomra lesz szükségünk.

3.11 Definíció. Az f: 𝒜 → ℝ függvény \underline{monoton növő}, ha

A ≤ B ⟹ f(A) ≤ f(B).

3.12 Tétel.

1. Ha b szubmoduláris a ⊓, ⊔ műveletekre, akkor a 3.10 Algoritmus megoldja a (3.2 P)-(3.2 D) primál-duál feladatpárt. Ha b egészértékű, akkor a (3.2 P) rendszer TDI.

2. Ha b szubmoduláris a ⊓, ⊔ műveletekre és monoton növő, akkor a 3.10 Algoritmus megoldja a (3.3 P)-(3.3 D) primál-duál feladatpárt. Ha b egészértékű, akkor a (3.3 P) rendszer TDI.

Bizonyítás. A két állítást egyszerre igazoljuk. Az algoritmus szabálya szerint:

• v_{i} ∈ A;

• v_{i} ∈ A_{j} ⟹ i ≥ j;

• v_{i} ≤ v_{j} ⟹ i ≥ j, v_{i} ≥ v_{j} ⟹ i ≤ j;

• I(A_{i}) = {v_{i}, …, v_{n}};

• i ≤ j ⟹ A_{i} ≥ A_{j};

• x(A_{i}) = b(A_{i}), azaz az A_{i} halmazok x-pontosak.

Így minden v_{i} ∈ V -re

∑ (y(Z) : v_{i} ∈ Z) = ∑ (y(A_{j}) : v_{i} ∈ A_{j}) = ∑ (y(A_{j}) : v_{i} ∈ A_{j}, i ≥ j) = = y(A_{i}) + ∑ (y(A_{j}) : v_{i} ∈ A_{j}, i > j) = c(v_{i}) − ∑ (y(A_{j}) : v_{i} ∈ A_{j}, i > j) +

+ ∑ (y(A_{j}) : v_{i} ∈ A_{j}, i > j) = c(v_{i}),

tehát y mindkét esetben duál megengedett. Az

y(Z) > 0, Z ∈ 𝒜 ⟹ x(Z) = b(Z)

közös optimalitási feltételek teljesülnek, ezért csak az maradt hátra, hogy x primál megengedett.

Először azt látjuk be, hogy b szubmodularitásából x ≤ b következik. Legyen A ∈ 𝒜, k := min(i : v_{i} ∈ A). k szerinti teljes indukciót használunk.

k = n : Z = {v_{n}} = A_{n}, így x(A_{n}) = b(A_{n});

k < n :

b(A) + b(A_{k+1}) ≥ b(A ⊓ A_{k+1}) + b(A ⊔ A_{k+1})  (3.4)

A⊓A_{k+1} ⊆ {v_{k+1}, …, v_{n}}, tehát az indukció szerint x(A⊓A_{k+1}) ≤ b(A⊓A_{k+1}). Másrészt

A ⊔ A_{k+1} = (I(A) ∪ I(A_{k+1}))^{+} = {v_{k}, …, v_{k+1}}^{+} = A_{k+1}.

Mivel az A_{i} halmazok x-pontosak, így (3.4) átrendezésével és a 3.9 Lemma felhasználásával

b(A) ≥ b(A ⊓ A_{k+1}) + b(A ⊔ A_{k+1}) − b(A_{k+1}) ≥
≥ x(A ⊓ A_{k+1}) + x(A ⊔ A_{k+1}) − x(A_{k+1}) = x(A).  (3.5)

Végül megmutatjuk, hogy monoton növő b esetén x ≥ 0. A (3.3 P)-(3.3 D) feladatpárnál feltehető, hogy b ≥ 0, különben a primál megoldáshalmaz üres. k szerinti indukcióval:

k = n : A = {v_{n}} = A_{n} ⟹ x(v_{n}) = b(A_{n}) ≥ 0;

k < n : Ekkor A_{k+1} = (A_{k+1} − A_{k}) ∪^{∗} (A_{k} − v_{k}),

[figure: A; A; v; k; k; k+1]

1. ábra

így b monotonitása és az indukciós feltevés alapján

x(v_{k}) = x(A_{k}) − x(A_{k} − v_{k}) = \underbrace{(x(A_{k}) − x(A_{k+1}))}_{≥ 0} +x(\underbrace{A_{k+1} − A_{k}}_{⊆ \{v_{k+1}, …, v_{n}\}}) ≥ 0.

■

A matroid- ill. polimatroid-optimalizáló 3.2 ill. 3.5 Algoritmus-ok speciális esetei a 3.10 Algoritmus-nak az üres rendezést (azaz V antilánc) választva. Ekkor ugyanis 𝒜 = 2^{V}, A ⊓ B = A ∧ B = A ∩ B és A ⊔ B = A ∨ B = A ∪ B minden A, B ∈ 𝒜.

3.13 Tétel.

1. Ha b szubmoduláris a ∧, ∨ műveletekre és P = (V, ≤) lefelé erdő, akkor a 3.10 Algoritmus megoldja a (3.2 P)-(3.2 D) primál-duál feladatpárt. Ha b egészértékű, akkor a (3.2 P) rendszer TDI.

2. Ha b szubmoduláris a ∧, ∨ műveletekre és monoton növő, akkor a 3.10 Algoritmus megoldja a (3.3 P)-(3.3 D) primál-duál feladatpárt. Ha b egészértékű, akkor a (3.3 P) rendszer TDI.

Bizonyítás. 1. Ha a részbenrendezés lefelé erdő, akkor a kétféle metszet ill. unió fogalma egybeesik, tehát állításunk közvetlenül adódik a 3.12 Tétel-ből.

2. A 3.12 Tétel bizonyítása lényegében változatlanul elmondható, egyedül a (3.5) utolsó egyenlőségjele helyett kell ≥ jelet tenni, a 3.9 Lemma 2. állítása szerint. ■

Megemlítjük, hogy [4]-ben a szerzők igazolják a tétel egyfajta megfordítását is: ha a mohó algoritmus minden célfüggvényre helyes erdményt ad, akkor b szubmoduláris.

Rámutatunk arra, hogy a 3.11-3.12 Tétel-ekben sem a monotonitási, sem a lefelé erdő tulajdonság nem hagyható el büntetlenül:

3.14 Példa. Legyen P = {v_{1}, v_{2}} a triviális (üres) rendezéssel. 𝒜 = {∅, {v_{1}}, {v_{2}}, {v_{1}, v_{2}}}, b értékei rendre 0, 1, 1, 0. Ez szubmoduláris mindkét műveletpárra, de nem monoton növő. c(v_{1}) = 0, c(v_{2}) = 1. Ekkor az algoritmus szerint A_{1} = {v_{1}, v_{2}}, A_{2} = {v_{2}}, x_{1} = b(A_{1}) − b(A_{2}) = −1 < 0.

3.15 Példa. Legyen P = {v_{1}, v_{2}, v_{3}}, a rendezés: v_{1} > v_{3}, v_{2} > v_{3}, tehát nem lefelé erdő, a célfüggvény értékei rendre 0, 1, 1. A_{1} = {v_{1}, v_{2}}, A_{2} = {v_{2}}, A_{3} = {v_{3}}. Ezeken kívül csak egy antilánc létezik: A = {v_{1}}. b(A_{1}) := 0, b(A_{2}) := 0, b(A_{3}) := −1, b(A) := −1. Ez a függvény szubmoduláris. Az algoritmussal x_{1} = 0, x_{2} = 0, x_{3} = −1 adódik, így x(A) = 0 > −1 = b(A).

Az itt leírt poliéderek, illetve az antiláncokon definiált ⊓, ⊔ műveletek fontos szerephez jutnak az 5.2 szakaszban. Végül megjegyezzük, hogy bár a mohó algoritmus helyességének igazolására több feltételre is támaszkodtunk, a TDI tulajdonsághoz minden esetben elegendő b szubmodularitása (l. 5.2 Tétel).

Gráfok és poliéderek

A bevezetőben már említettük, hogy a szubmoduláris áram poliédereket állítottuk ezen fejezet középpontjába. G = (V, E) végig irányított gráfot jelöl majd.

4.1. Szubmoduláris áram poliéderek

A folyamok, áramok általánosítására született meg a szubmoduláris áram poliéder fogalma.

4.1 Definíció. Legyenek f: E → ℤ ∪ {−∞}, f: E → ℤ ∪ {+∞}, f ≤ g korlátok, b: 2^{V} → ℤ ∪ {+∞} szubmoduláris függvény. Ekkor a

ϱ_{x}(Z) − δ_{x}(Z) ≤ b(Z) ∀Z ⊆ V  (4.1)

feltételnek eleget tevő x: V → ℝ vektort \underline{szubmoduláris áramnak} nevezzük. Ha még f ≤ x ≤ g is teljesül, akkor x megendedett szubmoduláris áram. A megendedett szubmoduláris áramok alkotják a Q(f, g; b) szubmoduláris áram poliédert.

A ϱ_{x}(Z) − δ_{x}(Z) ≤ b(Z) feltételeket elég egy ℱ ⊆ 2^{V} ∩, ∪-zárt halmazrendszerre megkövetelve is szubmoduláris áram poliédert kapunk: a b|_{2^{V} −ℱ} ≡ +∞ definícióval kiterjesztve b: 2^{V} → ℤ ∪ {+∞} szubmoduláris függvény lesz.

Az egyenlőtlenség-rendszer mátrixa (a korlátokból származó egységmátrixokat leszámítva) A ∈ {0, ±1}^{ℱ×E}, A_{Z,e} = 1, ha e belép Z-be, A_{Z,e} = −1, ha e kilép Z-ből, egyébként pedig 0.

Egyenértékű fogalomhoz jutunk, ha (4.1) helyett a

ϱ_{x}(Z) − δ_{x}(Z) ≥ p(Z) ∀Z ⊆ V

feltételt szabjuk, ahol p szupermoduláris. A gráf éleit kell csak megfordítani, és legyen p = −b.

Alapvető eredmények Frank András ill. J. Edmonds és R. Giles tételei.

4.2 Tétel. 1. Pontosan akkor létezik megengedett szubmoduláris áram, ha minden Z ⊆ V -re ϱ_{f}(Z) − δ_{g}(Z) ≤ b(Z).

2. A Q(f, g; b) poliéder egész, a leíró rendszer TDI.

A poliéder egész volta adódni fog a háló-poliéderekre vonatkozó 5.2 Tétel-ből.

4.3 Tétel. A szubmoduláris áram poliéder definíciójában b-ről csak keresztező szubmodularitást feltételezve szintén szubmoduláris áram poliédert kapunk.

Bizonyítás. Feltehetjük, hogy Q(f, g; b) ≠ ∅. Legyen λ_{x}: V → ℝ, λ_{x}(v) = = ϱ_{x} ({v}) − δ_{x} ({v}). Ekkor λ_{x}(Z) = ϱ_{x}(Z) − δ_{x}(Z), így

x ∈ (f, g; b) ⟺ λ_{x} ∈ {y ∈ ℝ^{V} : y(V) = 0, y(Z) ≤ b(Z) ∀Z ⊆ V } = B(b).

Mivel B(b) ≠ ∅, ezért az 1.4 Tétel szerint van olyan b^{↓}: 2^{V} → ℤ ∪ {+∞} teljesen szubmoduláris függvény, hogy B(b) = B(b^{↓}). Tehát

x ∈ Q(f, g; b) ⟺ λ_{x} ∈ B(b) ⟺ λ_{x} ∈ B(b^{↓}) ⟺ x ∈ Q(f, g; b^{↓}).

■

A szubmoduláris áram poliéderek jelentősége abban áll, hogy egyrészt viszonylag általános fogalmak, gyakran alkalmazhatóak, másrészt jól kidolgozott, polinomiális futásidejű algoritmusok ismeretesek, akár csak keresztezően szubmoduláris b esetére is.

4.2. Háló-mátrixok

Bár a háló-mátrixokat csak a 6. fejezetben tárgyaljuk, definíciójukat egy idekapcsolódó tétel okán előrehoztuk.

4.4 Definíció. Legyen ℒ disztributív háló, E pedig nemüres véges halmaz. Az A ∈ \{0, 1\}^{ℒ×E} mátrixot \underline{háló-mártixnak} nevezzük, ha minden oszlopára mint A_{e}: ℒ → {0, 1} függvényre fennáll a következő két tulajdonság:

(a) a, b, c ∈ ℒ, a ≤ b ≤ c, A_{e}(a) = A_{e}(c) = 1 ⟹ A_{e}(b) = 1,

(b) A_{e} moduláris (a háló-műveletekre nézve). Beszélhetünk 0, ±1 elemű háló-mátrixokról is, a feltételek ekkor:

(a) a, b, c ∈ ℒ, a ≤ b ≤ c, A_{e}(a) = A_{e}(c) = 1 ⟹ A_{e}(b) = 1,

(b) a, b, c ∈ ℒ, a ≤ b ≤ c, A_{e}(a) = A_{e}(c) = −1 ⟹ A_{e}(b) = −1,

(c) a, b ∈ ℒ, a ≤ b ⟹ A_{e}(a) · A_{e}(b) ≥ 0,

(d) A_{e} moduláris (a háló-műveletekre nézve).

Az alábbi tétel lényegében A. Schrijvertől származik, [9]-ben 0-1 háló-mát-rixokra szerepel. A tételt kissé általánosabban igazoljuk.

4.5 Tétel. Legyen A 0, ±1 elemű háló-mátrix, f: → ℝ ∪ {−∞}, g: E → ℝ ∪ {+∞} tetszőleges korlátok, és b: ℒ → ℤ ∪ {+∞} szubmoduláris. Ekkor

P = {x ∈ ℝ^{E} : f ≤ x ≤ g, Ax ≤ b}

szubmoduláris áram poliéder.

Bizonyítás. Elegendő konstruáluni egy olyan G′ = (V′, E′) gráfot és ℒ′ ⊆ 2^{V′} ℒ-lel izomorf ∩, ∪-zárt halmazrendszert, hogy az A mátrix egyenlő legyen az ℒ′ rendszer be-, és kilépési feltétel-mártixával. Ekkor ugyanis P = Q(f, g; b). A gráf élhalmaza természetesen azonosítható E-vel. A bizonyítás során léptennyomon hivatkozunk a 4.4 Definíció feltételeire.

Stone ismert reprezentációs tétele szerint az ℒ disztributív háló beágyazható egy alkalmas V halmaz hatványhalmazába, |ℒ| < ∞ esetén |V | < ∞ is választható. ℒ elemeit azonosítjuk V bizonyos részhalmazaival.

Tekintsük a mátrix e ∈ E-hez tartozó oszlopát. Legyen ℱ^{+} := {Z ∈ ℒ : A_{e}(Z) = 1}, ℱ^{0} := {Z ∈ ℒ : A_{e}(Z) = 0}, ℱ^{−} := {Z ∈ ℒ : A_{e}(Z) = −1}. (c) és (d) miatt ℱ^{+}, ℱ^{0}, ℱ^{−} egyaránt ∩, ∪-zárt. P_{1} := ∩ℱ^{+}, P_{2} := ∪ℱ^{+}, N_{1} := ∩ℱ^{−}, N_{2} := ∩ℱ^{−}. Ekkor (b) és (c) felhasználásával Z ∈ ℒ-re:

P_{1} ⊆ Z ⊆ P_{2} ⟺ Z ∈ ℱ^{+},
N_{1} ⊆ Z ⊆ N_{2} ⟺ Z ∈ ℱ^{−}.

Elsőként azt vizsgáljuk meg, hogy milyen tartalmazási relációk állhatnak fenn Z ∈ ℱ^{0} és P_{1} ill. P_{2} között.

P_{1} ⊆ Z, Z ⊆ P_{2}: lehetetlen, ugyanis Z ∈ ℱ^{+} következne;

P_{1} ⊆ Z, Z ⊈ P_{2}: lehetetséges;
P_{1} ⊈ Z, Z ⊆ P_{2}: lehetetséges;

P_{1} ⊈ Z, Z ⊈ P_{2}: ez is lehetetlen, ekkor Z ∪ P_{2} ⊋ P_{2}, így Z ∪ P_{2} ∉ ℱ^{+}, de (c) miatt Z ∪ P_{2} ∉ ℱ^{−}, tehát Z ∪ P_{2} ∈ ℱ^{0}; másrészt Z ∩ P_{2} ⊈ P_{1} alapján Z ∩P_{2} ∉ ℱ^{+}, és Z ∩P_{2} ⊆ P_{2} miatt Z ∩P_{2} ∉ ℱ^{−}, azaz Z ∩P_{2} ∈ ℱ^{0}; ekkor viszont

1 = A_{e}(P_{2}) + A_{e}(Z) ≠ A_{e}(Z ∪ P_{2}) + A_{e}(Z ∩ P_{2}) = 0,

ami ellentmond (d)-nek.

Analóg módon tekinthetők át a H_{1}, H_{2}-höz tartozó esetek. A kétféle osztályozást egybevetve ℒ elemeit (látszólag) 6 részre oszthetjuk.

ℱ^{+}: P_{1} ⊆ Z, Z ⊆ P_{2}, N_{1} ⊈ Z, Z ⊈ N_{2}
ℱ^{−}: P_{1} ⊈ Z, Z ⊈ P_{2}, N_{1} ⊆ Z, Z ⊆ N_{2}
ℱ_{1}^{0}: P_{1} ⊆ Z, Z ⊈ P_{2}, N_{1} ⊆ Z, Z ⊈ N_{2}
ℱ_{2}^{0}: P_{1} ⊈ Z, Z ⊆ P_{2}, N_{1} ⊈ Z, Z ⊆ N_{2}
P_{1} ⊆ Z, Z ⊈ P_{2}, N_{1} ⊈ Z, Z ⊆ N_{2}
P_{1} ⊈ Z, Z ⊆ P_{2}, N_{1} ⊆ Z, Z ⊈ N_{2}.

Az utolsó két esetben P_{1} ⊆ Z ⊆ N_{2} ill. N_{1} ⊆ Z ⊆ P_{2}, ami (c) alapján lehetetlen. Tehát igazándiból csak 4 osztályt kapunk. Vegyünk V -hez két új pontot: V^{∗∗} := V +u+v. Az oszlopot reprezentáló él u-ból v-be fog vezetni. Az új pontokat hozzáveszük bizonyos ℒ-beli halmazokhoz is, vigyázva arra, hogy az uv él éppen ℱ^{−} elemeiből lépjen ki és éppen ℱ^{+} elemeibe lépjen be, továbbá hogy az új halmazcsalád ℒ-lel izomorf háló legyen.

A v pont benne lesz majd minden ℱ^{+}-beli halmazban (ill. az alaphalmaz bővítése után a ℱ^{+}-ből származó módosított halmazokban), tehát P_{1}-ben is. De ekkor v-t hozzá kell majd venni minden ℱ_{1}^{0}-beli halmazhoz is. Az u kívül lesz minden ℱ^{+}-beli halmazon, P_{2}-n is, ezért egyetlen ℱ_{2}^{0}-belihez sem tartozhat majd. Az okoskodást folytatva az alábbi táblázat adódik:

ℱ^{+}: u ∉ v ∈
ℱ^{−}: u ∈ v ∉
ℱ_{1}^{0}: u ∈ v ∈
ℱ_{2}^{0}: u ∉ v ∉

Legyen V^{∗} := V + u. Tekintsük a φ_{u}: ℒ → 2^{V^{∗}},

φ_{u}(Z) = \{ \begin{matrix}Z & ha Z ∈ ℱ^{+} ∪ ℱ_{2}^{0} \\ Z + u & ha Z ∈ ℱ^{−} ∪ ℱ_{1}^{0} \end{matrix}

leképezést. Azt állítjuk, hogy φ_{u} háló-izomorfizmus. Mivel ℱ^{+} ∪ ℱ_{2}^{0} = {Z ∈ ℒ : Z ⊆ P_{2}}, ezért ℱ^{+} ∪ ℱ_{2}^{0} ∩, ∪-zárt. Az is igaz, hogy ℱ^{−} ∪ ℱ_{1}^{0} = {Z : Z ⊈ P_{2}} is ∩, ∪-zárt. Ugyanis X, Y ∈ ℱ^{−} ∪ℱ_{1}^{0} esetén N_{1} ⊆ X, Y, ezért N_{1} ⊆ X ∩Y, X ∪Y, így (c) szerint X ∩ Y, X ∪ Y ⊈ P_{2}. Tehát φ_{u} művelettartását elég X ⊆ P_{2}, Y ⊈ P_{2} halmazokra ellenőrizni. Ekkor persze X ∩ Y ⊆ P_{2}, X ∪ Y ⊈ P_{2}, azaz

φ_{u}(X ∩ Y) = X ∩ Y = X ∩ (Y + u) = φ_{u}(X) ∩ φ_{u}(Y)
φ_{u}(X ∪ Y) = (X ∪ Y) + u = X ∪ (Y + u) = φ_{u}(X) ∪ φ_{u}(Y).

Legyen ℒ^{∗} := φ_{u}(ℒ). Hasonlóan definiálható a φ_{v}: ℒ^{∗} → 2^{V^{∗∗}} leképezés, ez is izomorfizmus, itt az N_{2} halmaz játssza a kulcsszerepet. Az kaptuk tehát, hogy a G = (V^{∗∗}, uv) gráf helyesen reprezentálja a mátrix első oszlopát. Az eljárást a többi oszlopra is elvégezve a Stone-tételből adódó kiindulási V alaphalmazt lépésenként bővítve a kívánt tulajdonságú gráfhoz jutunk. ■

Megemlítjük speciális esetként, hogy minden 0-1 háló-mártix megegyezik valamely gráfban irányított vágások egy keresztező rendszerének incidencia-mát-rixával.

Mielőtt bármi kétségünk támadna a fent vázolt eljárás polinomiális kivitelezhetőségével szemben, megmutatjuk, hogy az egyetlen, algoritmikusan nem részletezett lépés, a kiindulási V megtalálása is megvalósítható polinom időben (természetesen n = |L|). Ehhez először is idézzük fel, mit is mond ki pontosan Stone tétele.

4.6 Definíció. Az L = (L, ∧, ∨) hálóban az I ⊆ L részhalmazt duális ideálnak nevezzük, ha

x ∈ I, a ∈ L, a ≥ x ⟹ a ∈ T, x, y ∈ I ⟹ x ∧ y ∈ I.

Az I ideál duális prímideál, ha duális ideál, és x, y ∈ L, x∨y ∈ L ⟹ x ∈ I vagy y ∈ I. A duális prímideálok halmazát jelölje ℐ.

4.7 Tétel. [Stone] Legyen L disztributív háló. Ekkor az

L ∋ x ⟼^{Φ} Φ(x) = {I : I duális prímideál, x ∈ I} ∈ 2^{ℐ}

leképezés háló-izomorfizmus L és Φ(L) között.

Látszik tehát, hogy véges hálóból kiindulva a V := ℐ reprezentáló alaphalmaz is véges lesz. Az egyetlen kérdés: hogyan algoritmizáljuk a Φ leképezést.

Véges hálóban a duális prímideáloknak létezik minimális eleme, és nyilván I = {x ∈ L : x ≥ min(I)}, továbbá min(I) ∨-irreducibilis (azaz a ∨ b = = min(I) ⟹ a = min(I) vagy b = min(I)). Másrészt ha a ∨-irreducibilis, akkor ⟨a⟩ := {x ∈ L : x ≥ a} duális prímideál. Az első két kritérium teljesülése világos. Ha pedig x, y ∈ L, x ∨ y ∈ ⟨a⟩, akkor (x ∧ a) ∨ (y ∧ a) = (x ∨ y) ∧ a = a miatt x ∧ a = a vagy y ∧ a = a, vagyis x ∈ ⟨a⟩ vagy x ∈ ⟨a⟩. Tehát a duális prímideálok és az ∨-irreducibilis elemek egyértelműen megfeletethetőek egymásnak, így elegendő megkeresni L ∨-irreducibilis elemeit, ezek segítségével a Φ leképezés O(n^{2}) lépésben megadható. Feladatunkat megoldja a következő algoritmus:

4.8 Algoritmus.

∨-irreducibilis elemek keresése U := ∅ Z := L Ciklus amíg Z ≠ ∅ U := U ∪ Z^{−} Z := Z − Gen ((L − Z) ∪ Z^{−})

Ciklus vége Algoritmus vége

Z^{−} jelöli a Z-beli minimális elemek, Gen(Z) pedig a Z elemeiből az ∨ művelet segítségével előállítható elemek halmazát. Az algoritmus végén U elemei éppen az ∨-irreducibilis elemek lesznek.

Az U elemei mind ∨-irreducibilisek, hiszen abban a lépésben, amikor x bekerül U-ba, az összes x-nél kisebb elem már L−Z-ben van, és ezekből nem lehetett x-et unióként előállítani, a későbbiek során pedig már csak x-nél nem kisebb elemek maradnak vissza. Az U-n kívüli elemek viszont azért nem kerülhettek be U-ba, mert előálltak valódi unióként. Az algoritmus helyességét ezzel beláttuk.

Lépésszám szerinti teljes indukcióval igazolható, hogy a Gen ((V − Z) ∪ Z^{−}) halmazok részhálók és lefelé zártak (azaz hálóelméleti ideálok), továbbá

Gen ((V − Z) ∪ Z^{−}) = {x ∈ L : x ≤ ⋁ (a : a ∈ (V − Z) ∪ Z^{−})} .

Így a ciklusmag halmazait lineáris időben ki tudjuk számítani, és az iterációk száma is legfeljebb n. Az L hálót reprezentáló halmazrendszert tehát elkészíthetjük O(n^{2}) lépésben.

4.9 Példa. A polimatroidok, szubmoduláris poliéderek szubmoduláris áram poliéderek.

Ugyanis ℒ = 2^{V}, a 4.5 Definíció feltételei pedig könnyen ellenőrizhetőek.

4.10 Példa. A (3.2 P) és (3.3 P) poliéderek szubmoduláris áram poliéderek, amennyiben a rendezés lefelé erdő.

Az egyenlőtlenség-rendszer mátrixa éppen az antiláncok családjának incidenciamátrixa. (𝒜, ⊓, ⊔) disztributív háló, továbbá egyszerű számolás mutatja, hogy A ≤ B ≤ C, v ∈ A ∩ C ⟹ v ∈ B.

4.11 Példa. Legyen G = (V, E) irányított gráf, ℱ ⊆ 2^{V} ∩, ∪-zárt halmazrendszer, p: ℱ → ℤ ∪ {−∞} pedig szupermoduláris. Ekkor

{x ∈ ℝ^{V} : x ≥ 0, ϱ_{x}(Z) ≥ p(Z) ∀Z ∈ ℱ}

szubmoduláris áram poliéder.

Ekkor ugyanis ℱ lesz a diszrtibutív háló, a mátrix oszlopaira pedig könnyű igazolni az elvárt taljdonságokat. Hamarosan másik szubmoduláris áram-konst-rukciót is látni fogunk erre a fontos poliéderosztályra.

4.3. Lefogási poliéderek

4.12 Definíció. Legyen G = (V, E) irányított gráf, ℱ ⊆ 2^{V}, p: ℱ → ℤ∪{±∞} tetszőleges. Az

L(p) = {x ∈ ℝ^{V} : x ≥ 0, ϱ_{x}(Z) ≥ p(Z) ∀Z ∈ ℱ}

poliédert lefogási poliédernek nevezzük.

Az irodalomban nincs elterjedt név erre az osztályra. Mivel tipikusan lefogási feladatokban fordulnak elő, ésszerűnek látszik az elnevezés. A legtöbb esetben (pl. amikor p valamilyen értelemben szupermoduláris) ℒ-re megköveteljük, hogy keresztező, metsző, stb. halmazrendszer legyen.

Lefogási poliéderrel találkozhatunk például Fulkerson híres, minimális költségű, adott s gyökerű feszítő fenyőt kereső algoritmusánál, p ≡ 1, ℱ = 2^{V −s} esetén, a fenyő incidencia-vektora az L(1) poliéder csúcsa lesz. A ϱ_{x}(Z) ≥ 1 feltételek biztosítják, hogy a fenyő minden halmazba belép (azaz minden ilyen halmazt lefog).

Teljesen szupermoduláris p esetén L(p) egész volta következik abból, hogy szubmoduláris áram poliéder. Ha p metszőn szupermoduláris, akkor már nem látszik közvetlen kapcsolat szubmoduláris áram poliéderekkel, de egyszerű kikeresztezéses bizonyítás mutatja a teljes duális egészértékűséget.

A 2. fejezetben már jeleztük, hogy a szubmodularitás fogalma másképpen is általánosítható.

Legyen G = (V, E) irányított gráf, ∅ ≠ T ⊆ V, tegyük fel, hogy

minden G-beli él feje (ahová az él mutat) T -ben fekszik  (*)

Legyen ℒ ⊆ 2^{V} azzal a tulajdonsággal, hogy X, Y ∈ ℒ, X ∩ Y ∩ T ≠ ∅ esetén X ∩ Y, X ∪ Y ∈ ℒ.

4.13 Definíció. A p függvényt T -metszőn szupermodulárisnak nevezzük, ha X, Y ∈ ℒ, X ∩ Y ∩ T ≠ ∅ esetén

p(X) + p(Y) ≤ p(X ∩ Y) + p(X ∪ Y).

A. Schrijver egy konstrukcióját Frank András ötletével fűszerezve a következő állítást igazolhatjuk.

4.14 Tétel. Ha p T -metszőn szupermoduláris, akkor P := L(p) szubmoduláris áram poliéder.

Bizonyítás. Tekintsük a következő konstrukciót. Legyen G′ = (V′; E′) = (T, E; E′) páros gráf, ahol E′-t E-ből kapjuk: e = uv ∈ E esetén legyen e′ = ev ∈ E′ ((*) miatt ez értelmes). Az x: E → ℝ ill. x: E′ → ℝ függvények tehát értelemszerűen azonosíthatóak. Az X ⊆ V által G-ben feszített élek halmazát i(X) jelöli. Legyen

ℒ′ = {(X ∩ T) ∪ F : X ∈ ℒ, F ⊆ i(X)}.

Ez szintén T -t metsző halmazokból áll. Legyen Z_{1}, Z_{2} ∈ ℒ′, Z_{i} = (X_{i} ∩ T) ∪ F_{i} és Z_{1} ∩ Z_{2} ≠ ∅. Sokszor ki fogjuk használni azt a tényt, hogy ekkor X_{1} ∩ X_{2} ∩ T ≠ ∅. Ebből X_{1} ∩ X_{2}, X_{1} ∪ X_{2} ∈ ℒ, továbbá F_{1} ∩ F_{2} ⊆ i(X_{1} ∩ X_{2}), F_{1} ∪ F_{2} ⊆ i(X_{1} ∪ X_{2}), azaz Z_{1} ∩ Z_{2} = ((X_{1} ∩ X_{2}) ∩ T) ∪ (F_{1} ∩ F_{2}) ∈ ℒ′, Z_{1} ∪ Z_{2} = ((X_{1} ∪ X_{2}) ∩ T) ∪ (F_{1} ∪ F_{2}) ∈ ℒ′, tehát ℒ′ metsző halmazrendszer: Z_{1}, Z_{2} ∈ ℒ′, Z_{1} ∩ Z_{2} ≠ ∅ ⟹ Z_{1} ∩ Z_{2}, Z_{1} ∪ Z_{2} ∈ ℒ′.

Legyen p′: ℒ → ℝ_{+}, p′(Z) = max (p(X) : X ∈ ℒ, Z = (X ∩ T) ∪ F ).

4.15 Lemma. Az így definiált p′ metszőn szupermoduláris ℒ′-en.

Valóban, legyen Z_{1}, Z_{2} ∈ ℒ′, Z_{1} ∩ Z_{2} ≠ ∅, Z_{1} ∩ Z_{2} ≠ ∅. Létezik olyan X_{1}, X_{2} ∈ ℒ, hogy p′(Z_{i}) = p(X_{i}). A fenti észrevétel szerint X_{1} ∩ X_{2} ∩ T ≠ ∅, továbbá p(X_{1} ∩ X_{2}) ill. p(X_{1} ∪ X_{2}) benne van a p′(Z_{1} ∩ Z_{2}) ill. p′(Z_{1} ∪ Z_{2})-beli maximumban, így

p′(Z_{1}) + p′(Z_{2}) = p(X_{1}) + p(X_{2}) ≤ p(X_{1} ∩ X_{2}) + p(X_{1} ∪ X_{2}) ≤ ≤ p′(Z_{1} ∩ Z_{2}) + p′(Z_{1} ∪ Z_{2}).

□

Jelölje G′ be- ill. kifok-függvényét ϱ′ ill δ′, a súlyozott befok-függvényt pedig ϱ′_{x}.

4.16 Lemma. Legyen P′ := {x : ϱ′_{x}(Z) ≥ p′(Z) ∀Z ∈ ℒ, x ≥ 0}. Ekkor P = P′.

Legyen először x ∈ P′. X ∈ ℒ, Z := (X ∩ T) ∪ i(X). Ekkor ϱ_{x}(X) = ϱ′_{x}(Z) ≥ p′(Z) ≥ p(X), tehát x ∈ P.

Legyen most x ∈ P. Z ∈ ℒ′, X ∈ ℒ pedig olyan, hogy Z = (X ∩ T) ∪ F, F ⊆ i(X), és p′(Z) = p(X). Ekkor ϱ′_{x}(Z) ≥ ϱ′_{x}((X ∩ T) ∪ i(X)) = ϱ_{x}(X) ≥ p(X) = p′(Z), azaz x ∈ P′. □

Figyeljük meg, hogy minden Z ∈ ℒ′-re δ′(Z) = 0.

Nem jelent semmiféle megszorítást, ha feltesszük, hogy ∅, V′ = T ∈ ℒ′, és p′(∅) = p′(V′) = 0.

Azt állítjuk, hogy Q = {x : ϱ′_{x}(Z) ≥ p′(Z) ∀Z ∈ ℒ} szubmoduláris áram poliéder. Ekkor az x ≥ 0 korlát hozzávételével P′ is szubmoduláris áram poliéder lesz.

ϱ′_{x}(Z) ≥ p′(Z) ∀Z ∈ ℒ′ ⟺
ϱ′_{x}(Z) ≥ p′(Z) ∀Z ∈ ℒ′ és ϱ′_{x}(V′) = p′(V′) ⟺

ϱ′_{x}(Z) − δ′_{x}(Z) ≥ p′(z) ∀Z ∈ ℒ′ és ϱ′_{x}(V′) − δ′_{x}(V′) = p′(V′) ⟺

∑ (ϱ′_{x}(v) − δ′_{x}(v) : v ∈ Z) ≥ p′(Z) ∀Z ∈ ℒ′ és
∑ (ϱ′_{x}(v) − δ′_{x}(v) : v ∈ V′) = p′(V′) ⟺

λ′_{x} := ϱ′_{x} − δ′_{x} ∈ {z : z(Z) ≥ p′(Z) ∀Z ∈ ℒ′ és z(V′) = p′(V′)} =: B(p′)

Q pontosan akkor lesz szubmoduláris áram poliéder, ha B(p′) bázispoliéder, amire még p′(V′) = 0 is teljesül (más szóval 0-bázispoliéder).

Terjesszük ki p′-t az egész 2^{V′}-re: Z ∉ ℒ′ esetén p′(Z) = −∞. Nyilván

B(p′) = {z : z(Z) ≥ p′(Z) ∀Z ⊆ V′ és z(V′) = p′(V′)}.

Az így kiterjesztett p′ továbbra is metszőn szupermoduláris 2^{V′}-n. A 2.13 Tétel szerint metszőn szupermoduláris függvény felső reszeltje teljesen szupermoduláris. A fenti észrevételek fehasználásával

B(p′) = {z : z(Z) ≥ p′^{∧}(Z) ∀Z ⊆ V′ és z(V′) = p′(V′) = 0}.

Világos, hogy p′^{∧}(V) ≥ 0. Ha most p′^{∧}(V) > 0, akkor V′ felpartícionálható A_{1}, …, A_{k} halmazokra úgy, hogy ∑ p′(A_{i}) > 0. Ekkor persze p′(A_{i}) > −∞, tehát A_{i} ∈ ℒ. Mivel azonban δ′(A_{i}) = 0, ezért az részek között nem vezethet él, így tetszőleges x ∈ B(p′)-re és A_{i}-re ϱ′_{x}(A_{i}) = 0, amiből p′(A_{i}) = 0 adódik. Ez pedig ellentmond p′^{∧}(V′) > 0-nak, kivéve, ha B(p′) = ∅. Ekkor persze Q = ∅ és P = ∅. Ha pedig p′^{∧}(V) = 0, akkor

B(p′) = {z : z(Z) ≥ p′^{∧}(Z) ∀Z ⊆ V′ és z(V) = p′^{∧}(V′) = 0},

tehát B(p′) 0-bázispoliéder. ■

A tétel új algoritmus lehetőségét mutatja gyökeres él-, és pontösszefüggőség növelésére.

Legyen D = (V, A) irányított gráf, s ∈ V, T ⊆ V − s adott. Tegyük fel, hogy s-ből T minden pontjába vezet k−1 élidegen út, de ugyanez k-ra már nem mondható el. Legyen G = (V, E) irányított gráf ugyanazon a ponthalmazon, és tegyük fel, hogy minden E-beli él végpontja T -ben fekszik. Legyen végül c ≥ 0 költségfüggvény az E éleken. Keressünk minimális költségű F ⊆ E halmazt, amire D^{+} = (V, A ∪ F)-re az élidegen utas feltétel k-ra is teljesül.

Legyen ℱ := {Z ⊆ V − s : Z ∩ T ≠ ∅, ϱ_{D}(Z) = k − 1}. A befok-függvény szubmodularitásából azonnal következik, hogy ℱ T -metsző. Menger tétele szerint F pontosan akkor fogja le ℱ-et, ha s-ből minden T -beli ponthoz vezet k élidegen út D^{+}-ban. A gyökeres élösszefüggőség-növelési feladat tehát ekvivalens egy lefogási poliéder optimalizálásával, ahol a jobboldali vektor T -metszőn szupermoduláris(nevezetesen konstans k − 1 értékű).

Legyen D = (V, A), s ∈ V, T ⊆ V − s, G = (V, E) mint fent, és ugyanaz a kérdés, csak most élidengen helyett pontidegen utakat tekintünk.

A szokásos pont-széthúzást alkalmazva a probléma visszavezethető az élidegen esetre. Minden v ∈ V pontot helyettesítsünk két új ponttal: v′_{t}-vel és v′_{f}-fel. s′ := s′_{f}. (Az eredetileg s-be lépő élekről el is felejtkezhetünk.) Legyen V′ := {v′_{t}, v′_{f} : v ∈ V }, T′ := {v′_{t} : t ∈ T }. A D′ = (V′, A′) digráf élhalmaza álljon egyrészt az u′_{f}v′_{t} élekből, ha uv ∈ A, másrészt az v′_{t}v′_{f} élekből, v ∈ v esetén. Az E′ éleket hasonlóan kajuk, de csak az u′_{f}v′_{t} típusú éleket tekintjük, a széthúzott pont két darabja közti éleket nem. Ekkor könnyen igazolható, hogy D-ben akkor és csak akkor vezet k pontidegen út s-ből v ∈ T -be, ha D′-ben van k élidegen út s-ből v′_{t}-be. Ugyanez igaz D ill. D′ helyett (V, A ∪ F) ill. (V′, A′ ∪ F′) gráfokra is, ahol F ⊆ E, F′ pedig az F -belieknek megfeleltetett élek halmaza.

Fulkerson minimális költségű, adott gyökerű feszítő fenyőt kereső algoritmusát Frank András általánosította T -metszőn szupermoduláris függvény lefogási poliéderére [6]. Ez egy kétfázisú mohó algoritmus, amely során azonban ellenőrizni kell, hogy élek egy halmaza lefog-e minden ℱ-beli halmazt. Ehhez szükség van egy folyam-algoritmust használó szubrutinra.

A 4.14 Tétel azt mutatja. hogy a szubmoduláris áram algoritmusok közvetlenül is alkalmazhatóak a lefogási poliéderre, megoldván a gyökeres összefüggőség növelésének problémáját. Mivel azonban L(p) ezen algoritmusok szempontából szokatlanul van megadva (a megszokott mód a definíció szerinti: a G = (V, E) gráf, és f, g, b által), további vizsgálatot tárgya lehet a szubmoduláris áram algoritmusoknak ezen poliéderekre történő alkalmazása.

Háló-poliéderek

Elérkeztünk dolgozatunk legáltalánosabb poliéderosztályához. A háló-polié-dereket A. J. Hoffman és D. E. Schwarz definiálta [8]-ben, majd Hoffman és H. Gröflin általánosították a modellt, ill. érdekes előállításokat igazoltak ([7]). Először ezeket tekintjük át. A fejezetet Greene ill. Greene és Kleitman nevezetes tételének bizonyításával zárjuk. A háló-poliéderek ezen szellemes alkalmazása szintén [8]-ben található.

5.1. Háló-poliéderek alapvető tulajdonságai

Adott (L, ≤) tetszőleges részbenrendezett halmaz, n := |L|, és két bináris művelet L-en a következő tulajdonsággal: a ∧ b ≤ a, b ≤ a ∨ b, azaz a ∧ b valamilyen alsó korlát, a ∨ b valamilyen felső korlát. A szub-, és szupermodularitást erre a műveletpárra fogjuk tekinteni. Hangsúlyozzuk: L nem feltétlenül háló!

5.1 Definíció. Az f: L → {0, ±1} függvény konzekutív, ha a, b ∈ L, a ≤ b ⟹ f(a) · f(b) ≥ 0, a, b, c ∈ L, a ≤ b ≤ c, f(a) = f(c) = 1 ⟹ f(b) = 1, a, b, c ∈ L, a ≤ b ≤ c, f(a) = f(c) = −1 ⟹ f(b) = −1.

Másszóval ha minden láncon nemnegatív vagy nempozitív, és minden láncban a nemnulla függvényértékek folyamatosan helyezkednek el.

Ha f 0-1-értékű, akkor csak a középső feltételt kell tekinteni.

A konzekutivitás szükséges és elégséges feltétele az alábbi két egyenlőtlenség:

|f(b) − f(a)| ≤ 1 ∀a ≤ b  (5.1)
|f(a) − f(b) + f(c)| ≤ 1 ∀a ≤ b ≤ c.  (5.2)

5.2 Tétel. Legyen A ∈ {0, ±1}^{n×k} mátrix, f, g ∈ {ℤ ∪ {±∞}}^{k} korlátok, r: L → ℤ.

1. Ha a mátrix oszlopai mint A_{j}: L → {0, ±1} függvények (j = 1, …, k) konzekutívak, szupermodulárisak, f ≥ 0, és r szubmoduláris, akkor a

P_{1} = {x ∈ ℝ^{k} : Ax ≤ r, f ≤ x ≤ g}

poliéder egész, a leíró rendszer TDI.

2. Ha a mátrix oszlopai konzekutívak, szubmodulárisak, f ≥ 0, és r szupermoduláris, akkor a

P_{2} = {x ∈ ℝ^{k} : Ax ≥ r, f ≤ x ≤ g}

poliéder egész, a leíró rendszer TDI.

3. Ha a mátrix oszlopai konzekutívak, modulárisak, és r szubmoduláris, akkor a

P_{3} = {x ∈ ℝ^{k} : Ax ≤ r, f ≤ x ≤ g}

poliéder egész, a leíró rendszer TDI.

Bizonyítás. A három állítás teljesen hasonló módon igazolható, most csak a P_{1} esetet követjük végig. A bizonyítás fő gondolatait már részleteztük, amikor beláttuk a 3.1 Tétel-t.

Elegendő megmutatni, hogy tetszőleges c ∈ ℤ^{k} maximalizálandó célfüggvény esetén ha van duális optimum, akkor az egész helyen is felvétetik. A duális feladat:

min(ry + gu − fv), y, u, v ≥ 0, ∑ (A_{j}(a)y(a)) + u_{j} − v_{j} = c_{j} ∀j = 1, …, k.

Soroljuk fel L elemeit olyan sorrendben, hogy a_{i} < a_{j} ⟹ i < j (pl. először felsoroljuk L minimális elemeit, azután a maradék halmaz minimális elemeit, és így tovább). Legyen (y, u, v) duális optimum. Tegyük fel, hogy {a ∈ L : y(a) > 0} nem lánc, azaz léteznek a, b összehasonlíthatatlan elemek, amelyekre y pozitív. Legyen Δ := min (y(a), y(b)), és változtassuk meg (y, u, v)-t.

u := u,
v_{j} := v_{j} + Δ · (A_{j}(a ∧ b) + A_{j}(a ∨ b) − A_{j}(a) − A_{j}(b)) ∀j = 1, …, k

y(c) := \{ \begin{matrix}y(c) + Δ & ha c = a ∧ b vagy c = a ∨ b, \\ y(c) − Δ & ha c = a vagy c = b, \\ y(c) & egyébként. \end{matrix}

A 3.1 Tétel bizonyításában részletezett számolások mintájára belátható, hogy (y, u, v) duál megengedett. A kikeresztezési eljárás végességének igazolása szintén megegyezik a korábban látottal. A végeredményként adódó megoldásban {a : y(a) > 0} lánc, és a konzekutivitás miatt az ennek megfelelő részmátrixban az 1-ek ill. −1-ek folyamatosan helyezkednek el, tehát a részmátrix teljesen unimoduláris. Az ebből kiszámítható optimális duális megoldás tehát egész. ■

5.3 Definíció. Az 5.2 Tétel-ben leírt poliédereket rendre szubmoduláris, szupermoduláris, ill. moduláris háló-poliédernek nevezzük.

Az elnevezés nem teljesen konzekvens, hiszen az első két esetben a jobboldali vektorra, a harmadikban pedig a mátrixra vonatkozik. Megemlítjük, hogy moduláris háló-poliédert kapunk akkor is, ha a definíciójában az Ax ≤ b feltételt Ax ≥ p-re cseréljük, ahol p szupermoduláris.

Az ezen dolgozatban leírt valamennyi poliéderosztály speciális esete a hálópoliédereknek. A legtöbb esetben közvetlenül látszik a definícióból, a lefogási poliéderek (T -) metszőn szupermoduláris változata pedig a 4.14 Tétel következtében.

Felmerül a kérdés, hogyan lehet jellemezni a konzekutív és szubmoduláris ill. szupermoduláris függvényeket. Választ a [7] eredményei adnak.

5.4 Definíció. Az f: L → \{0, 1\} függvényt \underline{növőnek} nevezzük, ha a ≤ b esetén f(a) ≤ f(b), fogyónak, ha a ≤ b esetén f(a) ≥ f(b).

Azonnal látszik, hogy növő vagy fogyó függvény konzekutív.

5.5 Lemma. Ha g_{1} növő, g_{2} fogyó. Ekkor f := g_{1} + g_{2} − 1 konzekutív. Ha g_{1} és g_{2} szubmoduláris/szupermoduláris/moduláris, akkor f is ilyen tulajdonságú.

Bizonyítás. Ha a ≤ b, akkor 0 ≤ g_{1}(b) − g_{2}(a) ≤ 1 és −1 ≤ g_{2}(b) − g_{1}(a) ≤ 0 miatt (5.1) teljesül. Ha pedig a ≤ b ≤ c, akkor 0 ≤ g_{i}(a) − g_{i}(b) + g_{i}(c) ≤ 1, tehát (5.2) is fennáll. A második állítás nyilvánvaló. ■

5.6 Lemma. Ha f konzekutív és szubmoduláris, akkor f^{+} is konzekutív és szubmoduláris, ahol f^{+} = max(f, 0).

Bizonyítás. f^{+} konzekutivitása magától értetődik, és kizárható a szubmodularitás szempontjából egyedül rossz f(a) = f(b) = 0, f(a ∧ b) = ±1, f(a ∨ b) = ∓1 eset. ■

Megjegyezzük, hogy szupermoduláris függvényekre a lemma nem marad érvényben, pl. L := {a, b, a ∧ b, a ∨ b}, f értékei rendre 1, -1, 0, 0.

5.7 Állítás. Legyen L háló, f konzekutív, továbbá

g^{1}(a) := max (f(b) : b ≤ a), g^{2}(a) := max (f(b) : b ≥ a).

Ekkor g^{1}, g^{2} konzekutív, és nemnegatív vagy nempozitív. Ha f szupermoduláris, akkor g^{1}, g^{2} is szupermoduláris. Ha L disztributív, és f szubmoduláris ill. moduláris, akkor g^{1}, g^{2} is szubmoduláris ill. moduláris.

Bizonyítás. a ≤ b esetén g^{1}(a) ≤ g^{1}(b), g^{2}(a) ≥ g^{2}(b), és (5.2) könnyen ellenőrizhető. Ha g^{1}(a) = −1 és g^{2}(b) = 1 állna, akkor létezik d ≤ a és e ≤ b, hogy f(d) = g^{1}(a) = −1 és f(e) = g^{1}(b) = 1. Ekkor d és e nem lehetnek összehasonlíthatók, ebből f(d∧e) = 0, ami d∧e ≤ a miatt ellentmond g^{1}(a) = −1-nek. Tehát g^{1} nemnegatív vagy nempozitív, amiből (5.2)-vel együtt adódik a konzekutivitás. g^{2}-re a bizonyítás analóg.

Tegyük fel, hogy f szupermoduláris, legyen d ≤ a, e ≤ b, hogy f(d) = g^{1}(a) és f(e) = g^{1}(b). Mivel d ∧ e ≤ a ∧ b és d ∨ e ≤ a ∨ b, ezért

g^{1}(a ∧ b) + g^{1}(a ∨ b) ≥ f(d ∧ e) + f(d ∨ e) ≥ f(d) + f(e) = g^{1}(a) + g^{1}(b),

tehát g^{1} szupermoduláris. g^{2}-re hasonlóan igazolható.

Végül legyen f szubmoduláris, L pedig disztributív. Ha g^{1}(a ∧ b) = 1, akkor g^{1}(a) = g^{1}(b) = g^{1}(a ∨ b) = 1. Ha viszont g^{1}(a ∧ b) ≤ 0, akkor legyen d ≤ a ∨ b olyan, hogy f(d) = g^{1}(a ∨ b). Ekkor

g^{1}(a ∨ b) = f(d ∧ (a ∨ b)) = f((d ∧ a) ∨ (d ∧ b)) ≤
≤ f(d ∧ a) + f(d ∧ b) − f(d ∧ a ∧ b).

Ha most f(d ∧ a ∧ b) = g^{1}(a ∧ b), akkor g^{1} szubmodularitása világos. Ha pedig g^{1}(a ∧ b) = 0 és f(d ∧ a ∧ b) = −1, akkor f konzekutivitása miatt g^{1}(a ∨ b) ≤ 0, ennélfogva g^{1}(a ∨ b) = g^{1}(a) = g^{1}(b) = 0, g^{1} most is szubmoduláris lesz. A bizonyítás g^{2}-re teljesen hasonló.

Az utolsó rész már következik az eddigiekből. ■

Ugyanígy igazolható az alábbi állítás.

5.8 Állítás. Legyen L háló, f konzekutív, továbbá

g̃^{1}(a) := min (f(b) : b ≤ a), g̃^{2}(a) := min (f(b) : b ≥ a).

Ekkor g̃^{1}, g̃^{2} konzekutív, és nemnegatív vagy nempozitív. Ha f szupermoduláris, akkor g̃^{1}, g̃^{2} is szupermoduláris. Ha L disztributív, és f szubmoduláris ill. moduláris, akkor g̃^{1}, g̃^{2} is szubmoduláris ill. moduláris.

5.9 Tétel. Legyen L háló, g: L → {0, 1} konzekutív. Ekkor létezik g^{1} növő és g^{2} fogyó függvény, hogy g = (g^{1} + g^{2} − 1)^{+}, továbbá 1. szupermoduláris g esetén g^{1}, g^{2} is szupermoduláris;

2. szubmoduláris g és disztributív L esetén g^{1}, g^{2} is szubmoduláris;

3. moduláris g és disztributív L esetén g^{1}, g^{2} is moduláris.

Bizonyítás. Definiáljuk g^{1}-et és g^{2}-t az 5.7 Állítás-ban leírt módon, f = g választással. Ekkor g^{1} növő, g^{2} fogyó lesz (nemnegatív is). Ha g(a) = 1, akkor g^{1}(a) + g^{2}(a) − 1 = 1, és a megfordítás is igaz, lévén g konzekutív. Ekkor persze g(a) = 0 ⟺ (g^{1}(a) + g^{2}(a) − 1)^{+} = 0. A többi állítás az 5.7 Állítás következménye. ■

Pontosan akkor teljesül (g^{1}+g^{2}−1)^{+} = g^{1}+g^{2}−1, ha minden a ∈ L, amelyre g(a) = 0, összehasonlítható valamely b ∈ L-lel, amelyre viszont g(b) = 1. Szupermoduláris, nemnegatív, nem azonosan nulla függvényre ez mindig igaz, szubmoduláris függvényre azonban általában nem teljesül: legyen L := {a, b, a ∨ b, a ∧ b}, g értékei rendre 1, 0, 0, 0.

5.10 Tétel. Legyen L háló, f: L → {0, ±1} konzekutív, és f ≠ 0.

1. Ha f szupermoduláris és valamely a_{0} ∈ L-re f(a_{0}) = 1, akkor létezik g^{1}, g^{2} növő ill. fogyó szupermoduláris függvény, hogy f = g^{1} + g^{2} − 1;

2. Ha f szubmoduláris és valamely a_{0} ∈ L-re f(a_{0}) = −1, akkor létezik g^{1}, g^{2} növő ill. fogyó szubmoduláris függvény, hogy f = g^{1} + g^{2} − 1;

3. Ha L disztributív, és f moduláris, akkor létezik g^{1}, g^{2} növő ill. fogyó moduláris függvény, hogy f = g^{1} + g^{2} − 1.

Bizonyítás. Legyen először f szupermoduláris, a g^{1}, g^{2} függvényeket pedig képezzük az 5.7 Állítás szerint. Ekkor g^{i}(a) = 1, ennélfogva g^{i} ≥ 0 (i = 1, 2). f(a) = 1 ⟺ g^{1}(a) + g^{2}(a) − 1 = 1. Tegyük fel, hogy f(a) = 0. Minthogy f(a_{0}) = 1, így a > a_{0} vagy a < a_{0} esetén g^{1}(a) vagy g^{2}(a) = 1, de mind a kettő nem állhat fenn. Ha a és a_{0} összehasonlíthatatlanok, akkor f szupermodularitása szerint f(a ∧ a_{0}) + f(a ∨ a_{0}) ≥ 1, így ismét g^{1}(a) vagy g^{2}(a) = 1, de csak az egyik igaz. Tehát g^{1}(a)+g^{2}(a)−1 = 0. Megfordítva, ha g^{1}(a)+g^{2}(a)−1 = 0, akkor f(a) ≤ 0. A -1 esetben f konzekutivitását használva g^{1}(a) = g^{2}(a) = 0 adódik. Végül világos, hogy g^{1}(a)+g^{2}(a)−1 = −1 maga után vonja f(a) = −1et. g^{1}, g^{2} szupermodularitása látszik az 5.7 Állítás-ból.

Ha f szubmoduláris, f := −f szupermoduláris, és f(a_{0}) = 1. Az első rész szerint f = g^{1} + g^{2} − 1, ahol

g^{1} = max (f(b) : b ≤ a) = − min (f(b) : b ≤ a) = −g̃^{1}(a),

g^{2} = −g̃^{2} hasonlóan. Így f = g̃^{1} + g̃^{2} + 1 az 5.8 Állítás-ban szereplő függvényekkel. Legyen most g^{i} := g^{i} + 1. Ekkor f = g^{1} + g^{2} − 1, g̃^{i} ≤ 0 miatt pedig g^{i} nemnegatív, növő ill. fogyó, és szubmoduláris.

Ha f moduláris, és valamely a_{0}-ra f(a_{0}) = 1, akkor az első rész szerint, ha valamely a_{0}-ra f(a_{0}) = −1, akkor a második rész szerint f = g^{1} + g^{2} − 1. g^{1}, g^{2} mindkét esetben növő ill. fogyó, továbbá az 5.7, 5.8 Állítás-ok szerint moduláris. ■

5.2. Greene és Greene – Kleitman tételei

Legyen (P, ≤), P = {p_{1}, …, p_{n}} részbenrendezett halmaz. Ismeretes, hogy a P -t fedő antiláncok minimális száma egyenlő a láncok hosszának maximumával, illetve a P -t fedő láncok minimális száma egyenlő az antiláncok elemszámának maximumával (Dilworth-tétel, ill. a tétel polárisa). Ezeket a tételeket hivatkozás nélkül is használjuk.

Felmerül a kérdés, mekkora elemszámú lehet legfeljebb γ db lánc ill. legfeljebb α db antilánc (diszjunkt) uniója. Legyen

c_{γ} = max {| ⋃_{i=1}^{γ} C_{i}| : C_{i} lánc} ill. a_{α} = max {| ⋃_{i=1}^{α} A_{i}| : A_{i} antilánc}.

Jelölje a ill. c a P -beli láncok ill. antiláncok hosszának maximumát. A fenti tételek szerint c_{a} = a_{c} = n, így a definíciók 1 ≤ α, γ ≤ n esetén érdekesek.

Mivel lánc és antilánc metszete legfeljebb egyelemű lehet, ezért tetszőleges A_{1}, …, A_{q} diszjunkt antiláncokra ill. C_{1}, …, C_{q} diszjunkt láncokra

c_{γ} ≤ qγ + |P − ⋃^{q} A_{i}| ill.

a_{α} ≤ qα + |P − ⋃^{q} C_{i}|, azaz

c_{γ} ≤ min {qγ + |P − ⋃^{q} A_{i}| : A_{1}, …, A_{q} diszjunkt antiláncok} ill.

a_{α} ≤ min {qα + |P − ⋃^{q} C_{i}| : C_{1}, …, C_{q} diszjunkt láncok}.

5.11 Tétel. [Greene] c_{γ} = min {qγ + |P − ⋃^{q} A_{i}| : A_{1}, …, A_{q} diszjunkt antiláncok}

5.12 Tétel. [Greene – Kleitman] a_{α} = min {qα+|P −⋃^{q} C_{i}| : C_{1}, …, C_{q} diszjunkt láncok}

Bizonyítás. [Hoffman – Schwarz] A tételeket egyszerre bizonyítjuk. Az 5.2 Tétel alapján az alábbi egyenlőtlenség-rendszerek teljesen duálisan egészértékűek:

x(A) ≤ t ∀A ∈ 𝒜, 0 ≤ x ≤ 1 (rögzített t ∈ ℤ^{+} mellett), ill.
x(A) + w ≥ |A| ∀A ∈ 𝒜, (x, w) ≥ 0.

Az 𝒜 halmazon a ⊓, ⊔ műveleteket kell tekinthetjük, hiszen ez moduláris, tehát mind szub-, mind szupermoduláris jobboldal esetén eleget tesz a háló-poliéder követelményeinek.

Legyen 1 ≤ γ ≤ n egész,

max 1x, x(A) ≤ γ ∀A ∈ 𝒜, 0 ≤ x ≤ 1,  (5.3 P)

és a megfelelő duális

min(1z + γ · 1y), z(p) + ∑ (y(A) : A ∈ 𝒜, p ∈ A) ≥ 1 ∀p ∈ P, (z, y) ≥ 0. (5.3 D)

Mivel (5.3 P) TDI, így van optimális 0-1 értékű x_{0} vektor. X := {p ∈ P : x_{0}(p) > 0}. x_{0}(A) = |X ∩ A| ≤ γ miatt X-ben minden antilánc legfeljebb γ elemű, tehát X legfeljebb γ db lánc uniója. Így max 1x = 1x_{0} ≤ c_{γ}. Másrészt

tetszőleges C_{1}, …, C_{γ} diszjunkt láncokra az Z = ⋃_{i=1}^{γ} C_{i} halmaz karakterisztikus

vektora primál megenegdett, így max{|Z| : Z = ⋃_{i=1}^{γ} C_{i}} ≤ max 1χ_{Z} ≤ max 1x.

Tehát

c_{γ} = max 1x = min(1z + γ · 1y).  (5.4)

Tekintsük most a (5.3 D) egy (z, y) optimális egész megoldását. Ekkor z és y 0-1 értékű. ℬ := {𝒜 : y(A) = 1} ⊆ 𝒜 jelölés mellett csak z = χ_{P −∪ℬ} lehetséges (különben a célfüggvény-érték kisebb volna). Tehát

min(1z + γ · 1y) = |P − ∪ℬ| + γ|ℬ| ≥ min {qγ + |P − ⋃^{q} A_{i}|},

ami (5.4)-gyel együtt épp az 5.13 Tétel nemtriviális egyenlőtlensége.

Vizsgáljuk most a

min(1x + αw), x(A) + w ≥ |A| ∀A ∈ 𝒜, (x, w) ≥ 0  (5.5 P)

ill.

max ∑ (y(A)|A| : A ∈ 𝒜), ∑ (y(A) : A ∈ 𝒜, p ∈ A) ≤ 1 ∀p ∈ P, ∑ (y(A) : A ∈ 𝒜) ≤ α, y ≥ 0 (5.5 D)

rendszereket, ahol 1 ≤ α ≤ n egész. Ekkor (5.5 P) TDI. Tekintsük (5.5 D) egy optimális egész megoldását. y nyilván 0-1 értékű. ℬ := {𝒜 : y(A) = 1}. Ekkor |ℬ| ≤ α, ℬ páronként diszjunkt antiláncokból áll, és ∑ y(A)|A| = | ∪ ℬ|, ezért

a_{α} ≥ max ∑ (y(A)|A|) = min(1x + αw).

Másrészt legfeljebb α diszjunkt antilánc uniójának karakterisztikus vektora duál megengedett, így

a_{α} = max ∑ (y(A)|A|) = min(1x + αw).  (5.6)

Térjünk át a (5.5 P) programra, legyen (x_{0}, w_{0}) optimális egész megoldás. Azt szeretnénk, ha x_{0} is 0-1 értékű volna. Tegyük fel, hogy valamely p ∈ P -re x_{0}(p) ≥ 1. Csak azok az antiláncok okozhatnak gondot, amelyek tartalmazzák p-t. De a feltétel teljesül A − p-re: x_{0}(A − p) + w_{0} ≥ |A − p| = |A| − 1, amiből x_{0}(A) + w_{0} = x_{0}(A − p) + x_{0}(p) + w_{0} ≥ |A| − 1 + 1 = |A|. Látszik tehát, hogy x_{0}(p) = 1 választással is primál megengedett vektort kapunk, és csak ez lesz optimális. Beláttuk, hogy 0 ≤ x_{0} ≤ 1. Legyen X := {p ∈ P | x_{0}(p) = 1}. Ekkor x_{0}(A) + w_{0} = |X ∩ A| + w_{0} ≥ |A|, amiből w_{0} ≥ |A| − |X ∩ A| = |A − X|, így

w_{0} ≥ max {|A − X| : A ∈ 𝒜} = max {|A| : A ∈ 𝒜, A ⊆ P − X} =
= α(P − X),

és (x_{0}, w_{0}) optimalitása miatt az elején is = áll, lévén (χ_{X}, α(P − X)) is megengedett megoldás. Tehát a Z := P − X halmaz q := α(Z) db lánc uniója, és

min(1x + αw) = 1x_{0} + αw_{0} = |X| + α · α(P − X) = |P − Z| + αq ≥
≥ min {αq + |P − ⋃ C_{i}|},

ami (5.6)-tal együtt az 5.14 Tétel nemtriviális irányú egyenlőtlensége. ■

Háló-mátrixok

A 4. fejezetben már megismerkedtünk a háló-mátrixokkal: olyan háló-polié-derekhez tartoznak, ahol L disztributív háló, a mártix oszlopai modulárisak. Bebizonyítottuk, hogy ezek a poliéderek szubmoduláris áram poliéderek. Az alábbiakban M. Cochand, A. Gaillard és H. Gröflin [1] és [2] cikkei alapján előbb példákat mutatunk háló-mátrixokra, majd jellemzésüket adjuk. Ezután néhány poliéderes előállítást igazolunk. Ebben a fejezetben kizárólag 0-1 hálómátrixokkal foglalkozunk, és feltesszük, hogy a háló legkisebb és legnagyobb elemének sorában csupa 0 áll. Az azonosan 0 sorokat csak a teljesség kedvéért hagyjuk meg. Az oszlopokról viszont feltehetjük, hogy nem azonosan nullák.

6.1. Példák

Valamely V véges halmazon adott ℱ keresztező halmazrendszer gyűrű-család, ha ∅, V ∈ ℱ. Legyenek 𝒞, 𝒟 gyűrű-családok. Az

ℒ := {L ⊆ V : L = C ∩ D, C ∈ 𝒞, D ∈ 𝒟, C ∪ D = V }

rendszert 𝒞 és 𝒟 metszetének, illetve metszet-családnak nevezzük. ℒ elemeit magukat is metszeteknek fogjuk hívni. Egy metszet persze többféle módon is előállhat. Legyen

ℱ := {(C, D) : C ∈ 𝒞, D ∈ 𝒟, C ∪ D = V }.

Ekkor az A ∈ {0, 1}^{ℱ×V} , A_{(C,D),v} = 1 ⟺ v ∈ C ∩ D – ami többször szereplő soroktól eltekintve éppen ℒ incidencia-mártixa – háló-mátrix.

ℱ háló az alábbi műveletekkel:

(C, D) ≤ (C′, D′) ⟺ C ⊆ C′ és D ⊇ D′,
(C, D) ∧ (C′, D′) := (C ∩ C′, D ∪ D′),
(C, D) ∨ (C′, D′) := (C ∪ C′, D ∩ D′).

A szükséges tulajdonságok könnyen ellenőrizhetők.

Legyen G = (V, E) irányított gráf, S ⊆ V irányított vágás magja (röviden mag), ha ϱ(S) = 0. Ismeretes, hogy magok metszete és uniója is mag. Irányított vágások egy (magok szerint) keresztező rendszerének incidencia-mátrixa hálómátrix. A 4.3 szakaszban láttuk, hogy a 0-1 háló-mártixok mind elő is állnak ilyen alakban.

6.2. Gyűrű-családok metszetei

Legyen A ∈ ℝ^{I×J} mátrix, U ⊆ J. Azt mondjuk, a B mártixot U összehúzásával kapjuk, ha az U elemeinek megfelelő oszlopokat kihagyjuk a mátrixból. Az U törlése viszont azt jelenti, hogy kihagyunk minden olyan sort is, amelynek van nullától különböző eleme az U-hoz tartozó oszlopokban.

6.1 Tétel. Tetszőleges A háló-mátrix előállítható alkalmas metszet-család incidencia-mátrixából néhány oszlop törlésével.

Bizonyítás. Legyen L az A háló-mátrix definíciójában szereplő disztributív háló, m := min(L), M := max(L). A 4.1 szakaszban tekintett reprezentáció során az ∨-irreducibilis elemek közül elhagyhatjuk a háló minimális elemét. Így az m-nek az üres halmazt feleltetjük meg. A többi ∨-irreducibilis elem alkotja az U halmazt, ez tehát a reprezentáció alaphalmaza. A reprezentáló leképezést Φval jelöljük. Az L-beli elemek jelölésére (esetleg indexelt) S betűket használunk.

A mátrix oszlopait j ∈ {1, …, k} = J-vel indexeltük. Fontos szerepet szerepet játszanak az

S_{j}^{1} = ⋀ (S ∈ L : A_{j}(S) = 1)
S_{j}^{2} = ⋁ (S ∈ L : A_{j}(S) = 1)
S_{j}^{3} = ⋀ (S ∈ L : S ≰ S_{j}^{2})

elemek. Láttuk, hogy A_{j}(S) = 1 ⟺ S_{j}^{1} ≤ S ≤ S_{j}^{2}. Az is világos, hogy S_{j}^{1} ∨-irreducibilis. Ha ugyanis előállna valódi unióként, akkor – mivel a nála kisebb elemek az A_{j} függvénnyel 0 értéket kapnak – A_{j}(S_{j}^{1}) = 0 adódna, holott ez az érték 1.

Belátjuk, hogy S_{j}^{3} is ∨-irreducibilis. Tegyük fel először, hogy S_{j}^{2} ≤ S_{j}^{3}. Ekkor S_{j}^{2} mindenkivel összehasonlítható, S_{j}^{3} egyetlen elemet fed L-ben (hálóelméleti értelemben), mégpedig S_{j}^{2}-t, tehát csak a triviális módon állhat elő unióként. Tegyük most fel, hogy S_{j}^{3} ≤ S_{j}^{2}. Ekkor létezik X, Y ∈ L, amire X, Y ≰ S_{j}^{2}, X, Y fedik S_{j}^{3}-t, és S_{j}^{3} = X ∩ Y. A_{j}(X) = A_{j}(Y) = 0, így A_{j}(S_{j}^{3}) = 0. Másrészt X-re és S_{j}^{2}-re a modularitást felírva A_{j}(S_{j}^{3}) = 1 adódik. Ez az eset tehát nem valósulhat meg. Végül ha S_{j}^{3} és S_{j}^{2} összehasonlíthatatlan, és S_{j}^{3} = X ∪ Y, X, Y < S_{j}^{3}, akkor megint csak a modularitásból A_{j}(X) = A_{j}(Y) = 1, ebből A_{j}(S_{j}^{3}) = 1. Másrészt nyilván A_{(}S_{j}^{3}) = 0 ellentmondás.

Tekintsük U-n a következő súlyozást: w_{j}(S_{j}^{1}) := 1, w_{j}(S_{j}^{3}) := −1, w_{j}(S) := 0 egyébként. Azonnal látható, hogy minden S ∈ L-re A_{j}(S) = w_{j}(Φ(S)). Jelölje w_{j}^{+} ill. w_{j}^{−} a súlyfüggvény pozitív ill. negatív részét, és legyen S ∈ L esetén w_{j}^{±}(S) := w_{j}^{±}(Φ(S)).

Definiáljuk az alábbi halmazrendszereket.

C_{S} := {j ∈ J : w_{j}^{+}(S) = 1}, D_{S} := {j ∈ J : w_{j}^{−}(S) = 0} minden S ∈ L-re, 𝒞 := {C_{S} : S ∈ L}, 𝒟 := {D_{S} : S ∈ L},

Először igazoljuk, hogy 𝒞 és 𝒟 gyűrű-családok a J halmazon. Legyen S, T ∈ L. C_{S} ∩ C_{T} = {j ∈ J : w_{j}^{+}(S) = w_{j}^{+}(T) = 1}. w_{j} definíciója szerint w_{j}^{+}(S) = w_{j}^{+}(T) = 1 ⟺ S_{j}^{1} ∈ Φ(S ∧ T). Következésképpen C_{S} ∩ C_{T} = C_{S∧T}. Hasonlóan mutatható meg, hogy C_{S} ∪ C_{T} = C_{S∨T}, D_{S} ∩ D_{T} = D_{S∨T}, D_{S} ∪ D_{T} = D_{S∧T}, tehát 𝒞, 𝒟 ∩, ∪-zárt rendszerek. Mivel pedig w_{j}^{+}(m) = w_{j}^{−}(m) = 0 és w_{j}^{+}(M) = w_{j}^{−}(M) = 1 (minthogy az oszlop nem azonosan nulla), ezért C_{m} = ∅, D_{m} = J, C_{M} = J, D_{M} = ∅, így 𝒞, 𝒟 gyűrű-családok.

Ekkor minden S ∈ L-re C_{S} ∪ D_{S} = J, és A a {C_{S} ∩ D_{S} : S ∈ L} halmazrendszer incidencia-mátrixa, ez pedig része az összes metszetek

ℒ := {C ∩ D : C ∈ 𝒞, D ∈ 𝒟, C ∪ D = J} =
= {C_{S} ∩ D_{T} : S, T ∈ L, C_{S} ∪ D_{T} = J}

családjának. Az S ≠ T halmazokhoz tartozó metszetek eltávolítása céljából bővítsük ki J-t J ∪ U-vá, a halmazrendszereket pedig az alábbi módon.

𝒞^{U} := {C_{S}^{U} = C_{S} ∪ Φ(S) : S ∈ L}, 𝒟^{U} := {D_{S}^{U} = D_{S} ∪ (U − Φ(S)) : S ∈ L}.

Azonnal adódik, hogy ezek is gyűrű-családok: C_{S}^{U} ∩ C_{T}^{U} = C_{S∧T}^{U}, C_{S}^{U} ∪ C_{T}^{U} = C_{S∨T}^{U}, C_{m}^{U} = ∅, C_{M}^{U} = J ∪ U, stb. Az

ℒ^{U} := {C_{S}^{U} ∩ D_{T}^{U} : C_{S}^{U} ∈ 𝒞_{U}, D_{T}^{U} ∈ 𝒟^{U}, C_{S}^{U} ∪ D_{T}^{U} = J ∪ U}

metszet-család minden S ≠ T -ből származó eleme belemetsz U-ba, az S = T esetből származóak pedig nem. Az U-nak megfelelő oszlopokat kiválasztva a tételben kimondott konstrukció (többszörös soroktól eltekintve) az A mátrixot szolgáltatja. ■

6.2 Lemma. Legyen 𝒞 gyűrű-család a V halmazon. Definiáljuk a G_{𝒞} = (V, E) irányított gráfot: v, w ∈ V, v ≠ w esetén vw ∈ E pontosan akkor, ha v ∈ C ∈ 𝒞ből következik, hogy w ∈ C. Ekkor 𝒞 éppen az irányított vágások magjainak komplementereiből áll (vagyis amikor δ(X) = 0).

Bizonyítás. Nyilvánvaló, hogy C ∈ 𝒞-re δ(C) = 0. Tegyük fel, hogy X ⊆ V, δ(X) = 0. Legyen v ∈ X, w ∈ V − X. vw ∉ E miatt van olyan C_{v,w} ∈ 𝒞, amire v ∈ C_{v,w}, w ∉ C_{v,w}. Ekkor

v ∈ ⋂_{w∈V −X} C_{v,w} ⊆ X, így

⋃_{v∈X} ⋂_{w∈V −X} C_{v,w} = X ∈ 𝒞.

■

Legyen 𝒞 és 𝒟 gyűrű-család a V halmazon, legyen ℒ a metszet-családjuk. Legyen továbbá 𝒟 := {D = V − D : D ∈ 𝒟}, nyilván ez is gyűrű-család. Készítsük el 𝒞 és 𝒟 fenti lemma szerinti gráf-reprezentációit: G_{𝒞} = (V, E_{k}), G_{𝒟} = (V, E_{p}). A két gráf egyesítésből kapjuk a H = (V, E_{k} ∪ E_{p}), két színnel színezett gráfot (a színek természetesen kék és piros). Világos, hogy 𝒞 = {C ⊆ V : Δ(C) ∩ E_{k} = ∅}, 𝒟 = {D ⊆ V : Δ(D) ∩ E_{p} = ∅}, ahol Δ(Z) jelöli a kilépő élek halmazát (most éppen a H gráfban). A H gráf mindkét színre tranzitív, azaz uv, vw ∈ E_{k} (ill. E_{p}) esetén uw ∈ E_{k} (ill. E_{p}). H-beli k-p-útnak nevezzük pontok olyan v_{1}, …, v_{2n+1} sorozatát, ahol n ≥ 0, továbbá n ≥ 1 esetén alternáló utat alkotnak, és az első él kék. Ha n ≥ 1, v_{1} = v_{2n+1}, és az színek váltakozva következnek, akkor k-p-körről beszélünk. Adott X ⊆ V esetén v_{1}, …, v_{2n+1} X-hez tartozó k-p-fül, ha k-p-út, n ≥ 1, v_{1}, v_{2n+1} ∈ X, a többi pont nincs X-ben. Amennyiben itt v_{1} = v_{2n+1}, akkor azt is megköveteljük, hogy v_{1}v_{2} kék legyen. A P út vagy kör pontjainak halmazát V (P) jelöli.

6.3 Tétel. L ⊆ V pontosan akkor metszet (azaz ℒ-beli), ha nincs hozzá tartozó k-p-fül.

Bizonyítás. Legyen L = C∩D metszet, és tegyük fel, hogy v_{1}, …, v_{2n+1} L-hez tartozó k-p-fül. Legyen S := {v_{2}, …, v_{2n}}. S∩C∩D = ∅, S = (S∩C)∪^{∗}(S∩D). Figyeljük meg, hogy ha v_{i} ∈ C, i páratlan, i ≤ 2n, akkor v_{i+1} ∈ C (hiszen Δ(C) ∩ E_{k} = ∅), továbbá ha v_{i} ∈ D, i páratlan, i > 1, akkor v_{i−1} ∈ D (mivel Δ(D) ∩ E_{p} = ∅). Minthogy v_{1}, v_{2n+1} ∈ C ∩ D, v_{2} ∈ S ∩ C, v_{2n} ∉ S ∩ C, létezik olyan páros i, amire i < 2n, v_{i} ∈ S ∩ C és v_{i+1} ∉ S ∩ C. De ekkor v_{i+1} ∈ S ∩ D, így v_{i} ∈ S ∩ D, tehát v_{i} ∈ S ∩ C ∩ D ellentmondás.

Tegyük most fel, hogy L ⊆ V -hez nem található k-p-fül. v ∉ L esetén a v_{1}, …, v_{k}, k > 1 út L-ből v-be vezető út, ha v_{1} ∈ L, v_{k} = v, i > 1-re v_{i} ∉ L, illetve v-ből L-be vezető út, ha v_{1} = v, v_{k} ∈ L, i < k-ra v_{i} ∉ L. Legyen

C := L ∪ {v ∉ L : létezik út L-ből v-be, ahol az első él kék} D′ := L ∪ {v ∉ L : létezik út v-ből L-be, ahol az utolsó él piros} Ekkor C ∈ 𝒞, D′ ∈ 𝒟, D := D′ ∪ C ∈ 𝒟, C ∪ D = V, és L ⊆ C ∩ D = C ∩ D′. Tegyük fel, hogy v ∈ (C ∩ D) − L. Ekkor létezik P út L-ből v-be, ami kék éllel kezdődik, és létezik P′ út v-ből L-be, ami piros élre végződik. A P ∪ P′ út első éle tehát kék, az utolsó piros, szélső pontjai L-be esnek, de a belseje diszjunkt L-től. A színosztályok tranzitivitását kihasználva k-p-fület kapunk. Tehát L = C ∩ D. ■

Legyen P = v_{1}, …, v_{2n+1} k-p-út vagy k-p-kör. Az x ∈ ℝ^{V}, x(v_{2i+1}) = 1 (i = 0, …, n), x(v_{2i}) = −1 (n ≥ 1, i = 1, …, n), x(v) = 0 (egyéb helyeken) vektort az út ill. kör alternáló vektorának nevezzük és d_{P} -vel jelöljük. Legyenek B_{i}, i ∈ I ill. R_{j}, j ∈ J a H-beli k-p-utak ill. k-p-körök alternáló vektorai, az ezekből mint sorokból összeállított mátrixokat B ill. R jelöli.

6.4 Tétel. Az x ≥ 0, Bx ≤ 1, Rx ≤ 0 rendszer teljesen duálisan egészértékű.

Bizonyítás. Megadunk egy algoritmust, ami a

min 1y, yB + zR ≥ c, y, z ≥ 0  (6.1)

duális program egy egész optimumát számítja ki. Megjegyezzük, hogy az egyetlen pontból álló k-p-utak alternáló vektorai B-ben egységmátrixot alkotnak, ezért mindig létezik az optimum. (6.1) egy megoldását homogénnek hívjuk, ha az (y, z) tartójának megfelelő sorok alkotta részmátrixban minden oszlop vagy nemnegatív, vagy nempozitív. Először azt igazoljuk, hogy mindig létezik homogén megoldás.

Definiájuk egy (y, z) optimális megoldás h ∈ ℝ_{+}^{V} inhomogenitási vektorát:

h_{v} := min(λ_{v}^{+}, λ_{v}^{−}), ahol
λ_{v}^{∗} := ∑ (y_{i} : B_{iv} = ∗1) + ∑ (z_{j} : R_{jv} = ∗1), ∗ = +, − v ∈ V

(y, z) pontosan akkor homogén, ha a hozzá tartozó h nullvektor. Ha h ≠ 0, akkor konstuálunk olyan optimális megoldást, amelyre h ≤ h, h ≠ h. Legyen v olyan pont, ahol h_{v} ≠ 0. Létezik a \left[{B \atop R}\right] mátrixban két alternáló vektor (y, z) tartójában, legyenek ezek d_{P} és d_{Q}, hogy d_{P} (v) = 1 és d_{Q}(v) = −1.

Tegyük fel először, hogy P és Q k-p-kör. Legyen U := {v ∈ V (P) ∪ V (Q) : d_{P} (v) · d_{Q}(v) = −1} és ε := min(z_{P} , z_{Q}). Megmutatjuk, hogy léteznek S_{k}, k = 1, …, m k-p-körök, hogy

supp(d_{S_{k}}) ⊆ supp(d_{P}) ∪ supp(d_{Q}), k = 1, …, m,  (6.2)
d_{P} + d_{Q} = ∑ (d_{S_{k}} : k = 1, …, m),  (6.3)
v ∈ U ⟹ d_{S_{k}}(v) = 0, k = 1, …, m,  (6.4)
v ∉ U ⟹ d_{S_{k}}(v) · d_{P} (v) ≥ 0 és d_{S_{k}}(v) · d_{Q}(v) ≥ 0 k = 1, …, m. (6.5)

Ekkor (y, z,

z_{T} := \{ \begin{matrix}z_{T} − ε & T = P, Q, \\ z_{T} + ε & T = S_{k}, k = 1, …, m, \\ z_{T} & egyébként \end{matrix}

is optimális megoldás, és a h inhomogenitási vektorára h ≤ h, h ≠ h, mivel h_{v} = h_{v}, ha v ∉ U, és h_{v} = h_{v} − ε, ha v ∈ U.

Az S_{1}, …, S_{m} köröket a következő módon kaphatjuk. Legyen F = (V (P) ∪ V (Q), E(P) ∪ E(Q). Ebben a gráfban minden v ∈ U pontra igaz, hogy két különböző színű él lép be és ki, a v ∉ U pontokra pedig az teljesül, hogy a belépő élek mind egyszínűek, a kilépőek pedig a másik színosztályból valók. Készítsük el az F′ = (V (P) ∪ V (Q), E′) gráfot az allábbi két művelet ismételt végrehajtásával: (1) töröljük az ab és ba éleket, ha ezek ugyanolyan színűek;

(2) minden maximális egyszínű utat helyettesítsünk egy ugyanolyan színű, az út kezdőpontjából a végpontjába vezető éllel (ilyen él létezik H-ban). Minthogy F′-ben minden pont ki-foka megegyezik a be-fokával, ezért F′ felbontható S_{1}, …, S_{m} körökre. Ezek a körök k-p-körök lesznek. F′ pontjai kétfélék lehetnek: vagy izolált, ha F -ben pontosan egy be-, ill. kilépő éle van, és ezek persze azonos színűek, vagy a be-foka, a ki-fokával, és ezen élek színezése megegyezik az F -belivel. Az első típusú pontok éppen U elemei. A (6.2)-(6.5) tulajdoságok könnyen ellenőrizhetőek.

Tegyük fel, hogy P k-p-út, Q pedig k-p-kör. Vegyünk hozzá H-hoz egy új q pontot, és két, alkalmasan színezett élt, hogy P k-p-kör legyen. A fentiek felhasználásával kapjuk az S_{1}, …, S_{m} köröket. A q pont elhagyása pontosan egy kört érint, és egy k-p-út vissza. Itt is elkészíthető tehát olyan optimális megoldás, amelynek inhomogenitási vektora kisebb. Hasonlóan tárgyalható két k-p-út esete.

Az eljárás végességének igazolásához ismét csak a 3.1 Tétel-ben látott ötlet siet segítségünkre. A kiindulási (y_{0}, z_{0}) választható racionálisnak, így minden közbülső ε többszöröse \frac{1}{N} -nek, így legfeljebb N · 1h_{0} lépésben homogén megoldást kapunk, ahol h_{0} a kiindulási megoldás inhomogenitási vektora.

Rátérünk az ígért duális algoritmusra. Az egyszerűbb tárgyalás kedvéért feltesszük, hogy H-ban nincsenek k-p-körök. Az algoritmus lépései a következők.

(1) Legyen V^{+} := {v ∈ V : c_{v} ≥ 0}, V^{−} := {v ∈ V : c_{v} < 0}. A G^{∗} = (V^{∗}, E^{∗}) gráf ponthalmaza álljon V^{+} egy, V^{−} két példányából, továbbá egy forrásból és egy nyelőből:

V^{∗} := V^{+} ∪ V^{1−} ∪ V^{2−} + s + t.

v ∈ V -re jelölje a megfelelő példánybeli elemet v^{+}, v^{1−}, v^{2−} értelemszerűen, illetve v^{∗}, ha világos, hogy melyik példányról van szó. Legyen

E^{∗} := {sv^{∗}, v^{∗}t : v^{∗} ∈ V^{+} ∪ V^{2−}} ∪
∪{v^{∗}w^{1−} : v^{∗} ∈ V^{+} ∪ V^{2−}, w^{1−} ∈ V^{1−}, vw ∈ E_{k}} ∪
∪{w^{1−}v^{∗} : v^{∗} ∈ V^{+} ∪ V^{2−}, w^{1−} ∈ V^{1−}, wv ∈ E_{p}}.

Legyenek a pontokhoz rendelt alsó és felső kapacitások

[ℓ_{v^{∗}}, u_{v^{∗}}] := \{ \begin{matrix}[c_{v}, ∞] & v^{∗} ∈ V^{+}, \\ [0, ∞] & v^{∗} ∈ V^{2−}, \\ [0, −c_{v}] & v^{∗} ∈ V^{1−}. \end{matrix}

(2) Határozzunk meg egy f ∈ ℝ_{+}^{E^{∗}} minimális egész folyamot, legyen a folyamérték β.

(3) Bontsuk fel f-et út-folyamok lineáris kombinációjára: f = ∑ (α_{i}p_{i} : i = 1, …, k), ahol p_{i} a P_{i}^{∗} út incidencia-vektora.

(4) Készítsük el a G^{∗}-beli P_{i}^{∗} utakból a megfelelő P_{i} k-p-utakat H-ban, legyen y_{P}^{∗} := α_{i}, ha P = P_{i}, y_{P}^{∗} := 0 egyébként.

Azt állítjuk, hogy az így kapott y^{∗} optimális duális megoldás. A bizonyítás első részéből tudjuk, hogy létezik y homogén optimális vektor, ehhez megfeleltethető egy 1y értékű megengedett folyam G^{∗}-ban. Jelölje ugyanis B′ az y tartójának megfelelő sorokból alkotott mátrixot, készítsünk B′ minden sorához (egy P_{i} k-p-úthoz) egy G^{∗}-beli utat a természetes módon, illetve minden ilyen P_{i}^{∗} útra y_{P_{i}} nagyságú út-folyamot. Ezen út-folyamok összege egy f megengedett folyam lesz. Tehát min 1y ≥ β.

Figyeljük meg, hogy G^{∗}-ban nincs kör. Tegyük fel ugyanis, hogy {v_{1}, …, v_{n} = v_{1}} ⊆ V^{∗} kör , a megfelelő V -beli pontok {w_{1}, …, w > n}. Ekkor létezik olyan i, j, hogy w_{i} = w_{j}, és w_{i}, …, w_{j−1} mind különbözőek. G^{∗} konstrukciója szerint j > i + 1. Ha v_{i} = v_{j}, akkor w_{i}, …, w_{j} = w_{i} k-p-kör volna. Tehát j > i + 2, v_{i} ∈ V^{1−} és v_{j} ∈ V^{2−}, vagy fordítva, ekkor pedig w_{i+1}, …, w_{j−1}, w_{i+1} lesz k-p-kör (közben kihasználtuk H tranzitivitását). Ebből következik, hogy a (3) lépésbeli felbontás létezik.

Legyen P_{i}^{∗} = {s, v_{1}, …, v_{n}, t} G^{∗}-beli út, w_{1}, …, w_{n} a megfelelő út H-ban. A fentihez hasonló érveléssel adódik, hogy ez k-p-út lesz. Tehát a (4)-beli értékadás is jól definiált. Az algoritmusból kapott y^{∗} megendedett megoldás, hiszen

∑ (y_{i}^{∗}B_{iv}) = ∑ (α_{i} : v^{+} ∈ V (P_{i}^{∗})) = f(Δ(v^{+})) ≥ ℓ_{v^{+}} minden v ∈ V^{+}-ra,

és

∑ (y_{i}^{∗}B_{iv}) = ∑ (α_{i} : v^{2−} ∈ V (P_{i}^{∗})) − ∑ (α_{i} : v^{1−} ∈ V (P_{i}^{∗})) ≥
≥ − ∑ (α_{i} : v^{1−} ∈ V (P_{i}^{∗})) = −f(Δ(v^{1−})) ≥ −u_{v^{1−}} minden v ∈ V^{−}-ra.

Tehát β = 1y^{∗}, azaz a kapott megoldás valóban optimális. Minthogy f egészértékű volt, a dekompozíció során adódó α_{i}-k is választhatók egésznek, így y^{∗} is egész lesz.

Az általános esetben H tartalmazhat k-p-köröket. Ekkor a (2)-beli folyam felbontható (G^{∗}-beli) P_{i}^{∗} utakra és Q_{j}^{∗} körökre. Minden P_{i}^{∗} felbontható egy útra és néhány körre, minden Q_{j}^{∗} pedig legalább egy körre. Az eljárás hasonló a homogén megoldás létezését bizonyító részben leírt módszerhez. A bizonyítást nem részletezzük. ■

6.5 Tétel. A 𝒫^{∗} = {x ∈ ℝ^{V} : Bx ≤ 1, Rx ≤ 0, x ≥ 0} poliéder ℒ poliéderes leírása: 𝒫^{∗} csúcsai éppen ℒ elemeinek incidencia-vektorai.

Bizonyítás. Az előző tétel szerint 𝒫^{∗} egész poliéder, és nyilván P^{∗} ⊆ [0, 1]^{V}, így csúcsai éppen a tartalmazott 0-1 vektorok.

Legyen x^{L} az L metszet incidencia-vektora, B_{i} pedig B egy sora, azaz egy P k-p-út alternáló vektora. Megmutatjuk, hogy B_{i}x^{L} = B_{i}(L) ≤ 1. Ha L ∩ V (P) = ∅, akkor B_{i}x^{L} = 0. Egyébként pedig legyenek P_{1}, …, P_{m} P -nek a maximális, L-be eső részútjai, a természetes módon rendezve, legyen v_{k} ill. w_{k} az első ill. utolsó pont P_{k}-ban. A P út minden olyan v pontjára, amelyre B_{iv} = 1, az út során belépő él piros, a kilépő pedig kék, feltéve, hogy az él létezik. Következésképpen minden 1 ≤ k < m, B_{iw_{k}} = 1 esetén B_{iv_{k+1}} = −1, másszóval a w_{k}, …, v_{k+1} részút L-hez tartozó k-p-fül volna. Így L∩V (P) elemei közül legfeljebb eggyel több elem kap a B_{i} vektorban 1-et, mint ahány −1-et, ezért B_{i}x^{L} ≤ 1. Hasonlóan igazolhatóak a k-p-körökre vonatkozó feltételek. Tehát minden L metszet esetén x^{L} csúcsa 𝒫-nek.

Megfordítva, legyen x 𝒫-beli 0-1 vektor, azaz valamely S halmaz incidenciavektora. Ha most S ∉ ℒ, akkor S-hez található k-p-fül, legyen e fül alternáló vektora B_{i} ill. R_{j}, attól függően, hogy a fül k-p-út vagy k-p-kör. Ekkor B_{i}x = B_{i}(S) = 2 ill. R_{j}x = R_{j}(S) = 1, tehát x ∉ 𝒫 adódik. ■

Legyen A ∈ {0, 1}^{ℱ×J} háló-poliéder. Megadjuk a sorok konvex burkának poliéderes leírását. Jelölje az A mátrix sorainak konvex burkát Conv(A), a mártix sorai és a nullvektor konvex burkát Conv(A, 0), a sorok által feszített kúpot Cone(A). Tekintsük a 𝒫 = {x ∈ ℝ^{J} : Ax ≤ 1} poliédert, és ennek polárisát: 𝒫^{∗} = {x ∈ ℝ^{J} : xz ≤ 1 ∀z ∈ 𝒫}. Közismert eredmény (megtalálható pl. [10]-ben), hogy

(𝒫^{∗})^{∗} = 𝒫,  (6.6)
Conv(A) = 𝒫^{∗},  (6.7)
𝒫 = Conv(B, 0) + Cone(R) − ℝ_{+}^{J} ⟺
⟺ 𝒫^{∗} = {x ∈ ℝ^{J} : Bx ≤ 1, Rx ≤ 0, x ≥ 0}.  (6.8)

Emlékeztetünk, hogy ebben a fejezetben feltettük, hogy az azonosan 0 sor szerepel a háló-mátrixokban.

Amennyiben A az ℒ metszet-család incidencia-mátrixa, akkor a fenti tételből azt kapjuk, hogy

Conv(A) = 𝒫^{∗} = {x : Bx ≤ 1, Rx ≤ 0, x ≥ 0}.

A 6.1 Tétel szerint a metszet-családokról szóló eredményeket felhasználhatjuk tetszőleges háló-mátrixoknál.

6.6 Tétel. Legyen A′ ∈ ℝ_{+}^{I′×(J+U)} mátrix, az U törléséből származó mátrix pedig A ∈ ℝ_{+}^{I×J}. 𝒫′ := {(x, u) ∈ ℝ^{J×U} : A′(x, u) ≤ 1} és 𝒫 := {x ∈ ℝ^{J} : Ax ≤ 1}, jelölje a megfelelő polárisokat 𝒫′^{∗} ill. 𝒫^{∗}. Ekkor

(a) Ha 𝒫′^{∗} = {(x, u) : x, u ≥ 0, B′(x, u) ≤ 1, R′(x, u) ≤ 0}, akkor 𝒫^{∗} = {x : x ≥ 0, Bx ≤ 1, Rx ≤ 0}, ahol B, R B′, R′-ből kapható U összehúzásával.

(b) Ha az előzőben a B′(x, u) ≤ 1, R′(x, u) ≤ 0, x, u ≥ 0 rendszer TDI, akkor a Bx ≤ 1, Rx ≤ 0, x ≥ 0 rendszer is TDI.

Bizonyítás. (a) Könnyen látszik, hogy 𝒫′ vetülete ℝ^{J}-re éppen 𝒫, azaz

𝒫 = {x ∈ ℝ^{J} : ∃(x, u) ∈ 𝒫′}.

(6.8) szerint

𝒫′ = Conv(B′, 0) + Cone(R′) − ℝ^{J+U}, így
𝒫 = Conv(B, 0) + Cone(R) − ℝ^{J},

tehát 𝒫^{∗} = {x : x ≥ 0, Bx ≤ 1, Rx ≤ 0}.

(b) Legyen c ∈ ℤ^{J}, és tekintsük a

min 1y, yB + zR ≥ c, y, z ≥ 0  (6.9 D)

duális programot, legyen (y^{∗}, z^{∗}) optimális megoldás, jelölje (6.9 P) a megfelelő primál feladatot, legyen x^{∗} primál optimális vektor. A J ∪ U partíció szerint kszítsük el a következő felbontást: B′ = (B, B^{U}), R′ = (R, R^{U}). Legyen c^{U} := ⌊y^{∗}B^{U} + z^{∗}R^{U}⌋, c′ := (c, c^{U}). Tekintsük most a

min 1y, y(B, B^{U}) + z(R, R^{U}) ≥ c′, y, z ≥ 0  (6.10 D)

feladatot, illetve a (6.10 P) primál problémát. Ekkor (y^{∗}, z^{∗}) ill. (x^{∗}, 0) megengedett megoldások, ezért (6.10 D)-nek létezik optimális megoldása. Minthogy a feltétel szerint (6.10 P) egyenlőtlenségrendszere TDI, így van (y′, z′) egész optimális vektor is. Világos, hogy ez (6.9 D)-nek is egész optimális megoldása, vagyis Bx ≤ 1, Rx ≤ 0, x ≥ 0 TDI. ■

Tetszőleges A háló-mátrix sorainak konvex burkát tehát a következőképpen kaphatjuk meg. Készítsük el a 6.1 Tétel szerint az ℒ^{U} metszet-családot, amelynek incidencia-mátrixából U törlésével áll elő A. ℒ^{U} reprezentáló gráfjában keressük meg a k-p-utakat és a k-p-köröket, ezek alternáló vektoraiból állítsuk össze a B′ és R′ mátrixokat, végül ezekben húzzuk össze U-t.

Ennek az előállításnak csak az a hibája, hogy nagyon sok sora lehet a mátrixoknak. Az alábbiakban megmutatjuk, hogy nem szükséges az összes k-p-út ill. kör Conv(A) leírásához.

Legyen A ∈ {0, 1}^{L×J} háló-mátrix. Emlékeztetünk a 6.1 Tétel halmazrendszereire:

𝒞^{U} = {C_{S}^{U} = {j ∈ J : w_{j}^{+}(S) = 1} ∪ Φ(S) : S ∈ L},
𝒟^{U} = {D_{S}^{U} = {j ∈ J : w_{j}^{−}(S) = 0} ∪ (U − Φ(S)) : S ∈ L}.

Legyen H = (J ∪ U, E_{k} ∪ E_{p}) az ℒ^{U}-t reprezentáló gráf. A k-p-utak ill. körök alternáló vektorai alkotják a B′ ill. R′ mátrixokat.

Legyen P H-beli út. Egy P′ részutat elkerülő útnak nevezünk, ha legalább három pontja van, végpontjai J-be, belső pontjai U-ba esnek. A három pontú elkerülő útra a könyök elnevezést használjuk.

6.7 Lemma. Legyen P k-p-út H-ban, V (P)∩J ≠ ∅. Ekkor létezik olyan (esetleg üres) k-p-út H-ban, hogy

(a) V (P′) ⊆ V (P) és P′ végpontjai J-ben vannak,

(b) P′ elkerülő részútjai (ha vannak) könyökök,

(c) B′_{P′j} ≥ B′_{P j} minden j ∈ J-re.

Bizonyítás. Ha V (P) ⊆ J, akkor P′ = P választható. A továbbiakban feltehető, hogy P -nek mind U-ban, mind J-ben van pontja. P = v_{1}, …, v_{2n+1}. Legyen P′ az a részút, amelyik a sorrendben első, páratlan indexű J-beli ponttól az utolsó ilyenig vezet. (Ha a páratlan indexű helyek mind U-beliek, akkor P′ = ∅ eleget tesz a feltéleknek.) Világos, hogy P′ k-p-út, és hogy megfelel (a)-nak és (c)-nek. Tegyük fel, hogy P′-nek létezik v_{1}, …, v_{k}, k > 3 elkerülő részútja, legyenek az élei e_{1}, …, e_{k−1}. A C^{U},D^{U} gyűrű-családok, ill. a H gráf definíciójából következik, hogy minden U-ból kilépő e élre

e ∈ E_{k} ⟺ e ∈ E_{p},

ezért Δ(U)-ban a kék és piros élek párhuzamosak. Tehát ha e_{1}, e_{k−1} ∈ E_{k} (E_{p}), akkor létezik e = v_{1}v_{k} ∈ E_{k} (E_{p}). Ha e_{1} ∈ E_{k} (E_{p}) és e_{k−1} ∈ E_{p} (E_{k}), akkor akkor pedig létezik e_{1}, e = v_{2}v_{k}, e ∈ E_{p} (E_{k}) élekből álló könyök, méghozzá k-p-könyök (a násik esetben p-k-könyök). Minden esetben az elkerülő utak áthidalhatóak vagy egyetlen éllel, vagy egy könyökkel, és továbbra is k-p-utat kapunk. Az eljárás végén (b)-nek is eleget tevő úthoz jutunk. ■

Ugyanígy bizonyítható, hogy Q k-p-kör, V (Q) ∩ J ≠ ∅ esetén van olyan Q′ k-p-kör H-ban, amire V (Q′) ⊆ V (Q), az elkerülő részútjai könyökök, és minden j ∈ J-re R_{Q′j} = R_{Qj}. Definiálhatjuk tehát a

H′ := (J, E′_{k} ∪ E′_{p} ∪ E′_{kp} ∪ E′_{pk})

gráfot, ahol E′_{k} = E_{k} ∩ Δ_{H}(J), E′_{p} = E_{p} ∩ Δ_{H}(J), és e ∈ E′_{kp} (E′_{pk}) pontosan akkor, ha H-ban létezik e tövéből e fejébe vezető k-p-könyök (p-k-könyök). A kp-könyök típusú éleket színezzük kékre a tövétől a közepéig, pirosra a közepétől a fejéig, a p-k-könyök-éleket pedig fordítva. A H′ mátrixot nevezzük az A háló-mátrix reprezentáló gráfjának.

6.8 Lemma. Ekkor e = ij H′-beli élre (1) e ∈ E′_{k} ⟺ S_{j}^{1} ≤ S_{i}^{1},

(2) e ∈ E′_{p} ⟺ S_{j}^{3} ≤ S_{i}^{3},
(3) e ∈ E′_{kp} ⟺ S_{j}^{3} ≤ S_{i}^{1},
(4) e ∈ E′_{pk} ⟺ S_{j}^{1} ≤ S_{i}^{3}.

Bizonyítás. Tekintsük az e = ij élt. Ekkor e ∈ E′_{k} pontosan akkor, ha minden S ∈ L-re w_{i}^{+}(Φ(S)) = 1 ⟹ w_{j}^{+}(Φ(S)) = 1. Csakhogy w_{i}^{+}(Φ(S)) ⟺ S_{i}^{1} ∈ Φ(S) ⟺ S_{i}^{1} ∈ S, és ugyanez j-re is igaz. Ilyen módon e ∈ E′_{k} akkor és csak akkor, ha {S ∈ L : S_{i}^{1} ≤ S} ⊆ {S ∈ L : S_{j}^{1} ≤ S}, azaz ha S_{j}^{1} ≤ S_{i}^{1}. Hasonlóan látható be (2) is. (3) és (4) közül is csak (3)-at részletezzük. e ∈ E′_{kp} pontosan akkor, ha van olyan k ∈ U, hogy minden S ∈ L-re w_{i}^{+}(Φ(S)) = 1 ⟹ k ∈ Φ(S) és k ∈ Φ(S) ⟹ w_{j}^{−}(Φ(S)) = −1. Tegyük fel, hogy k mindkét implikációt teljesíti, és jelölje k L-beli példányát K (emlékeztetünk, hogy U elemei éppen L m-től különböző ∨-irreducibilis elemei). A két implikáció ekvivalens K ≤ S_{i}^{1}- vel ill. S_{j}^{3} ≤ K-val. Így e ∈ E′_{kp} esetén S_{j}^{3} ≤ S_{i}^{1}. Megfordítva, ha S_{j}^{3} ≤ S_{i}^{1}, akkor k = S_{j}^{3} választással K ≤ S_{i}^{1} és S_{j}^{3} ≤ K, tehát e ∈ E′_{kp} ■

A k-p-utakat, köröket, ill. alternáló vektoraikat definiálhatjuk H′-ben is, figyelembe véve a könyök-élek színezését. A fenti eredményekből a következő tétel adódik.

6.9 Tétel. Legyen A háló-mátrix H := (J, E_{k} ∪ E_{p} ∪ E_{kp} ∪ E_{pk} reprezentáló gráffal. Legyen B ill. R a H-beli k-p-utak ill. körök alternáló vektoraiból mint sorokból összeállított mátrix. Ekkor

Conv(A) = {x ∈ ℝ^{J} : Bx ≤ 1, Rx ≤ 0, x ≥ 0},

és a leíró rendszer TDI.

A (6.8) Lemma szerint a reprezentáló gráf közvetlenül, a gyűrű-család nélkül is elkészíthető.

Végül megemlítjük, hogy A háló-mátrix és b: L → ℤ∪{+∞} szubmoduláris függvény esetén az {x : Ax ≤ b} poliéderre közvetlenül alkalmazhatók a szubmoduláris áram poliéder-algoritmusok. A részletes leírás megtalálható [2]ben.

Irodalomjegyzék

[1] M. Cochand – A. Gaillard – H. Gröflin: Lattice matrices, intersection of ring families and dicuts. Discrete Mathematics 110 (1992) 61—80.

[2] M. Cochand – A. Gaillard – H. Gröflin: Optimum partitioning into intersections of ring families. Discrete Applied Mathematics 76 (1997) 81–91.

[3] J. Edmonds – R. Giles: A min-max relation for submodular functions on graphs. Annals of Discrete Math. 1 (1977) 185–204.

[4] U. Faigle – W. Kern: Submodular linear programs on forests.

Mathematical Programing 72 (1996) 195–206.

[5] Frank András: An algorithm for submodular function on graphs. in: A. Bachem, M. Grötschel and B. Korte, eds., Bonn Workshop on Combinatorial Optimization, Bonn, 1980, North-Holland Mathematics Studies 66, North-Holland, Amsterdam, New York, 1982) 97–120.

[6] Frank András: Increasing the rooted-connectivity of a digraph by one. Math. Program. 84 (1999) 565–576.

[7] H. Gröflin – A. J. Hoffman: Lattice polyhedra II: Generalization, constructions and examples. Annals of Discrete Mathematics 15 (1982) 189–203.

[8] A. J. Hoffman – D. E. Schwarz: On lattice polyhedra. in: A. Hajnal and V. T. Sós, eds., Combinatorics: Proc. 5th Hung. Coll. on Comb. (North Holland, Amsterdam, 1978) 593–598.

[9] A. Schrijver: Total dual integrality from directed graphs, crossing families, and sub- and supermodular functions. in: W.R. Pulleylank, ed., Progress in Combinatorial Optimization, Academic Press, New York, 1984) 315–361.

[10] A. Schrijver: Theory of Linear and Integer Programing. Wiley, New York(1986)

[11] Várszegi Géza: Mohó algoritmus a lineáris programozásban. Szakdolgozat, ELTE TTK 1995.