Economic subjects | Operational Research » Király Csaba - Algoritmusok szupermoduláris függvények fedésére

http://www.doksihu Algoritmusok szupermoduláris függvények fedésére Szakdolgozat Írta : Király Csaba matematikus hallgató Témavezet® : Frank András egyetemi tanár Eötvös Loránd Tudományegyetem Természettudományi Kar Matematikai Intézet Operációkutatási Tanszék Budapest, 2010. június 3 http://www.doksihu Köszönetnyilvánítás : Szeretném ezúton megköszönni témavezet®mnek Frank Andrásnak, azt a rengeteg id®t, mellyel hozzájárult e dolgozat létrejöttéhez, valamint a sok érdekes problémát, melyet számomra felvetett. Köszönöm az EGRES csoport tagjainak a támogatást, külön köszönöm Frank Andrásnak, Király Tamásnak és Pap Júliának a 4.22 Tétel bizonyításához nyújtott segítséget. Köszönöm még Maczkó Renátának a nyelvtani hibák javításában nyújtott segítséget. http://www.doksihu Tartalomjegyzék Ábrák jegyzéke 5 El®szó 6 1. Bevezetés 7 1.1 1.2 Deníciók .

7 1.11 Halmazok, halmazrendszerek . 7 1.12 Halmazfüggvények . 8 1.13 Poliéderek . 10 1.14 Gráfok és hipergráfok . 10 1.15 Matroidok . 13 Tételek . 14 2. Halmazrendszerekr®l szóló tételek 2.1 Halmazrendszerek gráfja 2.2 Lamináris és keresztezés-mentes halmazrendszerek fa-reprezentációi 2.3 2.4 17 . 17 . 19 Kikeresztezés . 21 S -T -elválasztó halmazrendszerek . 25 3. Általános tételek és algoritmusok 31 3.1 Metsz® szubmoduláris függvények reszelése . 31 3.2 Fujishige tétele algoritmikusan . 33 4. Irányítások 41 4.1 Irányítási lemma gráfokra és hipergráfokra . 4.2 Keresztez® G-szupermuduláris függvényt fed® irányítások .

3 41 44 http://www.doksihu 4.3 Hipergráfok keresztez® szupermoduláris függvényt fed® irányítása . 48 4.4 Metsz® szupermoduláris függvényt fed® irányítások . 48 4.5 Gyökeresen k -élösszefügg®vé irányítás . 50 4.6 Gyökeresen (k, `)-élösszefügg®vé 4.7 Hipergráfok er®sen összefügg® irányítása . 58 4.8 Alkalmazás : Matroidok minimális vágásai . 63 4.9 Lokális halmaz-élösszefügg®ség meg®rzése . 64 5. Összefoglalás, további kérdések Irodalomjegyzék irányítás . 53 66 69 http://www.doksihu Ábrák jegyzéke 2.1 Lamináris rendszer reprezentálása feny®vel 4.1 Segédgráf a fokszám minimalizáló orákulumhoz 4.2 Az (k,1)-élösszefügg®vé . . irányító algoritmus futása 5 . 20 52 56 http://www.doksihu El®szó A dolgozat f®

célja gráfok és hipergráfok különböz® irányításait megtaláló algoritmusok megadása. Ezeket sokkal általánosabb algoritmusból fogjuk levezetni, illetve néhány esetben ennél egyszer¶bb megoldást is adunk. Látni fogjuk, hogy a gyakorlatban azok az irányítási problémák az érdekesek, ahol olyan irányítást keresünk, melyben minden halmaz befoka nagyobb egy keresztez® vagy metsz® szupermoduláris függvénynél. Ezért a dolgozatban keresztez® és metsz® szupermoduláris függvényekkel kapcsolatos algoritmusokkal foglalkozunk Szupermoduláris függvények ellentettje szubmoduláris, így (történeti okokból) néha át fogunk térni szubmoduláris függvényekre. Bevezetésként az 1. fejezetben áttekintjük a szükséges deníciókat, valamint a felhasznált tételeket. Ezt követ®en a 2 fejezetben keresztez® szupermoduláris függvényekhez köt®d® halmazrendszerekr®l szóló tételeket és algoritmusokattekintünk át. Ezek segítségével a 3

fejezetben algoritmust adunk a keresztez® szubmoduláris függvény bázis-poliéderének nemürességének eldöntésére, majd megismerkedünk a teljes reszel® algoritmussal. Ezt felhasználva a 4 fejezetben gráfok és hipergráfok keresztez® szupermoduláris függvényeket fed® irányításait megadó algoritmusokat kapunk, melyeknél speciális esetekben egyszer¶bb algoritmusokat adunk. A kapott eredményeket az 5. fejezetben foglaljuk részletesen össze A dolgozatban a saját eredményeket tételek, algoritmusok és bizonyítások esetén, (amennyiben a bizonyított állítás nem saját eredmény), csillaggal fogom jelölni. 6 http://www.doksihu 1. fejezet Bevezetés Ebben a fejezetben áttekintjük a dolgozatban felhasznált deníciókat, és tétele- 1 ket . 1.1 Deníciók 1.11 Halmazok, halmazrendszerek A dolgozatban el®forduló minden halmaz véges, így minden halmazrendszer alaphalmaza is véges. Az alábbiakban halmazok különbségét kedvéért

bizonyos esetekben Egy F halmazt A, B ⊆ S helyett −-szal hívunk, ha A ∪ B 6= S jelöljük. t ∈ F, s 6∈ F . átmetsz®nek mondjuk, ha sem üres. Ha ezeken kívül jelöljük. Az egyszer¶ség X − {v}-t X − v -vel, X ∪ {v}-t X + v -vel st-halmaznak halmazokat A ∩ B, A − B is teljesül, akkor az A és B és B − A egyike halmazt keresz- tez®nek hívjuk. Egy F halmazrendszert elem metszete és uniója is halmazgy¶r¶nek nevezünk, ha bármely két F -ben van. F -et F -beli metsz®nek illetve keresztez®nek ne- vezzük, ha a fenti tulajdonság csak átmetsz® illetve keresztez® halmazpárokra van megkövetelve. Metsz® de nem átmetsz® halmazokra az egyik tartalmazza a másikat, így az uniójuk a kisebb, a metszetük a nagyobb halmaz, ami miatt metsz® halmaz- 1 Azon tételeket és deníciókat, melyek a matematikus szak alapképzésében el®fordulnak nem említem külön. http://www.doksihu 8 1.1 Definíciók rendszer

tetsz®leges két metsz® (azaz nem diszjunkt) elemének metszete és uniója is a halmazrendszerben van. metszi át egymást. F -et F -et laminárisnak nevezzük, ha semelyik két eleme sem keresztezés-mentesnek nevezzük, ha semelyik két eleme sem keresztezi egymást. Egy K ⊆ 2S ugyanannyi tagja tartalmazza Az ∈T S∪∗ T F ⊆2 párra van kompozíciónak hívunk, ha halmazrendszert minden elemét K-nak. halmazrendszert S -T elválasztónak hívjuk, ha minden s ∈ S, t ∈ st-halmaz F -ben. F -et S -T -fa-kompozíciónak hívjuk, ha reprezen- tálható egy olyan irányított fával, amelynak csúcsai e mellett S S -nek vagy T -nek részhalmazai, S ∪ ∗ T -nek partícióját alkotják, éleinek pedig töve S -ben, hegye T -ben van. A reprezentálás úgy értend®, hogy F elemei pontosan az élek által meghatározott alapvágások, ahol egy irányított él által meghatározott alapvágáson a fából az él elhagyása után keletkezett gráf

azon komponensét értjük, ahova az él belép. 1.12 Halmazfüggvények Halmazfüggvényen itt olyan valós érték¶ függvényt értünk, mely egy S alaphal- maz részhalmazaihoz rendel (nem feltétlenül véges) értéket, azzal a kikötéssel, hogy az üres halmazon nullát vesz fel, és az Halmazfüggvényt nyerhetünk egy S -en felvett értéke véges. a ∈ RS vektorból, ha X ⊆ S -re a(X)-et P a(s)-nek deniáljuk. (Általában nem érthet® félre, hogy megtartjuk az a jelös∈X lést.) Hasonlóan ehhez egy tetsz®leges h halmazfüggvényre h-t értelmezhetjük az értelmezési tartományában lév® halmazok F rendszerén a h(F) := P h(F ) összeg- F ∈F gel. Egy b : 2S R ∪ {∞} A, B ⊆ S -re függvényt szubmodulárisnak nevezünk, ha minden teljesül a b(A) + b(B) ≥ b(A ∩ B) + b(A ∪ B) (1.1) szubmodularitási egyenl®tlenség. Ha (11) csak átmetsz® vagy csak keresztez® halmazokra teljesük, akkor nak mondjuk. Ha b-t metsz®(n)

illetve keresztez®(n) szubmoduláris- b metsz® szubmoduláris, akkor (1.1) bármely metsz® halmazpárra teljesül. Egy p : 2S R ∪ {−∞} függvényt szupermodulárisnak nevezünk, ha minden http://www.doksihu 9 1. Fejezet : Bevezetés A, B ⊆ S -re teljesül a p(A) + p(B) ≤ p(A ∩ B) + p(A ∪ B) (1.2) szupermodularitási egyenl®tlenség. Ha (12) csak átmetsz® vagy csak keresztez® halmazokra teljesük, akkor p-t metsz®(n) illetve keresztez®(n) szupermodulá- risnak mondjuk. Ismét igaz, hogy ha p metsz® szupermoduláris, akkor (1.2) bármely metsz® halmazpárra teljesül. Egy b : 2S R ∪ {∞} rendszerét. Amennyiben ∈ F(b) halmazokra b függvényre jelölje F(b) szubmoduláris, úgy a F(b) véges b-érték¶ halmazok halmazgy¶r¶, mivel ∞ > b(A) + b(B) ≥ b(A ∩ B) + b(A ∪ B). A, B ∈ Amennyiben b keresztez®n (vagy metsz®n) szubmoduláris, úgy ez csak keresztez® (illetve átmetsz®) halmazokra áll fenn, így

Egy F(b) keresztez® (illetve metsz®) rendszer lesz. b : 2S R ∪ {∞} (metsz®) szubmoduláris és egy p : 2S R ∪ {−∞} (met- sz®) szupermoduláris függvényt ha minden (átmetsz®) (metsz®(n)) paramoduláris párnak nevezünk, A, B ⊆ S -re teljesül a b(A) − p(B) ≥ b(A − B) − p(B − A) (1.3) kereszt egyenl®tlenség. Legyen azt a ∨ b : 2S R ∪ {∞} S b : 2 R ∪ {∞} tetsz®leges halmazfüggvény. Ekkor függvényt értjük, melyre b∨ (X) := min{b(P) : P X Legyen azt a alsó reszeltjén X ⊆ S -re partíciója}. (1.4) p : 2S R∪{−∞} tetsz®leges halmazfüggvény. Ekkor p fels® reszeltjén p∧ : 2S R ∪ {−∞} függvényt értjük, melyre p∧ (X) := max{p(P) : P X Egy b h : 2S R ∪ {±∞} függvényt értjük, melyre X ⊆ S -re partíciója}. függvény komplementerén azt a (1.5) h : 2S R ∪ {±∞} X ⊆ S -re h(X) := h(S) − h(S − X). (Itt fontos, hogy minden halmazfüggvényre

megköveteltük, hogy vegyen fel.) (1.6) S -en véges értéket http://www.doksihu 10 1.1 Definíciók Legyen b : 2S R ∪ {∞} tetsz®leges halmazfüggvény. Ekkor reszeltjén azt a b↓ : 2S R ∪ {∞} ∨  b↓ (X) := (b)∧ . Legyen p : 2S R ∪ {−∞} függvényt értjük, melyre b teljes (alsó) X ⊆ S -re (1.7) tetsz®leges halmazfüggvény. Ekkor p↑ : 2S R ∪ {−∞} ∧  p↑ (X) := (p)∨ . reszeltjén azt a függvényt értjük, melyre p teljes fels® X ⊆ S -re (1.8) 1.13 Poliéderek Egy b : 2S R ∪ {∞} és egy p : 2S R ∪ {−∞} függvényre legyenek S(b) := {z ∈ RS : z (X ) ≤ b(X ) (∀X ⊆ S )}, S 0 (p) := {z ∈ RS : z (X ) ≥ p(X ) (∀X ⊆ S )}, B(b) := {z ∈ RS : z(S) = b(S), z (X ) ≤ b(X ) (∀X ⊆ S )}, B 0 (p) := {z ∈ RS : z (S ) = p(S ), z (X ) ≥ p(X ) (∀X ⊆ S )}, Q(p, b) := {z ∈ RS : p(X ) ≤ z (X ) ≤ b(X ) (∀X ⊆ S )}. b szubmoduláris illetve bázis-poliédernek, nek

nevezzük. Ha vezzük, melynek Egy S(b)-t (p, b) p szupermoduláris függvényekre szubmoduláris- S 0 (p)-t paramoduláris pár, akkor alsó határfüggvénye p, B(b)-t illetve B 0 (p)-t szupermoduláris poliéder- Q(p, b)-t g-polimatroidnak ne- fels® határfüggvénye b. Q poliéder T ⊂ S -menti vetületén azt a Q0 poliédert értjük, melyet a Q-beli vektorok T elemeihez tartozó koordinátáinak eltörlésével kapunk. 1.14 Gráfok és hipergráfok A dolgozatban, amennyiben nincs más kikötve minden gráfon és hipergráfon megengedjük, hogy legyenek többszörös élek, (igazából a hurokélek sem okoznak túl nagy gondot, de az egyszer¶ség kedvéért inkább tiltjuk ®ket), és hipergráfok esetén tiltjuk az egy csúcsból álló éleket. Adott d(v) G = (V, E) jelöli a v gráfra illetve csúcs fokát, továbbá H = (V, E) hipergráfra tetsz®leges X, Y ⊆ V -re d(X) jelöli az X v ∈ V -re halmaz fokát, http://www.doksihu 11 1.

Fejezet : Bevezetés azaz azon (hiper)élek számát, melyek d(X, Y ) i(X) X -beli és X -en kívüli csúcsot is tartalmaznak, jelöli azon (hiper)élek számát, melyeknek van elemük jelöli az X által feszített (hiper)élek számát, és számát, melyeknek van csúcsa e(X) X -ben és Y -ban is, jelöli azon (hiper)élek X -ben. Az egyértelm¶ség kedvéért alsó indexbe néha beírjuk a (hiper)gráf nevét. Euler-gráfnak nevezünk, ha Egy G Egy G = (V, E) gráfot gráfon egy X ⊆ V csúcsok halmazát, melyekb®l fut él G = (V, E) Adott (szub)partíciójára G-ben minden csúcs foka páros. halmazra jelölje Γ(X) azon V − X -beli X -be. gráfon illetve H = (V, E) hipergráfon V P egy adott e(P) jelöli azon (hiper)élek számát, melyeket nem feszít a partíció egyetlen tagja sem. G-t illetve H-t k -partíció-összefügg®nek hívjuk, ha V P = {V1 , V2 , ., Vq } partíciójára minden e(P) ≥ k(q − 1). (1.9) G-t

