A leemelési művelet és alkalmazásai

Készítette: Király Tamás

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

Eötvös Loránd Tudományegyetem Természettudományi Kar Operációkutatási Tanszék

Budapest, 1999.

Tartalom

1 Bevezetés 2 1.1 Alapfogalmak, jelölések . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Irányított leemelések 6 2.1 Leemelés szubadditív tulajdonságú pontokról . . . . . . . . . . . . . . 7 2.2 Alkalmazás páros gráfokra . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Leemelés semleges pontokról . . . . . . . . . . . . . . . . . . . . . . . 9 2.4 Halmazfüggvények fedése irányított gráffal . . . . . . . . . . . . . . . 12

3 Irányítatlan leemelések 16 3.1 Leemelés páros többletfüggvény esetén . . . . . . . . . . . . . . . . . 17 3.2 Élidegen utak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3 Takarékos halmazfüggvények . . . . . . . . . . . . . . . . . . . . . . . 21 3.4 Leemelés általános igényfüggvény esetén . . . . . . . . . . . . . . . . 23 3.5 Halmazfüggvények fedése irányítatlan gráffal . . . . . . . . . . . . . . 26 3.6 Szimmetrikus szupermoduláris függvények fedése . . . . . . . . . . . 30

4 Vegyes gráfok 35

5 Fenyves-pakolás 40 5.1 Egy fenyves-pakolási tétel . . . . . . . . . . . . . . . . . . . . . . . . 40 5.2 Néhány szó az algoritmusról . . . . . . . . . . . . . . . . . . . . . . . 46 5.3 Kapacitások . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

6 Színezések 52 6.1 Alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.2 Poliéderes eredmények . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.3 Ferdén szupermoduláris színezés . . . . . . . . . . . . . . . . . . . . . 56 6.4 Egy pakolási feladat . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

7 Összefoglalás 61 7.1 Irányított és irányítatlan leemelés . . . . . . . . . . . . . . . . . . . . 61 7.2 Alkalmazások . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 7.3 Poliéderek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

1 Bevezetés

A kombinatorikus optimalizálás látókörébe kerülő problémák bonyolultsága széles skálán mozoghat: egyes feladatok egyszerű mohó algoritmussal megoldhatók, másokra még polinomiális közelítő algoritmus sem ismert. Az elméleti kutatások egyik fontos feladata olyan általános jellemzőket keresni, amik valamilyen értelemben karakterizálják a jól kezelhető problémák egy részét. Az egyik legjobban használható ilyen jellemző a szubmoduláris függvényekkel való kapcsolat: számos különböző területen bukkannak fel olyan algoritmusok, amiknek a hátterében valamilyen módon a szubmodularitás áll. A matroidelméleten keresztül a szubmoduláris folyamokig és ezek általánosításáig rendkívül sok elméleti eredmény született ezen a téren (lásd Fujishige [9], Frank [7]), és a közelítő megoldások vizsgálatában is hasznosnak bizonyult a szubmodularitás, illetve a szupermodularitás fogalma ([13], [12], [4]).

A gráfelméleti feladatok kezelhetőségének egyik oka, hogy itt természetes módon adódnak szubmoduláris függvények, például a csúcsok egy halmazába belépő élek száma. Ez lehetővé teszi olyan redukciós eljárások használatát, amik egyszerűsítik a gráfot, de a feladat szubmoduláris jellegét nem változtatják meg. A legegyszerűbb ilyen eljárás az úgynevezett élleemelés: egy us, st élpárt törlünk, és hozzáadunk a gráfhoz egy új ut élt (irányítottat vagy irányítatlant, attól függően, hogy milyen gráfról van szó). Lovász [16] és Mader [17] tételei megmutatták, hogy ez a művelet mind irányítatlan, mind irányított élösszefüggőségi problémák kezelésére alkalmas, és sok esetben erősen polinomiális algoritmust ad a megoldásra. A művelet alkalmazható vegyes gráfokra (Bang-Jensen, Frank és Jackson [1]), síkgráfokra (Nagamochi és Eades [19]), és hipergráfok élekkel való összefüggőség-növelésére (Benczúr és Frank [3]).

Egy általánosabb feladattípus, amivel kapcsolatban a leemelési művelet vizsgálható, a halmazfüggvények gráfokkal való fedésének kérdésköre. Keresztező szupermoduláris függvényekre az eredmények mind irányított (Frank [8]), mind irányítatlan esetben (Benczúr, Frank [3]) azt mutatták, hogy az élösszefüggőségi feladatokat is érdemes ebben a megközelítésben vizsgálni. E dogozat egyik célja, hogy ezeket az eredményeket, ahol lehet, kiterjessze ferdén szupermoduláris halmazfüggvényekre, és egységes szemléletben tárgyalja a különböző területeken használt leemelési tételeket.

A 2., 3. és 4. fejezetben irányított, irányítatlan és vegyes gráfokra vizsgáljuk a halmazfüggvény-fedési problémákat, és megmutatjuk, hogy az élösszefüggőségnövelésnél alkalmazott módszerek beleférnek az absztraktabb szemléletbe; ezenkívül néhány példával illusztráljuk, hogy a leemelési művelet a kombinatorikus optimalizálás más területein is jól hasznosítható.

Az 5. fejezetben egy pakolási feladatot ismertetünk, ami közös általánosítását adja Edmonds [5] és Gabow [11] fenyvesekre, illetve fenyőkre vonatkozó pakolási tételeinek. Míg Gabow a leemelési műveletet használta a bizonyításhoz, addig Edmonds tételét még nem sikerült ezzel a módszerrel belátni. Megmutatjuk, hogy a leemelés mellett más műveleteket is megengedve ez a nehézség áthidalható, és mindkét megközelítés előnyeit ki lehet használni.

Edmonds tételének egy érdekes alkalmazása Schrijver [21] bibranching-okra vonatkozó tétele, amire egyszerű bizonyítás adható egy szintén Schrijver nevéhez fűződő, meglepő szupermoduláris színezési tétel felhaszálásával. A 6. fejezetben ennek a színezési feladatnak a ferdén szupermoduláris változatát vizsgáljuk egy absztrakt, de talán általánosításra módot adó poliéderes módszerrel, és megnézzük, hogy az 5. fejezet eredményeit felhasználva mennyiben erősíthetjük Schrijver tételét. Végül az utolsó fejezetben összefoglaljuk az eredményeinket, és vázoljuk a vizsgált kérdéskörökben fennmaradó nyitott kérdéseket.

Köszönöm témavezetőmnek, Frank Andrásnak, hogy megismertetett ezzel az izgalmas témakörrel, és felvetéseivel egyre érdekesebb problémák felé terelt; külön köszönöm, hogy e dinamikusan fejlődő terület legfrissebb eredményeit bemutatva segítette a munkámat.

1.1 Alapfogalmak, jelölések

A dolgozatban a halmazokra vonatkozó jelöléseink néhol eltérnek a megszokottól: egy U véges alaphalmaz két részhalmazának különbségét X \ Y helyett X − Y -nal jelöljük; az egyelemű {x} halmazt nem különböztetjük meg az x elemtől:

X − x := X − {x},
X + x := X ∪ {x}.

XΔY az X és Y halmazok szimmetrikus differenciája, az alaphalmazra vonatkozó komplementer pedig \overline{X} = U − X. X s\overline{t}-halmaz, ha s ∈ X és t ∉ X; X elválasztja s-et és t-t, ha s\overline{t} vagy t\overline{s}-halmaz. X, Y ⊆ U metszők, ha X ∩ Y, X − Y, Y − X nem üresek, és keresztezők, ha ezenkívül \overline{X ∪ Y} sem üres. Az U alaphalmaz részhalmazainak egy F családját halmazrendszernek nevezzük (F ugyanannak a részhalmaznak több példányát is tartalmazhatja). F lamináris, ha nincs két metsző eleme; F keresztezésmentes, ha nincs két keresztező eleme.

Egy G = (U, E) irányítatlan gráfban X ⊆ U-ra d(X)-szel jelöljük az X-be lépő élek számát, irányított D = (U, A) gráfban pedig ρ(X) az X-be lépő, δ(X) az X-ből kilépő élek száma. Mindkét esetben X, Y ⊆ U-ra d(X, Y) jelöli az X − Y és Y − X között haladó élek, \overline{d}(X, Y) pedig az X ∩ Y és \overline{X ∪ Y} közötti élek számát. ρ_{D}(X), ρ_{A}(X), ρ_{s}(X) értelemszerűen annak felel meg, hogy hány él lép X-be a D digráfhoz tartozó, az A élhalmazhoz tarozó, illetve az s ponttal szomszédos élek közül.

Mind irányítatlan, mind irányított gráfokban egy u, v ∈ U pontpárra λ(u, v)-vel jelöljük az u-ból v-be menő élidegen utak maximális számát. Menger tétele szerint az irányítatlan esetben

λ(u, v) = min\{d(X) : X v\overline{u}-halmaz\},

irányított esetben pedig

λ(u, v) = min\{ρ(X) : X v\overline{u}-halmaz\}.

A leemelési műveletet irányított és irányítatlan gráfra is definiáljuk. Legyen s ∈ U egy kijelölt pont. Egy us, st élpár leemelése azt jelenti, hogy töröljük a gráfból az élpárt, és hozzáadunk a gráfhoz egy új ut élt. A leemelést u = t esetén is értelmezzük, ekkor hurokél keletkezik.

Z_{+} jelöli a nemnegatív egész számok halmazát. Egy tetszőleges f valós függvényre f^{+} := max{f, 0}. Halmazfüggvénynek az U alaphalmaz részhalmazain értelmezett p függvényeket nevezzük; p szimmetrikus, ha minden X ⊆ U-ra p(X) = p(U − X); monoton, ha minden Y ⊆ X ⊆ U-ra p(Y) ≤ p(X). Azt mondjuk, hogy egy G gráf, illetve D digráf fedi a p halmazfüggvényt, ha minden X ⊆ U-ra d_{G}(X) ≥ p(X), illetve ρ_{D}(X) ≥ p(X).

Egy b : 2^{U} → Z ∪ {∞} halmazfüggvényre az X, Y ⊆ U halmazpáron teljesül a szubmodularitási egyenlőtlenség, ha

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

b teljesen szubmoduláris, ha bármely két halmazra fennáll ez az egyenlőtlenség; metsző, illetve keresztező szubmoduláris, ha bármely két metsző, illetve keresztező halmazra fennáll; matroid-rangfüggvény, ha teljesen szubmoduláris, nemnegatív, monoton, és az egyelemű halmazokon 0-t vagy 1-et vesz fel. Hasonlóképp egy p : 2^{U} → Z ∪ {−∞} halmazfüggvény X, Y ⊆ U-n szupermoduláris, ha

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

Azt mondjuk, hogy p az X, Y ⊆ U halmazpáron ferdén szupermoduláris, ha az alábbi két egyenlőtlenség legalább egyike teljesül:

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

A dolgozatban sok helyen fogjuk használni az alábbi, tetszőleges G irányítatlan gráfra illetve D digráfra teljesülő azonosságokat:

d(X) + d(Y) = d(X ∩ Y) + d(X ∪ Y) + 2d(X, Y),  (1.1)
d(X) + d(Y) = d(X − Y) + d(Y − X) + 2\overline{d}(X, Y),  (1.2)
ρ(X) + ρ(Y) = ρ(X ∩ Y) + ρ(X ∪ Y) + d(X, Y),  (1.3)
ρ(X) + ρ(Y) = ρ(X − Y) + ρ(Y − X) + ρ(X ∩ Y) − δ(X ∩ Y) + \overline{d}(X, Y). (1.4)

Ezek helyessége azonnal következik, ha megnézzük az egyes élek hozzájárulását az azonosságok bal és jobb oldalához.

Az egyes témakörökhöz tartozó egyéb definíciókat és jelöléseket a megfelelő fejezetek elején ismertetjük.

2 Irányított leemelések

Irányított gráfok élösszefüggőségével kapcsolatos problémák megoldásában alapvető Mader [18] következő tétele:

2.1. Tétel. Legyen D = (V + s, A) digráf, amire ρ(s) = δ(s), és minden u, v ∈ V - re λ(u, v) ≥ k. Ekkor tetszőleges st élhez van olyan us él, hogy az us, st leemelés elvégzése után λ(u, v) ≥ k továbbra is fennáll minden u, v ∈ V pontpárra.

Ebben a fejezetben (a Frank András [8] által használt megközelítéshez hasonlóan) egy ennél általánosabb, halmazfüggvényekkel megadott feladatot definiálunk, és megvizsgáljuk, hogy mikor tudjuk biztosítani leemelhető élpár létezését. Tekintsünk egy D = (V +s, A) digráfot, és egy p : 2^{V +s} → Z_{+} halmazfüggvényt, amire p(∅) = 0, és

∀X ⊆ (V + s) ρ(X) ≥ p(X).  (2.1)

Szeretnénk úgy leemelni egy élpárt az s pontról, hogy ez a tulajdonság megmaradjon; a továbbiakban az ilyen élpárokat nevezzük leemelhetőnek. Ilyenek persze nem mindig vannak, így olyan feltételeket keresünk, amelyek biztosítják egy jó leemelés létezését. Vezessük be a következő jelöléseket:

m_{i}(X) :=ρ_{s}(X − s),
m_{o}(X) :=δ_{s}(X − s),
m(X) :=m_{i}(X) + m_{o}(X),
b(X) :=ρ(X) − p(X).

Egy X halmaz pozitív, ha p(X) > 0. Frank András [8] bebizonyította, hogy ha m_{i}(V) = m_{o}(V), minden X ⊆ V -re p(X) = p(X + s), és p keresztező szupermoduláris V pozitív részhalmazain, akkor van jó leemelés. Megmutatjuk, hogy ennek a tételnek a feltételei többféleképpen is gyengíthetők, és ezzel az alkalmazások körét is bővíteni tudjuk.

Egy X, Y halmazpárt erősen keresztezőnek nevezünk, ha m(X ∩ Y), m(\overline{X ∪ Y}), m(X − Y), m(Y − X) > 0. Azt mondjuk, hogy egy X, Y halmazpáron p kváziszupermoduláris, ha az alábbi három egyenlőtlenség legalább egyike teljesül:

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

2. p(X) + p(Y) ≤ p(X − Y) + p(Y − X) + ρ(X ∩ Y) − δ(X ∩ Y),

3. p(X) + p(Y) ≤ p(\overline{X − Y}) + p(\overline{Y − X}) + δ(\overline{X ∪ Y}) − ρ(\overline{X ∪ Y}).

Egy adott leemelést egy pozitív X halmaz akadályoz, ha a leemelés elvégzése után b(X) negatívvá válna. Ha adott a leemeléseknek egy halmaza, amelyből egy végrehajthatót szeretnénk kiválasztani, akadályozó rendszernek nevezzük a következő tulajdonságokkal rendelkező halmazrendszert:

• Az összes akadályozott leemeléshez van olyan halmaz a rendszerben, ami azt akadályozza, de bármelyik halmazt kihagyva a redszerből ez már nem teljesül.

• A rendszer minden eleme maximálisan akadályozó halmaz, azaz nincs olyan halmaz, ami a leemelések egy szigorúan nagyobb részét akadályozná.

2.1 Leemelés szubadditív tulajdonságú pontokról

Az első tételünk olyan s pontokra vonatkozik, amikre bizonyos szubadditivitási egyenlőtlenségek teljesülnek. Megmutatjuk, hogy ilyenkor a kvázi-szupermodularitás már biztosítja egy jó leemelés létezését.

2.2. Tétel. Tegyük fel, hogy (2.1) teljesül, minden X ⊆ V pozitív halmazra p(X) − p(\overline{s}) ≤ p(X + s), minden s ∈ X pozitív halmazra p(X) − p(s) ≤ p(X − s), m_{o}(V) > p(s), m_{i}(V) > p(\overline{s}), és bármely két pozitív, metsző halmazon p kváziszupermoduláris. Ekkor van s-ről leemelhető élpár.

Bizonyítás. Leemeléskor b legfeljebb 1-gyel csökkenhet, tehát miden X akadályozó halmazra b(X) = 0; az ilyen pozitív halmazokat nevezzük pontos halmaznak. Pontos X halmazra igazak az alábbi egyenlőtlenségek:

• Ha s ∉ X: m_{i}(X) − p(\overline{s}) ≤ m_{o}(V − X).

• Ha s ∈ X: m_{o}(V − X) − p(s) ≤ m_{i}(X).

Ebből következik, hogy egy X halmaz nem akadályozhatja az összes leemelést, hiszen s ∉ X esetén m_{i}(V) > p(\overline{s}) miatt vagy m_{i}(V − X) > 0, vagy m_{o}(V − X) > 0; s ∈ X esetén pedig m_{o}(V) > p(s) miatt vagy m_{o}(X) > 0, vagy m_{i}(X) > 0.

Legyen X_{1}, …, X_{k} egy akadályozó rendszer. Mivel egy halmaz nem akadályozhatja az összes leemelést, feltehető, hogy a rendszer nem egyelemű. Egy X, Y pozitív, metsző halmazpárra az alábbi egyenlőtlenségek legalább egyike teljesül:

b(X) + b(Y) ≥ b(X ∩ Y) + b(X ∪ Y) + d(X, Y),  (2.2)
b(X) + b(Y) ≥ b(X − Y) + b(Y − X) + \overline{d}(X, Y),  (2.3)
b(X) + b(Y) ≥ b(\overline{X − Y}) + b(\overline{Y − X}) + \overline{d}(X, Y).  (2.4)

Legyen X_{i}, X_{j} az akadályozó rendszer két metsző eleme. Három esetet vizsgálunk aszerint, hogy s hol helyezkedik el; kihasználjuk, hogy X_{i} és X_{j} pontos, és nincs olyan halmaz, ami az összes olyan leemelést akadályozza, amit valamelyikük akadályoz.

• Ha s ∈ \overline{X_{i} ∪ X_{j}}: X_{i} ∪ X_{j} nem lehet pontos, tehát a (2.2) egyenlőtlenség nem teljesülhet, így \overline{d}(X_{i}, X_{j}) = 0, speciálisan m(X ∩ Y) = 0.

• Ha s ∈ X_{i} ∩ X_{j}: X_{i} ∩ X_{j} nem lehet pontos, tehát a (2.2) egyenlőtlenség nem teljesülhet, így m(\overline{X_{i} ∪ X_{j}}) = 0.

• Ha s ∈ X_{j} − X_{i}: sem X_{j} − X_{i}, sem \overline{X_{j} − X_{i}} nem lehet pontos, tehát a (2.3) és a (2.4) egyenlőtlenség nem teljesülhet, így m(X_{i} − X_{j}) = 0.

Ezek az m-re vonatkozó állítások nem metsző akadályozó rendszer-beli halmazokra triviálisan teljesülnek. Segítségükkel könnyen belátható, hogy van jó leemelés:

Tegyük fel először, hogy van olyan X_{i}, X_{j} halmazpár, amire s ∈ \overline{X_{i} ∪ X_{j}}. Válasszuk u-t és t-t úgy, hogy u ∈ X_{j} − X_{i}, m_{o}(u) > 0, és t ∈ X_{i} − X_{j}, m_{i}(t) > 0. Ekkor s ∉ X_{k} esetén m(X_{i} ∩ X_{k}) = 0 miatt, s ∈ X_{k} esetén pedig m(X_{i} − X_{k}) = 0 miatt ezt a leemelést X_{k} sem akadályozhatja.

Ha egy darab s ∉ X_{i} halmaz van: legyenek u ∈ X_{i}, t ∉ X_{i} olyanok, hogy m_{o}(u) > 0, m_{i}(t) > 0. m(X_{i} − X_{k}) = 0 miatt ezt a leemelést sem akadályozhatja másik halmaz.

Ha csak s-et tartalmazó halmazok vannak az akadályozó rendszerben, legyen u ∈ ∩_{j≠1}X_{j}, t ∈ ∩_{j≠2}X_{j}, m_{o}(u) > 0, m_{i}(t) > 0. Ilyenek vannak, mert mindegyik halmaz akadályozó, és m(\overline{X_{i} ∪ X_{j}}) = 0; ezt a leemelést semmi nem akadályozhatja.

2.2 Alkalmazás páros gráfokra

Két ismert, páros gráfokra vonatkozó tételt bizonyítunk be a 2.2. Tétel segítségével. Legyen G = (A, B, E) egy páros gráf; F ⊆ E, X ⊆ A esetén Γ_{F} (X) := {v ∈ B : uv ∈ F valamilyen u ∈ X-re}. A Hall-tétel következő átalánosítását Lovász László [15] fogalmazta meg:

2.3. Tétel. Legyen p : 2^{A} → Z ∪ {−∞} metsző szupermoduláris függvény, minden v ∈ A, v ∉ X ⊂ A-ra p(v) ≥ 0 és p(X) + p(v) ≥ p(X + v). Akkor és csak akkor van olyan F ⊆ E élhalmaz, amire d_{F} (v) = p(v) minden v ∈ A-ra, és |Γ_{F} (X)| ≥ p(X) minden X ⊆ A-ra, ha |Γ_{E}(X)| ≥ p(X) minden X ⊆ A-ra.

Bizonyítás. Vegyünk hozzá a gráfhoz egy új z pontot. Irányítsuk a gráf éleit B-ből A felé, és minden v ∈ A pontra vegyünk fel d_{E}(v) darab vz irányított élt. Terjesszük ki a p függvényt a következőképpen:

p(Y) := p(A ∩ Y) − |B ∩ Y | (Y ⊆ A ∪ B).

Pontosan akkor igaz, hogy ∀Y ⊆ A ∪ B ρ(Y) ≥ p(Y), ha a tételben megfogalmazott feltétel fennáll. A 2.2. Tételt akarjuk többször egymás után alkalmazni, egészen addig, míg ρ(v) = p(v) nem teljesül minden v ∈ A-ra. Válasszunk ki egy s ∈ A pontot, amire ρ(s) > p(s). Legyen Y ⊆ A ∪ B-re

p′(Y) := \begin{cases}p(Y)^{+}, & ha s ∈ Y \\ 0, & ha s ∉ Y . \end{cases}

Könnyen látható, hogy p′-re teljesülnek a 2.2. Tétel feltételei (a kvázi-szupermodu-laritásból mindig az első egyenlőtlenség), így van jó leemelés. A leemelések egészen addig folytathatók, amíg A pontjai nem pontosak.

R. Rado [20] régebbi, matroid-rangfüggvényekre vonatkozó tétele hasonló módszerrel bizonyítható.

2.4. Tétel. Legyen r egy matroid-rangfüggvény B-n. Akkor és csak akkor létezik olyan F ⊆ E élhalmaz, amire minden v ∈ A-ra d_{F} (v) = 1 és minden X ⊆ A-ra r(Γ_{F} (X)) ≥ |X|, ha minden X ⊆ A-ra r(Γ_{E}(X)) ≥ |X|.

Bizonyítás. Vegyünk hozzá a gráfhoz egy új z pontot. Irányítsuk E éleit A-ból B felé, és minden v ∈ A ra vegyünk fel d_{E}(v) darab zv irányított élt. Legyen p a következő függvény:

p(Y) := \begin{cases}(|A − Y | − r(B − Y))^{+}, & ha z ∈ Y \\ 0, & ha z ∉ Y . \end{cases}