illetve H-t (k, `)-partíció-összefügg®nek hívjuk, ha minden P = {V1 , V2 , ., Vq } partíciójára a csúcshalmaznak e(P) ≥ k(q − 1) + `. (1.10) Az irányított gráf közismert fogalmához hasonlóan deniálhatjuk az irányított hipergráfokat. Ezt többféleképpen megtehetnénk, jelen esetben nevezzük pontból áll. egy v∈V lyeknek v A ∈ A irányított hipergráfnak, ha minden D = (V, A) csúcsra ρ(v) irányított gráfon, illetve jelöli a a hegye, illetve melyeknek v δ(v) v D = (V, A)-t akkor él egy hegy és néhány t® D = (V, A) irányított hipergráfon csúcs befokát, azaz azon (hiper)élek számát, me- jelöli a v csúcs kifokát, azaz azon (hiper)élek számát, a(z egyik) töve. Hasonlóan a fokszámhoz ρ és δ is kiterjeszthet® V részhalmazaira. Egy G = (V, E) gráfra vagy egy H = (V, E) hipergráfra legyen adott egy h : : 2V Z ∪ {−∞} függvény. G illetve H h-t fed® irányításán a (hiper)élek

egy olyan irányítását értjük, melyre minden Egy G = (V, E) gráfon adott lárisnak nevezünk, ha minden X ⊆ V -re h(X) ≤ ρ(X). h : 2V Z ∪ {−∞} függvényt G-szupermodu- X, Y ⊆ V -re h(X) + h(Y ) ≤ h(X) + h(Y ) + d(X, Y ). (1.11) http://www.doksihu 12 1.1 Definíciók Amennyiben (1.11) csak metsz®, illetve keresztez® halmazpárokra áll fenn, akkor h-t metsz®(n), illetve keresztez®(n) Egy D = (V, A) irányított gráfot illetve egy melyen adva van egy r∈V r 6∈ X ⊂ V, X 6= ∅ illetve egy D = (V, A) halmazra ρ(X) ≥ k. ρ(X) ≥ k, és minden G = (V, E) Egy D = (V, A) gráfra és nevezünk, ha minden r ∈ X ⊂ V (1,1)-élösszefügg® (hiper)gráfot röviden Egy halmazra által feszített élei megegyeznek R ⊆ V -re G/R-en G irányított gráfot r éleivel, továbbá u ∈ R-re uv ∈ E . amennyiben Egy R G/R gyökérpont, akkor r ∈ R. ρ(X) ≥ `. H = (V, E) vR v ∈ V −R H éleib®l, hogy R

V −R és a csúcs között Hasonlóan értelmezhet® irányított gráfok vR -et rR -nek r, ha G-ben volt egy r 6∈ R, illetve vR , nevezzük. azt a gráfot értjük, mely az halmaz összehúzásával keletkezik. Ennek csúcshalmaza úgy kapjuk Egy irányított V − R + vR . és egy R ⊆ V -re G/R-en hipergráfra és gyökér- azt a gráfot értjük, mely az gyökérpontja továbbra is Ez utóbbi esetben r ∈V r 6∈ X ⊂ V, X 6= ∅ összehúzása is, ebben az élek irányítását is megtartjuk. Amennyiben kijelölt nevezünk, er®sen összefügg®nek nevezünk. halmaz összehúzásával keletkezik. Ennek csúcshalmaza annyi él fut, ahány irányított hipergráfot, irányított hipergráfot, melyen adva van egy r-gyöker¶ (k, `)-élösszefügg®nek halmazra D = (V, A) nevezzük. r-gyöker¶ k -élösszefügg®nek gyökérpont, ha minden pont, G-szupermodulárisnak V − R + vR . H/R E ∈ E -re H/R-be E − R + vR -et éleit

vesszük be hiperélnek, amennyiben ez nem egy pontból áll. Hasonlóan értelmezhet® irányított hipergráfok összehúzása is, ebben az élek irányítását is megtartjuk, azaz az összehúzott hiperél feje megmarad az, ami volt, ha az eredeti feje nem volt amennyiben az eredeti feje kérpont, akkor r ∈ R, H/R G = (V, E) vR -et rR -nek H = (V, E) hipergráf értjük, melynek élei H azon r, ha vR lesz, r gyö- H-ban volt egy kijelölt r 6∈ R, illetve G[R]-rel H = (V, E) vR , illetve hipergráfban az H[R]-rel amennyiben csúcsa és A R⊆V halmaz jelöljük. illeszkedési gráfján, azt a v illetve nevezzük. gráfban illetve egy által feszített rész(hiper)gráfot Egy volt. Amennyiben gyökérpontja továbbra is ebben az esetben Egy R-beli R-ben, G = (V, E, E) páros gráfot hiperéle közt futnak, melyekre igaz, hogy v ∈ A. Adott ⊂V G = (V, E) gráfon illetve D = (V, E) irányított gráfon legyen ∅ 6= X, Y ⊂

diszjunkt halmazokra λG (X, Y ) := min{dG (Z) : Y ⊆ Z, Z ∩ X = ∅}, (1.12) http://www.doksihu 13 1. Fejezet : Bevezetés illetve λD (X, Y ) := min{ρD (Z) : Y ⊆ Z, Z ∩ X = ∅}. Ez Menger tétele szerint megegyezik az (1.13) X -b®l Y -ba futó éldiszjunkt (irányított) utak maximális számával. 1.15 Matroidok Az M = (S, F) matroidnak nevezzük, ha párt S véges halmaz, és F ⊆ 2S -re teljesül : 1. ∅ ∈ F, 2. ha X ⊆ Y ∈ F, 3. minden akkor X ⊆ S -re az X ∈ F, X -ben tovább nem b®víthet® F beli halmazok azonos elemszámúak. A 3. feltételben szerepl® elemszámot az ban) r(X)-szel jelöljük. elemeinek rendszerét hogy F M elemeit X halmaz rangjának nevezzük, és (általá- független halmazoknak nevezzük. bázisának nevezzük, és B -vel F maximális jelöljük. Nyilván teljesül, F = {F ⊆ S : ∃B ∈ B : F ⊆ B}. Egy M = (S, F) elemét elhagyva Egy matroid C −c M = (S, F) F ∈ F -re

van Legyen H -nak köre egy olyan C⊆S halmaz, melynek tetsz®leges c már független. matroid eleme vágása egy olyan F -ben, azaz H H ⊆ S elemeit törölve halmaz, melyre minden M rangja csökken. G = (V, E) irányítatlan gráf, l ∈ Z, és m : V Z+ , hogy minden uv ∈ E élre teljesül az m(u) + m(v) ≥ ` (1.14) egyenl®tlenség. Ekkor a G, `, m által meghatározott számolgatós (count) matroid függetlenjeit az F := {F ⊆ E : ∀X ⊆ V iF (X) ≤ m(X) − `, ha iF (X) ≥ 1} elemei adják. (Ezek tényleg egy matroid függetlenjei) Az így kapott matroidot jelöljük M (G, `, m)-mel. (1.15) M = (E, F) http://www.doksihu 14 1.2 Tételek Amennyiben m ≡ k , és l = k , akkor M (G, `, m) pont G grakus matroidjának k -szorosa, amelyben az élek egy részhalmaza pontosan akkor független, ha felbomlik k erd® uniójára. Az m ≡ 2, és l = 1 esetben M (G, `, m)-et G merevségi Legyen E∈ H = (V, E) irányítatlan hipergráf,

l ∈ Z, és matroidjának nevezik. m : V Z+ , hogy minden élre teljesül az m(E) ≥ ` (1.16) egyenl®tlenség. Ekkor a H, `, m által meghatározott számolgatós (count) matro- id függetlenjeit az F := {A ⊆ E : ∀X ⊆ V iA (X) ≤ m(X) − `, ha iA (X) ≥ 1} (1.17) elemei adják. (Ezek tényleg egy matroid függetlenjei) Az így kapott matroidot jelöljük Amennyiben idjának k M = (E, F) M (H, `, m)-mel. m ≡ k , és l = k , akkor M (H, `, m) pont H k -szorosa, hipergrakus matro- amelynek egy részhalmaza pontosan akkor bázis, ha felbomlik feszít® hiperfa uniójára, ahol feszít® hiperfának a hiperélek olyan részhalmazát nevezzük, melyekre helyettesíthet® minden hiperél valamely két csúcsa közti éllel, hogy a kapott gráf feszít® fa legyen. Amennyiben tartozó m ≡ 1, és l = 0, akkor transzverzális matroid. (Egy matroid függetlenjeit azon F ⊆ T M (H, `, m) pont G = (S, T, E) H illeszkedési gráfjához páros

gráfra a transzverzális halmazok alkotják, melyekre F bepárosítható S -be.) 1.2 Tételek Ebben a szakaszban a témához tartozó néhány alapvet® tételt tekintünk át, melyek szerepelnek a Poliéderes kombinatorika tárgy anyagában [6]. Ezeket itt nem bizonyítjuk. 1.21 Tétel A szub- és szupermoduláris poliéderek, valamint a bázis-poliéderek mind g-polimatroidok. http://www.doksihu 15 1. Fejezet : Bevezetés (p, b) p-t paramoduláris párra, ha akkor a kapott (p0 , b0 ) és b-t megszorítjuk valamely pár is paramoduláris, így Q(p0 , b0 ) ∅ 6= S 0 ⊆ S -re, g-polimatroid, s®t igaz az alábbi tétel. 1.22 Tétel (Vetítési tétel) A polimatroid vetülete a p és b függvények T ⊂ S (p, b) paramoduláris párhoz tartozó mentén az a S 0 = S − T -re vetület bármely egész eleme el®áll Q(p0 , b0 ) g- p0 b0 g-polimatroid, amelyre való megszorításai. Egészérték¶ Q(p, b) Q(p, b) (p, b) és esetén a egy

egész elemének vetületeként. A vetítési tételb®l rögtön következik az alábbi állítás. 1.23 Állítás A Ha p és b (p, b) Q(p, b) paramoduláris párral adott egészérték¶, akkor Q(p, b) g-polimatroid nemüres. tartalmaz rácspontot. A következ® tételb®l következik, hogy a dolgozatban bázis-poliéderekre kapott tételek és algoritmusok mind átvihet®ek g-polimatroidokra. 1.24 Tétel Legyen s∗ egy új elem az ramoduláris párra az b∗ (X) := Ekkor S∗   S -en részhalmazain deniáljuk a b(X), ha X ⊆ S,  −p(S − X), ha s∗ ∈ X. b∗ (S) = 0, b∗ kívül, és legyen szubmoduláris, és b∗ S ∗ := S + s∗ . (p, b) pa- függvényt a következ®képpen : (1.18) Q(p, b) a B(b∗ ) bázis-poliéder vetülete s∗ mentén. 1.25 Tétel Egy Q g-polimatroid alsó határfüggvénye az a telmezett függvény, mely A ⊆ S -en Q fels® határfüggvénye az a bS a b(A) = max{z(A) : z ∈ Q} ∨ =

B(b ). részhalmazain ér- p(A) := min{z(A) : z ∈ Q} értéket veszi fel. részhalmazain értelmezett függvény, mely A ⊆ S -en értéket veszi fel. 1.26 Tétel (Reszelési tétel) jesen szubmoduláris, továbbá a pS b metsz® szubmoduláris függvény alsó reszeltje tel- S(b) = S(b∨ ), s®t ha B(b) nemüres, akkor B(b) = http://www.doksihu 16 1.2 Tételek 1.27 Tétel (Teljes reszelési tétel) b keresztez® szubmoduláris függvény teljes akkor nemüres, olyan keresztez® szubmoduláris függvény, amelyre b(S) = 0 s®t ha ↓ B(b) = B(b ). 1.28 Tétel Legyen és S(b) = S(b↓ ), B(b) alsó reszeltje teljesen szubmoduláris, továbbá B(b) b nemüres. Ekkor b↓ (Z) = min{b(F ) : F Z -(S − Z) 1.29 Tétel (Bázispoliéder metszettétel) Legyen két bázis-poliéder, melyekre b1 (S) = b2 (S) =: k . csak akkor nemüres, ha minden Az fa-kompozíció}. B1 = B(b1 ) M := B1 ∩ B2 és B2 = B(b2 ) metszet akkor és X ⊆ S -re b1

(X) + b2 (S − X) ≤ k. Ha b1 és b2 0 Legyen B1 =: k . Az (1.19) egészérték¶, és 0 = B (p1 ) M := B1 ∩ B2 0 és B2 M nemüres, akkor 0 = B (p2 ) M tartalmaz rácspontot. két bázis-poliéder, melyekre p1 (S) = p2 (S) = metszet akkor és csak akkor nemüres, ha minden X ⊆ S -re p1 (X) + p2 (S − X) ≥ k. Ha p1 és p2 egészérték¶, és (1.20) M nemüres, akkor M tartalmaz rácspontot. http://www.doksihu 2. fejezet Halmazrendszerekr®l szóló tételek Ebben a fejezetben olyan halmazrendszerekr®l szóló tételeket vizsgálunk, melyek jól használhatóak keresztez® (és metsz®) szub- és szupermoduláris függvények vizsgálatakor. Éppen ezért itt f®leg keresztez® és keresztezés mentes halmazrendszerekr®l lesz szó, aminek többek közt az az alapja, hogy, mint kés®bb látni fogjuk, adott z vektorra amelyre z(X) ≤ b(X) teljesül minden X ⊆ S -en resztez® (vagy metsz®) szubmoduláris függvénnyel a pontos, azaz

valamilyen b ke- z(X) ≤ b(X)-et egyenl®séggel teljesít® halmazok keresztez® (illetve metsz®) rendszert alkotnak, amib®l általában szeretnénk egy keresztezés mentes (illetve lamináris) részt kiválasztani, mellyel még tovább dolgozunk. 2.1 Halmazrendszerek gráfja A V alaphalmazon fekv® irányított gráfot, ahol F halmazrendszerhez rendeljük azt a E = {uv : nincs uv -halmaz F -ben}. G(F) = (V, E) Ebben a szakaszban [9] állításait bizonyítjuk halmazrendszerek gráfjáról. Ezen állítások bizonyítása egyszer¶, de egy kicsit számolgatós, így a cikkben csak részben vannak bizonyítva 2.11 Állítás Ha él ∅, V ∈ F , és F halmazgy¶r¶, akkor F = {X ⊆ V : nem lép ki G(F)-ben X -b®l}. Bizonyítás: X ∈ F -re X -b®l ∈ X, v ∈ V − X -re uv Jelölje Xuv az nem léphet ki él halmaz, így F -beli uv -halmazt, F ⊆ {X ⊆ V : G(F)-ben, mivel nem lép ki él amennyiben van. Ekkor ha X minden u ∈

G(F)-ben X -b®l}. X -b®l nem lép ki él http://www.doksihu 18 2.1 Halmazrendszerek gráfja G(F)-ben, S T = akkor minden Xuv ∈ F, u ∈ X, v ∈ V − X -re mivel F halmazgy¶r¶, van V uv -halmaz F -ben, és így X = {X ⊆ V : véges alaphalmaz. Így u∈X v∈V −X G(F)-ben X -b®l} ⊆ F . nem lép ki él 2.12 Állítás Ha az F F0 metsz® rendszer a F := { halmazrendszer, melyre halmazrendszer} az F Bizonyítás: Jelölje F ⊆ F ∗, 0 S V A : A ⊆ F0 F∗ az F 0 -t és ∩ A2 = G(F 0 ) = G(F). tartalmazó egyik legsz¶kebb halmazgy¶r¶t. Ekkor F∗ zárt az unióképzésre. Másrészt F S zárt a metszet A1 , A2 ∈ F , ahol (i = 1,2-re) Ai = Ai , akkor A1 ∩ S (A1 (∩)A2 ), A1 ∪ A2 = A0 . Itt A1 (∩)A2 := {A0i ∩ A00j : A0i ∈ A1 , A00j ∈ ∈ A2 } ⊆ F 0 , ∅ ∈ F 0, akkor az diszjunkt halmazokból álló és az unióképzésre, mivel ha S ∅ ∈ F 0, alaphalmazon, és -t tartalmazó legsz¶kebb

halmazgy¶r¶, továbbá F 0 ⊆ F ∗, mivel  mivel amennyiben valamely A0i és ha pedig metsz®k, akkor használhatjuk diszjunktak, mivel Ai A00j F nem metsz®, akkor metszetük A1 (∩)A2 elemei S így (A1 (∩)A2 ) ∈ metsz® voltát. rendszerek diszjunkt halmazokból állnak, 0 ∈ F . Továbbá A := a (V, A1 ∪ A2 ) hipergráf összefügg® komponenseinek rendszere, ami diszjunkt részrendszere F -nek, mivel a komponensek metsz® F -beli halmazok uniójából állnak, továbbá nyilván diszjunkt halmazokból áll. Így F 0 -t F ∗ ⊆ F, F∗ = F. amib®l A bizonyításból azt is látjuk, hogy a legsz¶kebb tartalmazó halmazgy¶r¶ egyértelm¶. Az állítás második felét abból kapjuk, hogy akkor és csak akkor van F -ben, ha F 0 -ben van ilyen, mivel F 0 -beliek uniójaként, így azon u, v alkotó unió u-t tartalmazó tagja 2.13 Állítás Ha az F0 F 00 metsz® rendszer, továbbá Ekkor 0 Jelölje F ⊆ F ∗ F∗ ,

mivel F ⊆ F, továbbá az párokra, melyekre egy F 0 := { T V halmazok el®állnak F ∈ F uv -halmaz, az F -et  alaphalmazon, és A : A ⊆ F 00 } az F 00 -t ∅, V ∈ F 0 , akkor az tartalmazó legsz¶kebb G(F 00 ) = G(F 0 ). az F 00 -t 00 F ⊆ F ∗ tartalmazó egyik legsz¶kebb metsz® rendszert. , és F∗ metsz®, így metsz® halmazok metszetét tartalmazza, és tartalmazza diszjunktakét is, mivel rendszer, mivel ha F -beli uv -halmaz F 0 -beli uv -halmaz. keresztez® rendszer a halmazrendszer, melyre Bizonyítás: 0 A1 , A2 ∈ F 0 ∅ ∈ F 00 . átmetsz® halmazok, továbbá (i Másrészt F0 metsz® = 1,2-re) Ai = T Ai , http://www.doksihu 19 2. Fejezet : Halmazrendszerekr®l szóló tételek akkor A1 ∩ A2 = T (A1 ∪ A2 ), ami nyilvánvaló, és T A1 ∪ A2 = A1 (∪)A2 := {A0i ∪ A00j : A0i ∈ A1 , A00j ∈ A2 } ⊆ F 00 , (A1 (∪)A2 ). Itt mivel amennyiben valamely A0i és A00j diszjunkt lenne, akkor A1 és

A2 is az lenne, különben pedig A0i ∪ A00j ∈ ∈ F 00 , mivel ha az egyik tartalmazza a másikat, akkor ez nyilvánvaló, ha az unió V , akkor következik V ∈ F 00 -b®l, ha pedig kereszteznek, akkor következik F 00 keresztez® rendszer voltából. Így F 00 -t F ∗ ⊆ F 0, amib®l F ∗ = F 0. A bizonyításból azt is látjuk, hogy a legsz¶kebb tartalmazó metsz® halmazrendszer egyértelm¶. uv -halmaz Az állítás második felét abból kapjuk, hogy akkor és csak akkor van F 0 -ben, ha F 0 -beliek F -et F 00 -ben van ilyen, mivel metszeteként, így azon alkotó metszet v -t 00 F ⊆F u, v 0 , továbbá az F 0 -beli halmazok el®állnak párokra, melyekre egy nem tartalmazó tagja Nem ko-diszjunkt halmazok metszete F ∈ F uv -halmaz, F 0 -beli uv -halmaz. F 00 -ben az  van, amennyiben F 00 keresztez®, így a fenti állításnak igaz az alábbi er®sítése. 2.14 Állítás Ha az az az F0 F 00 -t F 00 keresztez®

rendszer a halmazrendszer, melyre F 0 := { T V alaphalmazon, és A : A ⊆ F 00 ∅, V ∈ F 0 , akkor ko-diszjunkt halmazokból áll} tartalmazó legsz¶kebb metsz® rendszer, továbbá G(F 00 ) = G(F 0 ). 2.2 Lamináris és keresztezés-mentes halmazrendszerek fa-reprezentációi Ebben a szakaszban áttekintjük a lamináris és keresztezés-mentes halmazrendszerek reprezentálásáról szóló tételeket. Belátjuk, hogy lamináris halmazrendszer reprezentálható feny®vel, keresztezés-mentes halmazrendszer pedig reprezentálható irányított fával. 2.21 Lemma Legyen F ⊆ 2V többször is szerepelhet. Ekkor hogy csúcsaiba V F lamináris halmazrendszer, melyben egy halmaz reprezentálható egy olyan F = (U, A) leképezhet®, oly módon, hogy az éleihez tartozó alapvágások által adott halmazok ®sképei, a multiplicitásokat gyelembe véve, pont Bizonyítás: feny®vel, F -et A tételt elég arra az esetre bizonyítanunk amikor többszörös

elemei, mivel a feny® F ∈ F -et adják. F -nek reprezentáló élét további nincsenek k csúccsal http://www.doksihu 2.2 Lamináris és keresztezés-mentes halmazrendszerek 20 fa-reprezentációi felosztva F +k·F A feny®nek inek : |F| + 1 csúcsa lesz, ezeket egy kivételével megfeleltethetjük F F ∈ F -hez ahhoz az uF reprezentációját kapjuk. uF tartozzon az csúcs, a plusz csúcs pedig legyen csúcshoz rendelünk, melyre maz, illetve ha v -t nem tartalmazza F A feny® éleit úgy kapjuk, hogy u0 -ba F a minimális v -t uF -be Egy tartalmazó egy halmaza sem, akkor nem fut él, u0 . eleme- v ∈ V -t F -beli hal- v -t u0 -hoz rendeljük. pedig egy él fut : abból az uG -b®l, ahol G a minimális olyan halmaz F -ben, melyre F ⊂ G, illetve ha nincs ilyen akkor az élet u0 -ból vezetjük uF -be (lásd 2.1 Ábra) Látható, hogy a kapott gráf- 2.1 ábra Lamináris rendszer reprezentálása feny®vel ban minden csúcs

befoka 1, és mivel mindenkibe egy t®le b®vebb halmazból fut él, ezért az éleken visszafele haladva valamikor azaz u0 -ból u0 -ba jutunk tetsz®leges uF -b®l indulva, minden más csúcs elérhet®, azaz tényleg feny®t kaptunk. A denícióból látszik, hogy az uF -be belép® élhez tartozó alapvágás ®sképe F.  Azt is láthatjuk, hogy minden csúcs annyiadik szintjére képz®dik a feny®nek, ahány F -beli halmaz ®t tartalmazza, ha az Ha egy keresztezés-mentes tetsz®leges v ∈V F u0 -at tekintjük a nulladik szintnek. halmazrendszert úgy megváltoztatunk, hogy egy elemet tartalmazó halmazokat komplementerükre cserélünk, ak- kor lamináris rendszert kapunk, mivel ennek az F0 halmazrendszernek ha lenne két metsz® tagja, akkor ezek kereszteznének is. Mivel keresztez® halmazok közül ha az egyiknek (vagy akár mindkett®nek) a komplementerét vesszük akkor a kapott halmazok továbbra is kereszteznek, ezért a fentiek ellent mondanának

annak, hogy keresztezés-mentes. F0 F feny®-reprezentációjában ha a komplementált halmazokba http://www.doksihu 21 2. Fejezet : Halmazrendszerekr®l szóló tételek futó éleket megfordítjuk, akkor 2.22 Tétel Legyen F ⊆ 2V F -nek keresztezés-mentes halmazrendszer, melyben egy hal- maz többször is szerepelhet. Ekkor fával, hogy csúcsaiba V kapjuk az alábbi, fa-reprezentációját : F reprezentálható egy olyan F = (U, A) irányított leképezhet®, oly módon, hogy az éleihez tartozó alapvágások F -et által adott halmazok ®sképei, a multiplicitásokat gyelembe véve, pont adják. A fát úgy is lerajzolhatjuk, hogy egy szintre rakjuk azokat a csúcsokat, melyek ugyanannyi alapvágásban vannak benne. Ebben a lerajzolásban minden él pont egy szintet lép fel, mivel azt a csúcsot, ahova az él mutat, eggyel több alapvágás tartalmazza, mégpedig az él alapvágása. A fenti tételt sok helyen alkalmazhatjuk. Segítségével például

bizonyítható a Lucchesi-Younger-tétel [16], a 2.41 Tétel, és az alábbi lemma is, mely a 321 Tétel bizonyításánál lesz hasznos. 2.23 Lemma K keresztezés-mentes kompozíciója V -nek. Ekkor K felbontható V partícióira és ko-partícióira. Bizonyítás: K Azt elég belátnunk, hogy elemei közül kiválasztható egy partíció vagy egy ko-partíció, mivel ennek törlése után ismét kompozíciót kapunk. Vegyük K fa-reprezentációjának szintezett lerajzolását. Mivel K kompozíció, így, mivel adott szinten lév® fa csúcsok ®sképeit ugyanannyi F -beli halmaz tartalmazza, vagy a legalsó vagy a legfels® szint csúcsainak ®sképe mind ∅. lév® csúcs ®sképe üres, akkor a bel®le induló élekhez tartozó Ha a legalsó szinten F -beli halmazok V partícióját adják, ha pedig a legfels® szinten lév® csúcs ®sképe üres, akkor a belé futó élekhez tartozó F -beli halmazok V ko-partícióját adják.  2.3

Kikeresztezés Adott V alaphalmazon értelmezett F halmazrendszerb®l keresztezés-mentes (il- letve lamináris) rendszert kaphatunk úgy, hogy a rendszer néhány fontos tulajdonsága megmaradjon, ha a keresztez® (illetve átmetsz®) párokat rendre lecseréljük a metszetükre és az uniójukra. Az eljárás véges, mivel a rendszerben szerepl® halmazok száma nem változik, és a halmazok méretének négyzetösszege szigorúan monoton http://www.doksihu 22 2.3 Kikeresztezés n®. Az alábbi állítás mutatja, hogy O(|F|2 ) kikeresztezési lépés után az eljárás véget ér. Egy kikeresztezési lépés átlagosan mindig egy F ∈F O(|F||V |) id®ben hajtható végre úgy, hogy halamazhoz keresünk ezt keresztez® halmazt, és ha nem találunk ilyet, akkor az alábbi állítás miatt ezt kés®bb nem kell vizsgálnunk. Mivel két halmaz keresztez® voltának ellen®rzése O(|V |) idej¶, így O(|F|) ellen®rzés O(|F||V |) id®ben végrehajtható, így az

algoritmus összideje 2.31 Állítás Ha A és B O(|F|3 |V |). két nem keresztez® (illetve nem átmetsz®) halmaz a V alaphalmazon, akkor teljesülnek az alábbiak. 1. Tetsz®leges heti át) C -re A∪C A∩C közül legfeljebb egy keresztezheti (illetve metsz- B -t. A és C A∪C és A∩C és B 2. Ha és kereszteznek (illetve átmetsz®k), és C nem keresztezi egyike sem keresztezheti (illetve metszheti át) B -t, akkor B -t. Bizonyítás: 1. Ha A diszjunkt, akkor A∩C mindenképpen diszjunkt B -t®l, így nem keresztezi (illetve nem metszi át). Ha A ⊆ B, akkor A ∩ C ⊆ B, így nem keresztezi (illetve nem metszi át). Ha B ⊆ A, akkor B ⊆ A ∪ C, így nem keresztezi (illetve nem metszi át). Ezzel a nem átmetsz® eset bizonyítása véget ért, a nem keresztez® esetben még az alábbi eset van : Ha A∪B =V, akkor (A ∪ C) ∪ B = V , 2. Az el®z® pontban leírtakat kapjuk, hogy A∪C és A A∩C és C A és

B diszjunkt és B ⊆ C, (b) A és B diszjunkt és C ∪B =V (c) A⊆B B ⊆ C, felcserélésével is elmondhatjuk, és ebb®l (bár ekkor A⊆B és C ∪B =V B -t, ha a nem keresztez® esetben, A ⊆ C, így nem kereszteznek (illetve nem metszenek át)), (d) B -t. sem keresztezi (illetve metszi át) (a) és így nem keresztezi a nem keresztez® esetben, http://www.doksihu 23 2. Fejezet : Halmazrendszerekr®l szóló tételek (e) C és B diszjunkt és B ⊆ A, (f ) C és B diszjunkt és A∪B =V (g) C ⊆B és B ⊆ A, (bár ekkor a keresztez® esetben, C ⊆ A, így nem kereszteznek (illetve nem metszenek át)), (h) C⊆B és A∪B =V a nem keresztez® esetben. A maradék nyolc eset közül négy nem állhat fenn, mégpedig ha diszjunkt és A ⊆ B, mivel ekkor diszjunkt, illetve a nem keresztez® esetben, ha B⊆A és junkt és ha C ⊆ B, A B⊆C és illetve ha A∪B =V, C és B mivel ekkor és B A és C

∪B = V, disz- C is illetve A∪C =V. A maradék négy eset már könnyen elintézhet® : Ha A Ha A, C ⊆ B , A ∩ C Ha B ⊆ A, C , és C is diszjunkt akkor B -t®l, és A∪C akkor ez teljesül is részhalmaza B ⊆A∪C és A ∪ B -re és A ∩ B -re is. B -nek. B ⊆A∩C is teljesül. Ezzel a nem átmetsz® eset bizonyítása véget ért, a nem keresztez® esetben még az alábbi eset van : Ha A ∪ B = C ∪ B = V , akkor (A ∪ C) ∪ B = V , és (A ∩ C) ∪ B = V is teljesül.  Ezzel az állítás bizonyítását befejeztük. A kapott F0 rendszer minden pontot annyiszor fed, ahányszor az eredeti, így például kompozícióból kompozíciót kapunk. Hasznos még meggyelni, hogy ha keresztez® (illetve metsz®) rendszer egy részrendszere, F 0 F egy is az, továbbá, hogy ha a szub- illetve a szupermodularitási egyenl®tlenségeket minden kikeresztezési lépésnél felírjuk az alábbi állítást kapjuk. 2.32 Állítás Ha

b keresztez®n (illetve metsz®n) szubmoduláris függvény, akkor a kikeresztezési eljárással kapott szerre b(F) ≥ b(F 0 ). Ha p F0 keresztezés-mentes (illetve lamináris) halmazrend- keresztez®n (illetve metsz®n) szupermoduláris függvény, akkor a kikeresztezési eljárással kapott mazrendszerre F0 keresztezés-mentes (illetve lamináris) hal- p(F) ≤ p(F 0 ). Mint fent láttuk a kikeresztezési eljárás nálható jól, ha |F| O(|F|3 |V |) id®ben fut le, így akkor hasz- kicsi. Bernáth alábbi tétele alapján könnyen kiválasztható egy http://www.doksihu 24 2.3 Kikeresztezés F0 V alaphalmazon értelmezett F részrendszere, mely minden olyan tartalmaz keresztez® rendszernek egy olyan < v 1 , v2 > mazrendszer a F -beli rendezett párra, ahol v1 -et tartalmazó, de v2 -t elkerül® halmazt, mely párra F0 F 2.33 Tétel (Bernáth, [1]) Legyen V Pv . méret¶ v 1 , v2 ∈ V , tartalmaz ilyet. keresztez® (vagy speciálisan

metsz®) hal- alaphalmazon. Legyen minden nemüres halmazok rendszere O(|V |) Ekkor v ∈ V -re az ®t elkerül® S Pv ≤ 2|V | − 2. maximális v∈V Bizonyítás(*): A tételt |V | szerinti indukcióval bizonyítjuk. nincs ilyen nemüres halmaz. Jelölje az F nyomát |V | = 1-re nyilván A ⊆ V -n F ∩ A := {F ∩ A : F ∈ ∈ F}. V0 Tegyük fel, hogy a tétel teljesül minden olyan zett keresztezés-mentes halmazrendszerre, ahol keresztezés-mentes halmazrendszer egy n elem¶ 0 |V | < n, V alaphalmazon értelmeés legyen F tetsz®leges alaphalmazon, melyr®l feltehet- jük, hogy eleme az összes egy elem¶ halmaz, mivel ezeket hozzávéve a keresztezésmentesség nem romolhat el, és S Pv nem csökken. v∈V Legyen v0 ∈ V -re Pv0 = {V1 , V2 , ., Vk }, mind elkerülik v0 -at, mely rendszer tagjai diszjunktak, mivel így ha lenne köztük kett® metsz®, akkor helyettük vehetnénk az uniójukat, amely az egyiküknél b®vebb lenne, ami

ellentmond a maximalitásnak. Mivel feltettük, hogy az egy elem¶ halmazok v 6= v0 esetén van v -t k S Vi = V − v0 . tartalmazó, i=1 Alkalmazzunk indukciót v0 -at F -ben v ∈ V -re vannak, azaz minden elkerül® halmaz, így van maximális is, azaz Vi -n Fi := F ∩ Vi -re. Legyen tehát minden v ∈ Vi -re i az ®t elkerül® maximális Fi -beli nemüres halmazok rendszere Pv . Ekkor indukció Pvi ≤ 2|Vi | − 2. v∈Vi Vi maximalitása miatt A S szerint ∩F =A vagy része legfeljebb egy olyan Vi ∩ F = A, akkor ∈ Fi -re a maximális olyan A eleme lehet melyre a maximális olyan F ∈ F halmaz, amelyre vagy tartalmazza v0 -t, v0 -t. mivel különben, ha ami ellentmond A1 A ∈ Pvi , akkor a hozzá tartozó maximális F vagy tartalmazza, vagy elkerüli. Így F Vi ∩ v ∈ Vi -re Pvi -nek tartalmazza mivel az halmaz, melyre Így tetsz®leges Vi -nek, v 6∈ A1 ∪ A2 ∈ Fi , ∈ F }), F ∈F által elkerült Pv = Aj -ket és A2

A1 és A2 is ilyen halmaz lenne, maximalitásának. Ha van ilyen Aj ∈ Pv0 -at S − {A} ∪ {F } ∪ ( {Aj ∈ Pv0 : Aj 6∈ a maximalitás miatt a többi Pvi nem tartalmazhatja b®vebb v -t elkerül® http://www.doksihu 2. Fejezet : Halmazrendszerekr®l szóló tételek halmaz, mivel a v0 -at Aj és így keresztezné A ∈ Fi -re nek, akkor v0 -at nem tartalmazó volta miatt tartalmazná, F -et, ami ellentmondás. Hasonlóan bizonyítható, hogy ha minden F ∈ F halmaz, melyre Vi ∩ F = A vagy része Vi S ∪ {Fi } ∪ ( {Aj ∈ Pv0 : Aj 6∈ Fi }), ahol Fi a maximális v0 -at a maximális olyan Pv = tartalmazó, de [ maximális 25 Pvi Ai -t elkerül® halmaz. A fentiekb®l kapjuk, hogy Pv − Pv0 ≤ [ Pvi ∪ {Fi } ≤ 2|Ai | − 1, v∈Ai v∈Ai amib®l [ Pv ≤ |Pv0 | + k [ X Pv − Pv0 ≤ k + (2|V − v0 | − k) = 2|V | − 2, i=1 v∈Ai v∈V mint állítottuk.  2.34 Megjegyzés 1 A bizonyításban igazából csak azt használtuk

ki, hogy F keresztez® elemeinek uniója is F -ben van, így a tétel ezzel a gyengített feltétellel is áll, mint azt Bernáth eredeti tétele is állította. 2. A tétel fenti bizonyítása lényegesen különböz® Bernáth eredeti bizonyításától, melyben ® azt látta be, hogy egy minimális nemtriviális (azaz legalább két elem¶) halmazt keresztez® halmazok száma nem nagyobb, mint a halmaz elemszámának a kétszerese mínusz kett®, így egy ilyen halmazt összehúzva indukcióval adódik a tétel. 2.4 S -T -elválasztó halmazrendszerek Ebben a szakaszban az alábbi tételre adunk bizonyítást. 2.41 Tétel Keresztez® S -T -elválasztó F halmazrendszerb®l kiválasztható egy S- Bizonyítás(*): Azt fogjuk bizonyítani, hogy a keresztezés-mentes minimális S- T -fa-kompozíció. T -elválasztó halmazrendszerek pontosan az El®ször megmutatjuk, hogy egy lasztható ki egy S -T -elválasztó S -T -fa-kompozíciók. S -T -elválasztó

keresztezés-mentes. keresztez® rendszerb®l hogy vá- http://www.doksihu 26 S -T -elválasztó 2.4 F S -T -elválasztó 2.42 Lemma (*). Legyen s ∈ S -re Fs ⊆ F az egyértelm¶ minimális halmazrendszerek keresztez® halmazrendszer. Jelölje Mst ∈ F st-halmazok (t végigfut T -n) hipergráfjának összefügg® komponenseinek rendszerét. Ekkor a [ G := Fs s∈S halmazrendszer keresztezésmentes G Bizonyítás: beli t-t S -T -elválasztó. deníciójából rögtön látszik, hogy tartalmazó halmaz, mely Fs G S -T -elválasztó, mert az deníciója szerint létezik minden Fs - t ∈ T -re, st-halmaz. Mivel minden s1 , s2 ∈ S, s1 6= s2 indirekten, hogy 1. eset : Ha s ∈ S -re Fs mellett F1 F2 és s2 6∈ F1 . elemei diszjunktak, a keresztezés-mentességet elég F1 ∈ Fs1 és F2 ∈ Fs2 halmazokra bizonyítani. Tegyük fel kereszteznek. t ∈ F1 ∩ T -re Ms2 t Ekkor egyben minimális s2 t-halmaz is a következ®

állítás miatt : 2.43 Állítás Ha s0 t-halmaz F ∈ Fs , és s0 ∈ S − F , akkor t ∈ F ∩ T -re Mst egyben minimális is. Bizonyítás: Mivel Mst ⊆ F 63 s0 így ez egyben viszont ha kisebb lenne, akkor az egy kisebb s0 t-halmaz st-halmaz is, így M s0 t része ennek, lenne, ami ellentmondana a  minimalitásnak. F1 -nek E miatt ha F1 alapján 2. eset : Ha Ms2 t F2 -nek F1 ∩ F2 F1 ⊆ F2 , mert a fentiek s2 ∈ F1 , elemei. akkor van olyan metszete egy kisebb Ugyanis ha van közös eleme, akkor elemei ugyanabban a komponensben vannak az íMs2 t halmazok hiper- gráfjában, mint és és s1 6∈ Ms2 t , akkor t ∈ F1 ∩ T , s1 t-halmaz s2 ∈ M s1 t . melyre Ekkor M s1 t lenne ellentmondásban a minimalitással. s1 6∈ Ms1 t ∪ Ms2 t , továbbá t a metszetben van, és s2 Ms1 t -ben benne van, míg Ms2 t -ben nincs, így Ms1 t és Ms2 t vagy kereszteznek, és akkor a metszet tényleg szerint mivel F -ben F1 és

F2 F -ben van, vagy van. Ha pedig M s2 t ⊂ M s1 t , s1 ∈ Ms2 t , akkor így a metszet Ms2 t ⊆ F2 , így M s2 t , ami deníció Ms2 t ⊆ F1 keresztez®k, így van olyan elem, amelyik nem eleme miatt és Ms1 t ∪ Ms2 t -nek,  így az el®z® gondolatmenet itt is elmondható. Az alábbi állítás rögtön következik az S -T -fa-kompozíció deníciójából : http://www.doksihu 27 2. Fejezet : Halmazrendszerekr®l szóló tételek 2.44 Állítás Ha F S -T -fa-kompozíció, akkor keresztezésmentes minimális S -T - elválasztó halmazrendszer. Most belátjuk, hogy az állítás megfordítottja is igaz. El®ször nézzük azt a speciális esetet, amikor F lamináris : 2.45 Állítás (*). Ha szer, akkor F S -T -fa-kompozíció, Bizonyítás: Ha S -T -elválasztó keresztezésmentes minimális halmazrend- s®t az ®t reprezentáló fa csillag, melynek közepe S. F ∈ F -re F ∩ S 6= ∅, akkor s ∈ F ∩ S -re és minden t ∈ F ∩ T

-re, F S -T -elválasztó volta miatt, van F -ben egy st-halmaz, mely a laminaritás miatt része F -nek, így viszont s0 ∈ S −F -re is ez s0 t-halmaz, így viszont F ellentmond a minimalitásnak. Így van ®t tartalmazó akkor F0 F T -nek egy partíciója, mivel F -beli, F S -T -elválasztó F -b®l. Így F kidobható lenne kidobható T F -b®l, ami minden elemére volta miatt, továbbá ha F 0 ⊆ F ⊆ S, tényleg reprezentálható a fent leírt csillaggal,  mint kívántuk. 2.46 Lemma (*). Ha szer, akkor F keresztezésmentes minimális S -T -elválasztó halmazrend- S -T -fa-kompozíció. Bizonyítás: Megadjuk a halmazrendszerhez tartozó fát. A fa csúcsai az atomok, azaz azon maximális diszjunkt halmazok, melyekb®l van maradék, amit semelyik F -beli Állítás miatt készen vagyunk. Mivel egyszerre az F minden eleme felépíthet®. Ha nem tartalmaz, akkor F S -T -elválasztó, F lamináris, így a 2.45 így egy atom sem metszheti S -et és

T -t is, mivel ha lenne a metszetben egy s illetve egy t elem is, akkor st-halmazt nem lehetne atomokból felépíteni. Az élek deniálásához szükségünk lesz az alábbi állításra : 2.47 Állítás F ∈ F -re egyértelm¶en létezik olyan A ⊆ T atom, hogy minden F -beli F 0 ⊆ F -re A 6⊆ F 0 . Bizonyítás: Van ilyen atom a minimalitás miatt, ugyanis különben hatnánk F -b®l, 1. eset : Ha F -et elhagy- így csak az egyértelm¶séget kell bizonyítani. F ∩ S = ∅, elhagyható lenne F -b®l, akkor és F atom, mivel F 0 ⊂ F -re F 0 6∈ F , mert ekkor F 0 ∈ F, F 0 ∩ F 6= ∅, F 0 ∩ V − F 6= ∅, F 6⊆ F 0 F0 esetén http://www.doksihu 28 S -T -elválasztó 2.4 S ⊂ F 0, F mivel s ∈ S, t ∈ T -re 2. eset : Ha egy A1 sem A2 miatt, minden s-et akkor indirekten bizonyítunk, azaz tegyük fel, hogy van atom is az állításbeli tulajdonsággal. Ekkor s ∈ F ∩ S -re azaz olyan, amely amely felesleges lenne,

mivel semely st-halmaz. F ∩ S 6= ∅, és egy F0 keresztezésmentes, viszont így halmazrendszerek s-et van s-et A1 -t®l A2 -t®l illetve A1 nem tartalmazza és amelynek A2 nem tartalmazza és amelynek A2 -t®l elválasztó F ∈ F1 elválasztó keresztezésmentes, mind tartalmazzák − F1 = S − F1 -re az A1 -et tartalmazó A2 A1 -et és A2 -t keresztezés-mentesség miatt, mivel Így viszont F1 F részhalmaza, és lecserélhetnénk F ∈ F -re, Az melyre F -hez mazból az A Minden és A1 -et A1 ∪ A2 - így mivel s ∈ (S ∩ F ) − F1 -et halmaz tartalmazza (S ∪ T ) − F ⊆ F1 ∩ Fs F F -nek, A1 -et s 6∈ F1 s 6∈ Fs . illetve  minimalitásának. egyértelm¶en létezik olyan 0 F ⊆F B⊂F 0 atom, hogy minden . eF tartozó irányított B ⊆ S él a fent deniált két halmaz közt fut : a B hal- halmazba. 2.49 Állítás Ha így deniáljuk az éleket, akkor a kapott irányított gráfban az halmazba

csak az Bizonyítás: − eF = BA F -be azért nem lép másik él, mert ha feltesszük, hogy egy eF 0 S − F -ben van, és F töve keresztez®k, így vagy F ⊂ F0 által tartalmazott atom így nem lehet F -t®l vagy eF 0 az eF 0 hogy B 6⊆ F 0 F0 ⊂ F. él kilép esetén F -b®l. eF 0 F -b®l és F B 6⊆ F , F 0 -t azaz 0 is belép metszik egymást, viszont nem F ⊂ F 0, akkor eF 0 hegye nem lehet F -be, ha pedig F 0 ⊂ F , akkor eF 0 ekkor sem léphet F -be, töve ami ellentmondás. nem léphet ki él, tegyük fel indirekten, hogy El®ször azt látjuk be, 0 deníciója szerint minden Ha nem lép be diszjunkt atom, így Annak bizonyításához, hogy −− = B 0 A0 F él lép be, és nem lép ki bel®le él. F -be, akkor mivel eF 0 F a halmazonként vett komplementerére alkalmazva kapjuk : F ∈ F -re 2.48 Állítás Fs elkerül® elhagyható lenne, ami ellentmond Az állítást 0 (S ∪ T ) − F -et. s-et halmaz,

részhalmaza. Van továbbá egy re az atomok rendszerében. Mivel ezek egyike sem részhalmaza F F -beli részhalmaza, illetve olyan halmaz, melyr®l feltehetjük, hogy nem metszi, mivel ha nem lenne ilyen, akkor F S -T -elválasztó volta eF 0 tartalmazó B ⊂ F 0. nem lép ki F -beli F 00 F -b®l, Ehhez megmutatjuk, ami ellentmodás. B0 B 0 -t, így halmaz tartalmazza http://www.doksihu 29 2. Fejezet : Halmazrendszerekr®l szóló tételek metszi F -et. B Ha hogy ne tartalmazza B -t, − F, F -b®l, mivel eF 0 kilép B F -et tartalmazó B 6= B 0 , mivel így F -beli miatt van A -t tetsz®leges miatt nem része F 0 -t, tehát , ami viszont azt jelentené, hogy (S ∪ T ) − F 0 ⊂ G. G F -et F ⊂ G. halmaz, mely nem tartalmazza egy ami ellentmond halmaz, mely A 0 volta deníciója keresztezésmentes, így nem is keresztezheti sem keresztezi, így, mivel Ekkor viszont B -t, G∈F B -t, F 00 F S -T -elválasztó Ekkor

viszont elválasztó F 0 -nek, viszont mivel F egyik sem tartalmazza, keresztezés-mentessége miatt így már B ⊆ F 0. s ∈ B -t®l F 00 -t, F ∪ F 00 6= S ∪ T . A0 ⊆ F 00 − halmaz, mely nem tartalmazza deníciójának. Láttuk tehát, hogy 0 00 akkor választhatjuk úgy így ekkor F 00 6⊆ F . F F ⊂ F csak az az eset maradt, hogy olyan F 0 -nek, nem lenne részhalmaza G egy olyan ami ellentmond B B0 ⊆ G ∩ F , F -et és s-et F -beli tartalmazó  deníciójának. A fenti állítás miatt a kapott irányított gráf irányítatlan értelemben körmentes, tehát irányított erd®. Azt hogy összefügg® úgy mutatjuk meg, hogy éleinek száma a csúcsszámánál eggyel kevesebb, azaz maximális körmentes, tehát fa. Mivel az élek és F elemei között bijekció van, így az élek száma pont 2.410 Állítás eggyel több F keresztezésmentes halmazrendszer atomjainak száma legfeljebb elemszámánál. Bizonyítás: = F ∪ {F

}. F |F|. Indukcióval |F|-re : az állítás F0 Azt látjuk be, hogy |F| = 1-re nyilvánvaló. Legyen atomjainak a száma legfeljebb eggyel több atomjainak a számánál, amib®l indukció miatt következik az állítás. legalább 2-vel több atomja nek, mégpedig A1 -et és F -nél A2 -t. ha F F -t, mivel F 0 -nek van Ekkor viszont F -ben F -nek tagja, az uniójukon kívül van elem például A1 -ben, melyet nem tartalmaz kell, hogy legyen olyan eleme, van A2 -ben, F -en és F0 F. F- eleme, keresztezi kívüli mégpedig F 0 -nek F -nek úgy lehet A1 -et tartalmazza, viszont így F A1 -ben s®t F 0 metszi, de nem tartalmazza két atomját mely ezek közül pont az egyiket, például 0 F0 = A2 -beli is van olyan eleme   Ezzel a Lemma bizonyítását befejeztük. A 2.42 Lemmából és a 246 Lemmából egy algoritmikus bizonyítást kapunk az alábbi tételre. A 2.41 Tétel bizonyítása : A 242 Lemmában kapott malizálva a

2.46 Lemma szerint S -T -fa-kompozíciót G halmazrendszert mini- kapunk.  http://www.doksihu 30 2.4 S -T -elválasztó Amennyiben rendelkezésre áll egy adott s ∈ S, t ∈ T -re halmazrendszerek a minimális meghatározó orákulum, akkor a 2.42 Lemma algoritmust is ad O(|S||T |)-szer hívja meg a minimális st-halmazt G st-halmazt el®állítására. Ez meghatározó orákulumot, illetve keres® algoritmust futtat a kívánt hipergráfokon, melyek futási ideje adott = (V, E) O( P |E| + |V |), O(|S|2 |T |2 )-tel. G minimaliE∈E zálását mohón elvégezhetjük, ha van egy táblázatunk, melyben tároljuk, hogy adott hipergráfon s ∈ S, t ∈ T -re hány st-halmaz ha minden általa elválasztott s ∈ S, t ∈ T -kre az ilyen szintén O(|S|2 |T |2 ) van ami becsülhet® H = G -ben. Egy halmazt akkor dobhatunk ki s ∈ S, t ∈ T -re G -b®l, ez a szám nagyobb, mint egy. Ekkor csökkentsük a számot eggyel és dobjuk ki a halmazt.

Ez idej¶. 2.411 Megjegyzés A 241 Tétel bizonyítható a 222 Tétel segítségével is úgy, hogy egy keresztezés-mentes S -T -elválasztó halmazrendszernek elkészíjük a fa- reprezentációját, és ennek segítségével csökkentjük a rendszer elemszámát, amíg a rendszer S -T -fa-kompozíció nem lesz. 2.412 Megjegyzés Az 128 tétel mutatja, hogy a teljes reszelt kiszámításához hasznos lehet, az itt leírt fa-kompozíció-algoritmus. Ezzel a továbbiakban nem foglalkozunk, helyette más algoritmust adunk a teljes reszelt kiszámítására http://www.doksihu 3. fejezet Általános tételek és algoritmusok Ebben a fejezetben a poliéderes kombinatorika témaköréhez tartozó messzemen®en általános tételeket és algoritmusokat tekintünk át. Az itteni eredményeket a 4 fejezetben irányítási tételekhez és algoritmusokhoz fogjuk felhasználni. 3.1 Metsz® szubmoduláris függvények reszelése Ebben a szakaszban bemutatjuk a [9] cikkben leírt

reszel® algoritmust, mely kiszámítja egy ⊆S S -en értelmezett metsz® szubmoduláris függvény reszeltjét egy halmazon, és megad egy (1.4) jobb oldalát minimalizáló partíciót F(b∨ ) = { A reszelt deníciójából látható, hogy S A : A ⊆ F(b) halmazokból álló halmazrendszer}, ami a 2.12 Állítás szerint a legsz¶kebb halmazgy¶r¶. Láttuk, hogy erre A Reszelési tételb®l látható, hogy így S0 ⊆ ∨ ∨ Q(p, b ) = S(b ) = S(b) F(b)-t diszjunkt tartalmazó G(F(b)) = G(F(b∨ )). p ≡ −∞-re p és b∨ paramoduláris párt alkot, g-polimatroid, és így az 1.25 Tétel szerint b∨ (A) = = max{z(A) : z ∈ S(b)}. Tehát olyan algoritmusra van szükségünk, mely z ∈ S(b)-re maximalizálja a z(A)-t. Ezt az alábbi mohó algoritmus megoldja, amennyiben rendelkezésre áll egy olyan minimalizáló orákulum, mely tetsz®leges számolja min{b(Z) − a(Z) : Z ⊆ X} a ∈ RS vektorra, és X⊆S értékét, továbbá megad

egy Z halmazra ki- halmazt, ahol a minimum felvétetik. Tegyük fel továbbá, hogy rendelkezésünkre áll a ∨ = G(F(b )) gráf, melyet a minimalizáló vel azt kell eldönteni minden s, t ∈ S -re, G(F(b)) = orákulummal könnyen el®állíthatunk, mihogy van-e st-halmaz, ami megtehet® a http://www.doksihu 32 3.1 Metsz® szubmoduláris függvények reszelése min{b0 (Z) : Z ⊆ S − t} nagyobb, mint b vektoron, mely értéke s-en maximális értéke, mindenütt máshol pedig 0. 3.11 Algoritmus (Reszel® algoritmus) szubmoduláris függvény, Kimenet : a érték kiszámításával olyan ∨ b (A) A⊆S Bemenet : b : 2S R ∪ {∞} metsz® halmaz. értéke, és egy P partíciója A-nak, mely (1.4) jobb oldalát mini- malizálja. El®készület : A 2.11 Állítás alapján, mivel F(b∨ ) halmazgy¶r¶, ellen®rizhetjük, hogy b∨ (A) véges- e, és amennyiben az, azaz lép ki él elkészíthetjük A A-ból, A = {u1 , u2 , ., u|A| }

elemeinek egy olyan b({u1 , u2 , ., ui }) < ∞ lépett ki G(F(b)) = G(F(b∨ ))-ben A-ból, minden akkor legyen i = 1,2, ., |A|-ra, u1 := u, és A akkor könnyen sorbarendezését, hogy uv mégpedig úgy, hogy ha az él többi elemét rendezzük sorba tetsz®lege- sen. Mohó algoritmus : Fusson i 1-t®l |A|-ig z(ui ) := min{b(B) − z(B − ui ) : B ⊆ {u1 , u2 , ., ui }, ui ∈ B}, minimalizáló orákulummal kiszámoljuk, és tároljuk azt a Bi értéket a halmazt, ahol a minimum felvétetik. Adjuk ki z(A)-t, és azt a P partícióját A-nak, melyet az (A, {Bi : i = 1,2, ., |A|}) hipergráf összefügg® komponensei adnak. 3.12 Állítás A Reszel® algoritmus jó Bizonyítás: z értékét A-n kívül deniáljuk −∞-nek, (vagy ha véges értéket akarunk akkor nagyon kicsinek), és így z ∈ S(b), mivel B ⊆ A-ra z(B) ≤ b(B), = max{i : ui ∈ B}-re z(ui∗ ) ≤ b(B) − z(B − ui∗ ), és mivel B 6⊆ A-ra z(B) = −∞ i∗

:= (illetve elég kicsi). Belátjuk, hogy zP következik az, hogy > z(A), minden elemén pontos, azaz z(A) akkor van olyan maximális, mivel B ∈ P, Következik továbbá az is, hogy Legyen tehát melyre P B ∈ P -re z(B) = b(B). partíciója A-nak, z 0 (B) > z(B) = b(B), és így ha amib®l Ebb®l 0 z (A) > z 0 6∈ S(b). z(A) = b(P). B ∈ P . B , mivel hipergráf komponens el®áll mint néhány Bi halmaz uniója, ahol az unió vehet® halmazonként úgy, hogy mindig egy az addigiak unióját http://www.doksihu 33 3. Fejezet : Általános tételek és algoritmusok metsz® Bi -t uniózzuk a többihez. metsz® szubmoduláris, így B0 és b(Bi ) = z(Bi ) z(ui ) B 00 pontos halmazokra deníciója miatt. Mivel b z(B 0 ) + z(B 00 ) = b(B 0 ) + + b(B 00 ) ≥ b(B 0 ∪ B 00 ) + b(B 0 ∩ B 00 ) ≥ z(B 0 ∪ B 00 ) + z(B 0 ∩ B 00 ) = z(B 0 ) + z(B 00 ), amib®l B 0 ∩ B 00 és B 0 ∪ B 00 is pontosak. Így tehát B is pontos

lesz, mivel mint fent beláttuk el®áll úgy, hogy mindig két metsz® pontos halmazt uniózunk össze, aminek  az eredménye pontos halmaz. A reszel® algoritmus futásideje így polinomiális. Amennyiben delkezésre áll az el®készület O(|A|) már ren- id®ben végrehajtható, a mohó részben pedig a |A|-szor fut, !majd keres® |A| P ideje O |Bi | = O(|A|2 ). minimalizáló orákulum hipergráfon, melynek G(F(b)) algoritmus fut egy |A|-n adott i=1 A Reszel® algoritmus alkalmas metsz® szubmoduláris (és hasonlóan metsz® szupermoduláris) függvény által adott bázis-poliéder egy (amennyiben a függvény egészérték¶ rács)pontjának kiszámítására, ha azt A = S -re futtatjuk, és a kapott z vek- z(S) = b(S). Amennyiben z(S) 6= b(S), akkor, mivel z(S) ≤ b(S), z(S) < b(S), q P b(Si ) = z(S) < az algoritmus kiad egy olyan {S1 , S2 , ., Sq } partíciót, melyre torra és < b(S), ami miatt B(b) 3.13 Tétel Legyen i=1 üres. Ezzel

bizonyítást kaptunk az alábbi tételre b : 2S R∪{∞} metsz® szubmoduláris függvény. Ekkor B(b) akkor és csak akkor nemüres, ha S minden P partíciójára teljesül a b(P) ≥ b(S) (3.1) egyenl®tlenség. 3.2 Fujishige tétele algoritmikusan Ebben a szakaszban két algoritmust adunk Fujishige alábbi tételére. 3.21 Tétel (Fujishige [10]) Legyen melyre b(S) = 0. akkor nemüres, ha q X i=1 b(Si ) ≥ 0 Ekkor a S b minden b keresztez®n szubmoduláris függvény által meghatározott {S1 , S2 , ., Sq } B(b) S -en, bázis-poliéder akkor és csak partíciójára (3.2) http://www.doksihu 34 3.2 Fujishige tétele algoritmikusan és q X b(S − Si ) ≥ 0, (3.3) i=1 S azaz rövidebben érték¶, akkor minden B(b) P partíciójára vagy ko-partíciójára b(P) ≥ 0 Ha b egész- tartalmaz rácspontot. z ∈ B(b) tetsz®leges q P 0 = (q − 1)z(S) = z(S − Si ) ≤ Bizonyítás: A feltételek szükségessége következik abból,

hogy pontra ≤ q P 0 = z(S) = z(Si ) ≤ i=1 q P q P b(Si ), illetve i=1 i=1 b(S − Si ). i=1 Az elégségesség bizonyításához megadunk egy b-t esetén rácspont. z ∈ B(b) pontot, mely egész b0 -re az egyelem¶ halmazokon csökkentve a kapott z® szubmodularitás továbbra is érvényben marad, továbbá partíciót vagy ko-partíciót nevezzünk akkor pontosnak, ha 0 a kereszte- B(b ) ⊆ B(b). b(P) = 0. b Egy Minden P s∈ ∈ S -re b(s) esetleges csökkentésével, mely egészérték¶ b-re nyilván egész csökkentés, feltehet®, hogy {s} benne van egy pontos partícióban vagy ko-partícióban. Mivel az {s}-et tartalmazó ko-partíció csak az {{s}, S − s} lehet, mely egyben partíció is, így {s} benne lesz pontos partícióban, nevezzük ezt kell belátnunk, hogy minden z(S) = 0. Ps -nek. X ⊆ S -re z(X) ≤ b(X) Legyen z(s) := b({s}). teljesül, valamint azt, hogy Ennek belátásához érdemes kimondani az alábbi

állítást. 3.22 Állítás Bizonyítás: S tetsz®leges K-ra K kompozíciójára b(K) ≥ 0. a kikeresztezési eljárást alkalmazva kapunk egy mentes kompozíciót, melyre a 2.32 Állítás szerint b(K) ≥ b(K0 ). K0 szerint felbomlik partíciókra és ko-partíciókra, ezeken szerint, így K-n b K0 nemnegatív a tétel feltételei  X ⊆ S tetsz®leges halmaz. Alkalmazva KX := S s∈X a fenti állítást kapjuk, hogy 0 ≤ b(KX ) = X s∈X amib®l keresztezés- a 2.23 Lemma is. Legyen tehát ∪ {X}-re Azt z(X) ≤ b(X). (b(Ps ) − b({s})) + b(X) = 0 − z(X) + b(X), (Ps − {s}) ∪ http://www.doksihu 35 3. Fejezet : Általános tételek és algoritmusok A fentiekb®l azt is tudjuk, hogy z(S) ≤ b(S) = 0, zokból álló partícióra alkalmazva kapjuk, hogy és (3.2)-t az egyelem¶ halma- z(S) = P b({s}) ≥ 0.  s∈S A fenti bizonyításból algoritmust kaphatunk, a 3.11 Reszel® algoritmus segítségével, amennyiben b véges

érték¶. A reszeltet olyan számolni, melyet úgy kapunk, hogy S − s-re és megszorítjuk szubmoduláris, és b valamilyen b-t b0 függvényre szeretnénk ki- csökkentjük néhány egyelem¶ halmazon, s ∈ S -sel. Az így kapott b0 függvény metsz® minimalizáló orákulumából könnyen nyerhet® ennek is egy b-re minimalizáló orákuluma, mivel a vonatkozó minimum kiszámítása után még ezt össze kell hasonlítani az egy elem¶ halmazokon vett értékeivel Reszel® algoritmus tényleg ki tudja számolni b0 reszeltjét S − s-en, b0 − a-nak. Így a b véges és mivel érték¶, így az algoritmus els® felére nincs szükség. 3.23 Algoritmus (*). melyre Bemenet : b : 2S R keresztez® szubmoduláris függvény, b(S) = 0. z ∈ B(b), Kimenet : akkor egy olyan P mely ha b partíció, vagy ko-partíció, melyre Legyen S = {s1 , s2 , ., s|S| } Legyen b0 (X) := b(X) X ⊆ S -re. Fusson i Legyen 1-t®l egészérték¶,

akkor rácspont, illetve ha b(P) < 0. |S|-ig z(si ) := − min{b0 (P) : P és legyen B(b) = ∅, Psi S − si partíciója S − si -nek}, azon partíciója, melyre a minimum felvétetik. b0 ({si }) := z(si ). %Most ellen®rizzük, hogy z B(b)-ben van-e : min{b(Z) − z(Z) : Z ⊆ S} < 0, és a minimum egy X halmazon vétetik fel, AkS (Ps −{s})∪{X} kompozícióra alkalmazzuk a kikeresztezési eljárást, kor a KX := Ha s∈X és a keletkezett keresztezés-mentes 0 KX kompozíciót a 2.23 Lemma bizonyításában leírtak alapján partíciókra bontjuk. Ezen partíciók egyikén Az algoritmus a b-t O(|S|)-szer negatív. futtatja a reszel® algoritmust, majd egyszer futtatja minimalizáló orákulumot, és amennyiben esetben egy b B(b) nemüres itt megáll. Ellenkez® O(|S|2 ) méret¶ kompozícióra futtatja a kikeresztez® algoritmust, melyr®l a 2.3 szakaszban láttuk, hogy így idejét is. A futásid® így O(|S|7 ) idej¶. Ez majorálja a

hátralev® két lépés O(|S|2 θ + |S|7 ), ahol θ a minimalizáló orákulum futásideje. http://www.doksihu 36 3.2 Fujishige tétele algoritmikusan Láthatjuk, hogy a sért® partíció megtalálása bonyolult és lassú is, pláne annak tükrében, hogy a minimalizáló orákulum futási ideje a gyakorlatban |S|5 -nél keve- sebb. Egy egyszer¶ trükkel, melyet a [9] cikkben találunk, ez egyszer¶síthet®, s®t ez az algoritmus végtelen értékeket felvev® keresztez® szubmoduláris függvényeken is használható. A cikkben leírt teljes reszel® algoritmusban van egy kis, könnyen javítható hiba, amit az alábbi leírásban áthúzással jelöltem A hiba valószín¶leg a 321 Tételnek a cikkben leírt bizonyítása miatt került be az algoritmusba, egyben egy kis gyorsítást is adna. A hibát Naitoh és Fujishige vette észre és javította ki [17] (lásd a 3.26 Megjegyzésben leírtakat) 3.24 Algoritmus (Teljes reszel® algoritmus) keresztez®

szubmoduláris függvény, melyre Kimenet : z ∈ B(b), akkor egy olyan P mely ha b Bemenet : b : 2S R ∪ {∞} b(S) = 0. egészérték¶, akkor rácspont, illetve ha partíció, vagy ko-partíció, melyre B(b) = ∅, b(P) < 0. 1. rész Legyen S = {s1 , s2 , ., s|S| } Legyen b1 (X) := b(X), b2 (X) := b(S − X) X ⊆ S -re. Fusson i 1-t®l |S|-ig Ha b(si ) + b(S − si ) = 0, akkor z(si ) := b({si }), ha b(si ) + b(S − si ) < 0, akkor {si , S − si } sért® partíció, különben pedig Legyen f (si ) := min{b1 (P) : P partíciója S − si -nek}, és legyen F S − si azon S − si -nek}, és legyen G S − si azon partíciója, melyre a minimum felvétetik. Legyen g(si ) := min{b2 (P) : P partíciója partíciója, melyre a minimum felvétetik. Ha f (si ) + g(si ) < 0, Különben legyen és legyen Ha Akkor Ugorj a 2. részhez, z(si ) ∈ [−f (si ), g(si )], tetsz®leges (ha lehet egész) szám, b1 ({si }) := z(si ),

b2 ({si }) := −z(si ). i = n, Akkor z ∈ B(b)-t adjuk ki. 2. rész Amíg van átmetsz® F ∈F és G∈G F := F − {F } ∪ {F − G}, G := G − {G} ∪ {G − F.} http://www.doksihu 37 3. Fejezet : Általános tételek és algoritmusok F 3.25 Megjegyzés A kapott F nek és G és G rendszerre továbbra is igaz, hogy b1 (F) + b2 (G) < 0, is partíciója, valamint, hogy F ∈ F, G ∈ G S F= S G- mivel amennyiben átmetsz® halmazok, akkor egyik sem egy elem¶, és így b1 (F )+b2 (G) = = b(F ) + b(S − G) ≥ b(F ∪ (S − G)) + b(F ∩ (S − G)) = b1 (F − G) + b2 (G − F ), mivel b keresztez® szubmoduláris, és része, és átmetsz®ek, így F és F S−G G és is keresztez®k. Az átmetsz® párok megsz¶ntetése miatt akkor F ⊆G vagy G ⊆ F. partíciója, mivel tetsz®leges mivel F F -nek Gj ⊆ F ∪ G F ∈ F G∈G F ⊆ G, F ∈ F -re F akkor a ∈ G − F -et fed® egy partíciója. E miatt diszjunkt

részrendszerekre halmazból, és az ezt particionáló halmazból, és az ezt particionáló G ∈ G -re és F0 F ∪G F -beli F ∩ G 6= ∅, G-nek halmaz nem tartalmazhatja G ⊆ F, akkor elemei feloszthatóak G egy G-t, elemeib®l Fi ⊆ F ∪ G úgy, hogy minden Fi egy halmazokból áll, és minden Gi egy (i, j = 1,2, .) G -beli ha elemeib®l kiválasztható elemei diszjunktak. Hasonlóan látható, hogy ha kiválasztható és Ha S − ui -nek keresztez®, mivel mindkett® halmazokból áll. Az algoritmus befejezése : részrendszereket. Ha van, válasszunk ki egy olyan Fi -t mely k P elemei az F ∈ F és G1 , G2 , ., Gk ∈ G halmazok, és ezekre b1 (F ) + b2 (G` ) < 0, `=1 és adjuk ki az F, S − G1 , S − G2 , ., S − Gk ko-partíciót Készítsük el a Fi és Gj Különben válasszunk ki egy olyan ∈F halmazok, és ezekre b2 (G) + k P Gi -t mely elemei az b1 (F` ) < 0, G ∈ G és adjuk ki a és F1 , F2 , ., Fk ∈ S

− G, F1 , F2 , ., Fk `=1 ko-partíciót. 3.26 Megjegyzés Az eredeti [9]-beli algoritmussal az a probléma, hogy amennyiben B(b) üres, akkor is ki tud adni egy z vektort, mint B(b) egy elemét. Ezt mutatja például az alábbi példa, mely Fujishige és Naitoh [17] ellenpéldájának véges érték¶ változata. Legyen = −1, ha S = {1,2,3,4}, X ∈ {{1,2}, {3,4}}, szubmoduláris, a z≡0 és legyen b(X) = 0, ha |X| = 0,1,3 és különben legyen vagy b(X) = 1. 4, legyen Ekkor b b(X) = keresztez®n B(b) = ∅, mert az {{1,2}, {3,4}} sért® partíció, viszont az algoritmus vektort adja ki, mint B(b) egy elemét. 3.27 Állítás A Teljes reszel® algoritmus javított változata már jó http://www.doksihu 38 3.2 Fujishige tétele algoritmikusan Bizonyítás: Tétel szerint B(b) 6= ∅. El®ször azt az esetet vizsgáljuk, amikor S minden P Ekkor a 3.21 partíciójára vagy ko-partíciójára teljesül, hogy Az algoritmus, hasonlóan a

Fujishige-tétel bizonyításához b(P) ≥ 0. b értékét csökkenti az egy elem¶ halmazokon és ezek komplementerén úgy, hogy ez a tulajdonság a kapott b0 -re megmarad, és minden s ∈ S -re b0 (s) + b0 (S − s) = 0. Be kell látnunk, hogy z(X) ≤ b(X) minden X ⊆ S -re. X = {si }-re ez tejesül, mert z(si ) ≤ g(si ) ≤ b2 (S − − si ) = b({si }), és hasonlóan teljesül − si ) = b(S − si ), ha pedig X = S − si -re z(S − si ) ≤ f (si ) ≤ b1 (S − |X| 6= 1, |S| − 1, akkor mivel S minden s elemére az {{s}, S − s} b0 -pontos partíció, és b0 -re teljesül a Fujishige-tétel feltétele, ezért a tétel bizonyításában leírtak alapján a és így z(X) ≤ b0 (X) = b(X), z(s) := b0 ({s}) (s ∈ S) vektor benne van B(b0 )-ben, s®t az is igaz, hogy Most vizsgáljuk azt az esetet, amikor van olyan {S1 , S2 , ., Sq } z(S) = 0. B(b) = ∅. Ekkor a 321 Tétel szerint S -nek partíciója, melyre (3.2) vagy (33) megsérül Legyen

i∗ := = min{max{i : si ∈ Sj } : j = 1,2, ., q} Azt látjuk be, hogy az algoritmus legkés®bb az i∗ -adik lépésben kiad egy partíciót. Feltehetjük, hogy si∗ ∈ S1 . Amennyiben az algoritmus nem ugrik át korábban a 2. részhez, akkor f (si∗ ) ≤ q X b1 (Sj ) + b1 ({si }) = si ∈S1 ,i6=i∗ j=2 q [ f (si∗ ) ≤ b1 X q X X b(Sj ) + z(si ), (3.4) si ∈S1 ,i6=i∗ j=2 ! Sj X + z(si ), (3.5) si ∈S1 ,i6=i∗ si ∈S1 ,i6=i∗ j=2 X b1 ({si }) = b(S − S1 ) + és g(si∗ ) ≤ q X si ∈S1 j=2 g(si∗ ) ≤ b2 q [ j=2 mivel X b2 (Sj ) + b2 ({si }) = ,i6=i∗ q X X b(S − Sj ) − si ∈S1 j=2 z(si ), (3.6) ,i6=i∗ ! Sj + X si ∈S1 b2 ({si }) = b(S1 ) − ,i6=i∗ X si ∈S1 z(si ), (3.7) ,i6=i∗ i∗ deníciója szerint S1 minden más elemére már deniáltuk z -t, és nincs olyan Sj (S1 -en kívül), melynek minden elemére deniálva lenne egy elem¶, akkor zi , így speciálisan ha Sj b1 (Sj

) = b(Sj ), és b2 (Sj ) = b(S − Sj ). Amennyiben (32) sérül meg, akkor (3.4) és (37) összegéb®l kapjuk, hogy f (si∗ ) + g(si∗ ) < 0, meg, akkor (3.5) és (36) összegéb®l kapjuk, hogy ha pedig (3.3) sérül f (ui∗ ) + g(ui∗ ) < 0. http://www.doksihu 39 3. Fejezet : Általános tételek és algoritmusok Még azt kell belátnunk, hogy az algoritmus által kiadott partíció valóban sért®. A 3.25 Megjegyzésben láttuk, hogy a módosított b1 (F) + b2 (G) < 0 fennáll a rendszerek particionálják ∩ Fi ) < 0 vagy j -re, vagy egyenl®tlenség. Az F ∪ G -t, F G és Fi (i = 1,2, .) b1 (F) + b2 (G) < 0 így b1 (F ∩ Gj ) + b2 (G ∩ Gj ) < 0 rendszerekre továbbra is miatt és Gj (j = 1,2, .) b1 (F ∩ Fi ) + b2 (G ∩ egyike biztosan fennáll valamely i-re  azaz az algoritmus tényleg ki tud adni egy sért® partíciót. Az algoritmus O(|S|)-szer futtatja a reszel® algoritmust, és amennyiben nemüres

megáll, viszont most ha b nem véges érték¶, akkor a reszel® algoritmus minden futása el®tt el kell készíteni a a minimalizáló orákulum G(F(b1 |S−si )) és G(F(b2 |S−si )) gráfokat, mely 2 O(|S| )-szer kedvéért vegyük észre, hogy ha B(b) való futtatását teszi szükségessé. (A teljesség j =1 vagy 2-re bj |∨S−si (S − si ) = ∞, akkor ezt a reszel® algoritmus nélkül is meg tudjuk határozni, és ebben az esetben biztos nem lépünk a 2. részre) Ha tez® része B(b) = ∅, akkor futtatjuk a második részt, melynek kikeresz- 2 O(|S| ) O(|S|) idej¶ lépésb®l áll, míg F ∪ G particionálása szintén O(|S|3 ) id®ben végrehajtható, és ezek közül egy sért® kiválasztásához meg kell határozni értékét minden szóba jöv® partíción, amihez O(|S|)-szer értékét meghatározó orákulumot kell futtatni. A futásid® így véges érték¶ felvev® b b-re O(|S|3 θ), ahol θ b-re O(|S|2 θ + |S|3 ), illetve

végtelen értékeket is a minimalizáló orákulum futásideje. Az algoritmus, amennyiben alkalmas a teljes reszelt kiszámítására, egy halmazon, ugyanis az 1.27 Tétel szerint keresztez® szubmoduláris b-re továbbá az b G(F(b)) = G(F(b↓ )), S = {s1 , s2 , ., s|S| } A⊆S S(b) = S(b↓ ), így a 3.12 Állítás bizonyításában leírtak alapján ha sorrendet úgy választjuk meg, hogy ↓ A = {s1 , s2 , ., s|A| }, és ↓ b ({s1 , s2 , ., si }) < ∞ minden i = 1,2, , |A|-ra, (amit amennyiben b (A) < ∞ meg is tehetünk), akkor nek A-n S(b)-n, z -t kívül pedig így egyenl® minden −∞-nek ↓ b (A)-val si -n (i = 1,2, ., |A|) deniálva z ∈ S(b), a lehet® legtöbbnek, azaz és z maximalizálja z(A) g(si )- értékét az 1.25 Tétel alapján A Fujishige-tételre visszavezethet® annak alábbi általánosabb formája. 3.28 Tétel (Fujishige, általános alak) függvény S -en. Ekkor a b S minden {S1 , S2 , ., Sq }

nemüres, ha q X i=1 b(Si ) ≥ b(S), által meghatározott Legyen B(b) b keresztez®n szubmoduláris bázis-poliéder akkor és csak akkor partíciójára (3.8) http://www.doksihu 40 3.2 Fujishige tétele algoritmikusan és q X b(S − Si ) ≥ (q − 1)b(S). (3.9) i=1 Ha b egészérték¶, akkor Bizonyítás: Legyen B(b) s∈S tartalmaz rácspontot. kijelölt pont, és csökkentsük b értékét b(S)-sel az s-et tartalmazó halmazokon. Ezzel a keresztez® szubmodularitás érvényben marad, és a kapott b∗ -ra már b∗ (S) = 0 is teljesül, továbbá B(b) akkor és csak akkor nemüres, ha B(b∗ ) sem az, hiszen z ∈ B(b) értékét s-en b(S)-sel csökkentve egy B(b∗ )-beli pontot kapunk, és z ∈ B(b∗ ) értékét s-en b(S)-sel növelve egy B(b)-beli pontot kapunk.  A Teljes reszel® algoritmus a fenti bizonyítás mintájára kiterjeszthet® minden keresztez® szubmoduláris függvényre, mivel elkészíthetjük − b(S)χs -en ha

b ∗ b minimalizáló orákulumából könnyen -nak egy minimalizáló orákulumát, úgy, hogy keressük a minimumot, ahol χs ∈ RS , χs (v) = 1 b − a helyett b − a − ha v = s, χs (v) = 0, v ∈ S − s. Ha p keresztez® szubmoduláris, akkor −p keresztez® szupermoduláris és B 0 (p) = = −B(−p), így Fujishige tétele megfogalmazható keresztez® szupermoduláris függ- vény bázis-poliéderére is, továbbá a Teljes reszel® algoritmust is könnyen átvihetjük erre az esetre. 3.29 Tétel (Fujishige, szupermoduláris függvényekre) Legyen z®n szupermoduláris függvény S -en. Ekkor a poliéder akkor és csak akkor nemüres, ha q X S p által meghatározott minden {S1 , S2 , ., Sq } p kereszte- 0 bázis- B (p) partíciójára p(Si ) ≤ p(S), (3.10) p(S − Si ) ≤ (q − 1)p(S). (3.11) i=1 és q X i=1 Ha p egészérték¶, akkor B 0 (p) tartalmaz rácspontot. http://www.doksihu 4. fejezet Irányítások Ebben a

fejezetben els®ként megismerkedünk az irányítási algoritmussal, melyet az irányítási lemma bizonyítása ad meg. Ezt követ®en, ennek segítségével általános tételeket bizonyítunk különböz® majdnem szupermoduláris függvényt fed® irányítások létezésér®l, és algoritmust adunk ezekre a Teljes reszel® algoritmus segítségével. Speciális esetekben a szükséges minimalizáló orákulumot is megadjuk, így algoritmust kapunk a gyökeresen k illetve (k, `)-élösszefügg® irányítás megtalálására. Ezek után egyszer¶bb algoritmusokat keresünk, majd beletekintünk ezen algoritmusok egy alkalmazásába. 4.1 Irányítási lemma gráfokra és hipergráfokra 4.11 Lemma (Irányítási lemma, Hakimi [13]) Legyen csain adott egy + m : V Z úgy, hogy minden m(V ) = |E|. Y ⊆ V -re és v csúcsra függvény. Ekkor ρ(v) = m(v), ha G G = (V, E) gráf csú- akkor és csak akkor irányítható e(X) ≥ m(X) (A fenti feltétel úgy is

megfogalmazható, hogy minden X ⊆ V -re i(Y ) ≤ m(Y ) és minden m(V ) = |E|.) Bizonyítás: A lemmát az alábbi általánosabb lemmából bizonyítjuk. 4.12 Lemma Egy G = (V, E) gráfnak akkor és csak akkor van olyan irányítása, amelyben (a) ρ(v) ≥ f (v) minden : V Z+ ∪ {−∞} v ∈ V -re, függvény. ha minden X ⊆ V -re e(X) ≥ f (X), ahol f : http://www.doksihu 42 4.1 Irányítási lemma gráfokra és hipergráfokra ρ(v) ≤ g(v) (b) minden : V Z+ ∪ {∞} v ∈ V -re, ha minden X ⊆ V -re i(X) ≤ g(X), G-nek van olyan irányítása is, melyre Bizonyítás: P f (v) ≤ g(v) nevezzük a P δ(X) = 0, Mivel csúcsot hibásnak, ha t ∈ X, van s∈V P P f (t) < ρ(t). G Válasszunk egy irányítására nézve G-nek egy olyan irányí- f (v)−ρ(v) összeg minimális, és tegyük fel indirekten, ρ(v), v∈X hibás, azaz f (s) melyre ρ(v) < f (v). v hibás hibás csúcs. Jelölje e(X) = így s∈X

g(x) ≥ illetve tását, mely hiánya, azaz a hogy van egy v ∈ V -re, A feltételek szükségessége nyilvánvaló, hiszen egy jó irányításra ρ(v) ≥ f (X), v minden f (v) ≤ ρ(v) ≤ g(v). ρ(v) ≥ i(X). v∈X v∈X Az elégségességet el®ször az (a) esetben bizonyítjuk. e(X) ≥ g : függvény. Amennyiben (a) és (b) feltétele is fennáll, továbbá akkor ahol X így az > ρ(s), Mivel X az s-b®l elérhet® pontok halmazát. Ekkor P f (X) ≤ e(X) feltételb®l f (X) ≤ ρ(v). az így van s-b®l X -ben v∈X többletes csúcs is, azaz olyan elérhet® pontok halmazát jelölte, ezért s-b®l t-be irányított út. Ezt az utat megfordítva ρ(t) eggyel csökken ρ(s) eggyel n®, és semelyik másik v csúcsra nem változik ρ(v), így, mivel t többletes, s pedig hibás csúcs volt, az új irányítás hibája kisebb lesz, ami ellent mond a bizonyítás elején tett feltételeknek. A (b) esetet hasonlóan bizonyíthatjuk, annyi

változtatással, hogy most azon csúcsokat tekintjük hibásnak, melyre g(v) < ρ(v), v és egy hibás csúcsba futó utat fordítunk meg. A harmadik eset bizonyításához induljunk ki egy olyan irányításból, melyre minden v ∈ V -re ρ(v) ≤ g(v), és gyeljük meg, hogy a hiba-csökkentési lépésben mindig olyan s csúcs befokát növeljük, melyre ρ(s) < f (s) ≤ g(s), után is ρ(s) ≤ g(s) ≤ g(v) feltételnek eleget tev® irányításra minden ezért az út fordítás megmarad, tehát minimális hibájú minden v ∈ V -re v ∈ V -re ρ(v) ≤ teljesül az f (v) ≤ ρ(v)  egyenl®tlenség. Az irányítási lemma bizonyítása : Figyeljük meg, hogy az m(V ) mellett a minden X ⊆ V m(X) ≤ e(X) feltételt − m(X) = m(V − X) ≤ e(V − X) = |E| − i(X), kapható a minden komplementerére felírva amib®l i(X) ≤ m(X). |E| − (Hasonlóan X ⊆ V -re i(X) ≤ m(X)-b®l m(X) ≤ e(X).) E miatt az általános lemmából