Pontosan akkor igaz ∀Y ⊆ (A ∪ B + z) ρ(Y) ≥ p(Y), ha minden X ⊆ A-ra r(Γ_{E}(X)) ≥ |X|. Válasszunk ki egy s ∈ A pontot, amire δ(s) > p(\overline{s}). Itt meg sem kell változtatni p-t, hogy alkalmazni lehessen a 2.2. Tételt, hiszen r teljes szubmodularitása miatt p pozitívakon metsző szupermoduláris, és s pozitív halmazokból való kihagyása, illetve azokhoz való hozzáadása is jól változtatja p-t a definíció szerint, hiszen p(\overline{s}) = 1, p(s) = 0. A leemeléseket addig lehet ismételni, amíg A pontjainak komplementerei nem pontosak.

2.3 Leemelés semleges pontokról

Az s pontot akkor nevezzük semlegesnek, ha minden X ⊆ V halmazra p(X) = p(X + s). Ez erősebb feltétel, mint a 2.2. Tételben használt szubadditivitás, így nem meglepő, hogy a többi feltétel gyengíthető.

2.5. Tétel. Tegyük fel, hogy (2.1) teljesül, m_{i}(V) = m_{o}(V), ∀X ⊆ V p(X) = p(X+s), és bármely két pozitív, erősen keresztező halmazon p kvázi-szupermoduláris. Ekkor tetszőleges st élhez van olyan us él, amivel leemelhető.

Bizonyítás. Rögzítsünk egy st élt; ehhez fogunk vele leemelhető us-t találni. Leemeléskor b legfeljebb 1-gyel csökkenhet, tehát miden X akadályozó halmazra b(X) = 0; az ilyen pozitív halmazokat nevezzük pontos halmaznak. Pontos X halmazra igazak az alábbi egyenlőtlenségek (kihasználva, hogy p(X) = p(X + s), és m_{i}(V) = m_{o}(V)):

• Ha s ∉ X: m_{i}(X) ≤ m_{o}(V − X), m_{o}(X) ≤ m_{i}(V − X).

• Ha s ∈ X: m_{i}(X) ≥ m_{o}(V − X), m_{o}(X) ≥ m_{i}(V − X).

Ebből rögtön következik, hogy egy X halmaz nem akadályozhatja az összes leemelést, hiszen akadályozó halmaz lévén s ∉ X esetén m_{i}(X) > 0 miatt m_{o}(V − X) > 0, s ∈ X esetén pedig m_{i}(V − X) > 0 miatt m_{o}(X) > 0.

2.6. Állítás. Egy akadályozó rendszer elemei páronként erősen keresztezőek.

Bizonyítás. Indirekt tegyük fel, hogy X és Y nem erősen keresztező. Három esetet vizsgálunk aszerint, hogy s hogy helyezkedik el.

1. s ∈ \overline{X ∪ Y}: Mivel akadályozó rendszer tagjai, m_{i}(X ∩Y), m_{o}(X −Y), m_{o}(Y − X) > 0, azaz az indirekt feltevés szerint m(\overline{X ∪ Y}) = 0. Ekkor m_{i}(X) ≤ m_{o}(V − X) ≤ m_{o}(Y) ≤ m_{i}(V − Y) < m_{i}(X), ellentmondás.

2. s ∈ X ∩ Y: Mivel akadályozó rendszer tagjai, m_{i}(\overline{X ∪ Y}),m_{o}(X − Y),m_{o}(Y − X) > 0, azaz az indirekt feltevés szerint m(X ∩ Y) = 0. Ekkor m_{i}(V − X) ≤ m_{o}(X) ≤ m_{o}(V − Y) ≤ m_{i}(Y) < m_{i}(V − X), ellentmondás.

3. s ∈ Y − X: Mivel akadályozó rendszer tagjai, m_{i}(X − Y), m_{o}(X ∩ Y), m_{o}(\overline{X ∪ Y}) > 0, azaz az indirekt feltevés szerint m(Y − X) = 0. Ekkor m_{i}(X) ≤ m_{o}(V − X) ≤ m_{o}(V − Y) ≤ m_{i}(Y) < m_{i}(X), ellentmondás.

Legyen X_{1}, …, X_{k} egy akadályozó rendszer. Mivel egy halmaz nem akadályozhatja az összes leemelést, feltehető, hogy a rendszer nem egyelemű; az állítás szerint elemei páronként erősen keresztezőek. Egy X, Y pozitív, erősen keresztező halmazpárra az alábbi egyenlőtlenségek legalább egyike teljesül:

b(X) + b(Y) ≥ b(X ∩ Y) + b(X ∪ Y) + d(X, Y),  (2.5)
b(X) + b(Y) ≥ b(X − Y) + b(Y − X) + \overline{d}(X, Y),  (2.6)
b(X) + b(Y) ≥ b(\overline{X − Y}) + b(\overline{Y − X}) + \overline{d}(X, Y).  (2.7)

Speciálisan az akadályozó rendszer X_{i}, X_{j} elemére:

• Ha s ∈ \overline{X_{i} ∪ X_{j}}: X_{i} ∪ X_{j} pontos, hiszen \overline{d}(X_{i}, X_{j}) > 0 miatt csak a (2.5) egyenlőtlenség teljesülhet.

• Ha s ∈ X_{i} ∩ X_{j}: X_{i} ∩ X_{j} pontos, hiszen \overline{d}(X_{i}, X_{j}) > 0 miatt csak a (2.5) egyenlőtlenség teljesülhet.

• Ha s ∈ X_{j} − X_{i}: vagy X_{j} − X_{i}, vagy \overline{X_{j} − X_{i}} pontos, hiszen d(X_{i}, X_{j}) > 0 miatt a (2.5) egyenlőtlenség nem teljesülhet.

Mindhárom esetben ellentmondásba kerültünk azzal, hogy X_{i} és X_{j} maximálisan akadályozó halmazok, tehát akadályozó rendszer csak egyelemű lehet.

A 4. fejezetben meg fogjuk mutatni, hogy a fenti tétel általánosítja a vegyes gráfok élösszefűggőség-növelésénél használt irányított leemelési módszert. Felvetődik a kérdés, hogy a kvázi-szupermodularitás feltétele tovább gyengíthető-e, például mi mondható el két kvázi-szupermoduláris függvény maximumáról; erről szól a következő tétel.

2.7. Tétel. Tegyük fel, hogy (2.1) teljesül, m_{i}(V) = m_{o}(V), ∀X ⊆ V p(X) = p(X +s), és ∑_{v∈V} |m_{i}(v)−m_{o}(v)| ≤ 2. Ezenkívül bármely három pozitív, páronként erősen keresztező halmaz közül kiválasztható egy pár, amin p kvázi-szupermoduláris. Ekkor van olyan us, st élpár, ami leemelhető.

Bizonyítás. Ha van olyan v pont, amire m_{i}(v) > m_{o}(v) (legfeljebb egy ilyen lehet), akkor legyen t := v; különben választhatjuk t-t tetszőleges olyan pontnak, amire m_{i}(t) > 0. Az előző tétel bizonyításával analóg módon belátható, hogy egy akadályozó rendszer elemei páronként erősen keresztezőek, és egy halmaz nem akadályozhatja az összes leemelést. Itt azonban kételemű akadályozó rendszer sem akadályozhatja az összes leemelést; azt kell felhasználnunk, hogy t-n kívül nincs olyan v pont, amire m_{i}(v) > 0, m_{o}(v) = 0, így egy ilyen rendszer két eleme nem lenne erősen keresztező.

Tegyük fel, hogy van egy X_{1} … X_{k} legalább 3-elemű akadályozó rendszer. A tétel feltételei szerint ezek között van kettő (X_{i}, X_{j}), amin p kvázi-szupermoduláris. Az előző tétel bizonyításával analóg módon igazolható, hogy ez ellentmond annak, hogy X_{i} és X_{j} maximálisan akadályozók.

Megjegyzés. Két kvázi-szupermoduláris függvény maximuma rendelkezik a tételben szereplő tulajdonsággal, hiszen tetszőleges három halmaz közül kettőnél ugyanaz adja a maximumot. Az alábbi egyszerű példa mutatja, hogy a ∑_{v∈V} |m_{i}(v)− m_{o}(v)| ≤ 2 feltételt nem lehet elhagyni:

1. Ábra : A középső pontról nem lehet leemelni, ha a jelölt halmazokra p = 1.

2.4 Halmazfüggvények fedése irányított gráffal

Mind az 2.5. Tétel, mind az 2.7. Tétel esetében egy jó leemelés után is fennmaradnak a tétel feltételei: a kvázi-szupermodularitásnál ρ(Z) − δ(Z) nem változik semmilyen Z halmazra; az 2.7. Tételnél pedig t-t úgy választottuk ki, hogy ∑_{v∈V} |m_{i}(v) − m_{o}(v)| ≤ 2 megmaradjon. Így ismételt műveletekkel az összes élt leemelhetjük s-ről. Ennek segítségével az alábbi halmazfüggvény-fedési problémára is alkalmazhatjuk az ismertetett módszereket:

Adott egy V alaphalmaz, és azon egy m_{i} : V → Z_{+} és egy m_{o} : V → Z_{+} függvény; az

m_{i}(X) := ∑_{v∈X} m_{i}(v),

m_{o}(X) := ∑_{v∈X} m_{o}(v)

jelölésekkel teljesüljön m_{i}(V) = m_{o}(V). Adott egy p : 2^{V} → Z_{+} halmazfüggvény, p(∅) = 0. Olyan D irányított gráfot szeretnénk találni, amire

ρ(v) = m_{i}(v) minden v ∈ V -re,
δ(v) = m_{o}(v) minden v ∈ V -re,

(2.8)

tehát D megfelel a fokszámelőírásoknak, és

ρ(X) ≥ p(X) minden X ⊆ V -re,  (2.9)

azaz D fedi p-t. Ennek szükséges feltétele, hogy minden X ⊆ V -re

p(X) ≤m_{i}(X),
p(X) ≤m_{o}(V − X)

teljesüljön. Pozitív halmazon és erősen keresztező halmazpáron ugyanazt értjük, mint eddig (az előbb definiált m_{i}, m_{o}-val). Azt mondjuk, hogy egy X, Y halmazpáron p kvázi-szupermoduláris, ha az alábbi három egyenlőtlenség legalább egyike teljesül:

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

2. p(X) + p(Y) ≤ p(X − Y) + p(Y − X) + m_{i}(X ∩ Y) − m_{o}(X ∩ Y),

3. p(X) + p(Y) ≤ p(\overline{X − Y}) + p(\overline{Y − X}) + m_{o}(\overline{X ∪ Y}) − m_{i}(\overline{X ∪ Y}).

2.8. Tétel. Tegyük fel, hogy minden X ⊆ V -re m_{i}(X) ≥ p(X), m_{o}(V −X) ≥ p(X), és bármely két pozitív, erősen keresztező X, Y halmazon p kvázi-szupermoduláris. Ekkor van (2.8)-at és (2.9)-et teljesítő D digráf.

2.9. Tétel. Tegyük fel, hogy minden X ⊆ V -re m_{i}(X) ≥ p(X), m_{o}(V −X) ≥ p(X), ∑_{v∈V} |m_{i}(v) − m_{o}(v)| ≤ 2, és bármely három pozitív, páronként erősen keresztező halmaz közül kiválasztható egy X, Y pár, amin p kvázi-szupermoduláris. Ekkor van (2.8)-at és (2.9)-et teljesítő D digráf.

Bizonyítás. Vegyünk fel egy új s pontot, legyen X ⊆ V -re p(X + s) := p(X), és definiáljuk a D′ digráfot a következőképpen: vegyünk minden vs élt m_{o}(v) multiplicitással, és minden sv élt m_{i}(v) multiplicitással. A feltételeket úgy határoztuk meg, hogy a D′ digráfra a 2.5. illetve 2.7. Tételt m_{i}(V)-szer alkalmazva le tudjuk emelni az összes élt s-ről. A kapott D digráf kielégíti a feltételeket.

Ennél általánosabb p függvényeket is kezelni tudunk a következő átalakítással: egyelőre tetszőleges p-re vezessünk be egy új halmazfüggvényt:

p′(X) := max_{Y ⊆V}(p(Y) − m_{i}(Y − X) − m_{o}(X − Y)).

Egyszerűen ellenőrizhető, hogy p′-re pontosan akkor van a fokszámelőírásnak megfelelő fedő digráf, ha p-re van; elegendő tehát p-re olyan feltételeket megadni, hogy p′-re alkalmazni lehessen a 2.8. vagy a 2.9. Tételt. Egy X ⊆ V halmazt lényegesnek nevezünk, ha p′(X) = p(X). X′ majorálja X-et, ha p′(X) = p(X′) − m_{i}(X′ − X) − m_{o}(X − X′). Pozitív halmazt csak pozitív majorálhat.

2.10. Állítás. p′(X) = max_{Y ⊆V} (p′(Y) − m_{i}(Y − X) − m_{o}(X − Y)). Speciálisan, ha X′ majorálja X-et, akkor X′ lényeges.

Bizonyítás. Indirekt tegyük fel, hogy

p′(X) < max_{Y ⊆V}(p′(Y) − m_{i}(Y − X) − m_{o}(X − Y)).

Ekkor van Y, Z ⊆ V: Z majorálja Y -t, és

p′(X) < p′(Y) − m_{i}(Y − X) − m_{o}(X − Y)
= p(Z) − m_{i}(Z − Y) − m_{o}(Y − Z) − m_{i}(Y − X) − m_{o}(X − Y).

Másrészt

m_{i}(Z − Y) + m_{i}(Y − X) ≥ m_{i}(Z − X),
m_{o}(X − Y) + m_{o}(Y − Z) ≥ m_{o}(X − Z),

tehát

p′(X) < p(Z) − m_{i}(Z − X) − m_{o}(X − Z),

ez pedig ellentmond p′ definíciójának.

2.11. Lemma. Ha egy pozitív, lényeges X′, Y′ páron p′ kvázi-szupermoduláris, akkor bármely olyan X, Y párra, amire X′ majorálja X-et, és Y′ majorálja Y -t, p′ kvázi-szupermoduláris.

Bizonyítás. Bárhogy van megadva m_{i} és m_{o}, az alábbi egyenlőtlenségek teljesülnek:

m_{i}(X′ − X) + m_{i}(Y′ − Y) ≥ m_{i}((X′ ∩ Y′) − (X ∩ Y)) + m_{i}((X′ ∪ Y′) − (X ∪ Y)) (2.10)

m_{o}(X − X′) + m_{o}(Y − Y′) ≥ m_{o}((X ∩ Y) − (X′ ∩ Y′)) + m_{o}((X ∪ Y) − (X′ ∪ Y′)) (2.11)

m_{i}(X′ − X) + m_{i}(Y′ − Y) + m_{i}(X ∩ Y) ≥ m_{i}((Y′ − X′) − (Y − X))

+ m_{i}((X′ − Y′) − (X − Y)) + m_{i}(X′ ∩ Y′) (2.12)

m_{o}(X − X′) + m_{o}(Y − Y′) + m_{o}(X′ ∩ Y′) ≥ m_{o}((Y − X) − (Y′ − X′)) + m_{o}((X − Y) − (X′ − Y′)) + m_{o}(X ∩ Y) (2.13)

m_{i}(X′ − X) + m_{i}(Y′ − Y) + m_{i}(\overline{X′ ∪ Y′}) ≥ m_{i}(\overline{Y′ − X′} − \overline{Y − X})

+ m_{i}(\overline{X′ − Y′} − \overline{X − Y}) + m_{i}(\overline{X ∪ Y}) (2.14)

m_{o}(X − X′) + m_{o}(Y − Y′) + m_{o}(\overline{X ∪ Y}) ≥ m_{o}(\overline{Y − X} − \overline{Y′ − X′})

+ m_{o}(\overline{X − Y} − \overline{X′ − Y′}) + m_{o}(\overline{X′ ∪ Y′}) (2.15)

(Az m_{i}-re és m_{o}-ra vonatkozó egyenlőtlenségek tulajdonképpen ugyanazok (X′ és X, illetve Y′ és Y felcserélésével). Az utolsó két egyenlőtlenségnél azért komplementereket írtunk, hogy világosabb legyen a kapcsolat a Lemma állításával.)

A Lemma bizonyítását arra az esetre írjuk le, ha a kvázi-szupermodularitásnál p′(X′) + p′(Y′) ≤ p′(X′ ∩ Y′) + p′(X′ ∪ Y′) teljesül; a másik két esetben a bizonyítás ezzel analóg módon végezhető.

p′(X) + p′(Y) = p(X′) + p(Y′) − m_{i}(X′ − X) − m_{o}(X − X′)
− m_{i}(Y′ − Y) − m_{o}(Y − Y′)
≤ p′(X′ ∩ Y′) + p′(X′ ∪ Y′) − m_{i}(X′ − X) − m_{o}(X − X′)
− m_{i}(Y′ − Y) − m_{o}(Y − Y′).

A (2.10) és (2.11) egyenlőtlenséget alkalmazva:

p′(X) + p′(Y) ≤ p′(X′ ∩ Y′) + p′(X′ ∪ Y′)
− m_{i}((X′ ∩ Y′) − (X ∩ Y)) − m_{o}((X ∩ Y) − (X′ ∩ Y′))
− m_{i}((X′ ∪ Y′) − (X ∪ Y)) − m_{o}((X ∪ Y) − (X′ ∪ Y′))
≤ p′(X ∩ Y) + p′(X ∪ Y).

A kvázi-szupermodularitás másik két eseténél a (2.12) és (2.13), illetve a (2.14) és (2.15) egyenlőtlenséget alkalmazva ugyanígy bizonyítható az állítás.

2.12. Tétel. Ha minden X ⊆ V -re m_{i}(X) ≥ p(X), m_{o}(V −X) ≥ p(X), és bármely két lényeges, erősen keresztező X, Y halmazon p′ kvázi-szupermoduláris, akkor van (2.8)-at és (2.9)-et teljesítő D digráf.

Bizonyítás. Azt kell belátni, hogy p′-re teljesülnek a 2.8. Tétel feltételei. Legyen X, Y pozitív, erősen keresztező, és majorálja X-et X′, Y -t Y′. Ha X′ és Y′ nem erősen keresztező, akkor p′ kvázi-szupermoduláris rajtuk, hiszen valamelyik egyenlőtlenség automatikusan teljesül (kihasználva, hogy p′ megegyezik két halmazon, ha a szimmetrikus differenciájukra m = 0). Ha X′ és Y′ erősen keresztező, akkor pedig a tétel feltétele biztosítja, hogy p′ kvázi-szupermoduláris a halmazpáron. Alkalmazhatjuk a Lemmát, ami szerint ekkor p′ X, Y -on is kvázi-szupermoduláris.

2.13. Tétel. Tegyük fel, hogy minden X ⊆ V -re m_{i}(X) ≥ p(X), m_{o}(V − X) ≥ p(X), ∑_{v∈V} |m_{i}(v) − m_{o}(v)| ≤ 2, és bármely három lényeges, páronként erősen keresztező halmaz közül kiválasztható egy X, Y pár, amin p′ kvázi-szupermoduláris. Ekkor van (2.8)-at és (2.9)-et teljesítő D digráf.

Bizonyítás. LegyenX, Y, Z három pozitív, páronként erősen keresztező halmaz, és majorálja őket sorrendben X′, Y′, Z′. Külön tekintve azt az esetet, amikor van köztük két nem erősen keresztező halmaz, és amikor nincs, az előző bizonyítással analóg módon beláthatjuk, hogy kiválasztható egy pár (pl. X′, Y′), amin p′ kváziszupermoduláris. A Lemma szerint ekkor p′ X, Y -on is kvázi-szupermoduláris, tehát használható a 2.9. Tétel.

3 Irányítatlan leemelések

Az élleemelés hatékonyságát először a következő, Lovász Lászlótól [16] származó tétel mutatta:

3.1. Tétel. Legyen G = (V + s, E) irányítatlan gráf, k ≥ 2 egész, és tegyük fel, hogy d(s) páros, és λ(u, v) ≥ k minden u, v ∈ V -re. Ekkor tetszőleges st élhez van olyan us él, amivel leemelhető úgy, hogy minden u, v ∈ V -re λ(u, v) ≥ k fennmarad.

Mader [17] a lokális élösszefüggőségre is talált hasonló tételt:

3.2. Tétel. Legyen G = (V +s, E) összefüggő irányítatlan gráf, amiben d(s) páros, és nincs s-ből induló elvágó él. Ekkor s-ről leemelhető egy élpár úgy, hogy λ(u, v) semmilyen u, v ∈ V párra sem csökken.

Mi az irányított esethez hasonlóan itt is egy olyan általánosabb halmazfüggvényfedési problémából indulunk ki, aminek a vizsgálata mind élösszefüggőségi kérdésekben (Benczúr és Frank [3]), mind az élidegen út problémák kapcsán (Bertsimas és Teo [4]) hasznosnak bizonyult. Adott egy V + s alaphalmaz egy kijelölt s ponttal, és ezen egy G = (V + s, E) gráf, valamint egy p szimmetrikus, nemnegatív egész halmazfüggvény V + s-en, p(∅) = 0. Tegyük fel, hogy teljesül a következő feltétel:

∀X ⊆ (V + s) d(X) ≥ p(X).  (3.1)

A célunk az s pontban leemelni egy élpárt úgy, hogy a fenti feltétel ne sérüljön; egy ilyen élpárt nevezünk leemelhetőnek. Azt fogjuk vizsgálni, hogy a p halmazfüggvény és a G gráf milyen tulajdonságai esetén lesz ez mindig megtehető. Vezessük be a következő jelöléseket:

m(X) := d(s, X − s),
b(X) := d(X) − p(X).

Egy X, Y halmazpárt erősen keresztezőnek nevezünk, ha m(X ∩ Y), m(\overline{X ∪ Y}), m(X−Y), m(Y −X) > 0; erősen metszőnek, ha m(X∩Y), m(X−Y), m(Y −X) > 0. Egy X halmaz pozitív, ha p(X) > 0. Azt mondjuk, hogy egy X, Y halmazpáron p ferdén szupermoduláris, ha az alábbi két egyenlőtlenség legalább egyike teljesül:

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

2. p(X) + p(Y) ≤ p(X − Y) + p(Y − X).

Egy X halmaz akadályoz egy leemelést, ha a leemelés elvégzése után b(X) negatív lenne (világos, hogy ekkor X csak pozitív halmaz lehet). Amennyiben több leemelés közül szeretnénk egy végrehajthatót kiválasztani, akadályozó rendszernek nevezzük a következő tulajdonságokkal rendelkező halmazrendszert:

• Mindegyik akadályozott leemelést a rendszer valamelyik halmaza is akadályozza, de bármelyik halmazt kihagyva a rendszerből ez már nem teljesül.

• A rendszer minden eleme maximális akadályozó halmaz, azaz nincs olyan halmaz, ami leemelések egy szigorúan nagyobb részét akadályozná.

3.1 Leemelés páros többletfüggvény esetén

Ha a b többletfüggvény minden halmazra páros, akkor az akadályozó halmazok rendelkeznek az irányított esetnél megfigyelt kellemes tulajdonságokkal, így hasonlóan általános tételeket lehet kimondani. Az itt ismertetett tételek Bertsimas és Teo [4] eredményein alapulnak, egy kicsit más megközelítésben.

3.3. Tétel. Tegyük fel, hogy (3.1) teljesül, minden X ⊆ V -re p(X) + p(s) ≥ p(X + s), b(X) páros, és m(V) > p(s); ezenkívül bármely két pozitív, erősen metsző X, Y - on p ferdén szupermoduláris. Ekkor tetszőleges st élhez van olyan us él, amivel leemelhető.

Bizonyítás A leemelésünk pontosan akkor jó, ha minden olyan X ⊆ V halmazra, amire u, t ∈ X, b(X) ≥ 2. A feltételek szerint b minden halmazon páros, így csak olyan pozitív X ⊆ V halmazok akadályozhatják a leemelést, amikre b(X) = 0. Az ilyeneket nevezzük pontos halmaznak. Tetszőleges X pontos halmazra