kapjuk, hogy hogy X = |E| feltétel G-nek van olyan irányítása, melyre minden v csúcsra teljesül, m(v) ≤ ρ(v) ≤ m(v), azaz ρ(v) = m(v).  http://www.doksihu 43 4. Fejezet : Irányítások A fenti bizonyítás egy olyan algoritmust is ad egy olyan irányítás megtalálására, melyre minden v ∈ V -re ρ(v) ≥ f (v). Az algoritmus egy tetsz®leges irányításból indul és minden lépésben egy hiányos csúcsból egy többletes csúcsba vezet® utat fordít meg. Ez, amennyiben el®zetesen eltároltuk a hiányos és többletes csúcsok hiányát és többletét, (ami O(|E|) lépésnél konstans idej¶), akkor megtesz, azaz a futásid® idej¶ az algoritmus elején, ezt követ®en minden O(|E|)-szer 2 O(|E| ). csökkenti a hiányt, amit O(|E|) id®ben Hasonló algoritmus adható a 4.12 Lemma másik két részére is. Az Irányítási lemma fenti bizonyítása az általánosabb lemmával és az algoritmussal együtt hipergráfokra is

hasonlóképpen elmondható. A kulcs lépés az, hogy ha A1 , A2 , ., A` hiperélekb®l áll egy irányított hiperút s-b®l t-be, azaz hogy s ∈ A1 , Ai feje ai , melyre ai ∈ Ai+1 (1 ≤ i ≤ `−1), és A` feje t, akkor ennek megfordítottját úgy kapjuk, hogy A1 fejének s-et, Ai fejének pedig ai−1 -et választjuk (2 ≤ i ≤ `). Ha így deniáljuk az út megfordítottját, akkor ha az irányítást csak egy hiperúton fordítjuk meg más v ∈ V − {s, t}-re ρ(v) v = s-re n® eggyel, v = t-re s-b®l t-be futó csökken eggyel, minden változatlan marad. Ezt beírva a fenti bizonyításba kapjuk az alábbi lemmát. 4.13 Lemma (Hipergráf irányítási lemma) Legyen csúcsain adott egy m : V Z+ ható úgy, hogy minden és m(V ) = |E|. Y ⊆ V -re és v csúcsra függvény. Ekkor ρ(v) = m(v), ha H H = (V, E) hipergráf akkor és csak akkor irányít- e(X) ≥ m(X) (A fenti feltétel úgy is megfogalmazható, hogy minden X ⊆ V

-re i(Y ) ≤ m(Y ) minden m(V ) = |E|.) Irányított  hipergráfban az X meghatározására alkalmazott szélességi keresés P O |E| id®ben fut, ami felülr®l becsülhet® O(|E||V |)-vel, így az irányítási alE∈E   P goritmus O |E| |E| ≤ O(|E|2 |V |) id®ben fut. (Ha a hiperélek mérete k konsE∈E tanssal felülr®l korlátozható, akkor a szélességi keresés futási ideje O(|E|).) http://www.doksihu 44 4.2 Keresztez® G-szupermuduláris függvényt fed® irányítások 4.2 Keresztez® G-szupermuduláris függvényt fed® irányítások Az Irányítási lemma segítségével a 3.21 Tételb®l levezetjük a nem negatív keresztez®n G-szupermoduláris 4.21 Tétel Legyen a G-szupermoduláris létezik h-t ≥ h(X)), függvényt fed® irányításokról szóló tételt [4]. G = (V, E) gráf csúcsain adott a függvény, melyre h : 2V Z+ h(∅) = h(V ) = 0. G-nek akkor és csak akkor fed® irányítása, (azaz olyan irányítása, melyre minden