m(X) − p(s) ≤ m(V − X)

teljesül. Ebből adódik, hogy nem lehet olyan pontos X halmaz, ami az összes leemelést akadályozza. Ebben az esetben ugyanis p(s) ≥ m(X) − m(V − X) = m(V) > p(s), ellentmondás.

Legyen X_{1}, …, X_{k} egy akadályozó rendszer. Ekkor t ∈ ∩_{i=1}^{k}X_{i}, és m(X_{i} − X_{j}) > 0 (i ≠ j), tehát páronként erősen metszőek. k = 1 estén tudjuk, hogy van jó leemelés, tehát feltehető, hogy k > 1. p és d tulajdonságai alapján bármely pozitív, erősen metsző X, Y ⊆ V halmazpárra az alábbi két egyenlőtlenség egyike teljesül:

b(X) + b(Y) ≥ b(X ∩ Y) + b(X ∪ Y),
b(X) + b(Y) ≥ b(X − Y) + b(Y − X) + 2m(X ∩ Y).

Speciálisan, ha k > 1, akkor b(X_{1}) + b(X_{2}) ≥ b(X_{1} ∩ X_{2}) + b(X_{1} ∪ X_{2}), hiszen a pontosság és m(X_{i} ∩X_{j}) > 0 miatt a második egyenlőtlenség nem teljesülhet. Ekkor viszont X_{1} ∪ X_{2} is pontos, ami ellentmond X_{1} és X_{2} maximalitásának, azaz k > 1 nem lehetséges.

Az irányított esethez hasonlóan, ha az s pont semleges, azaz minden X ⊆ V -re p(X) = p(X + s), akkor gyengébb feltételeknek eleget tevő p függvények is kezelhetőek (ilyenekre látunk majd példát az élidegen utakról szóló részben).

3.4. Tétel. Tegyük fel, hogy (3.1) teljesül, minden X ⊆ V -re p(X) = p(X + s), és b(X) páros; ezenkívül bármely három pozitív, páronként erősen keresztező halmaz közül kiválasztható egy pár, amin p ferdén szupermoduláris. Ekkor tetszőleges st élhez van olyan us él, amivel leemelhető.

Bizonyítás Pontos halmaz alatt ugyanazt értjük, mint az előző tétel bizonyításában. p(X) = p(X + s) miatt tetszőleges X pontos halmazra

m(X) ≤ m(V − X).

Ebből adódik, hogy nem lehet olyan pontos X és Y, hogy a kettő együtt az összes leemelést akadályozza. Ebben az esetben ugyanis t ∈ X∩Y, tehát m(X∩Y) > 0. Az előbbi egyenlőtlenséget használva m(X) ≤ m(V −X) < m(Y) ≤ m(V −Y) < m(X), ellentmondás.

Legyen X_{1}, …, X_{k} egy akadályozó rendszer. Ekkor t ∈ ∩_{i=1}^{k}X_{i}, és m(X_{i} − X_{j}) > 0 (i ≠ j). Az előbb bizonyítottak alapján m(\overline{X_{i} ∪ X_{j}}) > 0, tehát X_{1}, …, X_{k} páronként erősen keresztezőek. k = 2 estén tudjuk, hogy van jó leemelés, így feltehető, hogy k > 2. Most a p-re adott feltételek és d ismert tulajdonságai azt adják, hogy bármely három pozitív, páronként erősen keresztező halmaz között van kettő (X, Y), amire az alábbi két egyenlőtlenség egyike teljesül:

b(X) + b(Y) ≥ b(X ∩ Y) + b(X ∪ Y),
b(X) + b(Y) ≥ b(X − Y) + b(Y − X) + 2m(X ∩ Y).

Speciálisan, ha k > 2, akkor van X_{i} és X_{j}, hogy b(X_{i}) + b(X_{j}) ≥ b(X_{i} ∩ X_{j}) + b(X_{i} ∪ X_{j}), hiszen a pontosság és m(X_{i} ∩ X_{j}) > 0 miatt a második egyenlőlenség nem teljesülhet. Ekkor viszont X_{i} ∪ X_{j} is pontos, ami ellentmond X_{i} és X_{j} maximalitásának, azaz k > 2 nem lehetséges.

Megjegyzés A p-re megkövetelt szimmetria nem lényeges, ugyanis ha egy nem szimmetrikus p függvény kielégíti a tétel feltételeit, akkor azok a

p̂(X) := max(p(X), p(V − X))

szimmetrikus függvényre is teljesülnek.

3.2 Élidegen utak

Adott egy G = (V, E) irányítatlan gráf, és (s_{1}, t_{1}), …, (s_{k}, t_{k}) nem feltétlenül diszjunkt pontpárok. Szeretnénk élidegen utakat találni, amik az egyes pontpárokat összekötik. Jelöljük H-val az {s_{1}t_{1}, …, s_{k}t_{k}} élhalmazú igénygráfot; az élidegen utak létezésének szükséges feltétele, hogy minden X ⊆ V -re d_{G}(X) ≥ d_{H}(X) teljesüljön; ezt nevezzük vágásfeltételnek. Jelentős eredmények születtek azoknak az eseteknek a vizsgálatában, amikre ez a feltétel elégséges is. Ismert, hogy ha G + H Euler-gráf, és H dupla csillag (olyan gráf, ahol két csúcs lefogja az öszes élt), K_{4} vagy C_{5} (esetleg többszörös élekkel), akkor a vágásfeltétel elégséges; a többi igénygráfra pedig kostruálható olyan ellenpélda, ahol a vágásfeltétel teljesülése ellenére nincsenek megfelelő élidegen utak (Scrijver [22] rövid bizonyítást ad ezekre a tételekre). Bertsimas és Teo [4] megmutatta, hogy a fenti eredmény a három gráftípusra a leemelési művelet segítségével is egységesen igazolható; az ő módszerüket ismertetjük, kis módosítással.

3.5. Tétel. Tekintsünk egy H igénygráfot. Akkor és csak akkor lesz minden olyan (G, H) élidegen út probléma megoldható, amire G+H Euler és a vágásfeltétel teljesül, ha H dupla csillag, K_{4} vagy C_{5} (esetleg többszörös élekkel).

Bizonyítás. Könnyen ellenőrizhető, hogy a tételben szereplő gráfok pontosan azok, amik nem tartalmaznak részgráfként sem 3K_{2}-t, sem diszjunkt K_{2}-t és K_{3}- at. A szükségességhez tehát elég erre a két igénygráfra olyan feladatot mutatni, ami a vágásfeltétel teljesülése ellenére sem oldható meg. Az alábbi ábrán látható példákban a vágásfeltétel könnyen ellenőrizhető; élidegen utak viszont nem lehetnek, hiszen a legrövidebb utak hosszának összege is több, mint a G gráf élszáma.

2. Ábra : Nincsenek élidegen utak.

Az elégségességet a leemelési művelet segítségével bizonyítjuk. Legyen p(X) := d_{H}(X). Világos, hogy minden s ∈ V, X ⊆ V − s-re p(X + s) ≤ p(X) + p(s). Először megmutatjuk, hogy a tételben szereplő igénygráfoknál minden igényéllel nem szomszégos pontról le lehet emelni az éleket úgy, hogy d_{G}(X) ≥ p(X) fennmaradjon minden X ⊆ V halmazra. Elég tehát olyan gráfokra élidegen utakat találni, ahol minden pont valamelyik igényél végpontja, hiszen a leemeléseken fordított sorrendben végighaladva, az utakban a leemeléssel keletkező éleket a leemeltekre kicserélve, az eredeti gráfban kapunk élidegen utakat.

Legyen s egy olyan pont, ami nincs igényélen. Egy leemelhető élpár létezését szeretnénk igazolni a 3.4. Tétel segítségével. d_{G} −p páros, hiszen G+H Euler, tehát d_{G} + p páros; ez a tulajdonság a leemelések után is megmarad.

3.6. Lemma. Akkor és csak akkor választható ki bármely három páronként keresztező halmazból kettő, amin p ferdén szupermoduláris, ha H nem tartalmaz 3K_{2}-t, és nem tartalmaz diszjunkt K_{2}-t és K_{3}-at.

Bizonyítás. Az alábbi ábrán jelölt halmazok mutatják, hogy ha H tartalmaz 3K_{2}-t vagy K_{2} + K_{3}-at, akkor fenti tulajdonság nem teljesül.

3. Ábra : p egyik halmazpáron sem ferdén szupermoduláris.

Fordítva, ha van olyan X_{1}, X_{2}, X_{3}, hogy p semelyik kettőre sem ferdén szupermoduláris, akkor p definíciója alapján d_{H}(X_{i}, X_{j}) > 0 és \overline{d_{H}}(X_{i}, X_{j}) > 0 (i ≠ j). Könnyen látható, hogy az ebből adódó H-beli élek között vagy van 3K_{2}, vagy van K_{2} + K_{3}.

A továbbiakban feltehetjük, hogy minden pont rajta van H-beli élen, és H-beli él nem párhuzamos G-belivel (hiszen akkor a kettő elhagyható lenne). Legyen először H dupla csillag, és t_{1}, t_{2} két pont, ami az összes élt lefogja. Belátjuk, hogy ha s ≠ t_{1}, t_{2}, d_{G}(s) > p(s), és st_{1} ∈ E, akkor st_{1} leemelhető valamilyen us éllel. Legyen X_{1}, …, X_{k} egy akadályozó rendszer (X_{i} ⊆ V − s). p-nek a Lemmában igazolt tulajdonsága miatt k ≤ 2 (ez a 3.4. Tétel bizonyításában leírt módon igazolható), k = 1 esetén pedig X_{1} nem akadályozhatja az összes leemelést (lásd 3.3. Tétel bizonyítása). Tegyük fel, hogy k = 2, és az összes leemelés akadályozott. Ha az X_{1}, X_{2} halmazpáron p ferdén szupermoduláris, akkor a 3.3. Tétel bizonyításának a megfelelő részét alkalmazva X_{1} ∪ X_{2} is pontos lenne, ami ellentmond az akadályozó rendszer definíciójának. Ha a ferde szupermodularitás nem teljesül, akkor d_{H}(X_{1}, X_{2}) > 0 miatt t_{2} ∈ X_{1}ΔX_{2}, tehát s-ből nem megy X_{1} ∩ X_{2}-be H-beli él. Ekkor viszont p(X_{1}+s)+p(X_{2}+s) = p(X_{1})+p(X_{2}) = d_{G}(X_{1})+d_{G}(X_{2}) > d_{G}(X_{1}+s)+d_{G}(X_{2}+s), ellentmondás.

A fentiek alapján feltehető, hogy d_{G}(V − {t_{1}, t_{2}}) = p(V − {t_{1}, t_{2}}); ekkor a megoldhatóság már egyszerűen következik a vágásfeltételből.

Mivel feltettük, hogy H-beli él nem párhuzamos G-belivel, a K_{4} esetet valójában már megoldottuk a dupla csillaggal, hiszen nem szerepelhet a teljes négyes minden éle H-ban.

A C_{5} esetben belátjuk, hogy bármelyik st ∈ E élhez van us ∈ E, amivel leemelhető. A dupla csillagokra használt gondolatmenettel látható, hogy elég kételemű X_{1}, X_{2} akadályozó rendszerrel foglalkozni. Tegyük fel, hogy az összes leemelés akadályozott. A dupla csillag esethez hasonlóan itt is feltehető, hogy az X_{1}, X_{2} halmazpáron p nem ferdén szupermoduláris. Ekkor d_{H}(X_{1}, X_{2}) > 0 és \overline{d}_{H}(X_{1}, X_{2}) > 0, amiből könnyen látszik, hogy X_{1} ∩ X_{2} = t, azaz s-ből nem lép X_{1} ∩ X_{2}-be él H-ban. Innen p(X_{1} + s) + p(X_{2} + s) ≥ p(X_{1}) + p(X_{2}) = d_{G}(X_{1}) + d_{G}(X_{2}) > d_{G}(X_{1} + s) + d_{G}(X_{2} + s), ellentmondás.

Az eredeti gráfokra úgy kapunk élidegen utakat, hogy fordított sorrendben tekintjük a végrehajtott leemeléseket, és ha a leemeléssel keletkező él szerepel valamelyik útban, akkor kicseréljük a leemelés előtti élpárra.

3.3 Takarékos halmazfüggvények

Legyen G = (V, E) a teljes gráf V pontjain, c : E → R_{+} ∪ {∞} költségfüggvénnyel, H ⊆ V rögzített halmaz. Tekintsünk egy f : 2^{V} → Z_{+} halmazfüggvényt, és a következő optimalizálási feladatot:

IZ_{f}(H) := min ∑_{e∈E} c(e)x(e), ahol

∑_{u∈V} x(us) = f(s) (s ∈ H),

∑_{u∉X,v∈X} x(uv) ≥ f(X) (X ⊆ V),

x(e) ∈ Z_{+} (e ∈ E).

Jelöljük Z_{f}(H)-val az LP-relaxációhoz tartozó minimumot (tehát amikor az utolsó feltétel helyett x(e) ≥ 0 (e ∈ E) a követelmény), és P_{f}(H)-val az LP-relaxációhoz tartozó poliédert. Olyan feltételeket keresünk, amikkel Z_{f}(H) = Z_{f}(∅), azaz a H pontjaira megkövetelt egyenlőség nem változtat az LP-relaxáció minimumán; ez az úgynevezett takarékossági tulajdonság (parsimonious property). A fogalmat bevezető Goemans és Bertsimas [12] megmutatták, hogy az ezzel a tulajdonsággal rendelkező feladatok érdekes algoritmikus és strukturális tulajdonságokkal rendelkeznek. Mi [4] nyomán két olyan halmazfüggvény-családot ismertetünk, amikre teljesül a takarékossági tulajdonság.

3.7. Tétel. Tegyük fel, hogy c-re teljesül a háromszög-egyenlőtlenség, és f-re igazak a következők:

1. f(∅) = 0,

2. f szimmetrikus,

3. metsző halmazokon f ferdén szupermoduláris,

4. Minden s ∈ H, X ⊆ (V − s)-re f(X) + f(s) ≥ f(X + s).

Ekkor Z_{f}(H) = Z_{f}(∅).

Bizonyítás. Tekintsünk a Z_{f}(∅) minimumot adó x-ek közül egy olyat, amire a pontos halmazok száma a lehető legtöbb, ezen belül a pozitív élek száma a lehető legkevesebb. Tegyük fel, hogy van olyan s ∈ H pont, amire ∑_{u∈V} x(us) > f(s); ekkor a 3.3. Tétel bizonyítása egy az egyben átfogalmazható az itt tárgyalt nem egészértékű esetre. Azt kapjuk, hogy vannak u, t pontok, és ϵ > 0, hogy az x′(us) = x(us) − ϵ, x′(ts) = x(ts) − ϵ, x′(ut) = x(ut) + ϵ átalakítással kapott x′-re ∑_{e∈E} c(e)x′(e) = Z_{f}(∅), és vagy az us, ts élek egyike nullázódik, vagy keletkezik egy új pontos halmaz. Az x′ létezése ellentmond x választásának, tehát x ∈ P_{f}(H), ezzel a tételt bebizonyítottuk.

Goemans és Williamson [13], illetve Bertsimas és Teo [4] megmutatták, hogy a H = V esetben takarékossági tulajdonsággal rendelkező kombinatorikus problémákra jó közelítő algoritmust lehet konstruálni, speciálisan ha f 0-1 függvény, akkor 2közelítő algoritmust adtak. Ebbe a kategóriába tartozik többek közt az általánosított Steiner-fa, a T-join, a network survivability probléma.

A 3.4. Tétel segítségével általánosabb halmazfüggvényekre is igazolni tudjuk a takarékossági tulajdonságot, igaz, hogy ekkor H pontjaira erősebb megkötéseket kell tenni.

3.8. Tétel. Tegyük fel, hogy c-re teljesül a háromszög-egyenlőtlenség, és f-re igazak a következők:

1. f(∅) = 0,

2. f szimmetrikus, 3. bármely három, páronként keresztező halmaz közül kiválasztható kettő, amin f

ferdén szupermoduláris,

4. Minden s ∈ H, X ⊆ (V − s)-re f(X) = f(X + s).

Ekkor Z_{f}(H) = Z_{f}(∅).

Bizonyítás. Ha x-et ugyanúgy választjuk, mint az előző bizonyításban, akkor itt is igaz az ott használt állítás, csak most ennek igazolásához a 3.4. Tétel bizonyítására kell hivatkozni.

3.4 Leemelés általános igényfüggvény esetén

Ha nem tesszük fel b párosságát, nehézséget okoz, hogy egy leemelést nem csak pontos halmazok akadályozhatnak. A ferde szupermodularitás így nem lesz elég, de ha bevezetünk egy halmazhármasokra vonatkozó, ferde szupermodularitáshoz hasonló feltételt, akkor be tudunk bizonyítani egy olyan leemelési tételt, ami magában foglalja Mader tételét (3.2. Tétel), és (mint azt a 4. fejezetben meg fogjuk mutatni) a vegyes gráfok élösszefüggőség-növeléséhez használt irányítatlan leemelési műveletet.

3.9. Tétel. Tegyük fel, hogy (3.1) teljesül, m(V) páros, és p(X) = p(X +s) minden X ⊆ V -re. Ezenkívül p-re az alábbi tulajdonságok teljesülnek:

1. Az olyan keresztező pozitív X, Y halmazpárokon, amikre m(X ∩ Y) > 0 és m(\overline{X ∪ Y}) > 0, p ferdén szupermoduláris.

2. Ha X_{1}, X_{2}, X_{3} pozitív, páronként erősen keresztező, és bármely kettő metszete Z, akkor az alábbi két egyenlőtlenség legalább egyike teljesül:

p(X_{1}) + p(X_{2}) + p(X_{3}) ≤ p(X_{1} ∪ X_{2} ∪ X_{3}) + 2p(Z),

p(X_{1}) + p(X_{2}) + p(X_{3}) ≤ p(X_{1} − Z) + p(X_{2} − Z) + p(X_{3} − Z) + p(Z) − 2.

Ekkor tetszőleges st élhez van olyan us él, amivel leemelhető.

Bizonyítás. Egy X ⊆ V pozitív halmazt pontosnak nevezünk, ha b(X) = 0; veszélyesnek, ha b(X) ≤ 1. Egy leemelés pontosan akkor jó, ha nincs olyan veszélyes halmaz, ami mindkét végpontot tartalmazza. A b függvényre a következők igazak:

1. Az olyan pozitív, keresztező X, Y halmazpárokon, amelyekre m(X ∩ Y) és m(\overline{X ∪ Y}) pozitív, vagy m(X − Y) és m(Y − X) pozitív (ekkor X-re és \overline{Y} -ra igaz az előző), az alábbiak egyike teljesül:

b(X) + b(Y) ≥ b(X ∩ Y) + b(X ∪ Y) + 2d(X, Y),  (3.2)
b(X) + b(Y) ≥ b(X − Y) + b(Y − X) + 2\overline{d}(X, Y).  (3.3)

Speciálisan, ha X pontos, Y veszélyes, és m(X ∩ Y) > 0, akkor (3.2) teljesül.

2. Ha X_{1}, X_{2}, X_{3} pozitív, páronként erősen keresztező, és bármely kettő metszete Z, akkor az alábbi két egyenlőtlenség legalább egyike teljesül:

b(X_{1}) + b(X_{2}) + b(X_{3}) ≥ b(X_{1} ∪ X_{2} ∪ X_{3}) + 2b(Z),  (3.4)
\begin{aligned}b(X_{1}) + b(X_{2}) + b(X_{3}) & ≥ b(X_{1} − Z) + b(X_{2} − Z) + b(X_{3} − Z) \\ & + b(Z) + 2 + 2m(Z). \end{aligned}  (3.5)

Speciálisan, ha X_{1}, X_{2}, X_{3} veszélyes, és m(Z) > 0, akkor (3.4) teljesül.

Ha X pontos, p(X) = p(X + s)-et kihasználva m(X) ≤ m(V − X); veszélyes X esetén m(X) ≤ m(V − X) + 1 (általában m(X) − b(X) ≤ m(V − X)). Ezekből és m(V) párosságából adódik, hogy két halmaz nem akadályozhatja az összes leemelést. Tegyük fel ugyanis indirekt, hogy X és Y mindent akadályoz. Ekkor, kihasználva, hogy m(X ∩ Y) > 0,

m(X) ≤ m(V − X) + 1 ≤ m(Y) ≤ m(V − Y) + 1 ≤ m(X),

azaz végig egyenlőség áll, m(X) = m(Y), m(X ∩ Y) = 1, de ez ellentmond m(V) párosságának.

A következőkben megmutatjuk: feltehető, hogy minden pontos halmaz egypontú. Legyen X egy nem egypontú pontos halmaz; az X összehúzásával keletkező feladatra (p-t csak a megmaradó halmazokra megtartva) könnyen ellenőrizhetően teljesülnek a tétel feltételei, van tehát egy jó leemelés. Ha az eredeti gráfra ezt a leemelést akadályozná egy Y halmaz, akkor m(X − Y) > 0 esetén vagy X ∪ Y veszélyes lenne, vagy Y − X veszélyes és m(X ∩ Y) = 0 (nem keresztező X, Y -ra ez utóbbi teljesülne a fenti gondolatmenet alapján), m(X − Y) = 0 esetén pedig X pozitivitása miatt m(X ∩ Y) > 0, tehát az előzőek szerint m(\overline{X ∪ Y}) > 0, és a b-re teljesülő (3.2) egyenlőtlenség alapján X ∪ Y veszélyes lenne, ami lehetetlen.

Legyen X_{1}, …, X_{k} egy akadályozó rendszer. Feltehető, hogy k > 2, hiszen két halmaz nem akadályozhatja az összes leemelést. i ≠ j esetén X_{i} ∪ X_{j} nem veszélyes és m(X_{i}∩X_{j}) > 0, tehát (3.2) illetve (3.3) alapján vagy X_{i}∩X_{j} = t, vagy |X_{i}−X_{j}| = |X_{j}−X_{i}| = 1, hiszen pontosak. Tetszőleges k ≠ i, j-re (kihasználva, hogy a halmazok egyike sem hagyható ki a rendszerből) az első esetben X_{k}∩X_{i} = t vagy X_{k}∩X_{j} = t; a második esetben X_{k}∩X_{i} = X_{k}∩X_{j} = t vagy X_{k}∩X_{i} = X_{k}∩X_{j} = X_{i}∩X_{j}. Azonban e legutolsó esetben is a három halmaz metszete csak t lehet, hiszen X_{i} ∪ X_{j} ∪ X_{k} nem veszélyes a maximalitás miatt, így (3.4) szerint a metszetük pontos.

Most legyen X_{1}, …, X_{l} olyan l darab halmaz az akadályozó rendszerből, hogy bármely kettő metszete t. Legyen X := ∪_{i=1}^{l}X_{i}.

3.10. Állítás. Ha l páratlan, akkor b(X) ≤ l; ha emellett m(\overline{X}) > 0, akkor b(X − t) ≥ b(X) − 1. Ha X_{1} − t nem pontos, akkor a két egyenlőtlenség páros l esetén is fennáll.

Bizonyítás. Először a páratlan l-re vonatkozó két állítást bizonyítjuk l szerinti indukcióval. l = 1 esetén mindkét egyenlőtlenség teljesül. Tegyük fel, hogy l − 2-re már beláttuk mindkettőt. Ha az ∪_{i=1}^{l−2}X_{i}, X_{l−1}, X_{l} hármast tekintjük, a bre vonatkozó (3.5) egyenlőtlenség nem teljesülhet, hiszen az ellentétben lenne az indukció szerint fennálló b(∪_{i=1}^{l−2}X_{i} − t) ≥ b(∪_{i=1}^{l−2}X_{i}) − 1-gyel. Így (3.4) teljesül, ami az első bizonyítandó állítást adja. A második állításhoz az ∪_{i=1}^{l−2}X_{i} és ∪_{i=1}^{l}X_{i} − t halmazokat tekintjük. Ha ezekre (3.2) teljesül:

b(∪_{i=1}^{l−2}X_{i}) + b(∪_{i=1}^{l}X_{i} − t) ≥ b(∪_{i=1}^{l−2}X_{i} − t) + b(∪_{i=1}^{l}X_{i}),

azaz az indukció szerint b(∪_{i=1}^{l}X_{i} − t) − b(∪_{i=1}^{l}X_{i}) ≥ −1. Ha (3.3) teljesül:

b(∪_{i=1}^{l−2}X_{i}) + b(∪_{i=1}^{l}X_{i} − t) ≥ b(t) + b((X_{l−1} ∪ X_{l}) − t) + 2m(∪_{i=1}^{l−2}X_{i} − t),

tehát a tagokat felülről, illetve alulról becsülve

(l − 2) + b(∪_{i=1}^{l}X_{i} − t) ≥ 0 + 1 + 2(l − 2),
b(∪_{i=1}^{l}X_{i} − t) ≥ l − 1.

Abban az esetben, ha X_{1} − t nem pontos, l = 2-re is igazak az állítások, hiszen X_{1}-re és X_{2}-re (3.2) és (3.3) közül csak az első teljesülhet, így b(X_{1} ∪ X_{2}) = 2, és b(X_{1} ∪ X_{2} − t) ≥ 1, hiszen nem pontos. Innen az indukciót ugyanúgy használhatjuk külön a párosakra, mint fent a páratlanokra.

A továbbiakban két esetet különböztetünk meg. Tegyük fel először, hogy az X_{1}, …, X_{k} halmazok közül bármely kettő metszete t. Legyen X := ∪_{i=1}^{k}X_{i}. Akkor van jó leemelés, ha m(V − X) > 0. Ha k páratlan, az előző állítás szerint

m(V − X) ≥ m(X) − b(X) ≥ (k + 1) − k = 1.

Ha k páros, számozzuk úgy a halmazokat, hogy m(X_{k}) ≤ m(X_{i}) (i = 1, …, k). Legyen U := ∪_{i=1}^{k−1}X_{i}. Ekkor

m(V − X) = m(V − U) − m(X_{k} − U) ≥ m(U) − b(U) − m(X_{k} − U)
≥ m(U) − m(X_{k} − U) − (k − 1).

X_{k} választása alapján m(U) − m(X_{k} − U) ≥ k − 1, és egyenlőség esetén m(X_{i}) = m(X_{k}) = 2, de ez ellentmondana m(V) párosságának; így m(V − X) > 0.

Meg kell még vizsgálni azt az esetet, amikor van két halmaz, aminek metszete nem t. Ekkor a halmazok felsorolhatók a következő módon: X_{1}, …, X_{k_{1}}, Y_{11}, Y_{12}, …, Y_{k_{2}1}, Y_{k_{2}2}, ahol pontosan Y_{i1} és Y_{i2} metszi egymást t-nél bővebb halmazban. Definiáljuk az alábbi két halmazt:

U_{1} := (∪_{i=1}^{k_{1}}X_{i}) ∪ (∪_{i=1}^{k_{2}}Y_{i1}),
U_{2} := (∪_{i=1}^{k_{1}}X_{i}) ∪ (∪_{i=1}^{k_{2}}Y_{i2}).

Mind U_{1}, mind U_{2} esetén az unióban szereplő halmazok metszete páronként t, és mindkét unióban van halmaz, amiből t-t elhagyva nem pontosat kapunk. Így a 3.10. Állítást alkalmazva b(U_{1}) ≤ k_{1} + k_{2}, b(U_{2}) ≤ k_{1} + k_{2}. Ezt felhasználva

2m(V − X) = m(V − U_{1}) + m(V − U_{2}) − m(U_{1}ΔU_{2})
≥ m(U_{1}) − b(U_{1}) + m(U_{2}) − b(U_{2}) − m(U_{1}ΔU_{2})
≥ m(U_{1}) + m(U_{2}) − 2k_{1} − 2k_{2} − m(U_{1}ΔU_{2}) ≥ 2,

azaz m(V − X) > 0.

3.5 Halmazfüggvények fedése irányítatlan gráffal

A 3.4. és 3.9. Tételben a feltételek olyanok, hogy egy jó leemelés végrehajtása után továbbra is fennállnak. Így a leemelési műveletet meg lehet ismételni (tetszőleges új t-t választva), ameddig csak s-nek van szomszédja. Az irányított esethez hasonlóan tehát a fenti tételeket alkalmazhatjuk a következő fedési feladat megoldására:

Adott egy V alaphalmaz, egy m : V → Z_{+} fokszámelőírás és egy p : 2^{V} → Z_{+} szimmetrikus halmazfüggvény, p(∅) = 0. Eldöntendő, van-e olyan G = (V, E) gráf, amire

d(v) = m(v) minden v ∈ V -re,  (3.6)

tehát G teljesíti a fokszámelőírást, és

d(X) ≥ p(X) minden X ⊆ V -re,  (3.7)

azaz a G gráf fedi p-t. Vezessük be az m(X) := ∑_{v∈X} m(v) jelölést. Pozitív halmazon és erősen keresztező halmazpáron ugyanazt értjük, mint eddig (m új definíciójával). Könnyen látható, hogy G létezésének szükséges feltétele, hogy m(V) páros, és minden X ⊆ V -re

m(X) ≥ p(X).

3.11. Tétel. Tegyük fel, hogy minden X ⊆ V -re m(X) − p(X) páros, m(X) ≥ p(X), és bármely három pozitív, páronként erősen keresztező halmaz közül kiválasztható egy pár, amin p ferdén szupermoduláris. Ekkor van (3.6)-ot és (3.7)-et teljesítő G gráf.

3.12. Tétel. Tegyük fel, hogy m(V) páros, minden X ⊆ V -re m(X) ≥ p(X), és p-re az alábbi tulajdonságok teljesülnek:

1. Az olyan keresztező pozitív X, Y halmazpárokon, amikre m(X∩Y) és m(\overline{X ∪ Y}) pozitív, p ferdén szupermoduláris.

2. Ha X_{1}, X_{2}, X_{3} pozitív, páronként erősen keresztező, és bármely kettő metszete Z, akkor az alábbi két egyenlőtlenség legalább egyike teljesül:

p(X_{1}) + p(X_{2}) + p(X_{3}) ≤ p(X_{1} ∪ X_{2} ∪ X_{3}) + 2p(Z),

p(X_{1}) + p(X_{2}) + p(X_{3}) ≤ p(X_{1} − Z) + p(X_{2} − Z) + p(X_{3} − Z) + p(Z) − 2.

Ekkor van (3.6)-ot és (3.7)-et teljesítő G gráf.

Bizonyítás. A két tétel egyszerűen visszavezethető a 3.4. illetve a 3.9. Tételre: vegyünk fel egy új s pontot, legyen X ⊆ V -re p(X + s) := p(X), és tekintsük azt a G′ gráfot, aminek a minden v ∈ V -re m(v) multiplicitással vett sv élek alkotják az élhalmazát. A G′ gráfból kiindulva alkalmazhatjuk m(V)/2-ször a 3.4. Tételt, illetve a 3.9. Tételt; a végén kapott G gráf kielégíti a feltételeket.

E tételek szépséghibája, hogy nem lehet automatikusan elhagyni azokat a pontokat, amikre m = 0. Egy kis módosítással ezen is segíthetünk. Tetszőleges szimmetrikus p-re vezessünk be egy új halmazfüggvényt:

p′(X) := max_{Y:m(XΔY)=0} p(Y).

Könnyen látható, hogy akkor és csak akkor van p′-re nézve fedő gráf, ha p-re nézve van. Ha tehát p tulajdonságait úgy adjuk meg, hogy p′-re teljesülnek valamelyik tétel feltételei, akkor van jó gráf. Egy X halmazt lényegesnek nevezünk, ha p′(X) = p(X). X′ majorálja X-et, ha p′(X) = p(X′).

3.13. Tétel. Tegyük fel, hogy minden X ⊆ V -re m(X) − p(X) páros, m(X) ≥ p(X), és bármely három pozitív, lényeges, páronként erősen keresztező halmaz közül kiválasztható egy pár, amin p′ ferdén szupermoduláris. Ekkor van (3.6)-ot és (3.7)-et teljesítő G gráf.

3.14. Tétel. Tegyük fel, hogy m(V) páros, minden X ⊆ V -re m(X) ≥ p(X), és p-re az alábbi tulajdonságok teljesülnek:

1. A pozitív, lényeges, erősen keresztező X, Y halmazpárokon p′ ferdén szupermoduláris.

2. Ha X_{1}, X_{2}, X_{3} pozitív, lényeges, páronként erősen keresztező, és bármely kettő metszetét majorálja egy közös Z halmaz, akkor az alábbi két egyenlőtlenség legalább egyike teljesül:

p(X_{1}) + p(X_{2}) + p(X_{3}) ≤ p′(X_{1} ∪ X_{2} ∪ X_{3}) + 2p(Z),

p(X_{1}) + p(X_{2}) + p(X_{3}) ≤ p′(X_{1} − Z) + p′(X_{2} − Z) + p′(X_{3} − Z) + p(Z) − 2.

Ekkor van (3.6)-ot és (3.7)-et teljesítő G gráf.

Bizonyítás. Azt kell ellenőrizni, hogy a 3.11. és 3.12. Tétel feltételei teljesülnek p′-re. Ez minden egyes egyenlőtlenség esetén belátható úgy, hogy a baloldalon szereplő halmazok majoráló halmazait tekintjük, ezekre mint lényeges halmazokra a fetételek szerint igazak az egyenlőtlenségek (illetve ha a 3.11. Tétel 1. pontjában nem erősen keresztezők, akkor triviálisan igazak). A p′-vel felírt jobboldal pedig ugyanaz az eredeti halmazokra és a majoráló halmazokra.

A 3.13. Tétel tovább általánosítható, ha p′ helyett a következő függvényt tekintjük:

p′′(X) := max_{Y ⊆V}(p(Y) − m(XΔY)).

Itt is igaz, hogy p′′ szimmetrikus, és pontosan akkor van p-t fedő gráf, ha p′′-t fedő van. Most azokat az X halmazokat nevezzük lényegesnek, amikre p′′(X) = p(X). X′ majorálja X-et, ha p′′(X) = p(X′) − m(XΔX′). Pozitív halmazt csak pozitív majorálhat.

3.15. Állítás. p′′(X) = max_{Y ⊆V} (p′′(Y) − m(XΔY)). Speciálisan, ha X′ majorálja X-et, akkor X′ lényeges.

Bizonyítás. Indirekt tegyük fel, hogy ∃Y, Z ⊆ V: Z majorálja Y -t, és

p′′(X) < p′′(Y) − m(XΔY) = p(Z) − m(Y ΔZ) − m(XΔY).

Ekkor felhasználva az

m(Y ΔZ) + m(XΔY) ≥ m(XΔZ)

egyenlőtlenséget azt kapjuk, hogy

p′′(X) < p(Z) − m(XΔZ),

ami lehetetlen.

3.16. Lemma. Ha egy pozitív, lényeges X′, Y′ páron p′′ ferdén szupermoduláris, akkor bármely olyan X, Y párra, amire X′ majorálja X-et, és Y′ majorálja Y -t, p′′ ferdén szupermoduláris.

Bizonyítás. Szükségünk lesz az alábbi két, számolással ellenőrizhető egyenlőtlenségre:

m(XΔX′) + m(Y ΔY′) ≥ m((X ∩ Y)Δ(X′ ∩ Y′)) + m((X ∪ Y)Δ(X′ ∪ Y′)),(3.8)
m(XΔX′) + m(Y ΔY′) ≥ m((X − Y)Δ(X′ − Y′)) + m((Y − X)Δ(Y′ − X′)). (3.9)

Tegyük fel először, hogy p′′(X′) + p′′(Y′) ≤ p′′(X′ ∩ Y′) + p′′(X′ ∪ Y′). Ekkor

p′′(X) + p′′(Y) = p(X′) − m(XΔX′) + p(Y′) − m(XΔY′)
≤ p′′(X′ ∩ Y′) + p′′(X′ ∪ Y′) − m(XΔX′) − m(XΔY′).

A (3.8) egyenlőtlenséget alkalmazva:

p′′(X) + p′′(Y) ≤ p′′(X′ ∩ Y′) − m((X ∩ Y)Δ(X′ ∩ Y′))
+ p′′(X′ ∪ Y′) − m((X ∪ Y)Δ(X′ ∪ Y′))
≤ p′′(X ∩ Y) + p′′(X ∪ Y).

Hasonló a bizonyítás, ha p′′(X′) + p′′(Y′) ≤ p′′(X′ − Y′) + p′′(Y′ − X′) teljesül:

p′′(X) + p′′(Y) = p(X′) − m(XΔX′) + p(Y′) − m(XΔY′)
≤ p′′(X′ − Y′) + p′′(Y′ − X′) − m(XΔX′) − m(XΔY′).

A (3.9) egyenlőtlenséget alkalmazva:

p′′(X) + p′′(Y) ≤ p′′(X′ − Y′) − m((X − Y)Δ(X′ − Y′))
+ p′′(Y′ − X′) − m((Y − X)Δ(Y′ − X′))
≤ p′′(X − Y) + p′′(Y − X).

3.17. Tétel. Tegyük fel, hogy minden X ⊆ V -re m(X) − p(X) páros, m(X) ≥ p(X), és bármely három pozitív, lényeges, páronként erősen keresztező halmaz közül kiválasztható egy pár, amin p′′ ferdén szupermoduláris. Ekkor van (3.6)-ot és (3.7)-et teljesítő G gráf.

Bizonyítás. Megmutatjuk, hogy p′′-re teljesülnek a 3.11 Tétel feltételei. p′′(X)− m(X) páros, hiszen egy X-et majoráló X′ halmazra p′′(X) − m(X) = p(X′) − m(XΔX′) − m(X) = p(X′) − m(X′) − 2m(X − X′). Legyen X, Y, Z három pozitív, páronként erősen keresztező halmaz; meg kell mutatnunk, hogy kiválasztható közülük egy pár, amin p′′ ferdén szupermoduláris. Legyenek X, Y, Z majoráló halmazai rendre X′, Y′, Z′. Ha van köztük kettő (pl. X′, Y′), ami nem erősen keresztező, akkor ezeken a ferde szupermodularitás teljesül p′′-re, kihasználva hogy p′′ szimmetrikus, és megegyezik az olyan halmazokon, amiknek a szimmetrikus differenciáján m = 0. Ha pedig X′, Y′, Z′ páronként erősen keresztezők, akkor a tétel feltétele szerint van köztük egy pár (pl. X′, Y′), amin p′′ ferdén szupermoduláris. A Lemmát alkalmazva X′, Y′-re azt kapjuk, hogy X, Y -on p′′ ferdén szupermoduláris.

3.6 Szimmetrikus szupermoduláris függvények fedése

Az előző részben leírt halmazfüggvény-fedési feladatot most keresztező szupermoduláris halmazfüggvényekre vizsgáljuk. Benczúr András és Frank András [3] szükséges és elégséges feltételt találtak a megoldhatóságra, és ennek segítségével a hipergráfok irányítatlan gráf-élekkel való élösszefüggőség-növelésére is új eljárásokat tudtak adni. Az ebben a részben leírt bizonyítás lényegében az ő módszereiken alapul.

Az eddigi megközelítéshez hasonlóan most is először egy leemelési tételt bizonyítunk. Adott egy V + s alaphalmaz egy kijelölt s ponttal, és ezen egy G = (V + s, E) gráf, valamint egy p szimmetrikus, nemnegatív egész halmazfüggvény V + s-en, p(∅) = 0. Feltesszük, hogy minden X ⊆ V -re p(X) = p(X + s). A fejezet elején bevezetett jelöléseket használjuk, és egy újabb függvényt is definiálunk:

r(X) := m(X) − b(X) = p(X) − (d(X) − m(X)) (X ⊆ V).

Könnyen látható, hogy r(X) = r(V − X) (X ⊆ V), és (3.1) pontosan akkor teljesül, ha minden X ⊆ V -re m(X) ≥ r(X).

A szimmetria miatt p-t elég V részhalmazain tekinteni. Legyen p szupermoduláris az olyan pozitív, V -n keresztező X, Y ⊆ V halmazokon, amikre m(X ∩ Y) > 0 (ekkor r is szupermoduláris az ilyen halmazokon), és teljesüljön (3.1). Ahhoz, hogy ez utóbbi feltételt fenntartva s-ről az összes élt le tudjuk emelni, még más megszorításokat is kell tennünk: az alábbi példában, ha minden X ⊂ V halmazra p(X) = 1, akkor a jelölt halmazok miatt az s-ből a halmazok metszetébe vezető élt nem lehet leemelni.

4. Ábra : A vágásfeltétel nem elég.

Nevezzük V egy V_{1}, …, V_{l} partícióját hibás partíciónak, ha a következők teljesülnek:

• Ha U valahány (nem az összes) partícióelem egyesítése, akkor r(U) > 0,

• l − 1 > \frac{m(V)}{2}.

Könnyen látható, hogy hibás partíció létezése esetén nem lehet az összes élt leemelni, hiszen az új élek halmaza a partícióelemek összehúzása után tartalmazna egy feszítő fát, ami legalább l − 1 élt jelent. Benczúr András és Frank András [3] azonban belátta, hogy ha nincs hibás partíció, akkor a (3.1) feltétel már elégséges; most az övéktől kicsit eltérő bizonyítást adunk erre.

3.18. Tétel. Tegyük fel, hogy (3.1) teljesül, m(V) páros, nincs hibás partíció, és p szupermoduláris az olyan pozitív, V -n keresztező X, Y ⊆ V halmazokon, amikre m(X ∩ Y) > 0. Ekkor le lehet emelni s-ről egy élpárt úgy, hogy (3.1) fennmaradjon, és ne keletkezzen hibás partíció.

Bizonyítás. Először a hibás partíciók néhány tulajdonságát vizsgáljuk meg.

3.19. Állítás. Egy V_{1}, …, V_{l} partíció pontosan akkor hibás, ha l−1 > \frac{m(V)}{2}, és van olyan V_{i} eleme, amire r(V_{i}) = 1, r(V_{i} ∪ V_{j}) ≥ 1 (j ≠ i).

Bizonyítás. Hibás partícióban l−1 > \frac{m(V)}{2} miatt van olyan V_{i}, amire m(V_{i}) = 1, és így r(V_{i}) = 1. A másik irány: tegyük fel, hogy egy partícióra teljesül a fenti két tulajdonság. Ha U legfeljebb l−2 darab partícióelem egyesítése, és V_{i} ⊆ U, V_{j} ∩U = ∅, akkor r(V_{i} ∪ V_{j}) + r(U) ≤ r(V_{i}) + r(U ∪ V_{j}), tehát r(U) ≤ r(U ∪ V_{j}). Ebből világos, hogy tetszőleges V_{i} ⊆ U ≠ V unióra r(U) > 0. A V_{i}-t nem tartalmazókra ez r szimmetriájából következik.

Nevezzünk egy V_{1}, …, V_{l} partíciót pontos partíciónak, ha l − 1 = \frac{m(V)}{2}, és van olyan V_{i} eleme, amire r(V_{i}) = 1, r(V_{i}∪V_{j}) ≥ 1 (j ≠ i). Az első tulajdonság miatt van legalább két partícióelem, amire m = 1. Világos, hogy hibás partíció leemeléskor csak pontos partícióból jöhet létre.

3.20. Állítás. Legyen V_{1}, …, V_{l} pontos partíció, m(V_{1}) = m(V_{2}) = 1. Ekkor, ha U partícióelemek V_{1}-et tartalmazó és V_{2}-t nem tartalmazó egyesítése, akkor r(U) = 1.

Bizonyítás. A előző Állítás bizonyítása ebben az esetben azt adja, hogy 1 ≤ r(U) ≤ r(V − V_{2}), de r(V − V_{2}) = r(V_{2}) = 1, tehát r(U) = 1.

Ha egy leemelés egy pontos partíció két eleme közti élt hoz létre, akkor az előbbi állítás alapján van olyan U, amire r(U) nullázódik, azaz így nem jöhet létre hibás partíció. Egy leemelés tehát pontosan akkor jó, ha a két végpontot nem tartalmazza veszélyes halmaz, és nem tartalmazza pontos partíciónak eleme.

p szimmetriája miatt, ha X, Y ⊆ V pozitív, keresztező, és m(Y − X) > 0 vagy m(X − Y) > 0, akkor p(X) + p(Y) ≤ p(X − Y) + p(Y − X) is teljesül (az egyik halmazt komplementálva a szupermodularitást kapjuk), és ugyanez r-re is igaz. Ha X pontos halmaz, akkor r(X −Y) ≤ r(X), r(X ∩Y) ≤ r(X) tetszőleges Y halmazra. Legyen most X pontos, m(X) = 1, és V_{1}, …, V_{l} egy pontos partíció, ahol V_{l} az az elem, amire m(X ∩ V_{l}) = 1.

3.21. Állítás. {V_{1} − X, …, V_{l−1} − X, V_{l} ∪ X} pontos partíció.

Bizonyítás. Egyik halmaz sem üres, így a partíció elemszáma stimmel. Legyen U′ partícióelemek egyesítése, U′ ≠ V. Ha X ⊆ U′, akkor U′ = U ∪X, ahol U az eredeti partícióelemek egy részének egyesítése, és V_{l} ⊆ U. r(U′) = r(U ∪ X) ≥ r(U) + r(X) − r(U ∩ X) ≥ r(U) > 0 (ha U és X nem keresztezők, akkor ez triviálisan teljesül). Ha X ⊈ U′, akkor U′ = U −X, ahol U most is az eredeti partíció egy részének egyesítését jelöli, V_{l} ⊈ U. r(U′) = r(U − X) ≥ r(U) + r(X) − r(X − U) ≥ r(U) > 0 (ha U és X nem keresztező, itt is triviálisan teljesülnek az egyenlőtlenségek, hiszen tudjuk, hogy U − X, X − U ≠ ∅).

Az Állításban szereplő és az eredeti partíció ugyanazokat a leemeléseket akadályozza. Feltehető tehát, hogy minden olyan X pontos halmaz, amire m(X) = 1, egypontú; egy ilyen halmaz összehúzása után kapott feladatnak ugyanis pontosan akkor van megoldása, ha az eredetinek van; ez ugyanúgy látható be, mint a 3.9. Tételben.

Szeretnénk a leemelés t végpontját úgy kiválasztani, hogy ha a leemelés két végpontja nincs közös veszélyes halmazban, abból automatikusan következzen, hogy a két végpont nincs pontos partíció elemében sem. Legyen H azon pontos pontok halmaza, amikre m = 1. Definiáljunk H-n egy segédgráfot: az uv élt akkor vesszük be, ha r({u, v}) = 1. Legyen t ennek a gráfnak egy maximális fokszámú pontja.

3.22. Állítás. Ha V_{1}, …, V_{l} pontos partíció, és t ∈ V_{i}, akkor minden u ∈ V_{i}-re, amire m(u) > 0, van u-t és t-t tartalmazó veszélyes halmaz.