ha e(P) ≥ V minden q X P = {V1 , V2 , ., Vq } keresztez®n X ⊆ V -re ρ(X) ≥ partíciójára h(Vi ), (4.1) h(V − Vi ). (4.2) i=1 és e(P) ≥ q X i=1 Bizonyítás: e(P) = q P (4.1) szükségessége következik abból, hogy q P ρ(Vi ) ≥ h(Vi ). i=1 i=1 fed® irányításra e(P) = q P fed® irányításra (4.2) szükségessége pedig következik abból, hogy q P δ(Vi ) ≥ ρ(V − Vi ) ≥ Az elégségesség bizonyításához legyen h(V − Vi ). p(X) := h(X) + i(X). szubmoduláris függvény, mivel keresztez® szupermoduláris volta, valamint az q P G h-t i=1 i=1 i=1 összefüggés miatt G h-t X, Y ⊂ V Ekkor halmazokra h p keresztez® keresztez® G- i(X) + i(Y ) = i(X ∪ Y ) + i(X ∩ Y ) − d(X, Y ) p(X) + p(Y ) = i(X) + h(X) + i(Y ) + h(Y ) ≥ i(X) + i(Y ) + h(X ∪ ∪ Y ) + h(X ∩ Y ) + d(X, Y ) = i(X ∪ Y ) + i(X ∩ Y ) − d(X, Y ) + h(X ∪ Y ) + h(X ∩ ∩ Y ) + d(X, Y ) = p(X ∪ Y ) + p(X ∩ Y ). mivel