Bizonyítás.Feltehető, hogy m(V_{i}) > 2 (különben V_{i} is veszélyes lenne). Ekkor viszont a partíciónak három eleme is van, amire m = 1; legyen ez V_{1}, V_{2}, V_{3}. Tegyük fel először, hogy t-nek van olyan v szomszédja a segédgráfban, ami nincs benne V_{i}- ben; feltehető v ≠ V_{1}, V_{2}. Belátjuk, hogy ez lehetetlen, mert V_{i} helyett t-t és V_{i} − t-t a partícióba véve hibás partíciót kapnánk. A 3.20. Állítás szerint r(V_{1} ∪ V_{i}) = 1, tehát

1 + 1 = r(V_{1} ∪ V_{i}) + r({t, v}) ≤ r(v) + r(V_{1} ∪ V_{i} − t),

ami miatt r(V_{1} ∪ V_{i} − t) > 0. Legyen V_{j} a v-t tartalmazó partícióelem. Ekkor

1 + 1 = r(V_{1} ∪ V_{j}) + r({t, v}) ≤ r(v) + r(V_{1} ∪ V_{j} + t),

tehát r(V_{1} ∪ V_{j} + t) > 0. Másrészt a 3.20. Állítás szerint r(V_{1} ∪ V_{i} ∪ V_{j}) = 1, azaz

r(V_{1} ∪ V_{i}) + r(V_{1} ∪ V_{j} + t) ≤ r(V_{1} + t) + r(V_{1} ∪ V_{i} ∪ V_{j})

miatt r(V_{1} + t) > 0.

Ha V_{i} t segédgráfbeli szomszédain kívül nem tartalmaz u pontot, amire m(u) > 0, akkor teljesül az állítás. Tegyük fel, hogy nem így van. Jelölje l_{1} a V_{1}, … V_{l} halmazok közül azok számát, amikre m = 1. Ezek a halmazok H-beli pontok, méghozzá egy H-beli klikket alkotnak, így t kiválasztási módja és a feltevésünk alapján m(V_{i}) > l_{1}. Ez azonban ellentmond l − 1 = \frac{m(V)}{2}-nek.

Legyen X_{1}, …, X_{k} egy akadályozó rendszer. Feltehető, hogy k > 2, mert két halmaz a 3.9. Tételhez hasonlóan itt sem akadályozhatja az összes leemelést. Tudjuk, hogy olyan pozitív X, Y halmazokra, amik keresztezők és egyben erősen metszők, teljesül a következő két egyenlőtlenség:

b(X) + b(Y) ≥ b(X ∩ Y) + b(X ∪ Y),  (3.10)
b(X) + b(Y) ≥ b(X − Y) + b(Y − X) + 2m(X ∩ Y).  (3.11)

Mivel az akadályozó rendszerben maximális veszélyes halmazok vannak, a (3.10) egyenlőtlenség miatt X_{i} ∩ X_{j} pontos, (3.11) miatt pedig m(X_{i} ∩ X_{j}) = 1, tehát X_{i} ∩ X_{j} = t. Először azt az esetet vizsgáljuk, amikor W := ∪_{i=1}^{k}X_{i} ≠ V. A (3.10) egyenlőtlenséget k − 1-szer alkalmazva, a j-edik lépésben ∪_{i=1}^{j}X_{i}-re és X_{j+1}-re, azt kapjuk, hogy b(W) ≤ k. Így

m(W) − b(W) ≥ (k + 1) − k = 1,

tehát m(V − W) ≥ 1, van jó leemelés.

Tegyük fel most, hogy W = V. Feltehető, hogy m(X_{k}) ≤ m(X_{i}) (i = 1, …, k − 1). Legyen U := ∪_{i=1}^{k−1}X_{i}. Az előzőekhez hasonlóan egymás után alkalmazva a (3.10) egyenlőtlenséget, de most X_{k}-t nem hozzávéve, azt kapjuk, hogy b(U) ≤ k − 1. W = V -ből m(U) − b(U) ≤ m(X_{k} − t), azaz

m(U) ≤ m(X_{k} − t) + k − 1.

X_{k} választása szerint ez csak akkor lehet, ha m(X_{i} − t) = 1 (i = 1, …, k), tehát k + 1 = m(V). Ez pedig lehetetlen, hiszen {t, X_{1} − t, …, X_{k} − t} hibás partíció lenne.

A Tételből következik, hogy s-ről az összes élt le lehet emelni, hiszen a feltételek a leemelések során nem romlanak el. Térjünk át az előző részben definiált, V alaphalmaz, m fokszámfüggvény és p halmazfüggvény által megadott fedési feladatra. A jelölések ugyanazok, mint ott.

3.23. Tétel. Tegyük fel, hogy m(V) páros, m(X) ≥ p(X), nincs p-re nézve hibás partíció, és bármely két pozitív, keresztező X, Y halmazra, amelyre m(X ∩ Y) > 0, p(X) + p(Y) ≤ p(X ∩ Y) + p(X ∪ Y). Ekkor van (3.6)-ot és (3.7)-et teljesítő G gráf.

Bizonyítás. Vegyünk fel egy új s pontot, legyen X ⊆ V -re p(X + s) := p(X), és a G′ gráf élei legyenek sv m(v) multiplicitással minden v ∈ V -re. A 3.18. Tétel feltételei teljesülnek G′-re, hiszen p = r miatt nincs hibás partíció. Az 3.18. Tételt m(V)/2-ször alkalmazva s-ről az összes élt leemelhetjük; a kapott G gráf fedni fogja a p függvényt.

Vezessük be itt is a következő halmazfüggvényt:

p′(X) := max_{Y:m(XΔY)=0} p(Y).

Pontosan akkor van p-t fedő gráf, ha van p′-t fedő.

3.24. Tétel. Tegyük fel, hogy m(V) páros, m(X) ≥ p(X), nincs p′-re nézve hibás partíció, és bármely két lényeges, erősen keresztező X, Y halmazra p(X) + p(Y) ≤ p′(X ∩ Y) + p′(X ∪ Y). Ekkor van (3.6)-ot és (3.7)-et teljesítő G gráf.

Bizonyítás. Legyen V′ := {v ∈ V : m(v) > 0}. Erre a halmazra megszorítva p′-re teljesülnek a 3.23. Tétel feltételei, hiszen ha V′-n két halmaz keresztező, akkor a majoráló halmazaik V -n erősen keresztezőek, így azokra mint lényeges halmazokra alkalmazható p′-vel szupermoduláris egyenlőtlenség, ebből pedig következik az eredeti V′-beli halmazokra a szupermodularitás; V′-n nem lehet p′ szerint hibás partíció, hiszen az átalakítható lenne V p′ szerint hibás partíciójává. V′-n tehát van fedő gráf, és ez V -re is jó.

4 Vegyes gráfok

Jørgen Bang-Jensen, Frank András és Bill Jackson [1] általánosították Mader irányított és irányítatlan leemelési tételét vegyes gráfokra, és ennek segítségével kezelni tudtak bizonyos vegyes gráfokra vonatkozó élösszefüggőség-növelési problémákat. Megmutatjuk, hogy ezek a leemelési tételek a mi eddig bizonyított eredményeinkből is következnek. Legyen M(V + s, A ∪ E) egy vegyes gráf, ahol A az irányított, E az irányítatlan élek halmaza. Vezessük be a következő jelöléseket:

λ(x, y) az élidegen vegyes utak maximális száma x-ből y-ba,
ρ(x) := ρ_{A}(x),
δ(x) := δ_{A}(x),
d(x) := d_{E}(x),
T := {x ∈ V : ρ(x) ≠ δ(x)},
k := min_{x,y∈T} λ(x, y),
r(x, y) := min{k, λ(x, y)} (x, y ∈ V).

A Menger-tétel vegyes gráfokra vonatkozó változata szerint

λ(x, y) = min\{ρ(X) + d(X) : X y\overline{x} halmaz\}.

4.1. Állítás. r(x, y) = r(y, x).

Bizonyítás. Tegyük fel, hogy r(x, y) < r(y, x). λ(x, y) < λ(y, x) ≤ k, tehát van olyan X y\overline{x} halmaz, amire ρ(X) + d(X) = λ(x, y) < k, így vagy X, vagy V − X diszjunkt T -től. Ebből λ(x, y) = ρ(X) + d(X) = δ(X) + d(X) ≥ λ(y, x), ellentmondás.

4.2. Tétel. Tegyük fel, hogy s-sel csak irányított élek szomszédosak, és ρ(s) = δ(s). Ekkor minden st élhez van olyan us él, hogy az us, st leemeléssel kapott M′ gráfra λ_{M′}(x, y) ≥ r(x, y) minden x, y ∈ V pontra.

Bizonyítás. Vezessük be az

R(X) := max{r(x, y) : x ∉ X, y ∈ X},
p(X) := R(X) − d(X)

jelöléseket. R és p szimmetrikus, és minden X ⊆ V -re R(X) = R(X + s), p(X) = p(X + s). Ahhoz, hogy alkalmazhassuk a 2.5. Tételt, elég belátnunk, hogy p kváziszupermoduláris a keresztező halmazokon. Mivel p(X) = p(X + s), és ρ(s) = δ(s), ezt elég az X, Y ⊆ V halmazokra belátni. d-re teljesülnek a

d(X) + d(Y) ≥ d(X ∩ Y) + d(X ∪ Y),

d(X) + d(Y) ≥ d(X − Y) + d(Y − X),
d(X) + d(Y) ≥ d(\overline{X − Y}) + d(\overline{Y − X})

egyenlőtlenségek. Ha T ∩ X ∩ Y ≠ ∅, T ∩ \overline{X ∪ Y} ≠ ∅, akkor R(X) = R(Y) = R(X ∩ Y) = R(X ∪ Y) = k, így p kielégíti a kvázi-szupermodularitás első egyenlőtlenségét.

Tegyük fel most, hogy az első egyenlőtlenség nem teljesül, azaz R(X) + R(Y) > R(X ∩ Y) + R(X ∪ Y); ekkor könnyű ellenőrizni, hogy

R(X) + R(Y) ≤ R(X − Y) + R(Y − X).

Ha T ∩ X ∩ Y = ∅, akkor ρ(X ∩ Y) = δ(X ∩ Y) miatt

p(X) + p(Y) ≤ p(X − Y) + p(Y − X) + ρ(X ∩ Y) − δ(X ∩ Y).

Ha T ∩ \overline{X ∪ Y} = ∅, akkor ρ(\overline{X ∪ Y}) = δ(\overline{X ∪ Y}) miatt

p(X) + p(Y) ≤ p(X − Y) + p(Y − X) + δ(\overline{X ∪ Y}) − ρ(\overline{X ∪ Y})
= p(\overline{X − Y}) + p(\overline{Y − X}) + δ(\overline{X ∪ Y}) − ρ(\overline{X ∪ Y}),

tehát p kvázi-szupermoduláris.

A vegyes gráf egy élét irányítatlan értelemben elvágónak nevezzük, ha a kihagyásával keletkező gráf irányítatlan értelemben nem összefüggő.

4.3. Tétel. Tegyük fel, hogy k ≥ 2, s-sel csak irányítatlan élek szomszédosak, d(s) páros, és nincs s-sel szomszédos irányítatlan értelemben elvágó él. Ekkor minden st élhez van olyan us él, hogy az us, st leemeléssel kapott M′ gráfra λ_{M′}(x, y) ≥ r(x, y) minden x, y ∈ V pontra.

Bizonyítás. Legyen most is

R(X) := max{r(x, y) : x ∉ X, y ∈ X}.

p-t úgy szeretnénk választani, hogy szimmetrikus legyen; definiáljuk ezért a

p(X) := max{R(X) − ρ(X), R(X) − δ(X)}

képlettel. d(X) = d(V + s − X) miatt d(X) ≥ p(X) minden X ⊆ V + s halmazra teljesül. Be fogjuk látni, hogy p kielégíti a 3.9. Tételben szereplő feltételeket. Ezt most is elég az X ⊆ V halmazokra bizonyítani.

4.4. Lemma. X, Y ⊆ V -re vagy p(X) + p(Y) ≤ p(X ∩ Y) + p(X ∪ Y), vagy p(X) + p(Y) ≤ p(X − Y) + p(Y − X) teljesül.

Bizonyítás. X és Y helyett esetleg a komplementerüket véve feltehető, hogy p(X) = R(X) − ρ(X), p(Y) = R(Y) − ρ(Y). Ha T ∩ X ∩ Y ≠ ∅ és T ∩ \overline{X ∪ Y} ≠ ∅, akkor

R(X) = R(Y) + R(X ∩ Y) = R(X ∪ Y) = k, és
ρ(X) + ρ(Y) ≥ ρ(X ∩ Y) + ρ(X ∪ Y),

tehát erre az esetre bizonyítottuk a lemmát.

Tegyük most fel, hogy R(X) + R(Y) > R(X ∩ Y) + R(X ∪ Y); ekkor

R(X) + R(Y) ≤ R(X − Y) + R(Y − X).

Ha T ∩ X ∩ Y = ∅, akkor ρ(X ∩ Y) = δ(X ∩ Y) miatt

ρ(X) + ρ(Y) ≥ ρ(X − Y) + ρ(Y − X).

Ha T ∩ \overline{X ∪ Y} = ∅, akkor ρ(\overline{X ∪ Y}) = δ(\overline{X ∪ Y}) miatt

ρ(X) + ρ(Y) ≥ δ(X − Y) + δ(Y − X),

ezzel a lemmát beláttuk.

4.5. Lemma. Ha X_{1}, X_{2}, X_{3} ⊆ V páronként keresztezők, bármely kettő metszete Z, és X_{1} − Z, X_{2} − Z, X_{3} − Z, Z mindegyikében van s-sel szomszédos pont, akkor vagy

p(X_{1}) + p(X_{2}) + p(X_{3}) ≤ p(X_{1} ∪ X_{2} ∪ X_{3}) + 2p(Z),

vagy

p(X_{1}) + p(X_{2}) + p(X_{3}) ≤ p(X_{1} − Z) + p(X_{2} − Z) + p(X_{3} − Z) + p(Z) − 2.

Bizonyítás. Ha W ⊆ V elválasztja s két szomszédját, u-t és t-t, akkor R(W) ≥ 2. Tegyük fel ugyanis, hogy λ(u, t) = 1; ekkor van olyan X t\overline{u} halmaz, amire ρ(X) = 0, d(X) = 1, és a kilépő él s-sel szomszédos. Vagy X, vagy V − X diszjunkt T -től, tehát δ(X) = 0, ami ellentmond annak, hogy az s-sel szomszédos élek nem elvágóak.

4.6. Állítás. Legyen U := X_{1} ∪ X_{2} ∪ X_{3}. A következő két egyenlőtlenség legalább egyike teljesül:

R(X_{1}) + R(X_{2}) + R(X_{3}) ≤ R(U) + 2R(Z),  (4.1)

R(X_{1}) + R(X_{2}) + R(X_{3}) ≤ R(X_{1} − Z) + R(X_{2} − Z) + R(X_{3} − Z) + R(Z) − 2. (4.2)

Ha (4.1) nem teljesül, akkor vagy Z, vagy V − U diszjunkt T -től. Ha (4.2) nem teljesül, akkor X_{1} − Z, X_{2} − Z, X_{3} − Z közül legalább 2 diszjunkt T -től.

Bizonyítás. Az eseteket végignézve ellenőrizhető, felhasználva, hogy R(X_{1}−Z), R(X_{2} − Z), R(X_{3} − Z), R(Z) ≥ 2.

A lemma bizonyításához négy esetet vizsgálunk aszerint, hogy X_{1}, X_{2}, X_{3} közül hánynál adja δ a p definíciójában a maximumot.

1. Egyiknél sem δ adja a maximumot: ρ(X_{1}) + ρ(X_{2}) + ρ(X_{3}) ≥ ρ(U) + 2ρ(Z), tehát azt az esetet beláttuk, amikor a (4.1) egyenlőtlenség teljesül az állításban. Ha nem ez a helyzet, akkor T ∩ Z = ∅ esetén

ρ(X_{1}) + ρ(X_{2}) + ρ(X_{3}) ≥ ρ(X_{1} − Z) + ρ(X_{2} − Z) + ρ(X_{3} − Z) + ρ(Z),

T ∩ (V − U) = ∅ esetén pedig

ρ(X_{1}) + ρ(X_{2}) + ρ(X_{3}) ≥ δ(X_{1} − Z) + δ(X_{2} − Z) + δ(X_{3} − Z) + ρ(Z);

p-re tehát igaz a megfelelő egyenlőtlenség.

2. Egyetlen halmaznál (X_{1}) adja δ a maximumot: δ(X_{1}) + ρ(X_{2}) + ρ(X_{3}) ≥ δ(X_{1} − Z) + ρ(X_{2} − Z) + ρ(X_{3} − Z) + ρ(Z), tehát azt az esetet beláttuk, amikor R-re a (4.2) egyenlőtlenség teljesül. Ha nem ez a helyzet, akkor T ∩ (X_{1} − Z) = ∅ esetén

δ(X_{1}) + ρ(X_{2}) + ρ(X_{3}) ≥ ρ(U) + ρ(Z) + δ(Z),

T ∩ ((X_{2} − Z) ∪ (X_{3} − Z)) = ∅ esetén pedig

δ(X_{1}) + ρ(X_{2}) + ρ(X_{3}) ≥ δ(U) + 2ρ(Z).

3. Két halmaznál (X_{1}, X_{2}) adja δ a maximumot: δ(X_{1}) + δ(X_{2}) + ρ(X_{3}) ≥ δ(X_{1} − Z) + δ(X_{2} − Z) + ρ(X_{3} − Z) + δ(Z), azt az esetet beláttuk, amikor a (4.2) egyenlőtlenség teljesül. Ha nem ez a helyzet, akkor T ∩ (X_{3} − Z) = ∅ esetén

δ(X_{1}) + δ(X_{2}) + ρ(X_{3}) ≥ δ(U) + ρ(Z) + δ(Z),

T ∩ ((X_{1} − Z) ∪ (X_{2} − Z)) = ∅ esetén pedig

δ(X_{1}) + δ(X_{2}) + ρ(X_{3}) ≥ ρ(U) + 2δ(Z).

4. Mindháromnál δ adja a maximumot: δ(X_{1}) + δ(X_{2}) + δ(X_{3}) ≥ δ(U) + 2δ(Z), tehát azt az esetet elintéztük, amikor a (4.1) egyenlőtlenség teljesül. Ha nem ez a helyzet, akkor T ∩ Z = ∅ esetén

δ(X_{1}) + δ(X_{2}) + δ(X_{3}) ≥ δ(X_{1} − Z) + δ(X_{2} − Z) + δ(X_{3} − Z) + δ(Z),

4 Vegyes gráfok 39 T ∩ (V − U) = ∅ esetén pedig

δ(X_{1}) + δ(X_{2}) + δ(X_{3}) ≥ ρ(X_{1} − Z) + ρ(X_{2} − Z) + ρ(X_{3} − Z) + δ(Z).

A két Lemma alapján alkalmazható a 3.9. Tétel, így van jó leemelés.

5 Fenyves-pakolás

Az eddigi alkalmazásoknál úgy írtuk elő a feltételeket, hogy a leemelési műveletet mindig végre lehessen hajtani valamelyik élpáron. Ebben a fejezetben egy olyan feladatot tárgyalunk, ahol a leemelés más eszközökkel együtt kínál hatékony módszert a megoldásra.

Legyen adott egy D = (V, A) digráf, H_{1} ⊆ V, …, H_{k} ⊆ V részhalmazok, és egy r : V → Z_{+} igényfüggvény. Vezessük be a következő jelöléseket:

r(X) := max_{v∈X} r(v),
f(X) := |{j : H_{j} ∩ X ≠ ∅}|,
g(X) := |{j : H_{j} ⊆ X}|.

Fenyvesnek nevezünk egy irányított erdőt, ha minden pontjának befoka legfeljebb 1. A fenyves 0 befokú pontjainak halmaza a gyökérhalmaz. Célunk olyan élidegen F_{1}, …, F_{k} fenyveseket találni D-ben, amikre F_{i} gyökérhalmaza H_{i} (ekkor F_{i}-t H_{i}- fenyvesnek nevezzük), és minden v ∈ V pont legalább r(v) darab fenyvesben van benne. Ennek szükséges feltétele, hogy minden X ⊆ V halmazra r(X) ≤ ρ(X) + f(X) teljesüljön. Ahhoz azonban, hogy ez elégséges is legyen, megszorításokat kell tenni az igényfüggvényre: az alábbi digráfban például nincs két éldiszjunkt, a fekete pontokat tartalmazó z gyökerű fenyves.

5. Ábra : Nincs két megfelelő fenyves

Edmonds [5] az r ≡ k igényfüggvényre megmutatta, hogy a fenti vágásfeltétel elégséges. A H_{1} = H_{2} = ⋯ = H_{k} = {z} esetre Bang-Jensen, Frank és Jackson [1], majd Gabow [11] általánosabb igényekre is bebizonyította ezt. Mi mindezeknek az eredményeknek egy közös általánosítását fogjuk belátni.

5.1 Egy fenyves-pakolási tétel

Egy X ⊆ V halmazt pontosnak nevezünk, ha r(X) = ρ(X) + f(X). Az X halmaz korrekt, ha ρ(X) + g(X) ≥ δ(X). A v pont az X halmaz fő pontja, ha v ∈ X és r(v) = r(X). X és Y centrálisan metszők, ha X ∩ Y -ban X-nek vagy Y -nak van fő pontja. X és Y polárisan metszők, ha X − Y -ban van X-nek, Y − X-ben pedig van Y -nak fő pontja.

5.1. Tétel. Tegyük fel, hogy ∀X ⊆ V r(X) ≤ ρ(X) + f(X), és a következő feltétel teljesül: Ha r(v) < r(V) és v nem korrekt, akkor van v-t tartalmazó korrekt és pontos X halmaz, aminek v fő pontja. Ekkor van F_{1}, …, F_{k} élidegen fenyves úgy, hogy F_{i} H_{i}-fenyves, és minden v pont legalább r(v) darab fenyvesben van benne.

Bizonyítás. Feltehető, hogy a 0 igényű pontok korrekt pontok (különben volna a gráfban 0 igényű pontokból álló komponens, s ezt elhagyhatnánk). Szükségünk lesz néhány állításra a pontos és a korrekt halmazokkal kapcsolatban:

5.2. Állítás. X, Y ⊆ V -re az alábbiak igazak:

1. X, Y pontosak, centrálisan metszők ⇒ X ∪ Y és X ∩ Y pontos, d(X, Y) = 0; ha H_{i}-nek van közös pontja X-szel és Y -nal, akkor van közös pontja X ∩Y -nal is.

2. X, Y pontosak, polárisan metszők, X ∩ Y korrekt ⇒ X − Y és Y − X pontos, \overline{d}(X, Y) = 0, és ha H_{i}-nek van közös pontja X ∩Y -nal, akkor van közös pontja X − Y -nal és Y − X-szel is.

3. X, Y korrekt ⇒ X ∪ Y vagy X ∩ Y korrekt.

4. X, Y pontosak, polárisan metszők, X korrekt ⇒ X − Y korrekt.

Bizonyítás. A ρ és δ függvények tulajdonságait használva ezek könnyen ellenőrizhetőek.

Fel szeretnénk építeni pontos korrekt halmazoknak egy olyan L lamináris rendszerét, ami rendelkezik a következő tulajdonságokkal:

• Minden nem korrekt v pontra, amire r(v) < r(V), szerepel L-ben pontos korrekt halmaz, amiben v fő pont.

• L minimális abban az értelemben, hogy minden nem korrekt pontra csak 1 megfelelő halmazt tartalmaz.

L megkonstruálásához a nem maximális igényű, nem korrekt pontokat valahogy sorba rendezzük igényük szerint növekvő sorrendben: v_{1}, …, v_{l}; e szerint a sorrend szerint teszünk be L-be megfelelő halmazokat. Tegyük fel, hogy már van egy L_{i} lamináris rendszer, ami v_{1}, …, v_{i}-re tartalmaz pontos korrekt halmazokat, és minimális a fenti értelemben. Ha v_{i+1}-et fedi L_{i}, továbbléphetünk. Ha nem: a tétel feltétele értelmében van X_{i+1} pontos korrekt halmaz, amiben v_{i+1} fő pont. Az L_{i}- beli halmazokon a rögzített sorrendben végigmenve úgy módosítjuk X_{i+1}-et, illetve L_{i}-t, hogy együtt v_{1}, …, v_{i+1}-re megfelelő lamináris rendszert alkossanak. Adott lépésben: legyen X az a halmaz, amit X_{i+1} módosításával eddig kaptunk, Y pedig az L_{i}-beli soron következő halmaz.

1. Ha Y -nak van fő pontja X ∩ Y -ban, és X ∪ Y korrekt: X ∪ Y jó.

2. Ha Y -nak X ∩ Y -ban és azon kívül is van fő pontja, és X ∩ Y korrekt: X − Y jó.

3. Ha Y -ban fő pont csak X ∩ Y -ban van, és X ∩ Y korrekt: X ∩ Y jó Y helyett (laminaritás megmarad, mert L_{i} minimalitása miatt amik elromolhatnának, azok már sorrakerültek, tehát X-szel lamináris viszonyban vannak).

4. Ha X ∩Y -ban sem X-nek, sem Y -nak nincs fő pontja: X ∩Y korrekt halmazok diszjunkt uniója, tehát korrekt; ezért X-Y korrekt és pontos, tehát jó.

A rendszert minimálissá tehetjük, ha minden lépés után elhagyjuk a fölösleges halmazokat. Adjuk hozzá L-hez azokat a nem maximális igényű korrekt pontokat, amik egy L-beli halmazban sem fő pontok; legyen ez a lamináris rendszer L′.

A tételre indirekt bizonyítást adunk, amiből azonban polinomiális algoritmus készíthető a fenyvesek megtaláłására. Induljunk ki egy olyan ellenpéldából, amiben a pontok száma minimális, ezen belül az összes pontra az igények összege minimális, és ezen belül az élszám minimális. Készítsük el a fenti L halmazrendszert, továbbá legyen F egy maximális olyan lamináris rendszer, ami pontos halmazokból áll, és L elemeit tartalmazza.

Tekintsük az alábbi három műveletet:

1. \underline{Leemelés} egy 0-igényű pontról.

2. \underline{Éltörlés:} törlünk egy st élt, ahol st nem lép be L′-beli halmazba.

3. \underline{Halmazbővítés:} Adott H_{i} halmazra és st élre, ahol s ∈ H_{i}, t ∉ H_{i}, és st nem lép L′-beli halmazba: töröljük az st élt, és a t pontot hozzávesszük H_{i}-hez.

Egy X pontos halmaz akadályoz egy műveletet, ha a végrehajtás után r(X) > ρ(X) + f(X).

5.3. Állítás. Minden művelethez van egy akadályozó pontos halmaz.

Bizonyítás. Ha nincs akadályozó halmaz, akkor a művelet elvégzése után kapott kisebb élszámú gráfra teljesülnek a tétel feltételei, tehát van jó F′_{1}, …, F′_{k} fenyves. Ezeket viszont át tudjuk úgy alakítani, hogy az eredeti feladatra is jók legyenek: éltörlés esetén eleve jók; H_{i} bővítésénél az st élt hozzáadjuk F′_{i}-höz. us, st élek leemelése esetén: ha ut egyik F′_{i}-ben sincs benne, akkor us, st-t szabad élnek hagyjuk. Ha ut ∈ F′_{i}: st-t F′_{i}-höz hozzávesszük; ha van vs ∈ F′_{i}, ami ut-t elvágja az F′_{i}-beli gyökerétől, vagy s ∈ H_{i}, akkor us szabad él lesz, ellenkező esetben us-t is hozzávesszük F′_{i}-höz, és az esetleges vs ∈ F′_{i} -t szabad éllé tesszük.

5.4. Állítás. Minden művelethez van F-ben egy akadályozó pontos halmaz.

Bizonyítás. Tegyük fel, hogy X_{1} akadályoz egy műveletet, amit F-beli nem; ekkor F-et bővíteni lehet a következőképpen: Az F-beli halmazokat jelöljük Y_{1}, …, Y_{l}-lel, ahol L = Y_{1}, …, Y_{l_{1}}, és az L-beli halmazok igény szerint növekvő sorrendben vannak. A j. lépésben létrehozunk egy X_{j+1} halmazt, ami akadályozza a műveletet, és Y_{1}, …, Y_{j}-vel lamináris viszonyban van:

1. Ha X_{j} és Y_{j} centrálisan metszők: tegyük fel, hogy sem X_{j} ∩ Y_{j}, sem X_{j} ∪ Y_{j} nem felel meg.

(a) Leemelést (us, st) akadályoz: ha X_{j} s\overline{\{u, t\}} halmaz, akkor Y_{j} t\overline{s} vagy u\overline{s} halmaz, de ekkor, mivel van us és st él, d(X_{j}, Y_{j}) > 0, ellentmondás. Ha X_{j} \{u, t\}\overline{s} halmaz, hasonlóan Y_{j} csak s\overline{t} vagy s\overline{u} lehetne, de d(X_{j}, Y_{j}) > 0 miatt ez lehetetlen.

(b) Halmazbővítést (H_{i}), vagy éltörlést akadályoz: X_{j} t\overline{s} pontos halmaz, halmazbővítésnél X_{j}∩H_{i} ≠ ∅. Ha Y_{j} s\overline{t} halmaz: az st él miatt d(X_{j}, Y_{j}) > 0, ellentmondás. Ha s ∈ Y_{j}, és X_{j} ∩ Y_{j} ∩ H_{i} = ∅: f(X_{j}) + f(Y_{j}) > f(X_{j} ∩ Y_{j}) + f(X_{j} ∪ Y_{j}), ellentmondás.

2. Ha X_{j} és Y_{j} polárisan metszők, de centrálisan nem: tegyük fel, hogy sem X_{j} − Y_{j}, sem Y_{j} − X_{j} nem felel meg (felhasználjuk, hogy a metszet korrekt halmazok diszjunkt uniója, tehát korrekt).

(a) Leemelést (us, st) akadályoz: ha X_{j} s\overline{\{u, t\}} halmaz, akkor Y_{j} s\overline{t} vagy s\overline{u} halmaz, de ekkor, mivel van us és st él, \overline{d}(X_{j}, Y_{j}) > 0, ellentmondás. Ha X_{j} \{u, t\}\overline{s} halmaz, akkor Y_{j} u\overline{s} vagy t\overline{s} halmaz lehet, azaz itt is \overline{d}(X_{j}, Y_{j}) > 0 lenne.

(b) Halmazbővítést (H_{i}) vagy éltörlést akadályoz: X_{j} t\overline{s} pontos halmaz, halmazbővítés esetén X_{j} ∩ H_{i} ≠ ∅. Ha t ∉ Y, és (X_{j} − Y_{j}) ∩ H_{i} = ∅, akkor f(X_{j}) + f(Y_{j}) > f(X_{j} − Y_{j}) + f(Y_{j} − X_{j}), ellentmondás. Ha t ∈ Y_{j}, akkor a poláris metszés miatt t nem maximális igényű sem X_{j}-ben, sem Y_{j}-ben, így van olyan Z ∈ L′ halmaz, amire t ∈ Z ⊂ X_{j} ∩ Y_{j}; ellentmondás, mert ilyenkor nem is próbálkozhatnánk halmazbővítéssel.

5.5. Állítás. Olyan st él, amire s 0-igényű, nem léphet ki F-beli halmazból, és mindenképpen belép egy L′-beli halmazba.

Bizonyítás. Ha st kilépne egy F-beli halmazból, akkor lenne egy legszűkebb F-beli s\overline{t} halmaz (X). X pontos és s korrekt, tehát r(X) = r(X − s) ≤ ρ(X − s) + f(X − s) csak akkor teljesülhet, ha van olyan us él, amire u ∈ X; us, st leemelhető lenne (hiszen F-beli nem akadályozhatja), ellentmondás. Ha st nem lépne be L′- beli halmazba: tekintsük a legnagyobb F-beli t\overline{s} halmazt (X); X pontossága miatt r(X) = r(X + s) ≤ ρ(X + s) + f(X + s) csak úgy teljesülhet, ha vagy van us él, amire u ∉ X, vagy van s ∈ H_{i} halmaz, amire H_{i} ∩X = ∅. Az első esetben leemelést, a másodikban halmazbővítést lehetne alkalmazni, ellentmondás.

5.6. Állítás. A minimális pozitív igényű pontok között van korrekt.

Bizonyítás. Itt használjuk ki, hogy az ellenpéldánk minimális pontszámú. Tegyük fel először, hogy minden pozitív igényű pontnak ugyanannyi az igénye. Mivel ekkor L üres, 0-igényű pontból a fentiek alapján nem lép él pozitív igényűbe, tehát nincs is 0-igényű pont, hiszen az elhagyható volna. Ekkor viszont szükségképpen van s pont, amire ρ(s) ≥ δ(s), tehát s korrekt.

Tegyük fel, hogy különböző pozitív igények is vannak. Legyen s minimális pozitív igényű nem korrekt pont; ekkor s fő pont valamely X ∈ L halmazban. Az 5.5. Állítás szerint X 0-igényű pontjaiból nem lép él X-en kívülre (kilépne egy F-beli halmazból), és nem lép él X pozitív igényű pontjába sem (nem lépne be L′-belibe). Valójában tehát X-ben nincs is 0-igényű pont, hiszen ezek elhagyhatók lennének.

Most a feladatot két részre bonthatjuk: X összehúzásával a pontok számát csökkentjük, és mivel az összehúzott x pont korrekt, a feltételek sem romlanak el, így van jó F′_{1}, …, F′_{k} fenyves; x pontossága miatt minden x-be lépő élen belép fenyves. Másrészt tekinthetjük külön az X-re megszorított feladatot úgy, hogy az X-ből kilépő éleket elhagyjuk, és minden X-be lépő él helyett az X-beli végpontjára egy új egypontú H_{i} halmazt teszünk. Mivel a tétel feltételei itt is teljesülnek, van r(X) darab fenyves X-en a megfelelő gyökerekkel, hogy mindegyik eléri X minden pontját. X pontossága miatt ezek megfeleltethetők az összehúzással kapott feladat megoldásában x-et elérő fenyveseknek úgy, hogy az eredeti feladatra jó fenyveseket kapjunk, ami ellentmond az indirekt feltevésnek.

Legyen s egy minimális pozitív igényű korrekt pont, és csökkentsük le s igényét 0-ra. Mivel az ellenpéldánkban az igények összege minimális volt, vannak olyan F′_{1}, …, F′_{k} fenyvesek, amik a csökkentett igényeket kielégítik. Megmutatjuk, hogy ezek a fenyvesek megváltoztathatók úgy, hogy az eredeti igényeknek is megfeleljenek.

Az s-be lépő élek közül kiválasztunk r(s)−f(s) darabot úgy, hogy a már fenyveshez tartozó élek köztük legyenek (s-be lépett ennyi él; ha a fenyveshez tartozó élek száma ennél nem kevesebb, kész vagyunk). Azt mondjuk, hogy egy s-be lépő él és egy s-et gyökérpontként nem tartalmazó fenyves kompatibilis, ha a fenyvesben vezet olyan út egy gyökérpontból az él kezdőpontjába, amin nincs rajta s.

Célunk a kiválasztott élek és az s-t gyökérként nem tartalmazó F_{i} fenyvesek összepárosítása oly módon, hogy a párok kompatibilisek legyenek (tehát az élen a hozzá párosított fenyvest be lehessen vezetni s-be), az élek fedve legyenek, és az s-t eleve elérő fenyvesek is fedve legyenek. Az utóbbi fenyveseket fedő párosítás létezik (azokkal az élekkel, amin belépnek s-be), így a Mendelsohn-Dulmage tétel ételmében elég az éleket fedő párosítást találni; ennek létezéséhez a Hall tétel szerint elég azt belátni, hogy az élek tetszőleges részhalmazához van kellő számú valamelyikkel kompatibilis fenyves.

Először olyan élek halmazára ellenőrizzük a Hall-feltételt, amiknek a tőpontja 0igényű. Ha egy él 0-igényű tőpontjába nem lép él, a korrektség miatt a tőpont maga egy H_{i} halmaz, így ezek az élek nem befolyásolják a Hall-feltételt. Az olyan us éleket, amikre r(u) = 0 és ρ(u) ≠ 0, osztályokba soroljuk aszerint, hogy melyik a legnagyobb F-beli s\overline{u} halmaz (mivel az us élen nem lehetett műveletet végezni, ilyen halmaz van, és tartalmazza az összes u-ba lépő él tőpontját). Minden ilyen us élhez csak olyan kompatibilis F_{i} fenyveseket veszünk figyelembe, amiknek H_{i} gyökérhalmaza tartalmazza u-t és diszjunkt az él osztályához tartozó F-beli halmaztól; így különböző osztályhoz tartozó élekhez eleve különböző fenyveseket választunk, tehát a Hall feltételt elég külön-külön az osztályokra ellenőrizni. Adott osztályban: az osztályhoz tartozó F-beli X halmazhoz az élek tőpontjainak egy tetszőleges részét hozzávéve látható (X pontosságát használva), hogy az éleknek ehhez a részéhez kellő számú megfelelő gyökérhalmazú kompatibilis fenyves rendelkezésre áll.

Tekintsük most a kiválasztott élek egy olyan j elemszámú B részhalmazát, amiben van pozitív igényű tőpontú él. Mivel r(s) minimális pozitív igény volt, a Hall-feltétel teljesüléséhez elég belátni, hogy azon s-et gyökérpontként nem tartalmazó fenyvesek száma, amelyek valamelyik B-beli él tőpontját elérik, de egyik B-beli éllel sem kompatibilisek, ≤ r(s) − f(s) − j. Ez pedig teljesül, hiszen minden ilyen fenyves valamelyik nem B-beli kiválasztott élen lép be s-be.

Összességében tehát a Hall feltétel teljesül, így van az éleket fedő párosítás. Az F′_{1}, …, F′_{k} fenyveseket e párosítás szerint átalakítva az eredeti igényeket kielégítő fenyveseket kapunk, ami ellentmond az indirekt feltevésnek.

Megjegyzés. Bár a tétel kimondásából ez nem világos, valójában adott gráfra és gyökérhalmazokra van egy egyértelmű maximális igényfüggvény, amire a tétel érvényes. Ezt a következő lemma segítségével látjuk be:

5.7. Lemma. Tegyük fel, hogy teljesülnek az 5.1. Tétel feltételei. Legyen v egy nem maximális igényű, nem korrekt pont. Ekkor van legnagyobb olyan pontos M_{v} halmaz, aminek v fő pontja, és ez a halmaz korrekt.

Bizonyítás. Két v-t fő pontként tartalmazó pontos halmaz uniója is pontos a centrális metszés miatt, az 5.1. Tétel feltételei szerint pedig legalább 1 ilyen halmaz van, tehát van legnagyobb ilyen M_{v} halmaz. Az L lamináris rendszerben M_{v} bármelyik pontjához tartozó halmaz részhalmaza M_{v}-nek, hiszen ellenkező esetben a centrális metszés miatt uniójuk is pontos volna. Így M_{v} korrekt halmazok diszjunkt uniója, tehát maga is korrekt.

5.8. Tétel. Adott D = (V, A), H_{1}, …, H_{k}. Legyen r′(v) := min_{v∈X}(ρ(X) + f(X)), M_{v} a legnagyobb olyan halmaz, amire a minimum felvétetik (ennek létezése ugyanúgy bizonyítható, mint a Lemmában), és T azon v pontok halmaza, amelyekre sem v, sem M_{v} nem korrekt. Legyen

k := min_{v∈T} r′(v),
r(v) := min{k, r′(v)}.

Ekkor van F_{1}, …, F_{k} élidegen fenyves úgy, hogy F_{i} H_{i}-fenyves, és tetszőleges v pont legalább r(v) darab fenyvesben van benne.

Bizonyítás. Teljesülnek az 5.1 Tétel feltételei.

Könnyen látható, hogy ha valamelyik v pontra r(v) nagyobb lenne a most megállapítottnál, akkor már sérülnének a feltételek. Ha ugyanis az új r(v) k-nál nem nagyobb, akkor r(v) > min_{v∈X}(ρ(X) + f(X)). Ha viszont k-nál nagyobb, akkor k definíciója alapján van olyan nem korrekt és immár nem maximális igényű u pont, amire M_{u} sem korrekt, tehát az 5.7 Lemma szerint a feltételek nem teljesülhetnek.

Megjegyzés. Általános gráfra és igényekre a fenyves-pakolási probléma NPteljes. Nézzünk ugyanis egy (D = (V, A); s_{1}, t_{1}, s_{2}, t_{2}, …, s_{k}, t_{k}) irányított élidegen út problémát. Legyen D′ a következő: vegyünk D-hez t′_{1}, t′_{2}, …, t′_{k} pontokat (ezek halmazát nevezzük T′-nek), és t_{1}t′_{1}, …, t_{k}t′_{k} éleket. Legyen a T′-beli pontok igénye k, a többié 0; H′_{i} := T′ − t′_{i} + s_{i}. Könnyen látható, hogy az így kapott fenyves-pakolási problémának pontosan akkor van megoldása, ha az eredeti élidegen út problémának volt.

5.2 Néhány szó az algoritmusról

A bizonyítás polinomiális algoritmust ad a fenyvesek megtalálására. Kiindulunk az eredeti gráfból, elkészítjük az L lamináris rendszert. Kezdetben legyen F := L. A bizonyításban leírt műveleteket két részre osztjuk: az élműveletek (leemelés, éltörlés, halmazbővítés) csökkentik az élek számát. A pontok számát, illetve az igények összegét csökkentő pontműveletek a következők (ezeket csak akkor használjuk, ha élművelet már nem végezhető):

• \underline{Összehúzás:} egy nem korrekt minimális pozitív igényű ponthoz tartozó L-beli halmazból töröljük a 0-igényű pontokat, és a halmazt a bizonyításban szereplő módon összehúzzuk. Ne felejtsük el, hogy ekkor rekurzívan egy másik gráfra is meg kell oldani a feladatot, de a pontszámok összege és az élszámok összege nem nő.

• \underline{Igénynullázás:} ha esetleg 0-igényű pontból már nem lép él pozitív igényűbe, töröljük a 0-igényű pontokat; ezután nullázzuk egy korrekt minimális pozitív igényű pont igényét.

Legyen az algoritmus első részének egy fázisa a következő: olyan élműveleteket próbálunk végrehajtani egymás után, amiket F nem akadályoz. Ha egy ilyen mégsem végrehajtható, F bővíthető a bizonyításban szereplő módon. Amikor eljutunk egy olyan gráfhoz, ahol élműveletet már nem lehet végrehajtani, a bizonyítás szerint valamelyik pontművelet végrehajtható. A pontművelet után L-re és F-re is végezzük el a ponttörléseket és összehúzásokat (ezzel nincs gond, mert L-beli halmazt húztunk össze), és hagyjuk ki L-ből és F-ből a már nem pontos halmazokat; legyen ez a fázis vége.

Mivel minden fázisban csökken a pontok száma vagy a pozitív igényű pontok száma, az algoritmusnak ez a része legfeljebb 2n fázis után eljut oda, hogy minden v pontra f(v) ≥ r(v). Az algoritmus második részében a fenyveseket kell felépítenünk; ehhez egyszerűen fordított sorrendben kell tekinteni az első részben végzett műveleteket, és minden egyes művelethez elvégezni a bizonyításban leírt átalakításokat.

Érdemes külön megvizsgálni azt az esetet, amikor nincsenek különböző pozitív igények.

5.9. Állítás. Ha minden pont igénye 0 vagy l valamilyen l pozitív egész számra, akkor az algoritmus első része 1 fázisból áll.

Bizonyítás. Esetünkben L üres. Legyen T := {v : r(v) = l}. A tétel bizonyítása alapján az 1. fázis során eljutunk oda, hogy 0-igényű pontból T -be nem lép él. Megmutatjuk, hogy innentől csak halmazbővítést használva az 1. fázis végén minden v ∈ T -re f(v) ≥ l (lényegében Lovásznak az Edmonds tételre adott bizonyítását alkalmazzuk).

Indirekt tegyük fel, hogy vannak pontok, amikre ez nem teljesül; legyen Z egy maximális olyan része T -nek, amire f(Z) < l. Mivel f(Z) + ρ(Z) ≥ l, van uv Z-be lépő él; Z maximalitása miatt ∃H_{i}: u ∈ H_{i}, H_{i} ∩ Z = ∅. Megmutatjuk, hogy H_{i} bővíthető. Legyen X egy minimális olyan pontos halmaz, ami metszi H_{i}-t és \overline{H_{i}}-t is; ha ilyen nincs, H_{i} bővíthető v-vel. X ⊆ T, hiszen pontos halmaz T -vel vett metszete is pontos, és f(X) = f(X ∩ T). X-en belül van olyan u′v′ él, amire u′ ∈ H_{i}, v′ ∉ H_{i}, hiszen ellenkező esetben f(X − H_{i}) + ρ(X − H_{i}) < l állna fenn. Ha H_{i} bővítését az u′v′ él mentén akadályozná egy Y pontos halmaz (azaz u′ ∉ Y, v′ ∈ Y, H_{i} ∩ Y ≠ ∅), akkor ρ szubmodularitása miatt X ∩Y is pontos lenne, és H_{i} ∩X ∩Y ≠ ∅ teljesülne. Ez azonban ellentmondana X minimalitásának, tehát H_{i} bővíthető u′v′ mentén.

5.3 Kapacitások

Adott egy D = (V, A) digráf, egy r : V → {0, l} igényfüggvény (l pozitív egész), T := {v : r(v) = l}, és H_{1}, …, H_{k} ⊆ V gyökérhalmazok. Most azonban minden H_{i} halmaznak van egy α(H_{i}) pozitív egész multiplicitása, az éleken pedig megadunk egy kapacitásfüggvényt: c : A → Z^{+}. Célunk olyan F_{11}, …, F_{1t_{1}}, …, F_{k1}, … F_{kt_{k}} fenyveseket, és hozzájuk α(F_{ij}) multiplicitásokat találni, amikre F_{ij} H_{i}-fenyves, és teljesülnek a következők:

∑_{j=1}^{t_{i}} α(F_{ij}) = α(H_{i}),
∑_{e∈F_{ij}} α(F_{ij}) ≤ c(e) minden e ∈ A élre,
∑_{v∈F_{ij}} α(F_{ij}) ≥ l minden v ∈ T -re.