i(∅) = 0, i(V ) = |E|, B 0 (p) 6= ∅ p(∅) = 0, p(V ) = |E|, h(∅) = h(V ) = 0. bizonyításához a 3.29 Tétel szerint ellen®riznünk kell minden = {V1 , V2 , ., Vq } e(P) ≥ és Igaz továbbá, hogy q X i=1 -ra (3.10) és (311) teljesülését A tétel (41) feltétele szerint h(Vi ), P = http://www.doksihu 45 4. Fejezet : Irányítások melybe q P e(P) = |E| − i(Vi )-t helyettesítve kapjuk, hogy i=1 |E| − q X i(Vi ) ≥ q X h(Vi ), i=1 i=1 amit átrendezve p(V ) = |E| ≥ q X h(Vi ) + i(Vi ) = q X p(Vi ), i=1 i=1 ami pont (3.10) Hasonlóan a tétel (42) feltétele szerint e(P) ≥ q X h(V − Vi ), i=1 melybe e(P) = (q − 1)|E| − q P i(V − Vi )-t helyettesítve kapjuk, hogy i=1 (q − 1)|E| − q X i(V − Vi ) ≥ i=1 q X h(V − Vi ), i=1 amit átrendezve (q − 1)p(V ) = (q − 1)|E| ≥ q X h(V − Vi ) + i(V − Vi ) = i=1 ami pont (3.11) Így, mivel p Az p(V − Vi ), i=1 egészérték¶ is

feltehet®, hogy van egy egész vektorunk, melyet fokszámel®írásnak tekintünk. Az = p(V ) = |E|. q X m(X) ≥ p(X) m m ∈ B(p) függvényre egyenl®tlenségb®l kapjuk, hogy minden m(V ) = X ⊆ V -re m(X) ≥ i(X) + h(X) ≥ i(X), mivel h nemnegatív. Így az Irányítási lemma feltétele G-nek olyan irányítása, ahol minden csúcs befoka m(v). Erre az P ρ(v) − i(X) = m(X) − i(X) ≥ i(X) + h(X) − i(X) = h(X), ρ(X) = teljesül, tehát van irányításra azaz ez egy h-t v∈V fed® irányítás.  A fenti tétel bizonyítása mutatja, hogy a Teljes reszel® algoritmus után az irányítási algoritmust futtatva megkaphatjuk a kívánt irányítást, illetve ha az nem létezik, egy sért® partíciót vagy ko-partíciót. Ezek szerint az irányítás id®ben megkapható, ahol θ a b = −p-t O(|V |2 θ + |V |3 + |E|2 ) minimalizáló orákulum futási ideje. Most a 4.21 Tételb®l levezetjük a 321 Tétel szupermoduláris függvényekre vonatkozó

alakját. http://www.doksihu 46 G-szupermuduláris 4.2 Keresztez® 4.22 Tétel Legyen melyre p(S) = 0. p q X keresztez®n szupermoduláris véges érték¶ függvény Ekkor a csak akkor nemüres, ha függvényt fed® irányítások S p által meghatározott minden {S1 , S2 , ., Sq } B 0 (p) S -en, bázis-poliéderben akkor és partíciójára p(Si ) ≤ 0, (4.3) p(S − Si ) ≤ 0. (4.4) i=1 és q X i=1 Amennyiben p egészérték¶ és B 0 (p) nemüres, úgy tartalmaz rácspontot is. Bizonyítás: 1 Csak az elégségességet bizonyítjuk. El®ször legyen p véges, egészérté- k¶ keresztez®n szupermoduláris, melyre (4.3) és (44) fennáll az alaphalmaz minden partíciójára. Legyen p(X) + G = (S, E) dG (X) 2 ≥ 0. olyan Euler-gráf, melyre teljesül, hogy minden X ⊂ S -re Ilyen gráf könnyen konstruálható, mivel tetsz®leges számú élet hozzávehetünk. Ekkor a = 0, és S h(X) := p(X) + dG2(X) minden e(P) ≥ q X

függvény keresztez®n P = {S1 , S2 , ., Sq } G-szupermoduláris, h(S) = partíciójára h(Vi ), i=1 (4.3) és q P e(P) = i=1 e(P) ≥ q X dG (Si ) miatt 2 h(V − Vi ), i=1 (4.4) és e(P) = q P dG (Si ) miatt. A 421 Tételb®l következik, hogy van 2 i=1 fed® irányítása. Ez olyan irányítást jelent, hogy minden ! X v∈X 1A ρ(v) − i(X) = ρ(X) ≥ h(X) = p(X) + G-nek h-t X ⊆ S -re dG (X) . 2 bizonyítás, bár eddig nem jelent meg sehol, csak igen kis részben saját eredhmény. http://www.doksihu 47 4. Fejezet : Irányítások Ekkor X v∈X dG (v) ρ(v) − 2  X ! v∈X  amib®l, mivel P ρ(v) = |E| = P v∈S v∈S B 0 (p)-ben van, és egészérték¶, mivel Ezzel véges, egészérték¶ érték¶ B 0 (p) − i(X) − ρ(v)  dG (v) 2 G dG (X) ≥ p(X), 2 , a z(v) := ρ(v) − vektor Euler. p-re beláttuk a tételt. Ebb®l következik, hogy racionális nemüressége, és a feltételek sem változnak. p-re való

áttéréshez belátjuk, hogy tetsz®leges z®n szupermoduláris, a tétel feltételeit teljesít® (innent®l racionális érték¶  jó függvényekkel. A R (v ∈ S) p-re is igaz a tétel, mivel az értékek legkisebb közös többszörösével beszorozva Valós érték¶ nak dG (v) , 2 2S S 2 R p : 2S R kereszte-  jó ) függvény közelíthet®  jó függvények egy poliédert alkot- -ben, mivel mind a keresztez® halmazpárokra felírt szubmodularitási egyen- l®tlenség, mind a tétel feltételei egy-egy lineáris egyenl®tlenség, melyek együtt, mivel véges sokan vannak egy poliédert határoznak meg. A poliéder racionális pontjairól tudjuk, hogy s¶r¶n helyezkednek el, és azok a racionális érték¶  jó függvényeknek felelnek meg, így tényleg közelíthet® minden valós érték¶  jó függvény racionális érték¶ekkel. Még azt kell belátnunk, hogy, ha p : 2S R  jó  jó függvények egy sorozata, akkor abból, hogy a

üresek következik, hogy 0 B (p) függvényhez tart a B 0 (pi ) bázispoliéderek mind nem K := {z ∈ RS : sem üres. Legyen max{−p(X) : X ⊆ S} + 1 ≥ z(v) ≥ max{p(X) : X ⊆ S} − 1} hogy van olyan N ∈ N, hogy i ≥ N -re B 0 (pi ) ⊆ K , 0 v ∈ S, z ∈ B (pi )-re z(v) ≥ pi ({v}) ≥ p({v}) − 1, − v) ≤ −p(S − v) + 1. K kompakt, így a konvergens részsorozat, feltehet®, hogy zi pi : 2S Q minden kocka. v ∈ S -re K -ra mivel minden elég nagy igaz, i-re és és z(v) = −z(S − v) ≤ −pi (S − zi ∈ B (pi ) vektorokból kiválasztható egy 0 konvergens. A kapott határértékre z(S) = = p(S) = 0, és z(X) ≥ p(X) minden X ⊆ S -re a rend®r elv szerint, mivel zi (S) = 0, és z zi (X) ≥ pi (X) minden X ⊆ S fennállt minden i-re, és pi határértéke p zi -jé pedig volt. Tehát a kapott z ∈ B 0 (p), azaz B 0 (p) nemüres.  http://www.doksihu 4.3 Hipergráfok keresztez® szupermoduláris 48

függvényt fed® irányítása 4.3 Hipergráfok keresztez® szupermoduláris függvényt fed® irányítása A Hipergráf irányítási lemmából a 4.21 Tétel bizonyításával analóg módon levezethet® az alábbi tétel [8] H = (V, E) 4.31 Tétel Legyen a hipergráf csúcsain adott a resztez®n szupermoduláris függvény, melyre akkor létezik h-t ρ(X) ≥ h(X)), e(P) ≥ h : 2V Z+ h(∅) = h(V ) = 0. H-nak akkor és csak fed® irányítása, (azaz olyan irányítása, melyre minden ha q X V minden P = {V1 , V2 , ., Vq } ke- X ⊆ V -re partíciójára h(Vi ), (4.5) i=1 és X (e0P (A) − 1) ≥ e0P (Z) h(V − Vi ), (4.6) i=1 A∈E ahol q X jelöli, hogy Z hány tagját metszi P -nek. A 4.21 Tétel bizonyításának megismétléséhez képest csak annyit kell látnunk, hogy az elégségesség bizonyításánál a p := h + i itt is keresztez® szubmoduláris függvény, mivel egy szupermoduláris és egy keresztez® szupermoduláris

függvény összege. A 4.2 szakaszhoz hasonlóan itt is algoritmust kaphatunk a kívánt irányítás megtalálására, mivel a Teljes reszel® algoritmus után a hipergráf irányítási algoritmust futtatva megkaphatjuk a kívánt irányítást,  illetve ha az nem létezik,  egy sért® partíciót vagy ko-partíciót. Futási id®re korábbi futási id®b®l, ahol θ ismét a O |V |2 θ + |V |3 + |E| b= P |E| -t kapunk a két E∈E −p-t minimalizáló orákulum futási ideje. 4.4 Metsz® szupermoduláris függvényt fed® irányítások A 4.2 és a 43 szakaszokban láttuk, hogy keresztez® szupermoduláris (s®t gráfokra G-szupermuduláris) függvényt fed® irányítás algoritmussal megadható, ha létezik, http://www.doksihu 49 4. Fejezet : Irányítások illetve ellenkez® esetben adható egy sért® partíció. Ez persze metsz® (G-) szupermoduláris függvényen is jó, de meglehet®sen bonyolult Láttuk, hogy a Reszel® algoritmus alkalmas metsz®

szubmoduláris (és így metsz® szupermoduláris) függvény által adott bázis-poliéder egy (amennyiben a függvény egészérték¶ rács)pontjának kiszámítására. Ezt felhasználva az irányítási algoritmussal, a fentiekkel analóg módon adható egy egyszer¶bb algoritmus a fed® irányítás O(|V |θ + |V |2 + |E|2 ), ahol θ a b = −p-t minima- megtalálására, melynek futási ideje lizáló orákulum futási ideje. Hasonlóan a 313 Tételb®l és az Irányítási lemmából igazolható az alábbi tétel [3]. 4.41 Tétel Legyen a G = (V, E) szupermoduláris függvény, melyre h(∅) = 0. G-nek G- akkor és csak akkor létezik h-t fed® irányítása, (azaz olyan irányítása, melyre minden V minden P = {V1 , V2 , ., Vq } e(P) ≥ q X h : 2V Z+ metsz® gráf csúcsain adott a X ⊆ V -re ρ(X) ≥ h(X)), ha partíciójára h(Vi ). (4.7) i=1 Hasonlóan igazolható a 3.13 Tételb®l és a Hipergráf irányítási lemmából a 431 Tétel metsz®

szupermoduláris függvényekre vonatkozó   változata. Az erre a változatra kapott algoritmus O |V |θ + |V |2 + |E| P |E| , ahol θ ismét a b = −p-t mini- E∈E malizáló orákulum futási ideje. 4.42 Tétel Legyen a H = (V, E) szupermoduláris függvény. H-nak hipergráf csúcsain adott a akkor és csak akkor létezik (azaz olyan irányítása, melyre minden P = {V1 , V2 , ., Vq } e(P) ≥ q X p : 2V Z+ h-t metsz® fed® irányítása, X ⊆ V -re ρ(X) ≥ h(X)), ha V minden partíciójára h(Vi ). (4.8) i=1 A 4.41 tételt kiterjeszthetjük negatív függvényekre is Ehhez vegyük észre, hogy a fentiekkel analóg módon bizonyítható, hogy egy nyítások befokvektorai pontosan a a Reszelési tétel szerint h metsz® B 0 (h + i) ∩ B 0 (i) B 0 (h + i) = B 0 ((h + i)∧ ), G-szupermoduláris irá- metszet egész pontjai. Mivel ahol (h + i)∧ szupermoduláris, az 1.29 Tételb®l kiolvasható az alábbi tétel, melyre szubmoduláris

áramokkal való bizonyítás van [5]-ben. http://www.doksihu 50 4.5 Gyökeresen 4.43 Tétel Legyen a metsz® G = (V, E) G-szupermoduláris akkor létezik h-t ρ(X) ≥ h(X)), e(P) ≥ gráf csúcsain adott a függvény, melyre irányítás h : 2V Z ∪ {−∞} h(∅) = h(V ) = 0. G-nek akkor és csak fed® irányítása, (azaz olyan irányítása, melyre minden V ha q X k -élösszefügg®vé minden P = {V1 , V2 , ., Vq } X ⊆ V -re szubpartíciójára h(Vi ). (4.9) i=1 4.5 Gyökeresen k-élösszefügg®vé irányítás Legyen a G = (V, E) gráfon vagy a H = (V, E) r0 ∈ V hipergráfon adott egy gyökérpont. A 44 szakaszban tárgyalt tételeket és algoritmusokat a h(X) :=   0, ha r0 ∈ X, vagy k,  X=∅ különben metsz® (szuper)moduláris függvényre alkalmazva megkapjuk az r0 -ból gyökeresen k - élösszefügg® irányítás létezésének feltételét, illetve algoritmust is kapunk az irányítás vagy egy sért®

partíció megtalálására, amennyiben a b := −h − i-t minimalizáló orákulumot meg tudjuk konstruálni. A fentiekb®l tehát az alábbi tételeket kapjuk. 4.51 Tétel Legyen a csak akkor létezik G = (V, E) gráfnak r0 -gyöker¶ k -élösszefügg® 4.52 Tétel Legyen a H = (V, E) akkor és csak akkor létezik r0 kijelölt gyökérpontja. irányítása, ha hipergráfnak r0 G-nek akkor és k -partíció-összefügg®. kijelölt gyökérpontja. r0 -gyöker¶ k -élösszefügg® irányítása, ha H-nak k -partíció- összefügg®. Mint láttuk ahhoz, hogy algoritmust kapjunk a fenti két tételre az eddigiekb®l szükségünk van a minimalizáló orákulumok megkonstruálására. Ehhez gyeljük meg, hogy X ⊂ V -re h(X) = P v ∈ Xkχr0 (v) = (kχr0 )(X), risztikus vektora, így elég egy tetsz®leges minimalizáló orákulumot megadni, mivel 0 −i − h − a0 −i − a-ra, ahol a = a + kχr0 , illetve X = V V − v -n, és ezek illetve

−i(V ) − a0 (V ) a ∈ RV -re −i − a-t ahol χ r0 r0 valamely karakte- X ⊂ V -n helyett minimalizálhatunk esetén minden − v ∈ V -re minimalizálunk minimumát adjuk ki. http://www.doksihu 51 4. Fejezet : Irányítások P −i(Z) − a(Z) = e(Z) − Gráfokra (d(v) − a(v)), így −i(Z) − a(Z) = v∈Z e(Z)−i(Z)− P (d(v)−2a(v)) v∈Z = d(Z)−a0 (Z) , tehát elég 2 = 2 d − a-t minimalizálni tetsz®leges a-ra. A min{d(Z)−a(Z) : Z ⊆ X} érték, és az ezt minimalizáló halmaz kiszámításához legyen v ∈ V -re a+ (v) := max{a(v),0}, a− (v) = max{−a(v),0} a D = (V ∪ {s, t}, A) negatív része. Vegyük azt a : A Z ∪ {∞} és c : irányított gráfot, és azt a kapacitásfüggvényt, melyeket úgy kapunk G-b®l, élét mindkét irányba irányítva 1 kapacitással vesszük, az új beli pozitív és s hogy G minden csúcsból minden X- v csúcsba húzunk egy a+ (v) kapacitású irányított

élet, minden X -beli v csúcsból t húzunk az új húzunk az új csúcsba egy t a− (v) csúcsba egy ∞ kapacitású élet, és minden V − X -beli mivel az ponthalmaza is. csúcsot, akkor a kapacitása X +s Tetsz®leges Z csúcsból D-n szintez® kapacitású élet (lásd a 4.5 ábrát) (el®)folyam-algoritmussal [12] meghatározható a minimális kapacitása, s®t a vágás V − X -beli v ∞ Z ⊆ X + s, s-et t-t®l elvágó vágás Z tartalmazna mivel ha lenne, ami ellentmond a minimalitásnak, vágás kapacitása véges, mivel nem lép ki X + s-b®l ∞ kapacitású él. Y ⊆ X -re az Y + s vágás kapacitása pont dG (Y ) + a− (Y ) + a+ (X − Y ) = = a+ (X) + dG (Y ) − a(Y ), így Z + s kapacitása minimalizálja a+ (X) + dG (Y ) − a(Y ) értékét Y ⊆ X -re, ami miatt orákulum futási ideje így dG (Z) − a(Z) = min{dG (Y ) − a(Y ) : Y ⊆ X}. Az θ = O(|V |3 ), illetve X = V -n O(|V |4 ), melyet beírva a 4.4 szakaszban

kapott eredménybe gráfok gyökeresen k -összefügg®vé irányítása O(|V |4 ) id®ben megkapható, mivel a Reszel® algoritmusban csak az utolsó lépésben kell V -n minimalizálni. Hipergráfokra tekintsük az illeszkedési gráfot, és ott rendeljünk egy perélb®l induló e élhez 1 értéket. Ekkor |E| x(e) := azon hiperélekhez vezet® élekre írt = i(X). írt Hasonlóan deniálható x-értékek x-értékek 0 hi- X ⊆ V -re i0 (X) :=az X -b®l összege, mely hiperéleket e (X) :=az X -b®l E ∈E X feszíti= azon hiperélekhez vezet® élekre összege, mely hiperéleknek van pontjuk X -ben, és d0 (X) :=az X -b®l x-értékek összege, mely hiperéleknek van pontjuk P 0 X -ben, és X -en kívül is. Ekkor d (X) = e0 (X) − i0 (X) és i0 (X) + e0 (X) = d (v), v∈X P 0 0 0 (ahol d(v)=d({v})). Így −i(Z) − a(Z) = −i (Z) − a(Z) = e (Z) − (d (v) − azon hiperélekhez vezet® élekre írt 0 e0 (Z)−i0 (Z)− − a(v)), így −i(Z)

− a(Z) = P v∈Z 2 v∈Z (d0 (v)−2a(v)) = d0 (Z)−a0 (Z) 2 , tehát elég d0 − a-t http://www.doksihu 52 4.5 Gyökeresen k -élösszefügg®vé irányítás V v5 v1 X v3 v2 v4 G ⇓ V 1 v1 s a+ (v1 ) 1 v5 1 ∞ a− (v1 ) 1 t a+ (v3 ) a− (v3 ) v3 a− (v2 ) a+ (v2 ) 1 ∞ v2 v4 X 1 D 4.1 ábra Segédgráf a fokszám minimalizáló orákulumhoz minimalizálni tetsz®leges A a-ra. min{d0 (Z) − a(Z) : Z ⊆ X} tásához legyen ismét érték, és az ezt minimalizáló halmaz kiszámí- v ∈ V -re a+ (v) := max{a(v),0}, pozitív és negatív része. Vegyük azt a és a− (v) = max{−a(v),0} a D = (V ∪{s, t}∪E, A) irányított gráfot, és azt http://www.doksihu 53 4. Fejezet : Irányítások a c : A Z ∪ {∞} kapacitásfüggvényt, melyeket úgy kapunk az illeszkedési gráfból, E -beli hogy annak minden élét mindkét irányba irányítva bevesszük, és az kapacitását minden 1 -nak választjuk, az új

töv¶ek kapacitását |A| ∞-nek, az A ∈ E csúcsból húzunk az új t csúcsba egy a− (v) v csúcsból húzunk az új t csúcsba egy ∞ ponthalmaza is. akkor a kapacitása ∪E ∞, kapacitású élet, és minden s-et t-t®l Z ⊆ X + s ∪ E , mivel ha Z igaz, hogy a minimális vágásra szintez® (el®)folyam- elvágó vágás kapacitása, s®t a V − X -beli csúcsot, tartalmazna ∞ Z ∩ V -t X + s ∪ E -b®l ∞ metsz® hiperélek mind lenne, továbbá más hiperél nincs kidobva a kapacitás eggyel csökkenne, így deniálható az vágás, melynak ponthalmaza Tetsz®leges V − X -beli lenne, ami ellentmond a minimalitásnak, mivel az vágás kapacitása véges, mivel nem lép ki különben a kapacitás D-n kapacitású élet. algoritmussal meghatározható a minimális Z s csúcsból X -beli v csúcsba húzunk egy a+ (v) kapacitású irányított élet, minden X -beli v vágás hegy¶ek Y ⊆ X- az Y, s Y -hoz és az Y

-t X +s∪ kapacitású él. Az is Z -ben Z -ben, Y ⊆X vannak, mivel mivel különben halmazhoz tartozó metsz® hiperélek. tartozó vágás kapacitása d0 (Y ) + a− (Y ) + a+ (X − −Y ) = a+ (X)+d0 (Y )−a(Y ), így Z+s kapacitása minimalizálja a+ (X)+d0 (Y )−a(Y ) értékét Y ⊆ X -re, ami miatt Az orákulum futási ideje így d0 (Z ∩ V ) − a(Z ∩ V ) = min{d0 (Y ) − a(Y ) : Y ⊆ X}. θ = O(|V |3 ), illetve X = V -n ennek |V |-szerese, melyet beírva a 4.4  szakaszban kapott  eredménybe hipergráfok gyökeresen irányítása O |V |4 + |E| P |E| E∈E ban csak az utolsó lépésben kell k -összefügg®vé id®ben megkapható, mivel a Reszel® algoritmus- V -n minimalizálni. 4.53 Megjegyzés (*). A fenti két orákulum bár saját eredmény, meg kell jegyeznünk, hogy [9] megemlíti, hogy gráfokra a szükséges orákulum folyam-algoritmussal megkonstruálható, és [8] is említést tesz a hipergráfokra vonatkozó orákulum

meglétér®l. 4.6 Gyökeresen (k, `)-élösszefügg®vé irányítás Legyen a G = (V, E) gyökérpont, és legyen gráfon vagy a k ≥ `. H = (V, E) hipergráfon adott egy r0 ∈ V A 4.2 és a 43 szakaszokban tárgyalt tételeket és http://www.doksihu 54 4.6 Gyökeresen (k, `)-élösszefügg®vé irányítás r0 -ból gyökeresen algoritmusokat a h(X) :=  0,    X=∅ ha `, r0 ∈ X 6= V ha    V vagy k, különben keresztez® szupermoduláris függvényre alkalmazva megkapjuk az (k, `)-élösszefügg® irányítás létezésének feltételét, illetve algoritmust is kapunk az irányítás vagy egy sért® partíció megtalálására, mivel a b := −h − i-t minimali- záló orákulum megkonstruálható, hasonlóan az el®z® A futási   szakaszban leírthoz. O(|V |5 ), O |V |5 + |E| P |E| . A fenti E∈E behelyettesítve a 4.21 és a 431 tételekbe az alábbi tételeket kapjuk id® gráfokon így 4.61 Tétel Legyen

a gyenek k ≥ ` G = (V, E) irányítása, ha 4.62 Tétel Legyen a k ≥ ` H = (V, E) irányítása, ha r0 h-t el®re kijelölt gyökérpontja, és le- akkor és csak akkor létezik r0 -gyöker¶ (k, `)-partíció-összefügg®. nemnegatív egészek. (k, `)-élösszefügg® gráfnak G-nek nemnegatív egészek. (k, `)-élösszefügg® legyenek hipergráfokon pedig r0 hipergráfnak H-nak el®re kijelölt gyökérpontja, és akkor és csak akkor létezik r0 -gyöker¶ (k, `)-partíció-összefügg®. Mivel a Teljes reszel® algoritmus már igen bonyolult, érdemes ennél egyszer¶bb algoritmust adni. Ilyen algoritmust adok az `=1 esetre [14]. El®ször irányított gráfokról bizonyítunk két lemmát. 4.63 Lemma (*). Legyen gyökérponttal. Legyen gyöker¶ k -élösszefügg® D = (V, A) R ⊂ V és egy r0 -at irányított gráf egy el®re kijelölt tartalmazó csúcshalmaz, melyre D/R rR -gyöker¶ k -élösszefügg®. Ekkor r0 ∈ V D[R] r0

- D r0 -gyöker¶ k - élösszefügg®. Bizonyítás: Egy δD[R] (X ∪ R) ≥ k , Egy r0 ∈ X ⊂ V ami r0 ∈ X ⊂ V , halmazra, melyre R 6⊆ X , δD (X) ≥ k , D[R] r0 -gyöker¶ k -élösszefügg®ségéb®l melyre R ⊆ X , δD (X) ≥ k , D/R rR -gyöker¶ k -élösszefügg®ségéb®l mivel következik. mivel következik. δD/R (X − R + rR ) ≥ k , ami  http://www.doksihu 55 4. Fejezet : Irányítások D = (V, A) irányított gráf egy el®re kijelölt r0 ∈ V 4.64 Lemma (*). Legyen R⊂V kérponttal. Legyen gyö- r0 -at tartalmazó csúcshalmaz, melyre D[R] r0 -gyöker¶ egy (k, `)-élösszefügg® és D/R rR -gyöker¶ (k, `)-élösszefügg®. Ekkor D r0 -gyöker¶ (k, `)élösszefügg® Bizonyítás: D-re és D r0 -gyöker¶ k -élösszefügg®, és 4.63 Lemmát alkalmazhatjuk b®l azt kapjuk, hogy amib®l könnyen látható, hogy ← − D D megfordítottjára, ami← − D r0 -gyöker¶ `-élösszefügg®, D r0 -gyöker¶

(k, `)-élösszefügg®.  `=1 A fenti két lemmából most egy új bizonyítást adunk a 4.61 Tételre az esetben. Ebb®l az új bizonyításból olvassuk majd ki az algoritmust 4.65 Tétel Egy r0 összefügg®, ha van r0 -gyöker¶ (k, 1)-élösszefügg® |V |-re Bizonyítás(*): tetsz®leges él. gyöker¶ G (k, 1)-partíció-összefügg®sége G-nek, melyekb®l van út melyre r0 -ból ha e0 -at r0 D-ben r0 -ba. R − r0 -beli δD[R] (X) ≥ k miatt, A Menger-tétel szerint irányítása ami egy R ρ(R) = 0 csúcsba fut nem léphet ki melyre D irá- azon csúcsok halmaza, és minden X -re, k diszjunkt út, mely R-b®l, így a Menger-tétel Ebb®l következik, hogy a X -re, e0 = r0 u ∈ E G − e0 k -partíció-összefügg®, felé irányítjuk. Legyen minden olyan (k, 1)-partíció- irányítása. r0 -gyöker¶ k -élösszefügg® r0 ∈ X ⊂ R, ρD[R] (X) ≥ 1. tetsz®leges szerint gráf akkor és csak akkor vonatkozó indukcióval

bizonyítunk. Legyen így a 4.51 Tétel szerint van nyítását adja G = (V, E) r0 ∈ X ⊂ R . Így D[R] r0 -gyöker¶ (k,1)-élösszefügg®. Láthatjuk, hogy |R| ≥ 2, mivel r0 , u ∈ R, illetve, hogy ha R = V , akkor kész is vagyunk, hisz Ha R 6= V , V − R + rR -nek, ójára DG egy (k,1)-élösszefügg® akkor a következ®t csináljuk. Ha ahol rR ∈ X1 , tása. Legyen P = {X1 − rR ∪ R, X2 , X3 , .Xt } akkor a G/R-nek partíciója van egy Ezek szerint partíci- G/R (k,1)-partíció- rR -gyöker¶ (k,1)-élösszefügg® az az irányítása, melyet úgy kapunk, hogy G[R]-en irányí- megtart- G/R rR -gyöker¶ − − (k,1)-élösszefügg® irányításában. A 464 Lemmát alkalmazva G -re kapjuk, hogy G juk a D − G G-nek P = {X1 , X2 , .Xt } 0 V -nek eP (G/R) = eP 0 (G) ≥ k(|P| − 1) + 1. összefügg®. Indukció szerint irányítása. által adott irányítást, és a többi élet úgy irányítjuk, mint r0 -gyöker¶

(k,1)-élösszefügg® irányítása G-nek. A bizonyítás az alábbi algoritmust adja, melynek futása a ábrán látható, ám igazából nagyobb k -ra is hasonló.  k=1 esetben a 4.6 http://www.doksihu 56 4.6 Gyökeresen G (k, `)-élösszefügg®vé D irányítás G/R ⇒ ⇒ R rR r0 r0 ⇓ − G D rR 0 R00 r0 4.66 Algoritmus (*). (k,1)-élösszefügg®vé Bemenet : ⇐ r R0 R0 Kimenet : Legyen gyöker¶ egy e0 = r0 u ∈ E k -élösszefügg®vé (k,1)-partíció-összefügg® G = (V, E) − e 0 -vel r0 ∈ V r0 -gyöker¶ (k,1)-élösszefügg® gráf, gyökérpontja. irányítása G-nek. tetsz®leges él. Futtassuk a 45 szakaszban tárgyalt r0 - G − e0 -on, irányítsuk e0 -at r0 felé, és −0 D = (V, E ), melyben egy e ∈ E él irányított irányító algoritmust legyen az így kapott irányított gráf párját rR irányító algoritmus futása melynek lehetnek többszörös élei, és van egy el®re kijelölt − −

G = (V, E ), D0 (G/R)/R0 ⇐ ⇐ 4.2 ábra Az 00 jelöljük. Legyen R azon csúcsok halmaza, melyekb®l r0 elérhet® D-ben. R = V , akkor − D (k,1)-élösszefügg®, így G := D-t adjuk ki. Különben e ∈ E[R]-re legyen annak − E -beli irányított párja − e := − e 0 . Futtassuk az algoritmust rekurzívan G/R-en r (Ezt a halmazt tetsz®leges keres® algoritmussal meghatározhatjuk.) Ha R gyökérrel (ezt a fenti tétel bizonyítása alapján megtehetjük) és irányítsuk az E[R]-en kívüli éleket úgy, mint ahogy ez az algoritmus tette. 4.67 Megjegyzés (*). Egy nem egy olyan q elem¶ P partícióját (k,1)-partíció-összefügg® gráfon ki tudunk adni V -nek, melyre e(P) ≤ k(q − 1), mivel a 4.5 szakasz- http://www.doksihu 57 4. Fejezet : Irányítások ban leírt algoritmus ekkor valamelyik esetleg összehúzott nyítást, hanem egy P0 partíciót ad ki, melyre G0 gráfon futtatva nem irá- eG0 −e0 (P 0 ) ≤ k(|P 0 | −

1), melyb®l ha az összehúzással keletkezett új csúcsot az azt tartalmazó halmazban az ®sképével helyettesítjük, akkor egy olyan azaz P V -nek, partícióját kapjuk melyre eG−e0 (P) ≤ k(|P| − 1), eG (P) ≤ k(|P| − 1) + 1. Az algoritmust hipergráfokra is kiterjeszthetjük. Ehhez els® lépésként a 463 Lemmát és a 4.64 Lemmát terjesztjük ki hipergráfokra : 4.68 Lemma (*). Legyen r0 ∈ V D = (V, A) egy irányított hipergráf, és legyen ennek el®re kijelölt gyökérpontja. R ⊂ V 1. Legyen gyöker¶ egy r0 -at tartalmazó olyan csúcshalmaz, melyre D[R] r0 - k -élösszefügg® és D/R rR -gyöker¶ k -élösszefügg®. Ekkor D r0 -gyöker¶ k -élösszefügg®. 2. Legyen R⊂V egy (0, `)-élösszefügg® r0 -at tartalmazó olyan csúcshalmaz, melyre D[R] r0 -gyöker¶ és D/R rR -gyöker¶ (0, `)-élösszefügg®. Ekkor D r0 -gyöker¶ (0, `)-élösszefügg®. 3. Legyen R⊂V egy (k, `)-élösszefügg® r0 -at