Az f és g függvények, valamint a korrektség és a pontosság definíciója értelemszerűen kiterjeszthető a kapacitásos esetre. Csak olyan feladatokat vizsgálunk, amiknél minden 0-igényű pont korrekt, és minden X ⊆ V -re, amire X ∩ T ≠ ∅, f(X) + ρ_{c}(X) ≥ l teljesül. Ebben az esetben léteznek jó F_{ij} fenyvesek, hiszen a kapacitás helyett többszörös éleket véve az 5.1. Tétel alkalmazható. Az előző részben leírt algoritmust azonban úgy szeretnénk megváltoztatni, hogy erősen polinomiális legyen, és a különböző fenyvesek száma se legyen túl nagy. A H_{1} = H_{2} = ⋯ = H_{k} = {z} esetben Gabow és Manu [10], illetve Gabow [11] részletesen vizsgálták a kapacitásos feladatot; eredményeink részben az ő módszereiken alapulnak.

Az előzőekben láttuk, hogy élműveletek (leemelés, éltörlés, halmazbővítés) egymás utáni alkalmazásával eljutunk egy olyan gráfhoz, ahol f(v) ≥ l minden v ∈ T -re. Az élműveleteket úgy fogjuk módosítani, hogy kapacitásos gráfokra hatékonyabban működjenek. Technikai megjegyzések: párhuzamos élek között mindig egy fix sorrendet rögzítünk; egy élt megszüntetünk, ha a kapacitása nullázódik. c(uv)-vel jelöljük a kapacitások összegét az uv éleken.

• \underline{Leemelés:} s 0-igényű pont. Szeretnénk az us, st élekről annyi kapacitást áttenni egy új ut élre, amennyit csak lehet. Legyen q = min{f(X) + ρ_{c}(X) − r(X) : X \{u, t\}\overline{s} vagy s\overline{\{u, t\}} halmaz\}, ez a szám folyamkereséssel meghatározható. Ekkor a maximális leemelhető kapacitás min{c(us), c(st), q}. Ha q ≥ min{c(us), c(st)}, akkor teljes leemelésről beszélünk. Az us és az st élek kapacitását a megadott sorrendben csökkentjük.

• \underline{Éltörlés:} Legyen s tetszőleges, t ∈ T; q := min\{f(X) + ρ_{c}(X) − r(X) : X t\overline{s} halmaz\}. Az st élek összkapacitása min\{c(st), q\}-val csökkenthető. A csökkentést most is az st élek rögzített sorrendje szerint hajtjuk végre. Teljes az éltörlés, ha q ≥ c(st).

• \underline{Halmazbővítés:} s tetszőleges, t ∈ T, s ∈ H_{i}, t ∉ H_{i}; q := min\{f(X) + ρ_{c}(X) − r(X) : X t\overline{s} halmaz, H_{i} ∩ X ≠ ∅\}. A halmazbővítés legfeljebb min{c(st), α(H_{i}), q} kapacitással végezhető el. Ha ez szigorúan kisebb, mint α(H_{i}), nem a H_{i} halmazt bővítjük ki, hanem létrehozunk egy új H_{j} := H_{i} + t halmazt min{c(st), q} multiplicitással, és H_{i} multiplicitását valamint az st élek kapacitását (a megadott sorrendben) ennyivel csökkentjük. Teljes halmazbővítésről beszélünk, ha q ≥ min{c(st), α(H_{i})}.

Az algoritmus a kapacitás nélküli esettel analóg módon működik: kezdetben legyen F üres. Olyan műveleteket (leemelés éltörlés, halmazbővítés) próbálunk végrehajtani egymás után, amiket F nem akadályoz. Ha nem hajtható végre teljes művelet, a kapacitás nélküli bizonyítást alkalmazva F bővíthető. Amikor már több művelet nem hajtható végre, minden v ∈ T -re f(v) ≥ l teljesül, hiszen itt is használható az 5.9. Állítás. Az algoritmus második részében a műveleteken fordított sorrendben végigmenve a fenyveseket át kell alakítani; most azonban arra is figyelni szeretnénk, hogy minél kevesebb fenyves keletkezzen. A fenyvesek számát úgy tartjuk számon, hogy ha egy művelethez tartozó átalakításnál új fenyves keletkezik, akkor ezt a fenyvest ráterheljük a műveletben résztvevő egyik élre úgy, hogy egy élre csak egy fenyvest terhelünk. Ezt a következőképpen tehetjük meg:

• \underline{Leemelés:} A leemeléskor keletkezett ut élt használó fenyveseket kell sorban úgy átalakítani, hogy ut helyett a leemelés előtti us és st éleket használják. Az éleket a rögzített sorrendben tekintjük. Egy F_{ij} fenyvest a kapacitás nélküli esethez hasonlóan úgy szeretnénk átakakítani, hogy ut-t töröljük belőle, a soron következő st élt hozzáadjuk, és akkor vesszük be a soron következő us élt (az esetleg a fenyvesben levő vs élt törölve), ha enélkül a gyökérhalmaz megváltozna. Ezt azonban nem tudjuk megtenni, ha α(F_{ij}) nagyobb, mint az aktuális us illetve st él β szabad kapacitása. Ekkor az F_{ij} fenyvest kettéosztjuk egy β és egy α(F_{ij})−β multiplicitású fenyvesre; az előbbin el tudjuk végezni az átalakítást, az utóbbi bekerül az átalakítandó fenyvesek közé. Az új fenyvest ráterhejük arra az élre, aminek β volt a szabad kapacitása.

• \underline{Éltörlés:} Nem változtatjuk a fenyveseket.

• \underline{Halmazbővítés:}Az st-n végzett művelet egy H_{i} +t gyökérhalmazt hozott létre, szeretnénk az ehhez tartozó fenyveseket st élek rögzített sorrendben való hozzáadásával úgy átalakítani, hogy H_{i} legyen a gyökérhalmazuk. A soron következő F_{ij} fenyvest itt is akkor kell kettéosztani, ha α(F_{ij}) nagyobb, mint az aktuális st él β szabad kapacitása. A keletkező β multiplicitású fenyvesen el tudjuk végezni az átalakítást, az α(F_{ij}) − β multiplicitásút pedig betesszük az átalakítandó fenyvesek közé. Az új fenyvest ráterheljük a telítődött st élre.

Ha egy művelethez tartozó átalakításban ráterheltünk egy élre, akkor a művelet ezt az élt megszüntette, és utána mást is módosított. A megszűnés miatt egy élre csak egy fenyvest terhelhettünk, hiszen egy átalakításon belül az él a ráterheléskor telítődik.

Legyen egy művelet (leemelés, éltörlés, vagy halmazbővítés) növelési értéke a következő: (az élek számának változása a művelet során)+(a gyökérhalmazok számának változása a művelet során)+(a művelet során megszűnő élekre ráterhelt fenyvesek száma).

A növelési értékről a következőket állapíthatjuk meg:

1. Teljes művelet esetén a növelési érték ≤ 0 (leemelésnél 1 új él keletkezik, de nem lehet minden megszűnő él megterhelt; halmazbővítésnél, ha nő a gyökérhalmazok száma, akkor nem lehet minden megszűnő él megterhelt).

2. Nem teljes műveletnél bővítjük F-et. Azoknál a műveleteknél, ahol F egypontú halmazzal bővült, a növelési érték ≤ 0 (hiszen ez csak éltörlés vagy us, su leemelés lehet, átalakítást egyiknél sem kell végezni); a többi műveletre a növelési érték ≤ 1.

3. Ha s ∉ T, akkor vagy maradt az algoritmus első részének végére s-be lépő él vagy H_{i} = {s} halmaz, vagy az s-en végzett utolsó műveletre a növelési érték ≤ −1 (mivel s korrekt pont, ha az első lehetőség nem teljesül, akkor az utolsó művelet végén vagy két él szűnt meg egyszerre, vagy halmazbővítésnél egy él megszűnt úgy, hogy a gyökérhalmazok száma nem nőtt).

V -n egy olyan V -t nem tartalmazó lamináris rendszer elemszáma, aminek minden eleme tartalmaz T -beli pontot, legfeljebb |V | + |T | − 2. A rendszerben a nem egypontú halmazok száma legfeljebb |V | − 2. Ebből és a fenti három állításból következik, hogy ha a növelési értékeket összeadjuk az összes végrehajtott műveletre, és ebből levonjuk az algoritmus első részének végén megmaradt T -be nem lépő élek és T -től diszjunkt gyökérhalmazok számát, akkor legfeljebb |T |−2-t kapunk. A növelési érték definíciójából következik, hogy az algoritmus által adott fenyvesek száma nem lehet több, mint ha ehhez az összeghez hozzáadjuk az eredeti élek számát (m) és az eredeti gyökérhalmazok számát (k). Így a fenyvesek száma ≤ m + k + |T | − 2.

Az algoritmus futási idejét nem elemezzük részletesen. Mivel a nem teljes műveletek bővítik F-et, és legfeljebb 1-gyel növelik az élek számát, a teljesek pedig vagy csökkentik az élek számát, vagy bővítik valamelyik H_{i} halmazt, legfeljebb O(m) + O(kn) művelet lehetséges. Mind a művelet, mind a hozzá tartozó átalakítás végrehajtása erősen polinomiális.

6 Színezések

Színezésekkel kapcsolatos tételekre a fenyves-pakolások egy, a fejezet végén ismertetendő alkalmazásához van szükségünk; mivel azonban önmagukban is érdekes eredményekről van szó, részletesen foglalkozunk velük, bár nem kötődnek szorosan a leemelési művelethez.

Tekintsük a következő színezési feladatot: adott egy T alaphalmazon egy p : 2^{T} → Z_{+} halmazfüggvény. Szeretnénk T pontjait k színnel színezni úgy, hogy minden X ⊆ T halmazban legalább p(X) szín szerepeljen; ezt nevezünk jó színezésnek. A megoldhatóság szükséges feltétele, hogy minden X ⊆ T halmazra

p(X) ≤ min{|X|, k}  (6.1)

teljesüljön. Megmutatjuk, hogy ha p a pozitív metsző halmazokon ferdén szupermoduláris, akkor a feltétel elégséges is, sőt, ha p_{1} és p_{2} is ilyen, akkor közös jó színezés is van. Metsző szupermoduláris függvényekre ezt Alexander Schrijver [21] bizonyította be, Tardos Éva [23] pedig matroidelméleti bizonyítást adott Schrijver tételére. Mi egy kicsit más szemléletű poliéderes bizonyítást adunk, amihez a bázispoliéderek elméletének néhány eredményét fogjuk felhasználni.

6.1 Alapfogalmak

Legyen S az alaphalmaz, és b : 2^{S} → Z ∪ {∞} olyan halmazfüggvény, amire b(∅) = b(S) = 0. Tekintsük a következő poliédert:

B(b) := {x ∈ R^{S} : x(H) ≤ b(H) minden H ⊆ S-re, x(S) = 0}.

Az olyan poliédert, ami előáll így egy teljesen szubmoduláris b halmazfüggvényből, bázispoliédernek nevezzük (a pontos megnevezés 0-bázispoliéder lenne, de mivel csak olyan b halmazfüggvényekkel foglalkozunk, amikre b(S) = 0, a rövidebb kifejezést használjuk). A bázispoliéderek elméletéből az alábbi tételeket fogjuk használni (ezeket nem bizonyítjuk; az egész témakörről részletes ismertetés található Fujishige [9] könyvében):

6.1. Tétel. Minden bázispoliédernek van egész pontja (tehát van x ∈ Z^{S}, amire x ∈ B(b)).

6.2. Tétel. Minden B bázispoliéder egyértelműen meghatározza az őt definiáló teljesen szubmoduláris b függvényt: minden H ⊆ S-re b(H) = max_{x∈B} x(H).

6.3. Tétel. Ha B(b_{1}) és B(b_{2}) bázispoliéder, és B(b_{1}) ∩ B(b_{2}) ≠ ∅, akkor B(b_{1}) ∩ B(b_{2})-nek van egész pontja.

Szükségünk lesz néhány halmazrendszerekkel kapcsolatos fogalomra és jelölésre. Egy F halmazrendszerre és b halmazfüggvényre

b(F) := ∑_{X∈F} b(X). (Egy halmaznak több példánya is szerepelhet F-ben.)

Egy F_{1} és egy F_{2} halmazrendszer egyesítését F_{1} + F_{2}-vel jelöljük. Ha z ∈ S egy rögzített pont, akkor

F^{z} := {X : z ∉ X ∈ F} + {S − X : z ∈ X ∈ F} (megintcsak multiplicitásokkal).

Egy F rendszer az X ⊆ S halmaz kompozíciója, ha valamilyen k-ra S − X elemeit k-szor, X elemeit k + 1-szer fedi; X, Y ⊆ S esetén F (X, Y)-kompozíció, ha valamilyen k-ra S − (X ∪ Y) elemeit k-szor, XΔY elemeit k + 1-szer, X ∩ Y elemeit pedig k + 2-ször fedi.

Egy halmazrendszer keresztezésmentes, ha nincs két keresztező eleme. Ismert, hogy minden keresztezésmentes rendszer ábrázolható egy F irányított fa és egy φ : S → V (F) leképezés segítségével, ahol az élek felelnek meg F elemeinek. Egy X ⊆ S halmaz F keresztezésmentes kompozícióját fa-kompozíciónak nevezzük, ha φ az őt ábrázoló fa minden csúcsához rendel pontot, méghozzá bármely él kezdőpontjához csak S − X-belit, és bármely él végpontjához csak X-belit. Egy b : 2^{S} → Z ∪ {∞} halmazfüggvényre vezessük be a

b^{↓}(X) := min{b(F) : F az X fa-kompozíciója}

függvényt, amit b teljes alsó reszeltjének nevezünk.

6.2 Poliéderes eredmények

Ismert, hogy keresztező szubmoduláris b függvényre b^{↓} teljesen szubmoduláris. Most ezt kicsit általánosabb b-kre is belátjuk.

6.4. Tétel. Legyen S az alaphalmaz, z ∈ S egy kijelölt pont; b : 2^{S} → Z ∪ {∞} halmazfüggvény, ami S-nek minden partíciójára és ko-partíciójára nemnegatív. Tegyük fel, hogy bármely két keresztező X, Y halmazon vagy b(X)+b(Y) ≥ b(X ∩Y)+b(X ∪ Y), vagy van olyan legalább 3 elemű F (X, Y)-kompozíció, amire b(X) + b(Y) ≥ b(F), és F^{z} minden pontot legfeljebb annyiszor fed, mint {X, Y }^{z}. Ekkor b^{↓} teljesen szubmoduláris, és B(b) = B(b^{↓}) ≠ ∅.

Bizonyítás. B(b) = B(b^{↓}) mindenképpen teljesül. A szubmodularitás bizonyításához a következő lemmát használjuk:

6.5. Lemma. Rendelkezzen b a fenti tulajdonságokkal. Legyenek Z ⊆ W ⊆ S tetszőleges halmazok, és k ∈ Z_{+} rögzített. Tekintsük azokat az F (W, Z)-kompozíci-ókat, amiknek S nem eleme, és F^{z} minden pontot legfeljebb k-szor fed. Legyen F_{0} ezek közül olyan, amire b(F_{0}) minimális, ezen belül maximális elemszámú, és ezen belül ∑_{H∈F_{0}} |H|^{2} maximális. Ekkor F_{0} felbomlik W és Z fa-kompozíciójára, valamint S valahány partíciójára és ko-partíciójára.

Bizonyítás. F_{0} keresztezésmentes, hiszen ellenkező esetben egy keresztező X, Y pár helyett a tétel feltételei szerint vagy X∩Y, X∪Y -t, vagy egy legalább háromelemű X, Y -kompozíciót vehetnénk F_{0}-hoz. Az előbbi esetben az új rendszerben ∑_{H∈F} |H|^{2} nagyobb lenne, az utóbbi esetben pedig egy nagyobb elemszámú rendszert kapnánk. Ha F_{0} tartalmazza S-nek partícióját vagy ko-partícióját, hagyjuk ki ezeket belőle; a keletkező halmazrendszer legyen F_{1}. Ekkor F_{1} mint keresztezésmentes rendszer ábrázolható egy D = (V, A) irányított fával, amiben minden olyan v csúcsra, amihez nem tartozik S-beli pont, ρ(v) > 0 és δ(v) > 0 (különben tartalmazná S partícióját vagy ko-partícióját). D-ben minden irányított út legföljebb 2 hosszú, hiszen F_{1} minden pontot l-szer, l + 1-szer vagy l + 2-ször fed valamilyen l-re. D csúcsait három szintre oszthatjuk aszerint, hogy egy csúcs legföljebb milyen hosszú irányított út végpontja. Az élekhez tartozó F_{1}-beli halmazokra igazak a következők:

• Tekintsünk egy 1. szinten lévő v pontot. A v-ből kilépő élekhez tartozó halmazok együtt a v-hez tartozó pontok kivételével minden S-beli pontot 1-szer fednek.

• Tekintsünk egy 3. szinten lévő v pontot. A v-be lépő élekhez tartozó halmazok együtt a v-hez tartozó S-beli pontokat 1-gyel többször fedik, mint a többi pontot.

Ebből következik, hogy az 1. és 2. szint közti élekhez tartozó halmazok W fakompozícióját alkotják, a 2. és 3. szint közöttiekhez tartozók pedig Z fa-kompozíció-ját.

A tétel a Lemmából egyszerűen bizonyítható: legyen X, Y ⊆ S tetszőleges, F_{X} és F_{Y} pedig X-nek illetve Y -nak olyan fa-kompozíciója, amin a b^{↓} definíciójában szereplő minimum fölvétetik. Legyen Z := X ∩ Y, W := X ∪ Y, és alkalmazzuk a Lemmát egy olyan k-val, amire (F_{X} + F_{Y})^{z} minden pontot legfeljebb k-szor fed. A Lemmából adódik, hogy X ∩Y -nak és X ∪Y -nak van olyan fa-kompozíciója, ami mutatja, hogy b^{↓} X, Y -on szubmoduláris. B(b^{↓}) nem üres, hiszen S-nek nincs negatív fa-kompozíciója (azaz partíciója vagy ko-partíciója), tehát B(b^{↓}) bázispoliéder.

Legyen továbbra is S az alaphalmaz, b : 2^{S} → Z ∪ {∞} halmazfüggvény, b(∅) = b(S) = 0. Adott továbbá S-nek egy S_{1}, …, S_{k} partíciója, b(S_{i}) = 0 (i = 1, …, k); U_{i} := ∪_{j=1}^{i}S_{j}. Olyan feltételeket szeretnénk b-re megadni, hogy a B(b) poliédernek mindenképpen legyen egész pontja. Egy F halmazrendszerre és egy X halmazra vezessük be a következő jelölést (a halmazok multiplicitással értendők):

F ∩ X := {H ∩ X : H ∈ F, X ⊈ H}.

Egy X, Y ⊆ U_{i} halmazpár i-keresztező, ha X ∩ S_{i}, Y ∩ S_{i} keresztező S_{i}-n. U_{i}-re megszorított feladat alatt azt értjük, hogy a b-nek csak U_{i} részhalmazain értelmezett megszorítása által meghatározott B(b|_{U_{i}}) poliéder elemeit keressük.

6.6. Tétel. Legyen minden S_{i} halmazban egy kijelölt z_{i} pont. Tegyük fel, hogy igazak a következők:

1. Rögzített i-re bármely két i-keresztező X, Y halmazhoz van olyan F U_{i}-beli halmazokből álló (X, Y)-kompozíció, amire b(X) + b(Y) ≥ b(F), és vagy F ∩ S_{i} = {(X ∩Y)∩S_{i}, (X ∪Y)∩S_{i}}, vagy F ∩S_{i} legalább háromelemű, és (F ∩S_{i})^{z_{i}} minden S_{i}-beli pontot legfeljebb annyiszor fed, mint {X, Y }^{z_{i}}.

2. S_{1}-nek minden partíciója és ko-partíciója nemnegatív.

3. Minden i-re az U_{i−1}-re megszorított feladat tetszőleges egész megoldása kiegészíthető az U_{i}-re megszorított feladat nem feltétlenül egész megoldásává.

Ekkor B(b)-nek van egész pontja.

Bizonyítás. Legyen b^{1} b megszorítása az S_{1} halmazra. A feltételeket úgy határoztuk meg, hogy a 6.4. Tétel alkalmazható, így B(b^{1}) bázispoliéder, azaz az U_{1}- re megszorított feladatnak van egész megoldása. Tegyük fel most, hogy van egy egész m megoldásunk az U_{i−1}-re megszorított feladatra. Definiáljuk S_{i} részhalmazain a b^{i} függvényt a következőképpen:

b^{i}(X) := min{b(Y) − m(Y − X) : Y ⊆ U_{i}, Y ∩ S_{i} = X}.

Mivel az m megoldás kiegészíthető U_{i}-re, S_{i}-nek nem lehet b^{i} szerint negatív partíciója vagy ko-partíciója. m értéke megegyezik egy halmazon és annak kompozícióján, így a 6.4. Tétel összes feltétele teljesül, B(b^{i}) bázispoliéder, ennek egész elemét mhez hozzáadva az U_{i}-re megszorított feladat egész megoldását kapjuk.

6.7. Tétel. Tegyük fel, hogy b_{1} és b_{2} rendelkezik a fenti tulajdonságokkal, és minden i-re az U_{i−1}-re megszorított feladatok bármely közös egész megoldása kiegészíthető az U_{i}-re megszorított feladatok közös, nem feltétlenül egész megoldásává (i = 1-re: U_{1}- en van közös nem feltétlenül egész megoldás). Ekkor B(b_{1}) ∩ B(b_{2})-nek van egész pontja.

Bizonyítás. A 6.6. Tétel bizonyítását kell alkalmazni egyetlen módosítással: az egészértékű kiterjesztést az biztosítja, hogy a B(b_{1}^{i}) és a B(b_{2}^{i}) bázispoliéder metszete nem üres, tehák van közös egész elemük.

6.3 Ferdén szupermoduláris színezés

Tekintsük a T alaphalmazon a p pozitív metsző halmazpárokon ferdén szupermoduláris függvénnyel megadott színezési feladatot, ahol p-re teljesül (6.1); legyen C = {c_{1}, …, c_{k+1}} a színek halmaza; C_{j} := {c_{1}, …, c_{j}}. Vegyünk hozzá T -hez egy új pontot: T′ := T ∪ {z}, és legyen C′ = C_{k}. Definiáljunk S := T′ × C′-n egy b halmazfüggvényt a következő módon:

• Ha z ∉ A ⊂ T′, és B ⊆ C′, akkor b(A × B) := |A| − (p(A) − |B|)^{+}.

• Ha z ∈ A ⊂ T′, és B ⊆ C′, akkor b(A × B) := −(p(T′ − A) − |C′ − B| − 1)^{+}.

• A többi halmazra b = ∞.

6.8. Állítás. B(b)-nek pontosan akkor van egész pontja, ha T -n van jó színezés.

Bizonyítás. Tegyük fel, hogy x ∈ B(b). Legyen z_{i} := (z, c_{i}), S_{i} := T′ × c_{i}; b(S_{i}) = b(S − S_{i}) := 0. Mivel t ∈ T -re b((t, c_{i})) = 1, b((T′ − t) × c_{i}) = 0, és b(t × C′) = 1, x megad egy színezést: t ∈ T -t pontosan akkor színezzük a c_{i} színnel, ha x((t, c_{i})) = 1; a kimaradó pontokat c_{k}-val színezzük. Ha lenne egy A ⊆ T halmaz, amire p(A)-nál kisebb elemszámú a benne szereplő színek B halmaza, c_{k} ∉ B esetén b(A × B) < |A| = x(A × B) miatt, c_{k} ∈ B esetén b((T′ − A) × (C′ − B)) < 0 = x((T′ − A) × (C′ − B)) miatt ellentmondásra jutnánk.