tartalmazó olyan csúcshalmaz, melyre D[R] r0 -gyöker¶ és D/R rR -gyöker¶ (k, `)-élösszefügg®. Ekkor D r0 -gyöker¶ (k, `)-élösszefügg®. Bizonyítás: 1. El®ször a lemma els® részét bizonyítjuk Ha az δD[R] (X ∪ R) ≥ k -ból, akkor teljesül, azt kapjuk, hogy ami δD (X) ≥ k . miatt teljesül, azt kapjuk, hogy halmazra D[R] r0 -gyöker¶ k -élösszefügg® δD/R (X − R + rR ) ≥ k -ból, akkor r0 ∈ X ⊂ V Ha az ami r0 ∈ X ⊂ V volta miatt halmazra halmazra R 6⊆ X , (0, `)-élösszefügg® Ha az ami akkor halmazra ρD[R] (X ∪ R) ≥ `-b®l, R ⊆ X, D/R rR -gyöker¶ (0, `)-élösszefügg® ρD (X) ≥ `. volta δD (X) ≥ k . volta miatt teljesül, azt kapjuk, hogy r0 ∈ X ⊂ V R ⊆ X, D/R rR -gyöker¶ k -élösszefügg® 2. A második rész bizonyítása az els®höz hasonlóan a következ® Ha az ⊂ V R 6⊆ X , akkor ami r0 ∈ X ⊂ D[R] r0 -gyöker¶ ρD (X) ≥ `. ρD/R (X − R + rR ) ≥

`-ból, volta miatt teljesül, azt kapjuk, hogy http://www.doksihu 58 4.7 Hipergráfok er®sen összefügg® irányítása  3. A harmadik rész az els® két részb®l rögtön következik A 4.68 Lemma 3 részének segítségével bizonyítható a 462 Tétel az ` = 1 esetben analóg módon a 4.65 Tétel bizonyításával Ehhez szükség van még a 452 Tételre, és Menger-tételének irányított hipergráfokra való alábbi kiterjesztésére : 4.69 Tétel Legyen D = (V, A) Akkor és csak akkor fut k irányított hipergráf irányított hiperút s s-b®l t-be, és t két tetsz®leges csúcsa. ha minden X st-halmazra ρD (X) ≥ k . Bizonyítás: Az illeszkedési gráfot irányítsuk úgy, hogy minden tövéb®l A A∈A irányított hiperél felé legyen az él irányítva, míg a hegyhez futó él legyen a hegy felé irányítva. Az így kapott gráfban pontosan akkor van k st út, ha D-ben is van, és erre alkalmazva az irányított él-Menger

tételt kapjuk, hogy ez pontosan akkor teljesül, ha a gráfban minden ez pontosan akkor teljesül, ha st-halmazbefoka D-ben minden legalább k, és könnyen látható, hogy st-halmazbefoka legalább k.  Így láthatjuk azt is, hogy a 4.66 Algoritmus is m¶ködik irányított hipergráfokra is. Mindkét esetben az algoritmus futási ideje |V |-szerese a gyökeresen k -összefügg®- vé irányító algoritmus idejének, ez gráfokra megegyezik az általános elméletb®l nyerttel, ámde annál jóval egyszer¶bb, hipergráfokra egy kicsit lassabb. 4.7 Hipergráfok er®sen összefügg® irányítása A 4.66 Algoritmus hipergráfokra vonatkozó változata a k = 1 esetben meg- adja a hipergráf er®sen összefügg® irányítását. Ez azért jó, mert ha a gyökeresen összefügg® irányítást a 4.5 szakaszban leírtnál egyszer¶bben tudnánk számolni, akkor egy egyszer¶ algoritmust kapnánk hipergráfok er®sen összefügg® irányításának megtalálására.

4.71 Megjegyzés Gráfokra ilyen egyszer¶ algoritmus bármely keresési algoritmus, mivel egy tetsz®leges fát a gráfban egy gyökért®l kifele irányítva gyökeresen élösszefügg® irányítást kapunk, viszont gráfok er®sen összefügg® irányítását fülfelbontásokkal gyorsan és egyszer¶en meg tudjuk találni, így ebben az esetben nem annyira érdekes más er®sen összefügg®vé irányító algoritmus. http://www.doksihu 59 4. Fejezet : Irányítások Hasonlóan a gráfokhoz hipergráfokra is egy feszít® fát fogunk megkeresni, ami a hipergrakus matroid egy bázisa. H = (V, E) egy hipergráf. Szeretnénk a H-hoz tartozó hipergrakus Legyen tehát matroid egy bázisát meghatározni. Az erre vonatkozó algoritmust az alábbi tétel bizonyításából fogjuk kiolvasni : 4.72 Tétel (*). Egy γ elem¶ R ⊆ V, hogy H = (V, E) H hipergráfban akkor és csak akkor létezik olyan megirányítható oly módon, hogy V elérhet® irányított úton,

ha minden P = {V1 , V2 , .Vq } R-b®l minden más csúcs partíciójára eH (P) ≥ q − γ. Bizonyítás: R (4.10) Legyen G = (V, E, E0 ) páros gráf a H illeszkedési gráfja. A tételbeli halmaz és a hozzá tartozó irányítás megadása ekvivalens a egy n−γ H illeszkedési gráfján elem¶ olyan  jó párosítás éleinek lefele irányításával a többi él felfele irányítása mellett, (bár ekkor a nem fedett hiperéleket valójában nem irányítjuk meg). 4.73 Állítás G hiperélek minden egy párosítása pontosan akkor jó, ha a párosítás által fedett ∅ 6= A ⊆ E Bizonyítás: Ha az M részhalmazára teljesül, hogy |ΓG (A)| ≥ |A| + 1. párosítás  jó, akkor ha lenne olyan ∅ 6= A ⊆ E , melyre |A| ≤ ≤ |ΓG (A)| < |A| + 1, akkor A-ba nem lépne V − ΓG (A)-ból él, ΓG (A)-ba pedig csak A-ból mehet párosításél, így ΓG (A) nem érhet® el a nem fedett pontokból alternáló úton, ami

ellentmondás. Ha pedig egy párosításra teljesül az állításban adott feltétel, akkor egy a párosítás által fedett v∈V csúcsra nézzük az ® párját, ennek a szomszédai legalább ketten vannak. Ezeknek, ha mind fedettek, ismét nézzük a párjaikat, majd ezek szomszédjait, és így tovább, amíg csak fedett csúcs van a halmazban Így egy szigorúan b®vül® halmazsorozatot kapunk, mely így valamikor tartalmazni fog nem fedett csúcsot, amikor is megállhatunk, mivel ebb®l a csúcsból van irányított út lyet az az alternáló út ad, amelyen által fedett Legyen V -beli v∈V M0 maximális elemszámú  jó párosítás G-nek D0 . 0 R, ahol 0 me- ide jutottunk. Mivel ez minden a párosítás  csúcsra igaz, így a párosítás  jó. csúcsok halmaza irányítása v -b®l v -be D-ben, 0 |R | = γ , G-n, valamint az és legyen a nem fedett M0 által meghatározott http://www.doksihu 60 4.7 Hipergráfok er®sen összefügg®

irányítása r ∈ R0 -re Xr Legyen M 0 -párjait feszíti kívülr®l, amivel az ® jelöli az R0 − r-b®l r 6= r0 R0 -beli halmaza. Ekkor csúcsok az M 0 alternáló úton el nem érhet® csúcsokra Xr H-ban, Xr és Xr0 diszjunktak. Az (Xr −r)-beli csúcsok M 0 -párjait, akkor Ar csúcsaiba r ∈ ΓG (A), és a maximális olyan |ΓG (A)| = |A| + 1, Xr feszíti olyan P s®t ha R − r-b®l is. Ha E Xr -be A részhalmaza mivel ha lenne másik R − r-b®l. visszajutni, mivel a V − Xr -beli egy nem fedett hiperél, és erre van egy út E -be, ami V -b®l Xr -beli csak r ∈ R0 , P és M0 szimmetrikus dierenciája V -beli R − r-b®l, azaz a módosított párosítás is  jó. Ehhez elég azt belátni, hogy P mind elérhet®ek, mivel csak Xr hogy csúcsokon halad át. Azt látjuk be, hogy által adott párosításhoz tartozó irányítás, továbbra is elérhet® minden E csúcsok E -t, ugyanis ha E -nek van pontja Xr

-ben, és azon kívül is, akkor fut r-b®l út megfordítása által kapott irányításban, ami hogy Ar r-b®l megy irányított út, ami nem léphet V −Xr -beli csúcsba, mivel ha ilyenbe lép, akkor nem tudnánk elérhet®ek (Xr − r)-beli R0 − r-b®l D0 -ben, ilyen, akkor annak a szomszédai sem lennének elérhet®ek Xr csúcsok mivel különben egy ilyen hiperélbe lépne él -párjához is el tudnánk jutni a párosított éleknek, melyre V -beli P csúcs csúcsai élein módosul az irányítás. Ehhez viszont elég látni, továbbra is elérhet®, ami azért teljesül, mert deníciója szerint fut olyan út E -nek van Xr -en kívüli, amibe R − r-b®l, ami nem lép Xr -be, így nem tartalmaz módosított élet, azaz a módosított irányításban is benne van, amib®l következik, hogy P Ha minden pontja is elérhet®, amib®l jön az ellentmondás. E nem metsz bele semelyik alapján létez® olyan + E)| = |A| + 1. A Xr -be, akkor

tekintsünk egy a 4.73 Állítás részhalmazát a párosított hiperéleknek, melyre Ekkor minde r ∈ R-re A ∩ Ar = ∅, mert különben |ΓG (A + |ΓG (A ∪ Ar )| ≤ ≤ |ΓG (A)|+|ΓG (Ar )|−|ΓG (A∩Ar )| ≤ |A|+1+|Ar |+1−|A∩Ar |−1 = |A∪Ar |+1, ami ellentmond Ar maximalitásának, mivel csúcsot. Ez alapján az Ar -ek A 6= Ar , mert E nem tartalmaz Xr -beli által még fel nem particionált párosított hiperélekb®l válasszunk ki maximális olyan A-kat, melyekre |ΓG (A)| = |A| + 1. Ekkor a kapott A halmazok diszjunktak, mivel, ha A és A0 metszenek, akkor |ΓG (A∪A0 )| ≤ |ΓG (A)|+ + |ΓG (A0 )| − |ΓG (A ∩ A0 )| ≤ |A| + 1 + |A0 | + 1 − |A ∩ A0 | − 1 = |A ∪ A0 | + 1- S®t ekkor az ezekb®l nyert ΓG (A) halmazok is diszjunktak egymástól és az is, ugyanis különben lenne olyan 0 A és A0 (ahol az egyik 0 A Ar Xr halmazoktól is lehet), melyekre |ΓG (A ∪ A )| ≤ |ΓG (A)| + |ΓG (A )| − 1 ≤ |A| + 1

+ |A | + 1 − 1 = |A ∪ A0 | + 1, ahol az utolsó egyenl®ség azért teljesül, mert 0 A és A0 diszjunktak. Ezzel ha a nem http://www.doksihu 61 4. Fejezet : Irányítások fedett csúcsokat még egy részes halmazokként bevesszük, olyan partícióját kapjuk V -nek, melyre igaz, hogy minden nem párosított hiperélet feszíti valamelyik tagja a partíciónak. Az is igaz, hogy A-beli r ∈ R0 -re a Ar -beli hiperéleket illetve a fent deniált hiperéleket is feszítik a partíció tagjai, amib®l, mivel |A| = |ΓG (A)| − 1, az következik hogy pont mint kereszt-hiperéle, ami azaz az M 0 -höz |R0 | > γ |R0 |-vel |Ar | = |Xr − r|, és több tagja van a partíciónak, esetén sértené a tétel feltételét, tehát |R0 | ≤ γ ,  tartozó irányítás jó. A tétel bizonyításából az alábbi algoritmust kapjuk. 4.74 Algoritmus (*). Kimenet : −γ H-hoz H = (V, E) hipergráf. tartozó hipergrakus matroid egy bázisa, és

amennyiben ez elem¶, akkor egy R-b®l Bemenet : γ elem¶ R ⊆ V, és ehhez H-nak n− egy olyan irányítása, hogy minden más csúcs irányított úton elérhet®, továbbá, ha γ 6= 1, V egy olyan P partíciója, melyre (4.10) egyenl®séggel teljesül H Legyen olyan M illeszkedési gráfja a G = (V, E, E) párosítást, hogy legyen nem fedett mazából minden irányításában V -beli páros gráf. Ebben keresünk maximális V -beli csúcs, és ezek ∅ 6= R ⊆ V fedett csúcs irányított úton elérhet® legyen az M -hez hal- tartozó G-nek. Tároljuk még a nem vizsgált hiperélek F ⊆E halmazát. Kiindulás : R := V , M := ∅, F := E . Általános lépés : Ismételd amíg F ∈F Legyen Ha F 6= ∅. tetsz®leges. |ΓG (F ) ∩ R| ≥ 2, Akkor legyen v ∈ ΓG (F ) ∩ R tetsz®leges, R := R − v, M := = M + F v, F := F − F . Ha ΓG (F ) ∩ R = {v}, legyen X⊆V az elért pontok halmaza Ha + F v, F := F − F , Ha

és ΓG (F ) ∩ R = ∅, F -re Akkor futtassunk alternáló keresést Különben v ∈ X, Akkor M és R := R − v, M := M + R := R, M := M, F := F − F. Akkor tetsz®leges R-b®l ΓG (F ) vezet® az el®z® eset feltétele teljesül. Befejezés : Az M + F v -n R − v -b®l, által párosított hiperéleket adjuk ki, mint bázis. P útra M := M 4 P -re http://www.doksihu 62 4.7 Hipergráfok er®sen összefügg® irányítása R-et adjuk ki gyökérhalmaznak és hozzá az Minden r ∈ R-re M -hez futtassunk alternáló keresést tartozó irányítást. R − r-b®l, így el nem ért csúcsok  halmaza. Xr ∪ r∈R Futtassunk alternáló keresést Amíg van Legyen % Xv Ha Legyen v∈V − S S Xv egy Xv és legyen (r ∈)Xr ⊆ V az  v ∈ V − R : ∃Xv Xv v -b®l csúcs : nem párosítás élen indulva. az elért csúcsok halmaza. 0 v ∈ V -re már létez® tartalmazza valamely P = {Xv : v ∈ R Xv0 halmazt vagy

tartalmazza vagy diszjunkt t®le. Xv0 -t, vagy olyan akkor töröljük v ∈ V − R, Xv0 -t. melyre van Xv }.  Az algoritmus O(|E|+|V |)-szer futtat alternáló keresést, ami O P  |E| id®ben E∈E fut. Ezt az algoritmust meghívva a gyökeresen-(k,1)-élösszefügg®vé irányító algorit-  musban az er®sen összefügg® irányítás megtalálására egy P O |V |(|E| + |V |)  |E| E∈E idej¶ algoritmust kapunk. 4.75 Megjegyzés Ennél jobb algoritmust kapunk, ha a mai ismereteink szerint gyorsítjuk [7] fokszámkorlátosan er®sen összefügg®vé irányító algoritmusát, és azt az illeszkedési gráfra alkalmazzuk úgy, hogy minden befok korlátot is |E| − 1-nek |E| ∈ E hiperélen az alsó és fels® választjuk. Maga az algoritmus hasonlít az irányítási al- goritmusra ; azon annyit kell változtatni, hogy eleve egy er®sen összefügg® irányításból indulunk ki, és ezt mindig úgy változtatjuk, hogy ügyelünk arra, hogy ne

fordítsunk meg olyan élet, mely belép egy befokú halmazba. Ehhez meg kell határozni, hogy mely csúcsokba megy legalább két diszjunkt út a hibás csúcsból, amire a ma ismert leggyorsabb algoritmus Suurballe és Tarjan sokkal általánosabb algoritmusa [19]. Ezekb®l a  hipergráf er®sen összefügg® irányítására O log  P ! |E| E∈E 1+ |V |+|E| (|E| + |V |)  2 P |E|  E∈E idej¶ algoritmust kapunk. Hipergráf gyökeres élösszefügg®vé irányítására is alkalmas [7] egy másik algoritmusa, melyre szintén a fenti futási id®t kapjuk, aminél az itt vázolt algoritmus gyorsabb. http://www.doksihu 63 4. Fejezet : Irányítások 4.8 Alkalmazás: Matroidok minimális vágásai A (k, `)-partíció-összefügg®ség (` > 0-ra) per)élet elhagyva egy k -partíció-összefügg®. hogy a (hiper)gráfban még mindig van kell a (k, `)-partíció-összefügg®séget k azt jelenti, hogy ` tetsz®leges (hi- Ez Tutte [20] tétele szerint

azt jelenti, feszít®fa. A fentiekben láttuk, hogy hogyan ellen®rizni, amennyiben 0 ≤ ` ≤ k. Király [15] többek közt ezt felhasználva megmutatta, hogy (hiper)grakus matroidok minimális vágása meghatározható. 4.81 Megjegyzés A (hiper)grakus matroidok (k -szorosának) minimális vágásának meghatározásán kívül a transzverzális matroid minimális vágását is meg tudjuk határozni. Tekintsük a dot, melyben tehát G = (S, T, E) F ⊆S páros gráal megadott transzverzális matroi- pontosan akkor független, ha bepárosítható T -be. (Érdemes megjegyezni, hogy amennyiben a transzverzális matroidot, mint számolgatós matroidot nézzük, a fenti gráf a hipergráf illeszkedési gráfjának felel meg.) Alternáló utas algoritmussal határozzuk meg fedi T -t, G egy maximális M párosítását. Ha ez a párosítás nem akkor a nem fedett csúcsok nem érhet®ek el alternáló úton a nem fedett beli csúcsok nem fedett R halmazából, így ,

(mivel feltehet®, hogy nincs izolált csúcs T -beliek párosítás, (ahol valamelyik t s M -párja), utat. Ezért feltehetjük, hogy M s∈S szomszédját elhagyva T fedi T -t, ne legyen párosítható és a vágás a lesz a maximális s®t azt is, hogy van nem fedett S − Z -re, Z ⊆S azaz valamely meg a Hall-feltétel. Ezek szerint a minimális vágás elemszáma : X ⊆ T } + 1, T -ben), mivel az alternáló utas algoritmus nem talál javító mivel különben bármely csúcs vágást alkotna. Ahhoz, hogy az kell, hogy M − st S- ΓG (X) X -hez S -beli csúcs, vágás legyen így X ⊆ T -re sérüljön min{|ΓG (X)| − |X| : nem párosított csúcsaiból, és még egy X -hez párosított csúcsból áll. A fenti minimum meghatározásához tekintsük azt a nyított gráfot, ahol s∗ új csúcsból az M által fedetlen minden elemébe fut egy irányított él, és a többi él T D = (S ∪ T ∪ {s∗ }, A) S -beli M csúcsok

éleinek S, halmazának a többi G-beli él felé irányításából keletkezik. Ebben az irányított gráfban könnyen látható, hogy két s∗ -ból valamely t∈T csúcsba futó út pontosan akkor éldiszjunkt, ha közös bel- s® pont nélküliek, és így a Menger-tétel segítségével igazolható, hogy min{|ΓG (X)| − |X| : t ∈ X ⊆ T } X R irá- halmaz egy s∗ forrású t-be pontosan éldiszjunkt út megy, s®t a minimum és az azt adó t nyel®jú folyam-algoritmus segítségével meg is határozható. http://www.doksihu 64 4.9 Lokális halmaz-élösszefügg®ség meg®rzése Ezt az algoritmust minden t ∈ T -re futtatva a fent kívánt minimumot, és a matroid minimális vágását is megkaphatjuk. 4.82 Megjegyzés Az imént leírt algoritmus szintén a reprezentáló gráf egy megfelel® irányításán alapul, csakúgy, mint a korábban említett, illetve az itt nem leírt esetei a (k -szoros) (hiper)grakus matroidok minimális

vágásának. Ez veti fel azt a kérdést, hogy számolgatós matroidok minimális vágásait (speciálisan a merevségi matroid minimális vágását) meg lehet-e határozni valamilyen irányítási tétel segítségével. (Számolgatós matroidok minimális vágása a kombinatorikus optimalizálás egyik érdekes nyitott problémája [2].) 4.9 Lokális halmaz-élösszefügg®ség meg®rzése Ebben a szakaszban látni fogjuk, hogy az alábbi sejtés egy gyengítése következik az itt korábban leírtakból. 4.91 Sejtés Van olyan G = (V, E) gráfon igényekre teljesül olyan C ≥ 2 {Xi , Yi } V egész, melyre teljesül az alábbi állítás. Ha a λG (Xi , Yi ) ≥ Cfi minden irányítása, melyre min{λD (Xi , Yi ), λD (Yi , Xi )} ≥ fi D = (V, A) fi ∈ Z diszjunkt részhalmazaiból álló párok, és i ∈ {1,2, ., k}-ra, akkor G-nek van minden i∈ ∈ {1,2, ., k}-ra A fenti sejtés halmazpárok helyett pontpárokra Nash-Williams tétele [18] szerint C =

2-vel igaz. Fukunaga [11] a fenti sejtés vizsgálatakor a 4.43 Tételb®l az alábbi érdekes tételt bizonyította. 4.92 Tétel Legyen = (V, E) minden r ∈ V , X1 , X2 , ., Xk ⊆ V − r, gráfnak létezik olyan i ∈ {1,2, ., k}-ra, ha D = (V, A) és f1 , f2 , ., fk ∈ Z irányítása, melyre λg (r, Xi ) ≥ ifi minden Egy λD (r, Xi ) ≥ fi G= teljesül i ∈ {1,2, ., k}-ra Bizonyítás (vázlat): A tételt úgy bizonyítjuk, hogy rekurzívan megkonstruálunk D1 = (V, A1 ), D2 = (V, A2 ), ., Dk = (V, AK ) ⊆ Ai+1 , és minden i ∈ {1,2, ., k}-ra λDi (r, Xj ) ≥ fj minden részirányításait G-nek, hogy Ai ⊆ teljesül j ∈ {1,2, ., i}-re, (4.11) http://www.doksihu 65 4. Fejezet : Irányítások és δDi (Y ) ≤ i ρDi (Y ) minden Xj ⊆ Y ⊆ V − r-re, D1 X1 megkonstruálásához f1 éldiszjunkt ahol j ∈ {i +1, i+2, ., n} r-b®l X1 -be felé, és ezeket az irányított éleket tegyük A1 -be. (4.12) futó utat

irányítsunk meg Ekkor könny¶ ellen®rizni, hogy (4.11) és (412) fennáll Ha már 0 0 Di -t deniáltuk valamely 1 ≤ i < n-re, akkor Di+1 0 D = (V , A ) = Di /Xi+1 , h(X) := és deniáljuk azt a  f − ρD0 (X),    i+1 −fi+1 − ρD0 (X), halmazfüggvényt ha vXi+1 ∈ X és r 6∈ X, ha vXi+1 6∈ X és r ∈ X,    Erre a h −ρD0 (X), deniálásához legyen V 0 -n, melyre különben. h-ra megmutatható, hogy metsz®n szupermoduláris, és teljesíti a 4.43 Tétel feltételét azon a ha összehúzzuk ®sét hozzávéve = (V, Ai+1 ) G0 gráfon, melyet a még meg nem irányított élek gráfjából kapunk, Xi+1 -et. Ai -hez a Így 0 G0 -nek G -n van h-t fed® irányítása, amib®l ezen élek deniált irányítással belátható, hogy a kapott gráfra (4.11) és (412) fennáll G-beli Di+1 =  http://www.doksihu 5. fejezet Összefoglalás, további kérdések A 2. fejezetben láttuk, hogy hogyan kapható

meg keresztezés-mentes halmazrendszerek fa-reprezentációja, valamint, hogy hogyan alkalmazható algoritmusokban a kikeresztezési eljárás Ezen kívül ezek alkalmazásaként algoritmust adtunk S -T fa-kompozíció kiválasztására S -T -elválasztó keresztez® rendszerb®l. Ezek felhasználásával a 3. fejezetben algoritmust adtunk a Fujishige-tétel bizonyítása alapján, ami f®leg a kikeresztezés lassúsága miatt, elég lassú volt Ennek javításaként megismerkedtünk a javított teljes reszelési algoritmussal. Az irányítási algoritmusok segítségével a teljes reszel® algoritmusból általános gráf és hipergráf irányítási algoritmusokat nyertünk. Ezekb®l speciális esetként kiolvastuk a gyökeresen (k, `)-élösszefügg® irányítás megadására vonatkozó algorit- must, mely segítségével (további itt nem tárgyalt algoritmusok bevonásával) meg lehet határozni a k -szoros (hiper)grakus matroidok minimális vágását. Itt felve-

t®dött az a kérdés, hogy esetleg más keresztez® szupermoduláris függvényre alkalmazva az irányítási algoritmusokat más számolgatós matroidok minimális vágásai is meghatározhatóak-e ? Ennek tükrében különösen érdemes speciális h-kra felírni a tételt, mint azt a 4.9 szakaszban meg is tettük Mivel a teljes reszel® algoritmus elég bonyolult, érdemes volt egyszer¶bb algoritmust adni a (k, `)-élösszefügg®vé irányítás megkeresésére. Ezt az ` = 1 esetben sikerült is megtennünk, ami hasznos, mivel ez egy olyan eset, amit más területekkel (szerkezetek merevségével) foglalkozó matematikusok is használnak. Itt felvet®dik az a kérdés, hogy nagyobb `-re nem adható-e hasonló egyszer¶ algoritmus ? Mivel ez nem t¶nik túl valószín¶nek, érdemes ennek speciális esetét vizsgálni, például `= http://www.doksihu 5. Fejezet : Összefoglalás, további kérdések = k − 1-re A 67 adható-e egyszer¶ algoritmus ?

(k,1)-élösszefügg®vé irányító algoritmus segítségével hipergráfok er®sen össze- függ® irányításának megtalálására sikerült egy szintén egyszer¶ algoritmust adni. Ennek kapcsán beletekintettünk az erre ismert leggyorsabb algoritmusba, mely egy viszonylag bonyolult algoritmust használt. Ez felveti azt a kérdést, hogy nem adhatóe hasonlóan gyors s®t lineáris idej¶ gyors algoritmus annak eldöntésére, hogy egy irányított gráfban mely csúcsokba fut két él-diszjunkt irányított út ? http://www.doksihu Irodalomjegyzék [1] A. Bernáth A representation for intersecting families. Mat. Lapok (NS), 13(1) :612, 2006/07. (Hungarian, with English summary) [2] EGRES. Egres open problems lemon.cseltehu/egres/open/Destroying rigidity [3] A. Frank On disjoint trees and arborescences In Algebraic Methods in Graph Theory, 25, pages 59169. Colloquia Mathematica Soc J Bolyai, Norh-Holland, 1978. [4] A. Frank On the orientation of graphs J Comb

Theory, Ser B, 28(3) :251 261, 1980. [5] A. Frank Orientations of graphs and submodular ows Conguressus Nume- rantium, 113 :111142, 1996. [6] A. Frank Poliéderes kombinatorika. ELTE TTK, 2007. (Hungarian.) www.cseltehu/frank/jegyzet/polkomb/ [7] A. Frank and A Gyárfás How to orient the edges of a graph In Combinato- rics, 18, pages 353364. Colloquia Mathematica Soc J Bolyai, Norh-Holland, Keszthely, 1976. [8] A. Frank, T Király, and Z Király On the orientation of graphs and hypergraphs Discrete Applied Mathematics, 131(2) :385400, 2003 [9] A. Frank and É Tardos Generalized polymatroids and submodular ows. Mathematical Programming, 42 :489563, 1988. 68 http://www.doksihu 69 IRODALOMJEGYZÉK [10] S. Fujishige Structures of polyhedra determined by submodular functions on crossing families. Mathematical Programming, 29 :125141, 1984 [11] T. Fukunaga Graph orientations with set connectivity requirements In Yingfei Dong, Ding-Zhu Du, and Oscar H. Ibarra,

editors, ISAAC, volume 5878 of Lecture Notes in Computer Science, pages 265274. Springer, 2009 [12] A. V Goldberg and R E Tarjan A new approach to the maximum ow problem. In STOC, pages 136146 ACM, 1986 [13] S. L Hakimi On the degrees of the vertices of a directed graph J Franklin Inst., 279(4) :290308, 1969 [14] Cs. Király Simple algorithm for (k,1)-arc-connected orientation of a gra- ph. Technical Report QP-2010-02, Egerváry Research Group, Budapest, 2010 www.cseltehu/egres [15] T. Király. Computing the minimum cut in hypergraphic matroids. Technical Report QP-2009-05, Egerváry Research Group, Budapest, 2009. www.cseltehu/egres [16] C. L Lucchesi and D H Younger A minimax relation for directed graphs J London Math. Soc, s2-17(3) :369374, 1978 [17] T. Naitoh and S Fujishige A note on the frank-tardos bi-truncation algorithm for crossing-submodular functions. Mathematical Programming, 53 :361363, 1992. [18] C. S J A Nash-Williams On orientations,

connectivity and odd vertex pairings is nite. Canadian Journal of Mathematics, 12 :555567, 1960 [19] J. W Suurballe and R E Tarjan A quick method for nding shortest pairs of disjoint paths. Networks, 14(2) :325336, 1984 [20] W. T Tutte On the problem of decomposing a graph into n connected factors J. London Math Soc, 36 :221230, 1961