Fordítva, egy színezés meghatároz egy x : S → {0, 1} vektort, ahol x(z_{i})-t úgy választjuk, hogy x(S_{i}) = 0 teljesüljön. b(A×B) < x(A×B) semmilyen A ⊆ T′, B ⊆ C′-re nem lehetséges, hiszen z ∉ A esetén A, z ∈ A esetén pedig T′ − A kevés színt tartalmazna.

6.9. Tétel. Ha p pozitív metsző halmazpárokon ferdén szupermoduláris függvény, és (6.1) teljesül, akkor van jó színezés.

Bizonyítás. Belátjuk, hogy a fent definiált S_{i} halmazokkal és z_{i} kijelölt pontokkal b kielégíti a 6.6. Tétel feltételeit. Legyen i tetszőleges, és tekintsünk egy X = A_{1} × B_{1} és Y = A_{2} × B_{2} i-keresztező halmazpárt. A 6.6. Tétel feltételeinek megfelelő F halmazrendszert kell találnunk.

Ha z_{i} ∉ A_{1}, és b(X) = |A_{1}|, akkor b(X) = ∑_{t∈A_{1}} b(t×B_{1}), tehát ezek a halmazok és Y jó rendszert alkotnak, hiszen X és Y i-keresztezése miatt X ∩ S_{i} nem lehet egyelemű. Hasonlóan, ha z_{i} ∈ A_{1}, és b(X) = 0, akkor b(X) ≥ ∑_{t∉A_{1}} b((T′−t)×B_{1})) miatt kapunk jó rendszert.

A fentiek alapján feltehető, hogy z_{i} ∉ A_{1} esetén p(A_{1}) > 0 és b(X) = |A_{1}| + |B_{1}|−p(A_{1}), z_{i} ∈ A_{1} esetén pedig p(T′−A_{1}) > 0 és b(X) = 1+|C′−B_{1}|−p(T′−A_{1}), valamint ugyanez igaz A_{2}, B_{2}-re. Különbözőképpen adjuk meg az F halmazrendszert attól függően, hogy z_{i} hol van, és a ferde szupermodularitásnál melyik egyenlőtlenség teljesül p-re a b(X) és b(Y) definíciójában szereplő két halmazon. Tegyük fel először, hogy ezeken a halmazokon p szupermoduláris, és z_{i} ∈ X, z_{i} ∈ Y, vagy z_{i} ∉ X, z_{i} ∉ Y. Ekkor a következő halmazrendszer megfelel:

F := {(A_{1} ∩ A_{2}) × (B_{1} ∩ B_{2}), (A_{1} ∪ A_{2}) × (B_{1} ∪ B_{2}),

(\overline{A_{1} − A_{2}}) × (B_{2} − B_{1}), (\overline{A_{2} − A_{1}}) × (B_{1} − B_{2}), T′ × (C_{i} − (B_{1}ΔB_{2}))\}.

Könnyen látható ugyanis p szupermodularitása alapján, hogy b(X)+b(Y) ≥ b((A_{1}∩ A_{2}) × (B_{1} ∩ B_{2})) + b((A_{1} ∪ A_{2}) × (B_{1} ∪ B_{2})), a rendszer többi elemére pedig b nem pozitív.

Legyen most z_{i} ∉ X, z_{i} ∈ Y, p szupermoduláris az A_{1}, T′ − A_{2} halmazokon. Tekintsük a következő halmazrendszert:

F := {(A_{1} ∩ A_{2}) × (B_{1} ∪ B_{2}), (A_{1} ∪ A_{2}) × (B_{1} ∩ B_{2}),
(A_{1} − A_{2}) × (B_{1} − B_{2}), (A_{2} − A_{1}) × (B_{2} − B_{1})}.

Tudjuk, hogy p(A_{1}) + p(\overline{A_{2}}) ≤ p(A_{1} − A_{2}) + p(\overline{A_{2} − A_{1}}). Ez alapján

b(X) + b(Y) = |A_{1}| + |B_{1}| − p(A_{1}) + 1 + |C′ − B_{2}| − p(\overline{A_{2}})
≥ |A_{1} ∩ A_{2}| + |A_{1} − A_{2}| + |B_{1}| − p(A_{1} − A_{2})
+ 1 + |C′ − B_{2}| − p(\overline{A_{2} − A_{1}})
≥ |A_{1} ∩ A_{2}| + |A_{1} − A_{2}| + |B_{1} − B_{2}| − p(A_{1} − A_{2})
+ 1 + |C′ − (B_{2} − B_{1})| − p(\overline{A_{2} − A_{1}})
≥ b((A_{1} ∩ A_{2}) × (B_{1} ∪ B_{2})) + b((A_{1} − A_{2}) × (B_{1} − B_{2}))
+ b((A_{2} − A_{1}) × (B_{2} − B_{1})) + b((A_{1} ∪ A_{2}) × (B_{1} ∩ B_{2})).

A többi F-re megkövetelt tulajdonság könnyen ellenőrizhető. Ha a ferde szupermodularitás másik egyenlőtlensége teljesül, az alábbi halmazrendszereket választjuk:

z_{i} ∉ X, z_{i} ∉ Y:

F := {(A_{1} ∩ A_{2}) × (B_{1} ∩ B_{2}), (A_{1} ∩ A_{2}) × (B_{1} ∪ B_{2}),
(A_{1} − A_{2}) × B_{1}, (A_{2} − A_{1}) × B_{2}}.

z_{i} ∈ X, z_{i} ∈ Y:

F := \{(\overline{A_{2} − A_{1}}) × B_{1}, (\overline{A_{1} − A_{2}}) × B_{2}, (A_{1} ∪ A_{2}) × (B_{1} ∪ B_{2}),

(A_{1} ∪ A_{2}) × (B_{1} ∩ B_{2}), T′ × (C_{i} − (B_{1} ∩ B_{2})), T′ × (C_{i} − (B_{1} ∪ B_{2}))}.

z_{i} ∉ X, z_{i} ∈ Y:

F := {(A_{1} ∩ A_{2}) × B_{1}, (A_{1} − A_{2}) × (B_{1} − B_{2}),
(A_{1} ∪ A_{2}) × B_{2}, (\overline{A_{1} − A_{2}})) × (B_{2} − B_{1}), T′ × (C_{i} − (B_{2} − B_{1}))\}.

Ezeknek a rendszereknek az alkalmassága hasonlóan ellenőrizhető, mint a szupermoduláris esetben; ezt nem részletezzük.

Be kell még látnunk, hogy egy U_{i−1}-re megszorított x′ egész megoldás kiterjeszthető U_{i}-re. Ennél többet látunk be: x′ kiterjeszthető x ∈ B(b) vektorrá a következő definícióval (j > i):

x((t, c_{j}) := \begin{cases}\frac{1}{k+1−i}, & ha t ≠ z, x′(t × C_{i}) = 0 \\ 0, & ha t ≠ z, x′(t × C_{i}) = 1 \\ −\frac{x′(T ×C_{i})}{k+1−i}, & ha t = z. \end{cases}

Tegyük fel, hogy b(A × B) < x(A × B) valamilyen A, B-re. Feltehető, hogy B = (B ∩ C_{i}) ∪ (C_{l} − C_{i}) valamilyen l-re. tekintsük az alábbi függvényeket:

b^{∗}(j) :=b(A × ((B ∩ C_{i}) ∪ (C_{j} − C_{i})) (j ≥ i),
x^{∗}(j) :=x(A × ((B ∩ C_{i}) ∪ (C_{j} − C_{i})) (j ≥ i).

b^{∗} konkáv, x^{∗} lineáris, és b(i) ≥ x(i), b(k) = x(k), tehát b^{∗} ≥ x^{∗}, speciálisan b^{∗}(l) ≥ x^{∗}(l), ami ellentmond a feltevésnek.

6.10. Tétel. Tekintsünk egy p_{1} és egy p_{2} pozitív metszőkön ferdén szupermoduláris függvénnyel megadott színezési feladatot ugyanazon a T alaphalmazon és C színhalmazon, ahol (6.1) mindkét függvényre teljesül. Ekkor van közös jó színezés.

Bizonyítás. Elég belátni, hogy a p_{1}-nek és p_{2}-nek megfeleltetett b_{1} és b_{2} függvénnyel megadott poliéderekre alkalmazható a 6.7. Tétel. Ehhez csak azt kell megmutatni, hogy minden i-re az U_{i−1}-re megszorított feladatok közös egész megoldása kiterjeszthető U_{i}-re közös, nem feltétlenül egész megoldássá. Azonban az előző bizonyításban használt kiterjesztés közös kiterjesztés lesz, hiszen nem függ b-től. i = 1 esetén is ugyanígy definiálhatjuk x-et, ekkor minden v ∈ S, v ≠ z_{i}-re x(v) = \frac{1}{k+1}.

Megjegyzés. Ha egy p pozitív metszőkön ferdén szupermoduláris függvényre csak az U_{1}-re megszorított feladatot nézzük, akkor a különböző megoldások éppen azt mutatják, hogy milyen halmazok alkothatják az első színosztályt; a fenti gondolatmenet alapján tehát a lehetséges színosztályok általánosított polimatroidot alkotnak. A színezési tételeket ennek a ténynek a felhasználásával egyszerűbben is be lehet bizonyítani, de a mi módszerünk kevésbé használja a színezési feladat szigorú szerkezetét, így talán más problémák kapcsán jobban használható.

6.4 Egy pakolási feladat

Legyen D = (V, A) digráf, V = S ∪ T kételemű partíció. Nevezzünk egy részgráfot kettős fenyvesnek, ha S-et összehúzva egy s ponttá s gyökerű fenyő (s-ből léphetnek ki többszörös élek), T -t összehúzva egy t ponttá és az élek irányítását megfordítva pedig t gyökerű fenyő (itt is jöhetnek t-ből többszörös élek). Legyen r : V → Z_{+} igényfüggvény a pontokon, r(X) := max_{v∈X} r(v), k := r(V). A célunk k darab éldiszjukt kettős fenyvest találni a gráfban úgy, hogy minden v pont legalább r(v) darabban szerepeljen. Ennek szükséges feltétele, hogy minden X ⊆ S-re δ(X) ≥ r(X) és minden X ⊆ T -re ρ(X) ≥ r(X) teljesüljön. Schrijver [21] megmutatta, hogy r ≡ k esetén ez egyben elégséges feltétel is; az algoritmikus vonatkozásokat Keijsper [14] elemezte részletesen. Mi egy kicsit általánosabb igényfüggvényre látjuk be az elégségességet, Schrijver bizonyításának a gondolatmenetét alkalmazva. Vezessük be a következő jelöléseket:

A_{S} :={uv ∈ A : u, v ∈ S},
A_{T} :={uv ∈ A : u, v ∈ T },
A_{0} :={uv ∈ A : u ∈ S, v ∈ T }.

.

6.11. Tétel. Tegyük fel, hogy minden v ∈ S, r(v) < r(S)-re δ_{A_{S}}(v) ≥ ρ_{A_{S}}(v), és minden v ∈ T, r(v) < r(T)-re ρ_{A_{T}} (v) ≥ δ_{A_{T}} (v). Ebben az esetben akkor és csak akkor létezik k darab olyan éldiszjukt kettős fenyves a gráfban, amik közül minden v pontot legalább r(v) darab tartalmaz, ha minden X ⊆ S-re δ(X) ≥ r(X) és minden X ⊆ T -re ρ(X) ≥ r(X).

Bizonyítás. A_{0} részhalmazain definiáljuk a p_{S} és p_{T} függvényeket:

p_{S}(Y) := max{r(X) − δ_{A_{S}}(X) : X ⊆ S, Y az X-ből kilépő A_{0}-élek halmaza},
p_{T} (Y) := max{r(X) − ρ_{A_{T}} (X) : X ⊆ T, Y az X-be lépő A_{0}-élek halmaza}.

6.12. Állítás. p_{S} és p_{T} pozitív metszőkön ferdén szupermoduláris.

Bizonyítás. Legyen Y_{1}, Y_{2} két metsző élhalmaz, p_{S}(Y_{1}), p_{S}(Y_{2}) > 0. Ekkor van X_{1} ⊆ S és X_{2} ⊆ S halmaz, ami Y_{1}-re, illetve Y_{2}-re a p_{S} definíciójában szereplő maximumot adja. Az állítás következik abból a tényből, hogy az X_{1}, X_{2} halmazpáron r ferdén szupermoduláris, −δ_{A_{S}}-re pedig a ferde szupermodularitás mindkét egyenlőtlensége teljesül. p_{T} -re ugyanígy látható be a ferde szupermodularitás.

A tétel feltételei szerint minden Y ⊆ A_{0}-ra p_{S}(Y) ≤ |Y |, p_{S}(Y) ≤ k, és ugyanez igaz p_{T} -re. A 6.10. Tételt alkalmazva tehát A_{0} elemei színezhetők k színnel úgy, hogy minden Y élhalmazban legalább max{p_{S}(Y), p_{T} (Y)} szín van. Legyenek a színosztályok Y_{1}, …, Y_{k}, H_{i} := {u : uv ∈ Y_{i}}, J_{i} := {v : uv ∈ Y_{i}}. p_{S}-et és p_{T} -t úgy választottuk, hogy az 5.1. Tétel szerint az alábbi két fenyves-pakolási feladatnak van megoldása:

1. T pontjait töröljük, és a maradék élek irányítását megfordítjuk. H_{1}, …, H_{k} gyökérhalmazú élidegen fenyveseket keresünk, amik közül minden v pont legalább r(v) darabban van benne.

2. S pontjait töröljük. J_{1}, …, J_{k} gyökérhalmazú élidegen fenyveseket keresünk, amik közül minden v pont legalább r(v) darabban van benne.

Adott i-re a J_{i} és H_{i} gyökérhalmazú fenyveseket, illetve fordított fenyveseket a megfelelő Y_{i}-beli élekkel összekötve megkapjuk a kívánt kettős fenyveseket.

7 Összefoglalás

Ebben a fejezetben összefoglaljuk a dolgozat fő eredményeit, és néhány szót szólunk a tárgyalt kérdéskörök összefüggéseiről, valamint a jövőbeni vizsgálatok lehetséges irányairól.

7.1 Irányított és irányítatlan leemelés

A dolgozatban megmutattuk, hogy a legtöbb ismert leemelési tételt ki lehet terjeszteni az általunk vizsgált halmazfüggvény-fedési feladatra. Irányított esetben a ferde szupermodularitás helyett a 2. fejezetben definiált kvázi-szupermodularitás az a fogalom, ami ezt lehetővé teszi, így Mader tétele is általánosítható (2.5. Tétel). Új eredmény, hogy irányított gráfokra is megfogalmazható egy szubadditivitást használó leemelési művelet (2.2. Tétel), és Mader irányítatlan tételének is van általánosítása az absztrakt megközelítésben (3.9. Tétel).

Bár a bizonyításokban alkalmazott módszerek hasonlóak az irányított és az irányítatlan esetben, jelentős különbségeket is felfedezhetünk. Míg az előbbinél a szimmetria hiánya okoz gondot, az utóbbit a veszélyes halmazok bonyolultabb szerkezete miatt nehéz kezelni. Éppen ezért nem meglepő, hogy mind a tételek pontos megfogalmazása, mind az alkalmazások terén külön kell foglalkozni a két esettel.

Ami a nyitott kérdéseket illeti, két olyan jelenséget említek meg, amivel a dolgozat nem foglalkozott részletesen. Ismertettük Benczúr András és Frank András [3] tételét (3.18. Tétel), ahol a vágásfeltétel csak egy partíciós feltétellel együtt biztosítja a megoldhatóságot. Nem ismert, hogy megfogalmazhatók-e hasonló, a vágásfeltételnél erősebb feltételek elégségességét kimondó állítások ferdén szupermoduláris függvényekre, illetve digráfok esetében a 2.7. Tételben szereplő halmazfüggvényekre.

A másik érdekes jelenség, hogy bizonyos körülmények között a leemelhető élpárokra további megkötéseket lehet tenni. Erre példa a Bang-Jensen, Gabow, Jordán és Szigeti [2] által vizsgált partícióhoz kötött élösszefüggőség-növelés, valamint Nagamochi és Eades [19] eredménye, akik síkgráfok élösszefüggőség-növelését oldották meg. Általánosságban vizsgálható, hogy az ilyen megkötések a halmazfüggvény-fedési feladatot hogyan befolyásolják.

7.2 Alkalmazások

A dolgozatnak nem volt célja, hogy átfogó képet adjon a leemelési művelet alkalmazásairól; ehelyett arra törekedtünk, hogy néhány friss eredmény bemutatásával illusztráljuk a témakörben rejlő lehetőségeket. Megmutattuk, hogy Rado és Lovász páros gráfokra vonatkozó tételei (2.4., 2.3. Tétel) egy leemelési tétel (2.2. Tétel) speciális esetének is tekinthetők. Érdemes lesz megvizsgálni, hogy ez hogy viszonyul a Frank András és Tardos Éva [6] által bebizonyított más irányú általánosításhoz. A Bertsimas és Teo [4] cikke nyomán a 3. fejezetben ismertetett két példa (a takarékos tulajdonság és az élidegen utak problémája) mutatja, hogy a leemelési művelet gyakorlati alkalmazása nem szűkíthető le élösszefüggőségi kérdésekre. Utóbbiakkal nem is foglalkoztunk részletesen, hiszen az eredmények ismertetése meghaladta volna a dolgozat kereteit; beláttuk azonban, hogy a nehezebb, vegyes gráfokra vonatkozó tételek (4.2. Tétel, 4.3. Tétel) is kezelhetők a módszereinkkel.

Az 5. fejezetben közös általánosítását adtuk Edmonds [5] és Gabow [11] pakolási tételeinek (5.1. Tétel), majd ennek segítségével a 6. fejezetben beláttuk Schrijver bibranching-pakolási tételének egy kiterjesztését (6.11. Tétel). Bár az általunk adott feltételek technikai jellegűnek tűnhetnek, az általános fenyves-pakolási feladat NP-teljessége miatt ez nehezen elkerülhető. A bizonyítás olyan algoritmust nyújt a fenyvesek megtalálására, ami a kapacitásos esetben erősen polinomiális marad, és jó felső korlátot ad a különböző fenyvesek számára. Az algoritmus Gabow módszeréhez hasonlóan egy lamináris rendszert épít, de a leemelési műveleten kívül más eszközöket is alkalmaz. Az ebből a megközelítésből, és a többi ismertetett eredményből fakadó alkalmazások feltérképezése további munkát igényel.

7.3 Poliéderek

A 6. fejezetben Schrijver szupermoduláris színezési tételét kiterjesztettük ferdén szupermoduláris függvényekre, és olyan poliéderes bizonyítást adtunk, ami nem használja a színezések néhány speciális jellemzőjét, így alkalmas lehet további általánosítások bizonyítására; érdemes megvizsgálni, hogy milyen feladatok jellemezhetőek az itt leírt poliéderrel. Mindez beleillik az olyan poliéderekkel kapcsolatos kutatások sorába, amelyek nem feltétlenül teljesen duálisan egészértékű rendszert határoznak meg, de rendelkeznek a bázispoliéderek néhány kedvező tulajdonságával.

Schrijver színezési tételére eddig nem sikerült kizárólag leemelést használó bizonyítást adni. Felvetődik a kérdés, hogy jellemezhetőek-e valamilyen módon azok a feladatok, amiknek a megoldására a leemelési művelet már nem alkalmas. Egy érdekes megfigyelés, hogy a színezést meghatározó halmazfüggvény lehet két metsző szupermoduláris függvény maximuma, de az a gyengébb feltevés már nem elegendő, hogy három kölcsönösen metsző halmaz közül kettőn a függvényre teljesül a szupermoduláris egyenlőtlenség; márpedig a leemelési tételek ilyen jellegű feltételeket tudtak kezelni. A poliéderes és a leemelést használó módszerek viszonyának mélyrehatóbb elemzésével elképzelhető, hogy mindkét megközelítés előnyeit kihasználó eljárásokhoz juthatunk.

Irodalom

[1] J. Bang-Jensen, A. Frank and B. Jackson, Preserving and increasing local edgeconnectivity in mixed graphs, SIAM J. Disc. Math. Vol. 8., No. 2, pp. 155–178, 1995.

[2] J. Bang-Jensen, H. N. Gabow, T. Jordán, Z. Szigeti, Edge-connectivity augmentation with partition constraints, in Proc. 9th ACM-SIAM Symp. on Discrete Algorithms, 1998, pp. 306–315.

[3] A. Benczúr and A. Frank, Covering symmetric supermodular functions by graphs, Mathematical Programming Series B, Vol. 84, No. 3 (1999), pp. 483– 504.

[4] D. Bertsimas and C. Teo, The parsimonious property of cut covering problems and its applications, Operation Research Letters 21 (1997) 123–132.

[5] J. Edmonds, Edge-disjoint branchings, in Combinatorial Algorithms (B. Rustin, Ed.), Academic Press, New York, 1973, pp. 91–96.

[6] A. Frank and É. Tardos, An application of submodular flows, Linear Algebra and its Applications 114/115 (1989) 329–348.

[7] A. Frank, Applications of submodular functions, in Surveys in Combinatorics, London Mathemetical Society Lecture Note Series 187, Cambridge Univ. Press (Ed. K. Walker) 1993, pp. 85–136.

[8] A. Frank, Connectivity augmentation problems in network design, in Mathematical Programming: State of the Art (J. R. Birge and K. G. Murty, Eds.), Univ. of Michigan, 1994, pp. 34–63.

[9] S. Fujishige, Submodular Functions and Optimization, North-Holland, Amsterdam, 1991.

[10] H. N. Gabow and K. S. Manu, Packing algorithms for arborescences (and spanning trees) in capacitated graphs, Mathematical Programming Series B, Vol. 82, No. 1-2 (1998), pp. 83–109.

[11] H. N. Gabow, Perfect arborescence packing in preflow mincut graphs, Tech Rept. CSCI-790-95, Dept. of Comp. Sci., Univ. of Col. at Boulder, Boulder, CO, 1995. pp. 528–538.

[12] M. X. Goemans, D. Bertsimas, Survivable networks, linear programming relaxations and the parsimonious property, Math Programming 60 (1993) 145–166.

[13] M. X. Goemans and D. P. Williamson, A general approximation algorithm for constrained forest problems, Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, 1992, pp. 307–316.

[14] J. Keijsper, New techniques in network optimization, Academisch proefschrift (1998).

[15] L. Lovász, A generalization of König’s theorem, Acta Math. Acad. Sci. Hungar. 21 (1970), 443-446.

[16] L. Lovász, On two min-max theorems in graph theory, J. Combin. Theory Ser. B, 21 (1976), pp. 26–30.

[17] W. Mader, A reduction method for edge-connectivity in graphs, Ann. Discrete Math. 3 (1978), pp. 145–164.

[18] W. Mader, Konstruktion aller n-fach kantenzusammenhängenden Digraphen, European J. Combin. 3 (1982), pp. 63–67.

[19] H. Nagamochi and P. Eades, Edge-splitting and edge-connectivity augmentation in planar graphs, IPCO IV. LNCS 1412 (1998) pp. 96–111.

[20] R. Rado, A theorem on independence functions, Quart. J. Math Oxford 13 (1942), 83–89.

[21] A. Schrijver, Supermodular colourings, in Matroid Theory (A. Recski and L. Lovász, Eds.), Colloq. Math. Soc. János Bolyai 40, North-Holland, 1985, pp. 327–344.

[22] A. Schrijver, Short proofs on multicommodity flows and cuts, J. Combin. Theory Ser. B 53 (1991), 32–39.

[23] É. Tardos, Generalized matroids and supermodular colourings, in Matroid Theory (A. Recski and L. Lovász, Eds.), Colloq. Math. Soc. János Bolyai 40, North-Holland, 1985, pp. 359–382.