VA LOGATOTT FEJEZETEK A KOMBINATORIKUS OPTIMALIZA LA SBAN (Frank Andras)
1. FEDE S E S PAKOLA S FENYO} KKEL E S FA KKAL Az alabbiakban tobb helyutt is szuksegunk lesz a kovetkez}o lemmara, ezert hasznalunk a szerepl}o grafra es befok fuggvenyre vessz}os jelolest. Legyen D0 = (V; E) iranytott graf %0 befok fuggvennyel es L a V reszhalmazainak olyan rendszere, amelyre X; Y 2 L; X \ Y 6= ;-b}ol kovetkezik, hogy X \ Y; X [ Y 2 L. Tegyuk fel, hogy %0 (X) k0 fennall minden X 2 L halmazra. Nevezzuk X-t pontosnak, ha %0 (X) = k0 .
1.0 LEMMA Ket egymast metsz}o pontos halmaz metszete es unioja is pontos. A maximalis pontos halmazok diszjunktak.
Biz. A masodik resz nyilvan kovetkezik az els}ob}ol. Felhasznalva %0 szubmodularitasat azt kapjuk, hogy k0 + k0 = %0 (X) + %0 (Y ) %0 (X [ Y ) + %0 (X \ Y ) k0 + k0 , amib}ol a lemma kovetkezik. Alapvet}o a kovetkez}o J. Edmondstol [1973] szarmazo tetel, amelyre kes}obb gyenge feny}opakolasi tetelkent fogunk hivatkozni, megkulonboztetend}o az er}os alaktol, amelyben el}ore megadott reszfeny}oket kell kiegeszteni. (Ennek pontos kimondasa es bizonytasa a Matroidelmelet jegyzet 9. fejezeteben szerepelt.)
1.1 TE TEL Adott egy D = (V; A) iranytott graf egy s kijelolt ponttal es adott egy k 0 egesz szam. Akkor es csak akkor letezik D-ben k paronkent elidegen s-gyoker}u feszt}o feny}o, ha %(X) k teljesul minden ; 6= X V ? s halmazra.
(1:1)
Biz. [Lovasz, 1976] A feltetel szuksegessege nyilvanvalo. Az elegend}oseg igazolasa k szerinti indukcioval tortenik. k = 0-ra a tetel semmitmondo, gy legyen k > 0. Az s gyokerb}ol kiindulva feleptunk egy F (elhalmazu) feny}ot ugy, hogy
%A?F (X) k ? 1 minden X V ? s halmazra. (1:2) Indukcio alapjan a tetel bizonytasaval keszen vagyunk, ha F-t sikerul (1:2)-t kielegt}o feszt}o feny}ove novelni. Legyen tehat F egy olyan feny}o, amely teljesti (1:2)-t es meg nem feszt}o (azaz V (F) 6= V ). (Kezdetben F allhat az ures halmazbol). Nevezzunk egy X V ? s halmazt pontosnak (F-re nezve), ha (1:2) -t egyenl}oseggel teljesti. Az 1.0 Lemmat %0 := %A?F -re es k0 := k ? 1-re alkalmazva azt kapjuk, hogy ket egymast metsz}o pontos halmaz metszete is az. Celunk olyan e elt talalni, amelynek tove V (F)-ben van, feje V ? V (F)-ben van, es nem lep pontos halmazba. Az (1:1) feltetel szerint V ? V (F)-nek nincsen pontos reszhalmaza. Amennyiben minden pontos halmaz benne van V (F)-ben, ugy barmely V (F)-b}ol kilep}o e elre az F 0 = F + e feny}o kielegti (1.2)-t. Ha van olyan M pontos halmaz, amelyre M ? V (F) 6= ;, akkor ezek kozul legyen M egy minimalis. Ekkor van olyan e = uv 2 A el, amelyre u 2 M \ V (F) es v 2 M ? V (F). Valoban, ha ilyen el nem letezne, akkor k ? 1 %0 (M ? V (F)) %0 (M) = k ? 1 miatt k ? 1 = %0 (M ? V (F)) = %(M ? V (F)) volna, vagyis X := M ? V (F) megsertene (1:1)-t. Az e el nem lephet semmilyen Y pontos halmazba, mert kulonben az 1.0 lemmat X := M-re es Y -ra alkalmazva azt kapnank, hogy M \ Y is pontos volna, ami viszont M \ Y M ? u miatt ellentetben allna M minimalis valasztasaval. Kovetkezeskepp az F 0 = F + e feny}o is kielegti (1.2)-t.
Gyakorlat Vezessuk le Edmonds teteleb}ol a Menger tetel iranytott, elidegen valtozatat. Az 1998 tavaszan tartott kurzus anyaga 1
Feladat Igazoljuk, hogy egy elelhagyasra nezve minimalis k-elosszefugg}o, n pontu iranytott grafnak legfeljebb 2k(n ? 1) ele van (masszoval, hogy iranytott graf k-szoros elosszefugg}osegenek van legfeljebb 2k(n ? 1)
elt hasznalo tanuja). Peldaval mutassuk meg, hogy ez a korlat eles.
Feladat Legyen c olyan nem-negatv valos sulyozas a D digraf elhalmazan, amelyre %c (X) 1 teljesul minden ; 6= X V ? s halmazra. Nevezzunk egy X halmazt pontosnak, ha itt egyenl}oseg teljesul. Igazoljuk, hogy letezik olyan s-gyoker}u feszt}o feny}o, amely minden pontos halmazba pontosan egyszer lep be.
Feladat Igazoljuk az Edmonds tetel alabbi kiterjeszteset. Legyen D = (V; E) iranytott graf. Legyen F a V ? s reszhalmazainak olyan rendszere, amelyre X; Y 2 F , X \ Y 6= ;-b}ol kovetkezik, hogy X [ Y; X \ Y 2 F . Amennyiben minden X 2 F halmaz befoka legalabb k, akkor E felbonthato k reszre ugy, hogy minden X 2 F -re mindegyik resz tartalmaz X-be lep}o elt. Feladat Adott D = (V; A) iranytott graf es k 0 egesz szam. Legyen s 2 V es T V ? s olyan, hogy minden v 2 V ? s ? T pontra %(v) (v). Akkor es csak akkor letezik D-ben k darab olyan paronkent elidegen s-gyoker}u feny}o, melyek mindegyike tartalmazza T minden pontjat, ha %(X) k teljesul minden olyan ; 6= X V ? s halmazra, amelyre T \ X = 6 ;. Feladat Peldaval mutassuk meg, hogy az el}obbi feladatban a %(v) (v) kovetelmeny nem hagyhato ki. Egy iranytott erd}ot akkor nevezzunk fenyvesnek, ha minden pont befoka legfeljebb egy, azaz ha az erd}o minden komponense feny}o. A 0 befoku pontok halmazat a fenyves gyoker-halmazanak nevezzuk. Egy D = (V; A) iranytott graf feszt}o fenyvesen olyan fenyvest ertunk, amelynek ponthalmaza V , mg elhalmaza az A-nak resze. A kovetkez}o feladat az 1.1 Tetel altalanostasanak tekinthet}o.
Feladat A D = (V; A) iranytott grafban legyen R1; : : :; Rk a pontoknak k (nem feltetlenul diszjunkt, vagy kolonboz}o) reszhalmaza. Akkor es csak akkor letezik D-nek k elidegen feszt}o fenyvese, melyek gyokere rendre R1; : : :; Rk , ha barmely ; 6= Z V reszhalmazra %(Z) legalabb azon Ri halmazok szama, melyek diszjunktak Z-t}ol. 1.2 TE TEL Egy G = (U; A) iranytott grafban akkor es csak akkor letezik k paronkent elidegen feszt}o feny}o, ha
Xt % i=1
G (Xi ) k(t ? 1)
(1:3)
fennall U minden fX1 ; X2; : : :; Xt g resz-partciojara.
Biz. A szukegesseg bizonytasahoz tegyuk fel hogy van k diszjunkt feszt}o feny}o es legyen fX1 ; : : :; Xt g egy resz-partcio. A feszt}o feny}ok mindegyike a t halmaz kozul legalabb t ? 1-be belep, gy (1.3) szuksegessege
kovetkezik. Az elegend}oseg igazolasahoz adjunk G-hez egy uj s-sel jelolt pontot, es vezessunk s-b}ol minden pontba k parhuzamos elt. A keletkezett digrafra persze teljesul (1.1). Hagyjunk most el (tetsz}oleges sorrendben) uj eleket ameddig csak lehetseges az (1.1) feltetel megsertese nelkul. Jelolje D az gy kapott digrafot. Persze %D (U) k. Ha itt egyenl}oseg all, akkor keszen is vagyunk, mert az Edmonds tetel szerint a D-ben van k diszjunkt s-gyoker}u feszt}o feny}o. Ezek mindegyike, %D (U) = k miatt, pontosan egy s-b}ol kilep}o elt hasznal, gy ezen eleket kihagyva G-nek k darab feszt}o feny}ojet kapjuk. Most kimutatjuk, hogy %D (U) > k-bol egy (1.3)-t sert}o resz-partcio letezese kovetkezik. Nevezzuk U egy X reszhalmazat pontosnak, ha %D (X) = k, es jelolje a maximalis pontos halmazokat X1 ; X2; : : :; Xt. Az 1.0 Lemma szerint az Xi halmazok paronkent diszjunktak. Mivel D-b}ol mar uj el nem hagyhato el (1.1) P megsertese nelkul, minden P uj el belep pontos P halmazba, ePs ezert belep valamelyik Xi-be is. Ezekb}ol kt = i %D (Xi ) = %D (U) + i %G (Xi ) > k + i %G (Xi ), azaz %G (Xi ) < k(t ? 1), ellentetben (1.3)-mal.
2
Feladat Iranytott grafban keressunk k elidegen feszt}o fenyvest, melyek egyuttes komponens szama a lehet}o
legkisebb. Mutassuk meg, hogy ez ekvivalens azzal, hogy minimalis szamu uj elt adunk a digrafhoz ugy, hogy a kiegesztett digraf tartalmaz k elidegen feszt}o feny}ot. Az 1.1 tetel egyfajta fedesi ellenparja K. Vidyasankartol [1978] szarmazik.
1.3 TE TEL Legyen s a D = (V; A) digraf egy kijelolt pontja, amibe nem lep be el. D eleit akkor es csak akkor lehet k darab s-gyoker}u feszP t}o feny}ovel fedni, ha (i) minden v 2 V ? s pontra %(v) k, es (ii) minden X V ? s halmazra k ? %(X) (k ? %(v) : v 2 T(X)), ahol T(X) := fv 2 X: letezik olyan uv 2 A el, amelyre u 2 V ? X g. Gyakorlat Igazoljuk az (i) es (ii) feltetelek szuksegesseget. Biz. (Elegend}oseg) Elemi konstrukcioval. Minden v 2 V ? s pontra adjunk D-hez a v egy kopiajat, amelyet v0 -vel jelolunk. Adjunk k parhuzamos elt v-b}ol v0 -be es k ? %(v) parhuzamos elt v0 -b}ol v-be (ezen utobbi szam (i) miatt nem-negatv). Tul ezen, minden uv 2 A elre adjunk k parhuzamos elt u-bol v0 -be. Alkalmazzuk az 1.1 tetelt a megnovelt D0 digrafra es gyeljuk meg, hogy k D0 -beli diszjunkt feszt}o feny}o megfelel k fed}o feny}onek D-ben. Tovabba, ha %0 (X 0 ) < k valamely X 0 V 0 ? s halmazra, ahol %0 a megnovelt digraf befok fuggvenyet jeloli, akkor X = fv 2 X 0 ; v0 62 X 0 g megserti (ii)-t. Az Edmonds tetel egy masik erdekes alkalmazasa a kovetkez}o.
1.4 TE TEL A D = (V; A) digraf elhalmaza akkor es csak akkor fedhet}o le k fenyvessel, ha (i) minden pont befoka legfeljebb k, es (ii) i(X) k(jX j ? 1)teljesul minden X V halmazra, ahol i(X) jeloli az X altal fesztett elek szamat.
Biz. Mindket feltetel szuksegessege nyilvanvalo. Az elegend}oseget elemi konstrukcioval igazoljuk. Adjunk a digrafhoz egy uj s pontot es minden v pontraPk ? %(v) parhuzamos elt s-b}ol v-be. Az uj D0 digrafban minden X V halmazra fennall %0 (X) = %(X)+ (k ? %(v) : v 2 X) = %(X) ? %(X) ? i(X)+kjX j k. Az 1.1 tetel szerint letezik k diszjunkt s-gyoker}u feszt}o feny}o. Ezeket az eredeti D-re megszortva k fenyvest kapunk, melyek fedik D eleit. Iranytatlan grafokra konnyen levezethetjuk Nash-Williams [1960] (tortenetileg korabbi) tetelet.
1.5 TE TEL Egy G = (V; E) iranytatlan graf elhalmaza akkor es csak akkor fedhet}o le k erd}ovel, ha minden ; 6= X V reszhalmazra i(X) k(jX j ? 1). Biz. Az 1.4 tetel es a kovetkez}o konny}u lemmma implikalja a tetelt. LEMMA Egy G = (V; E) iranytatlan graf eleinek akkor es csak akkor van olyan iranytasa, amelyben minden pont befoka legfeljebb k, ha
i(X) kjX j teljesul minden X V -re.
()
Biz. (Elegend}oseg) G egy iranytasaban nevezzunk egyPpontot hibasnak, ha a befoka nagyobb, mint k. Valasszunk G-nek egy olyan iranytasat, amelynek a (%(v) ? k) : v hibas) osszeggel de nialt hibaja
minimalis. Ha ez a hiba 0, vagyis ha nincs hibas csucs, akkor keszen vagyunk. Legyen most a t csucs hibas, es jeloljuk X-szel a megadott iranytasban azon pontok halmazat, amelyekb}ol t elerhet}o. Ekkor X-be nem megy be el, es X szukseP gkeppen tartalmaz egy olyan s pontot, amelyre %(s) < k. Valoban, ha nem letezne ilyen pont, akkor i(X) = (%(v) : v 2 X) > kjX j allna, ellentmondasban ()-gal. Egy s-b}ol t-be vezet}o ut eleinek iranytasat megfordtva G-nek olyan iranytasat kapjuk, amelynek hibaja kisebb, mint a meglev}o iranytase. 3
Feladat Igazoljuk az el}obbi eljarassal, hogy adott g : V ! Z+ [ f1g eseten G-nek P akkor es csak akkor letezik olyan iranytasa, amelyben %(v) g(v) minden v csucsra fennall, ha i(X) v2X g(v). Feladat Adott f : V ! Z+ eseten G-nek P akkor es csak akkor letezik olyan iranytasa, amelyben %(v) f(v) minden v csucsra fennall, ha e(X) v2X f(v), ahol e(X) jeloli azon elek szamat, amelyeknek legalabb egyik vege X-ben van. Amennyiben f g es G-nek letezik az f also korlatot kielegt}o iranytasa es letezik a g fels}o korlatot kielegt}o iranytasa, ugy letezik olyan iranytasa is, amelyben f(v) %(v) g(v) teljesul minden v pontra.
A G = (U; E) iranytatlan grafban d(X; Y ) jelolje az X ? Y es Y ? X kozott vezet}o elek szamat. Legyen Y ) := d(X; U ? Y ) es d(X) := d(X; U ? X). A D = (U; A) iranytott grafban %(X) jeloli az X-be d(X; lep}o elek szamat, (X) := %(U ? X). d(X; Y ) jeloli azon elek szamat melyek egyik vege X ? Y -ben a masik Y ) := d(X; U ? Y ): Y ? X-ben van. d(X;
Gyakorlat Y ): (1:4) d(X) + d(Y ) = d(X \ Y ) + d(X [ Y ) + 2d(X; Y ); d(X) + d(Y ) = d(X ? Y ) + d(Y ? X) + 2d(X;
Gyakorlat %(X) + %(Y ) = %(X \ Y ) + %(X [ Y ) + d(X; Y ): Y ). Ha minden v 2 X \ Y pontra %(v) (v), akkor %(X) + %(Y ) %(X ? Y ) + %(Y ? X) + d(X; Y ). Ha minden v 2 U ? (X [ Y ) pontra %(v) (v), akkor (X) + (Y ) (X ? Y ) + (Y ? X) + d(X; Y ): Ha (X [ Y ) = %(X [ Y ), akkor %(X) + %(Y ) = (X ? Y ) + (Y ? X) + d(X; Iranytasok segtsegevel Edmonds teteleb}ol levezethetjuk Tutte diszjunkt fakra vonatkozo eredmenyet is.
TUTTE TE TELE Egy G = (V; E) iranytatlan grafban akkor es csak akkor letezik k diszjunkt feszt}o fa, ha V minden F := fV1 ; : : :; Vtg partciojara fennall, hogy i(F ) k(t ? 1); (1:5) P ahol i(F ) a reszek kozott vezet}o elek szamat jeloli (azaz i(F ) = i d(Vi)=2). Az elegend}oseg bizonytasa erdekeben csupan azt kell belatnunk, hogy valamely kijelolt s pontra letezik G-nek (1.1)-t kielegt}o iranytasa. Ebben az esetben ugyanis Edmonds tetele miatt a megiranytott grafban letezik k diszjunkt feszt}o feny}o, melyek az eredeti iranytatlan grafban megadjak a keresett k diszjunkt feszt}o fat.
1.6 TE TEL Legyen G = (V; E) iranytatlan graf es s egy kijelolt pontja. Akkor es csak akkor letezik G-nek olyan iranytasa, amelyben %(X) k fennall V ? s minden X reszhalmazara, ha (1.5) teljesul V minden partciojara.
Biz. A tetelben el}ort iranytast nevezzuk az alabbiakban jonak. Ha letezik jo iranytas, akkor mindegyik s-t nem tartalmazo Vi reszhalmazra %(Vi ) k gy i(F ) k(t ? 1). Az elegend}oseg igazolasahoz adjunk G-hez minimalisan sok s-b}ol kiindulo uj elt ugy, hogy a kiegesztett grafban mar letezzek jo iranytas. Ha ez a minimumnulla, akkor keszen vagyunk,gy tegyuk fel, hogy pozitv. Jelolje % a megnovelt graf jo iranytasanak a befok fuggvenyet. Feltehetjuk, hogy %(s) = 0. Nevezzunk egy X V ? s halmazt pontosnak, ha %(X) = k. Az 1.0 Lemma alapjan ket nemures metszet}u pontos halmaz metszete es unioja is pontos. Legyen e = st egyike az ujonnan hozzaadott eleknek es jelolje T a t-b}ol elerhet}o pontok halmazat. 1.7 LEMMA Ha Z pontos es Z \ T 6= ;, akkor Z T. Biz. Tegyuk fel, hogy Z 6 T. Ekkor Y := V ? T-re k = %(Y ) + %(Z) = %(Y \ Z) + %(Y [ Z) + d(Y; Z) k + 0 + d(Y; Z) k. Ebb}ol %(Y [ Z) = 0 es d(Y; Z) = 0 adodik. Az els}o egyenl}oseg miatt t 2 Z (mert 4
kulonben T \ Z pontjai nem lennenek elerhet}oek t-b}ol). Ekkor viszont az e el miatt d(Y; Z) > 0, amely ellentmondas a lemmat bizonytja. Ket eset lehetseges. Ha letezik T-ben olyan v pont, amely nincs benne pontos halmazban, akkor vegyunk egy t-b}ol v-be vezet}o P iranytott utat, fordtsuk meg P eleinek iranytasat, es hagyjuk ki az e elt. Az uj iranytas tovabbra is jo lesz, ellenmondasban az uj elek szamanak minimalitasaval. Nezzuk most azt az esetet, amikor T minden pontja benne van egy pontos halmazban. Jelolje V1; : : :; Vt?1 azon maximalis pontos halmazokat, melyek metszik T-t. Az 1.0 Lemma szerint ezek paronkent diszjunktak es az 1.7 Lemma szerint a T part Pciojat alkotjak. Legyen Vt := V P? T es F := fV1; : : :; Vtg. Mivel %(Vt) = 0, azt kapjuk, hogy k(t ? 1) = (%(Vi ) : i = 1; : : :; (t ? 1)) = (%(Vi ) : i = 1; : : :; t) = i0 (F ) > i(F ), ellentmondasban (1.5)-tel. (Itt i0 (F ) a kulonboz}o reszek kozotti elek szamat jeloli a megnovelt grafban es az e uj el lete miatt biztosan nagyobb, mint i(F ).)
2. IRA NYITATLAN LEEMELE SEK E S ALKALMAZA SAIK: I. Legyen G = (U; E) iranytatlan grafnak e = su es f = sv ket szomszedos ele. Azt mondjuk, hogy a Gef = (U; E ? fe; f g + uv) graf a G-b}ol az e es f elek leemelesevel keletkezett. Analog modon de nialhatjuk a leemelest egy G = (U; E) iranytott grafban is: legyenek e = us es f = sv iranytott elek, ekkor de ncio szerint Gef = (U; E ? fe; f g + uv). Konnyen latszik, hogy mind az iranytott, mind az iranytatlan esetben (x; y; G) (x; y; Gef ) minden x; y pontparra fennall. Tehat leemelessel az elosszefugg}oseg csak csokkenhet. Kerdes, hogy mikor nem csokken. A kovetkez}o alapavet}o tetel Lovasztol szarmazik.
2.1 TE TEL Legyen a G = (V + s; E) iranytatlan grafban az s pont d(s) foka pozitv es paros, es tegyuk fel, hogy (x; y; G) k minden x; y 2 V pontparra, (2:0) ef ahol k 2 egesz. Ekkor minden e = st elhez letezik olyan f = sv el, amelyekre (x; y; G ) k minden x; y 2 V pontparra. Biz. Menger tetele alapjan a (2:0) felteves azzal ekvivalens, hogy d(X) k minden ; 6= X V reszhalmazra, (2:1) ahol d(X) jeloli az X halmaz fokszamat, vagyis azon elek szamat melyeknek az egyik vegpontja X-ben van, a masik X-n kvul. Leemeleskor ha egy halmaznak csokken a fokszama, akkor 2-vel csokken. Egy X V reszhalmazt nevezzunk veszelyesnek, ha d(X) k + 1 es legyen F a t pontot tartalmazo maximalis (azaz
nem b}ovthet}o) veszelyes halmazainak a rendszere. Legyen S az s szomszedainak halmaza. Egy f = sv el akkor nem emelhet}o le az adott e = st ellel, ha v benne van egy t pontot tartalmazo veszelyes halmazban, azaz v benne van F valamelyik tagjaban. A tetel bizonytasahoz azt kell kimutatnunk, hogy F nem fedheti le S minden pontjat. Ehhez szuksegunk van az alabbi lemmara.
2.2 LEMMA Egy iranytatlan grafban, melynek ponthalmaza U, barmely A; B; C U halmazra fennall a kovetkez}o azonossag. d(A) + d(B) + d(C) d(A \ B \ C) + d(A ? (B [ C)) + d(B ? (A [ C)) + d(C ? (A [ B)) + 2d(A \ B \ C; U ? (A [ B [ B)): Biz. Az egyenl}otlenseget eleg egyel}u grafokra igazolni. Ilyenekre pedig az egyenl}otlenseg az el elhelyezkedeset}ol fugg}o egyszer}u esetszetvalasztassal ellen}orizhet}o. A lltjuk, hogy jFj 2. Ha ugyanis A; B; C 2 F , akkor a lemma alapjan 3(k + 1) d(A) + d(B) + d(C) d(A \ B \ C)+d(A ? (B [ C))+d(B ? (A [ C))+d(C ? (A [ B))+2d(A \ B \ C; U ? (A [ B [ B)) k+k+k+k+2, ami ellentmond a k 2 feltevesnek. Nem letezhet F -ben S-et magaban foglalo veszelyes X halmaz, mert akkor d(V ? X) = d(X) ? d(s) (k + 1) ? 2 = k ? 1, ami ellentmondana (2.1)-nek. 5
Az sem lehet, hogy az F ket X; Y tagja lefedi S-t. Ebben az esetben ugyanis k+1+k+1 d(X)+d(Y ) = Y ) k + k + 2; amib}ol az adodik, hogy s-b}ol egyetlen el megy X \ Y -ba. d(X ? Y ) + d(Y ? X) + 2d(X; Az := d(s; X ? Y ) es := d(s; Y ? x) jelolest hasznalva azt kapjuk, hogy d(s) = 1 + + . Miutan d(s) paros, 6= es legyen mondjuk > . De ekkor d(V ? X) = d(X + s) = d(X) ? ( + 1) + d(X) ? 2 (k + 1) ? 2 k ? 1, vagyis V ? X megserti (2.1)-t.
Gyakorlat Peldan mutassuk meg, hogy a fenti tetel k = 1-re nem ervenyes. Mutassuk meg, hogy a tetelben a d(s) parossagara tett feltetel nem hagyhato ki. 2.1A TE TEL Legyen a G = (V + s; E) iranytatlan grafban az s pont d(s) foka pozitv es paros, es tegyuk fel, hogy (2:0) (x; y; G) k minden x; y 2 V ? s pontparra, ahol k 2 egesz. Ekkor az s-sel szomszedos
elek parba allthatok ugy, hogy a parok leemelesevel kapott G0 = (V; E 0 ) graf k elosszefugg}o.
Biz. A 2.1 Tetel ismetelt alkalmazasaval az eredmeny rogton kovetkezik. Kozismert, hogy minden 2-elosszefugg}o graf el}oallthato egy pontbol kiindulva "fulek" hozzaadasaval, ahol a ful egy olyan ut, amelynek ket vege mar meglev}o pont, mg bels}o pontjai (ha vannak egyaltalan) uj pontok. A fulon nincsenek pont-ismetl}odesek, eltekintve attol, hogy ket vegpontja esetleg egybeeshet (amikoris a ful egy kor). Ebb}ol a jellemzesb}ol rogton adodik, hogy minden 2-elosszefugg}o graf el}ollthato egy pontbol kiindulva ket m}uvelet tetsz}oleges sorrendben torten}o egymasutani alkalmazasaval, ahol az egyik m}uvelet ket meglev}o pont osszekotese uj ellel, a masik pedig egy meglev}o el felosztasa uj ponttal. Ezen utobbi el}oalltas nyltszni altalanostasa a kovetkez}o.
2.3 TE TEL Egy G = (V; E) iranytatlan graf akkor es csak akkor 2k-elosszefugg}o, ha egy pontbol kiindulva el}oallthato az alabbi ket m}uvelet egymas utani ismetelt alkalmazasaval.
(A) Ket letez}o pontot kossunk ossze egy ellel, (B) Valasszunk ki tetsz}olegesen k meglev}o elt, mindegyiket osszuk fel egy ponttal, es egyestsuk a k osztaspontot egyetlen uj pontta.
Gyakorlat Igazoljuk, hogy a fenti m}uveletek valoban 2k-elosszefugg}o grafot eredmenyeznek. Biz. A tetel nem-trivialis reszenek bizonytasahoz szuksegunk van az alabbi lemmara. 2.4 LEMMA Minden legalabb ket pontu, el-elhagyasra nezve minimalis K-elosszefugg}o grafnak van K foku pontja.
Biz. Egy el elhagyasa pontosan akkor rontja el a graf K-elosszefugg}oseget, ha letezik olyan K-foku halmaz, amely az el egyik vegpontjat tartalmazza, a masikat nem. Legyen X olyan halmaz, amelyre d(X) = K es X elemszama minimalis. Keszen vagyunk, ha X egyelem}u. Tegyuk fel, nem ez a helyzet. Termeszetesen letezik olyan e = ab el, amelynek mindket vege X-ben van, mert kulonben X minden pontja legfeljebb d(X) = K foku volna. Most letezik olyan Y ab-halmaz (azaz a-t tartalmazo, b-t nem tartalmazo halmaz), amelyre d(Y ) = K. Az X minimalitasa miatt sem Y , sem V ? Y nem lehet X-nek resze vagyis X es Y keresztez}ok. De ekkor K + K d(X) + d(Y ) d(X \ Y ) + d(X [ Y ) K + K, amib}ol d(X \ Y ) = K kovetkezik, ellentetben X minimalitasaval.
A tetel bizonytasahoz jE j szerinti indukciot alkalmazunk. A tetel semmitmondo, ha jV j = 1, gy legyen jV j 2. A felteves szerint G 2k-elosszefugg}o. Amennyiben letezik olyan e el, amelyre G0 := G ? e is
2k-elosszefugg}o, akkor indukcio alapjan G0-nek mar letezik kvant el}oalltasa, es ezt kiegesztve az e el hozzaadasaval, a G keresett el}oalltasat kapjuk. Tegyuk most fel, hogy G el-elhagyasra nezve minimalis 2k-elosszefugg}o graf. A lemma szerint letezik egy s pontja, amelynek a foka 2k. Alkalmazzuk a 2.1A tetelt. A keletkez}o G0 graf 2k-elosszefugg}o, gy indukcio alapjan G0-nek mar letezik kvant el}oalltasa. Ebb}ol G el}oalltasat ugy kapjuk meg, hogy a G0-ben szerepl}o k leemelt elre alkalmazzuk a (B) operaciot. 6
Feladat Igazoljuk, hogy egy graf akkor es csak akkor 3-elosszefugg}o, ha egy pontbol el}oall a fenti (A) es az alabbi (B') es (C) m}uveletek egymas utani alkalmazasaval.
(B') Osszunk fel egy meglev}o elt egy uj ponttal, es az osztopontot kossuk ossze egy tetsz}oleges meglev}o ponttal. (C) Osszunk fel ket kulonboz}o elt egy-egy uj ponttal es az osztopontokat kossuk ossze egy ellel.
Feladat Igazoljuk, hogy a 2.4 Lemmaban valojaban ket pont is letezik a kvant tulajdonsaggal. Gyakorlat Legyen K = 2k + 1 es tegyuk fel, hogy G = (V; E) graf K-elosszefugg}o. Igazoljuk, hogy a K-as vagasok keresztezes-mentes rendszert alkotnak.
Feladat Igazoljuk, hogy paratlan K eseten, ha G elelhagyasra nezve minimalis K-elosszefugg}o graf (amelynek legalabb ket pontja van), akkor van olyan e = uv ele, amely legfeljebb csak az u vagy a v csucs altal (esetleg) meghatarozott minimalis vagasokban van benn. Feladat Igazoljuk a Lovasz tetelnek egy olyan valtozatat, amelyben az s csucson kvul adott meg egy z csucs, (2.0) csupan minden x; y 2 V ? z pontparra van felteve, es a leemeles utan a (x; y; Gef ) k egyenl}otlenseget minden x; y 2 V ? z pontparra koveteljuk meg. Feladat Igazoljuk, hogy minden 2k + 1 elosszefugg}o graf egy pontbol kiindulva el}oallthato az alabbi m}uveletek egymas utani ismetelt alkalmazasaval.
(A) Ket letez}o pontot kossunk ossze egy ellel, (B) Valasszunk ki tetsz}olegesen k meglev}o elt, mindegyiket osszuk fel egy ponttal, egyestsuk a k osztaspontot egyetlen uj s pontta, es huzzunk be meg egy uj elt s-b}ol egy meglev}o csucshoz. (C) Valasszunk ki tetsz}olegesen k meglev}o elt, mindegyiket osszuk fel egy ponttal, egyestsuk a k osztaspontot egyetlen uj s pontta. A keletkezett grafban valasszunk ki tetsz}olegesen k meglev}o elt, mindegyiket osszuk fel egy ponttal, egyestsuk a k osztas-pontot egyetlen uj z pontta. Vegul kossuk ossze az s es z csucsokat egy uj ellel. Tegyuk most fel, hogy egy G = (V; E) iranytatlan graf nem k-szor elosszefugg}o, de uj elek hozzaadasaval azza akarjuk tenni. Tobb kerdes is megfogalmazhato. Peldaul, mennyi a szukseges uj elek minimalis szama, illetve ami ezzel ekvivalens, dontsuk el, hogy adott szamu uj el elegend}o-e. Vagy, adott fokszam-el}oras eseten mikor letezik olyan noveles, amelyre az uj elek grafjaban minden pont foka az el}ort. Ezen utobbi kerdes megvalaszolasaval kezdjuk.
2.5 TE TEL Adott G = (V; E) graf es m : V ! Z+ fokszam-el}oras. Akkor es csak akkor letezik olyan H = (V; F) graf, amelyre dH (v) = m(v) teljesul minden v 2 V pontra es G + H k-elosszefugg}o, ha m(V ) paros es
m(X) k ? dG(X) P teljesul minden ; 6= X V reszhalmazra, ahol m(X) := (m(v) : v 2 X).
(2:3)
Biz. Ha letezik a kvant H, akkor k dG+H (X) = dG(X) + dH (X) dG(X) + m(X), amib}ol (2.3)
kovetkezik. m(V ) parossaga trivialisan szukseges. Az elegend}oseg bizonytasahoz adjunk a grafhoz egy uj s pontot es minden v 2 V pontra m(v) parhuzamos elt s es v kozott. A (2.3) feltetel szerint teljesul a 2.1A tetel feltetele. Igy az s-sel szomszedos uj elek leemelhet}ok ugy, hogy k-elosszefugg}o grafot kapjunk. A leemelt elek H grafja kielegti a tetel felteteleit. Nezzuk most meg, hogy hany el hozzavetelevel tehet}o egy graf k-eloosszefugg}ove. Nemures diszjunkt halmazoknak egy rendszeret resz-partconak nevezzuk. 7
2.6 TE TEL (Watanabe-Nakamura) Egy G = (V; E) iranytatlan graf akkor es csak akkor tehet}o legfeljebb
uj el hozzaadasaval k-elosszefugg}ove, ha a pontok minden fX1 ; : : :; Xtg resz-partciojara X (2:4) 2 (k ? d(Xi )): i
P
Masszoval, azon elek minimalis szam, melyek hozzaadasaval G k-elosszefugg}ove tehet}o egyenl}o maxd i (k ? d(Xi )=2e , ahol a maximum a V osszes resz-partciojara megy.
Biz. A tetel els}o alakjaval foglalkozunk. A szuksegesseg bizonytasa egyszer}u gyakorlo feladat. Az elegend}oseghez legyen m : V ! Z+ olyan fuggveny, amelyre (2.3) fennall es m(V ) minimalis. LEMMA m(V ) 2 . Biz. Nevezzunk egy X V halmazt pontosnak, ha d(X) = m(X). Az m minimalitasa miatt minden v
pont, amelyre m(v) > 0, benne van pontos halmazban. Minden ilyen pontra tekintsunk egy v-t tartalmazo Pv minimalis pontos halmazt. A lltjuk, hogy ezen halmazok altal alkotott F halmazrendszer laminaris. Valoban, ha Pu; Pv metsz}oek, akkor m(Pu)+m(Pv ) = k ? d(Pu)+k ? d(Pv ) k ? d(Pu ? Pv )+k ? d(Pv ? Pu) m(Pu ? Pv )+m(Pv ? Pu) = m(Pu ) + m(Pv ) ? 2m(Pu \ Pv ) m(Pu ) + m(Pv ), amib}ol az adodik, hogy m(Pu \ Pv ) = 0 es hogy a Pu ? Pv ; Pv ? Pu halmazok pontosak, ellentetben a Pu es Pv minimalis valasztasaval. Legyenek az F lamininaris rendszer maximalis tagjai X1 ; : : :; Xt . Ezek tehat pontos halmazok s lefedik Pi em(X az o sszes olyan v pontot, amelyekre m(v) pozit v. A (2.4) felt e telb} o l kapjuk, hogy m(V ) = i) = Pi(k ? d(Xi)) 2 , amivel a lemmat belattuk. Amennyiben m(V ) paratlan, tetsz}oleges v pont m-erteket noveljuk meg 1-gyel. Alkalmazzuk az el}oz}o tetelt. A kapott H grafnak a Lemma miatt legfeljebb ele van.
Gyakorlat Mutassuk meg, hogy a tetel k = 1-re nem ervenyes. Feladat A tort elosszefugg}oseg novelesi problemaban a G = (V; E) graf elosszefugg}oseget ugy akarjuk novelni, hogy tort eleket is hasznalhatunk, (azaz minden uj elt egy hozzarendelt pozitv kapacitassal egyutt adunk meg, es a keletkez}o kapacitasos grafot akkor tekintjuk k-elosszefugg}onek, ha minden vagasban az eredeti elek szama plusz az uj elek kapacitasainak osszege legalabb k.) A cel a felhasznalt kapacitasok osszegenek minimalizalasa. Mutassuk meg, hogy k 1 eseten az optimalis megoldas valaszthato felegesznek, tovabba hogy az egeszertek}u novelesi feladatban k 2 eseten az optimum erteke legfeljebb fellel nagyobb, mint a tort novelesi feladat optimumae. k = 1-re viszont az elteres a (jV j ? 1)=2 erteket is elerheti. Vegezetul bemutatunk a Lovasz tetelnek meg egy szep alkalmazasat. 1960-ban C.St.J.A. Nash-Williams altalanostotta H.E. Robbins [1939] kovetkez}o konny}u eredmenyet: G iranytatlan graf eleit akkor es csak akkor lehet ugy megiranytani, hogy er}osen osszefugg}o iranytott grafot kapjunk, ha G 2-elosszefugg}o. Az altalanostas megfogalmazasa erdekeben nevezzunk egy iranytott [iranytatlan] grafot k-elosszefugg}onek, ha minden pontbol minden mas pontba vezet k elidegen iranytott [iranytatlan] ut. (Ezek szerint digraf 1-elosszefugg}osege ugyanaz, mint az er}osen osszefugg}oseg.)
GYENGE IRA NYITA SI TE TEL [Nash-Williams, 1960] A G iranytatlan graf eleit akkor es csak akkor
lehet ugy iranytani, hogy az eredmenyul kapott iranytott graf k-elosszefugg}o legyen, ha G 2k-elosszefugg}o.
Biz. A feltetel nyilvan szukseges. Az elegend}oseg igazolasahoz jV j + jEj szerinti indukciot hasznalunk. A jV j = 1; jE j = 0 alapeset trivialis. Alkalmazzuk a 2.3 tetelt. Amennyiben G egy G0 2k-elosszefugg}o grafbol all el}o egy uj e el hozzaadasaval, ugy vegyuk a G0-nek indukcio alapjan letez}o k-elosszefugg}o iranytasat, es iranytsuk e-t tetsz}olegesen: G gy keletkez}o iranytasa k-elosszefugg}o lesz. Amennyiben G egy G0 grafbol a (B) operacio segtsegevel all el}o, akkor a G0 -nek egy k-elosszefugg}o iranytasa termeszetes modon kiterjeszthet}o a G iranytasava, amely nyilvan k-elosszefugg}o lesz. 8
3. IRA NYITATLAN LEEMELE SEK: II Legyen G = (V + s; E) iranytatlan osszefugg}o graf, amelyben (u; v) = (u; v; G) jeloli az u; v pontpart elvalaszto minimalis vagas elemszamat, ami Menger tetele alapjan az u-t es v-t osszekot}o elidegen utak maximalis szama. E szamot az u es v lokalis elosszefugg}osegenek hvjak. Egy elpart leemelhet}onek mondunk, ha a ket el kozos vege az s pont es leemelesuk minden u; v 2 V pontpar lokalis elosszefugg}oseget meg}orzi. Az alabbiakban megvizsgaljuk, hogy mikor van leemelhet}o elpar. Feltesszuk, hogy V -nek legalabb ket pontja van, es hogy az s szomszedjai kozott a lokalis elosszefugg}oseg legalabb 2, ami azzal ekvivalens, hogy: nincs s-b}ol indulo elvago el.
()
3.1A TE TEL (Mader) Legyen G = (V + s; E) osszefugg}o iranytatlan graf, amelyben d(s) 6= 3 es () teljesul. Ekkor letezik leemelhet}o elpar.
Valojaban a tetelnek a kovetkez}o valtozatat fogjuk bizonytani.
3.1B TE TEL (Mader) Legyen G = (V + s; E) osszefugg}o iranytatlan graf, amelyben d(s) paros es () teljesul. Ekkor az s-b}ol kiindulo elek d(s)=2 parba allthatok ugy, hogy e parokat egymas utan leemelve a lokalis elosszefugg}osegek nem csokennek.
Gyakorlat Igazoljuk, hogy ha G-ben () fennall, akkor egy leemelhet}o par leemelese utan is fennall. El}oszor is belatjuk, hogy a ket alak ekvivalens. Tegyuk fel el}oszor, hogy az A tetel igaz. Akkor az el}oz}o gyakorlat miatt, egymas utan talalhatunk leemelhet}o parokat, oszesen d(s)=2-t, es gy a B tetel kovetkezik. Tegyuk most fel, hogy a B tetel igaz, es igazolni akarjuk az A tetelt. Amennyiben d(s) paros, nincs mit bizonytani. Ha d(s) paratlan, akkor a felteves szerint legalabb 5. Adjunk a grafhoz uj egy x pontot es kossuk s-hez 3 parhuzamos ellel. A () fennall a keletkez}o G0 grafra es gy a B tetel alkalmazhato G0-re. A tetel altal biztostott (d(s) + 3)=2 leemelhet}o par kozul legfeljebb harom hasznal uj elt, gy d(s) 5 miatt az egyik par eredeti elekb}ol all, es ez a par termeszetesen az eredeti G-ben is leemelhet}o.
A 3.1B tetel bizonytasa. Feltesszuk, hogy a tetel ervenyes minden G-nel kisebb grafra. Eleg azt igazolni, hogy van leemelhet}o par ugyanis ezen alltas ismetelt alkalmazasaval megkapjuk a 3.1B tetelt. Szuksegunk lesz a kovetkez}o halmaz-fuggvenyre. Legyen R(V ) := R(;) = 0 es ; X V -re R(X) := max((u; v) : u 2 X; v 2 V ? X): (3:1) Rogton latszik, hogy d(X) R(X) minden X V reszhalmazra fennall. 1. LEMMA Egy elpar akkor es csak akkor leemelhet}o, ha a leemelesevel keletkez}o G0 grafra d0(X) R(X) fennall minden X V -re. Biz. Ha az elpar leemelhet}o, akkor d0(X) R(X) kovetkezik az R de nciojabol. Fordtva, ha az elpar leemelese csokkenti valamely u; v par lokalis elosszefugg}oseget, akkor letezik olyan X halmaz, amelyre jX \ fu; vgj = 1 es d0(X) < (u; v; G). Esetleges komplementalassal feltehet}o, hogy X V . Most d0 (X) < (u; v; G) R(X), es a lemma kovetkezik. Nevezzunk egy X V halmazt pontosnak, ha d(X) = R(X), majdnem-pontosnak, ha d(X) = R(X) + 1, es veszelyesnek, ha pontos vagy majdnem-pontos, azaz R(X) d(X) R(X) + 1. Jegyezzuk meg, hogy d(V ) = d(s) 2 miatt a V halmaz sohasem veszelyes. Mivel egy leemeles egy halmaz fokat 2-vel tudja csokkenteni, egy fe = st; f = sug elpar akkor es csak akkor emelhet}o le, ha nincsen u es t mindegyiket tartalmazo veszelyes halmaz.
9
Egy X halmaz tobbletet jelolje s(X) := d(X) ? R(X). Lattuk, hogy a tobblet nemnegatv. X akkor pontos, ha s(X) = 0 es akkor veszelyes, ha s(X) 1.
2. LEMMA Az R fuggveny ferden szupermodularis, azaz X; Y V eseten a kovetkez}o egyenl}otlensegek kozul legalabb az egyik fennall.
R(X) + R(Y ) R(X \ Y ) + R(X [ Y ); R(X) + R(Y ) R(X ? Y ) + R(Y ? X):
(3:2 ) (3:2 )
Biz. Figyeljuk meg, hogy ha Y -t V ?Y -nal helyettestjuk, akkor (3.2 ) es (3.2 ) egymasba transzformalodik. Legyen (z; z 0 ) egy olyan pontpar, amely maximalizalja a (z; z 0) erteket az osszes olyan parok kozul, melyeket legalabb az X es Y egyike szetvalaszt. Szimmetria miatt feltehetjuk, hogy z 2 X es z 0 2 V ? X. Az Y -t esetleg V ? Y -nal felcserelve feltehetjuk, hogy z 62 Y . Ha z 0 2 Y , akkor (z; z 0) = R(X) = R(Y ) = R(X ? Y ) = R(Y ? X) es gy (3.2 ) fennall (valojaban egyenl}oseggel). Ha z 0 62 Y , akkor (z; z 0 ) = R(X) = R(X [ Y ) = R(X ? Y ). Vilagos, hogy R(Y ) R(X \ Y ) vagy R(Y ) R(Y ? X). Ennek megfelel}oen (3.2 ) vagy (3.2 ) fennall. A dG-re vonatkozo ismert azonossagok alapjan, a 2. lemmabol kapjuk:
3. LEMMA Minden X; Y V -re a kovetkez}o egyenl}otlensegek kozul legalabb az egyik teljesul. s(X) + s(Y ) s(X \ Y ) + s(X [ Y ) + 2dG (X; Y ): (3:3 ) s(X) + s(Y ) s(X ? Y ) + s(Y ? X) + 2dG(X; Y ): (3:3 ) 4. LEMMA Legyen T pontos halmaz (; T V ) es legyen e = su; f = sv ket el. Jelolje a T osszehuzasaval keletkez}o grafot G0 es legyen e0 illetve f 0 az e es f-nek megfelel}o ket el G0-ben. Ha fe0 ; f 0 g leemelhet}o G0-ben, akkor fe; f g is leemelhet}o G-ben. Biz. Legyen Z olyan halmaz, amelyre Z V ? T vagy T Z V es jelolje Z 0 a G0 azon ponthalmazat, amely Z-b}ol keletkezett a T osszehuzasakor. Ekkor R0(Z 0 ) R(Z) es dG (Z) = dG (Z): Ezert, ha Z veszelyes G-ben, akkor Z 0 veszelyes G0-ben. Ha fe; f g nem volna leemelhet}o G-ben, akkor letezne G-nek u es v pontokat tartalmazo X veszelyes halmaza. Most Z := X [ T nem lehet G-ben veszelyes, mert akkor Z 0 veszelyes volna G0 -ben, es ekkor fe0; f 0 g nem volna leemelhet}o G0-ben. Azt kaptuk tehat, hogy s(X [ T) 2. Alkalmazzuk az el}oz}o lemmat X-re es T-re. Most a (3.3 ) alternatva nem allhat fenn, mert akkor 0+1 s(T)+s(X) s(X \ T)+s(X [ T) 0+2. T) 0+0+2d(X; T): Ezert (3:3 )-nak kell fennallnia, azaz 0+1 s(T)+s(X) s(X ? T)+s(T ? X)+2d(X; Innen 2d(X; T) = 0 es s(D) 1 kovetkezik, ahol D := X ? T. Az egyenl}osegb}ol kovetkezik, hogy u; v 2 D, mg az egyenl}otlenseg azt jelenti, hogy D veszelyes G-ben. De akkor D0 veszelyes G0-ben, mutatva, hogy fe0 ; f 0 g nem emelhet}o le G0 -ben, ellentmondasban a lemma feltevesevel. 0
Tegyuk fel indirekt, hogy a tetel nem igaz G-re. Mivel feltettuk, hogy a tetel igaz minden G-nel kisebb grafra, a 4. Lemma alapjan minden pontos halmaz egyelem}u.
5. LEMMA Ha minden pontos halmaz egyelem}u, akkor (x; y) = min(d(x); d(y)) minden x; y 2 V -re. Biz. A lemma rogton adodik, ha meg gyeljuk, hogy egy X V halmaz pontos, amennyiben elvalasztja x-t es y-t, es (x; y) = d(X). Jeloljuk S-sel az s szomszedainak a halmazat, es legyen t 2 S egy olyan pont, amelynek foka minimalis. 10
6. LEMMA R(X ? t) R(X) fennall minden olyan X V halmazra, amelyre t 2 X es jS \ X j 2. Biz. Legyen u 2 S \ (X ? t). A t valasztasa miatt d(u) d(t). R(X) de ncioja miatt letezik v 2 X es z 2 V ? X, amelyekre R(X) = (v; z). Ha v = 6 t, akkor R(X ? t) (v; z) = R(X). Ha v = t, akkor az 5. Lemma miatt R(X) = (t; z) = min(d(t); d(z)) min(d(u); d(z)) = (u; z) R(X ? t): 7. LEMMA Ha X veszelyes, akkor d(s; X) d(s; V ? X). Biz. Legyen := d(s; X) es := d(s; V ? X). Ekkor R(V ? X) = R(X) d(X) ? 1 = d(V ? X) ? + ? 1 R(V ? X) ? + ? 1, amib}ol + 1. Keszen vagyunk, ha : = + 1 viszont nem fordulhat el}o, mert akkor d(s) = 2 + 1 volna, ellentmondasban a feltevessel, hogy d(s) paros. Miutan G ellenpelda, semmilyen fst; sug elpar nem emelhet}o le, es ezert s minden szomszedja benne van t-t tartalmazo veszelyes halmazban. Legyen L a t pontot tartalmazo veszelyes halmazoknak olyan csaladja, amely fedi S-t es a lehet}o legkevesebb tagja van.
8. LEMMA jLj 3: Biz. Az el}oz}o lemmabol tudjuk, hogy jLj 2: Tegyuk fel indirekt, hogy jLj = 2 es legyen L = fX; Y g. Ekkor tehat S X [ Y , es ismet az el}oz}o lemmat hasznalva kapjuk, hogy d(s; X) d(s; V ? X) < d(s; Y ) d(s; V ? Y ) < d(s; X); ellentmondas. (Az utolso egyenl}otlenseg azert igaz, mert (S ? X) [ ftg Y ). Legyen X1 ; X2 ; X3 az L harom tagja es legyen F := fX1 ; X2; X3 g. Az L minimalis valasztasa folytan mindharom Xi tartalmaz egy olyan si 2 S elemet, amely a masik kett}oben nincs benne. 9. LEMMA F barmely ket X; Y tagjara (3:3 ) teljesul. Biz. Tegyuk fel indirekt, hogy (3:3 ) nem all. Ekkor a 3. lemma szerint (3:3 ) fennall. Az L minimalitasa miatt s(X [ Y ) 2, ezert 1 + 1 s(X) + s(Y ) s(X \ Y ) + s(X [ Y ) 0 + 2; amib}ol s(X \ Y ) = 0 kovetkezik, vagyis az, hogy X \ Y pontos. Mivel minden pontos halmaz egyelem}u, gy X \ Y = ftg. Ekkor X ? Y = X ? ftg es Y ? X = Y ? ftg, es gy a 6. lemma alapjan R(X) R(X ? Y ) es R(Y ) R(Y ? X). Y ), Ezert ervenyes, R(X)+R(Y ) R(X ? Y )+R(Y ? X); amib}ol s(X)+s(Y ) s(X ? Y )+s(Y ? X)+2d(X; vagyis (3:3 ) megiscsak fennall. Y ) = 1. 10. LEMMA F barmely ket X; Y tagjara jX ? Y j = jY ? X j = 1 es d(X; Y ) 0 + 0 + 2: Innen Biz. Az el}oz}o lemma szerint 1 + 1 s(X) + s(Y ) s(X ? Y ) + s(Y ? X) + 2d(X; kovetkezik, hogy d(X; Y ) = 1 es hogy X ? Y es Y ? X is pontos, es ezert egypontu. Befejezesul, legyen M := X1 \X2 \X3 . A 10. lemmaboles L minimalitasabolkovetkezik, hogy Xi = M+si i ; Xj ) = 1(1 i < j 3). Ez viszont azt jelenti, hogy az st el az egyetlen M-b}ol (i = 1; 2; 3), es hogy d(X kilep}o el, vagyis st elvago el, ellentmondasban a tetel feltevesevel. LOKA LIS E LO SSZEFU GGO} SE G NO VELE S Az el}oz}o fejezetben lattuk, hogy Lovasz leemelesi tetele mikent hasznalhato az elosszefugg}oseg novelesere. Nem meglep}o hogy Mader lokalis elosszefugg}oseget meg}orz}o leemelesi tetelet is fel lehet hasznalni a lokalis elosszefugg}oseg optimalis novelesere. Ennek reszleteit dolgozzuk ki az alabbiakban. Legyen G = (V; E) iranytatlan graf. r(x; y) (x; y 2 V ) nemnegatv egeszertek}u fuggveny, amely szimmetrikus, azaz r(x; y) = r(y; x). Adott tovabba egy m : V ! Z+ fuggveny, amelyre m(V ) paros. Feltesszuk, hogy G-nek nincsen olyan C komponense, amelyre m(C) = 1. () 11
3.2 TE TEL Akkor es csak akkor letezik olyan H = (V; F) graf, amelyre dH (v) = m(v) minden v 2 V -re fennall es
(x; y; G+ ) r(x; y) teljesul minden x; y pontparra, ahol G+ = G + H = (V; E [ F), ha m(X) R(X) ? dG (X)
(3:4) (3:5) (3:6)
ervenyes minden X V reszhalmazra, ahol R(X) := max(r(x; y) : x 2 X; y 2 V ? X).
Biz. Amennyiben letezik (3.5)-t kielegt}o graf, akkor dG(X) + dH (X) = dG+ (X) R(X), amib}ol m(X) dH (X) R(X) ? dG(X), azaz (3.6) fennall. Az elegend}oseg bizonytasahoz adjunk egy uj s pontot a grafhoz es minden regi v pontra m(v) parhuzamos elt s es v kozott. A kelektkez}o G0 grafban (3.6) miatt (x; y; G0) r(x; y) minden x; y 2 V pontparra fennall. Alkalmazhatjuk Mader tetelet (3.1B tetel). A leemelt elek H grafja kielegti a kvanalmakat. Azt mondjuk, hogy a G graf valamely C komponense marginalis (r-re nezve), ha R(C) 1. 3.3 TE TEL Tegyuk fel G-nek nincs marginalis komponense. Akkor es csak akkor letezik olyan legfeljebb
el}u H = (V; F) graf, amelyre (x; y; G+ ) r(x; y) teljesul minden x; y pontparra, ahol G+ = G + H = (V; E [ F), ha X(R(X ) ? d (X )) 2 (3:7) i G i teljesul V minden fX1 ; : : :; Xt g resz-partciojara. Biz. Jeloljuk az X halmaz hianyat q(X) := R(X) ? dG(X)-szel. Korabban lattuk, hogy q kielegti az alabbiak egyiket: q(X) + q(Y ) q(X \ Y ) + q(X [ Y ); (3:8 ) q(X) + q(Y ) q(X ? Y ) + q(Y ? X): (3:8 ) Legyen most m : V ! Z+ olyan, hogy teljesul ra (3.6), es tegyuk fel, hogy m minimalis abban az ertelemben, hogy barmely ponton eggyel csokkentve az erteket, (3.6) mar megserul. Ekkor minden v pont, amelyre m(v) > 0, benne van pontos halmazban, ahol egy X halmaz akkor pontos, ha m(X) = q(X). Legyen F pontos halmazoknak egy olyan rendszere, amely fedi az osszes v pontot, amelyre m(v) > 0, tjuk, hogy F resz-partcio. Tegyuk indirekt jFj minimalis es ezen belul P(jZ j : Z 2 F ) minimalis. All fel, hogy X; Y ket metsz}o tagja F -nek. Amennyiben ( ) teljesul, akkor X [ Y is pontos ellentetben jFj minimalitasaval. Amennyiben ( ) teljesul, ugy m(X) + m(Y ) = q(X) + q(Y ) q(X ? Y ) + q(Y ? X) m(X ? Y )+m(Y ? X) = m(X)+m(Y ) ? 2m(X \ Y ), amib}ol X ? Y , Y ? X pontosak es m(X \ Y ) = 0. Vagyis F -ben helyettesthetjuk X; Y -t az X ? Y; Y ? XPhalmazokkal,Pellentetben P(jZ j : Z 2 F ) minimalitasaval. Legyen F = fX1; : : :; Xt g. Most m(V ) = m(Xi ) = (R(Xi ) ? dG (Xi )) 2 , azaz m(V ) 2 . Az m-t valamely v ponton (ahol m(v) 1) megnovelve feltehetjuk, hogy m(V ) = 2 . Mivel G-nek nincs marginalis komponense, teljesul (), ezert a 3.2 tetel alapjan keszen vagyunk. 5. EGYENSU LYI IRA NYITA SOK A 2. fejezetben mar megfogalmaztuk a kovetkez}o tetelt.
GYENGE IRA NYITA SI TE TEL [Nash-Williams, 1960] A G iranytatlan graf eleit akkor es csak akkor
lehet ugy iranytani, hogy az eredmenyul kapott iranytott graf k-elosszefugg}o, ha G 2k-elosszefugg}o. 12
A feltetel elegend}osegere korabban ket bizonytast is lattunk. Az egyik szubmodularis aramokat hasznalt, a masik Lovasz leemelesi tetelere eptett. Nash-Williams valojaban egy sokkal er}osebb tetelt bizonytott. Ennek megfogalmazasahoz egy G iranytott vagy iranytatlan grafban (x; y; G) jelolje a lokalis el-osszefugg}oseget x-b}ol y-ba, ami tehat az x-b}ol y-ba vezet}o elidegen utak maximalis szama.
ERO} S IRA NYITA SI TE TEL 4.0 [Nash-Williams, 1960] Minden G = (V; E) iranytatlan grafnak van olyan D := G~ iranytasa, amelyre
(x; y; D) = b(x; y; G)=2c ervenyes minden x; y 2 V pontparra.
(4:0)
Raadasul az iranytas olyannak is valaszthato, amelyben minden pont be- es kifoka legfeljebb eggyel ter el. Nash-Williams egy olyan iranytast, amely kielegtit (4.0)-t egyensulyinak nevez. Ha G 2k-elosszefugg}o, akkor (x; y; G) 2k minden x; y pontparra, es ezert az er}os iranytasi tetelb}ol kovetkezik a gyenge nemtrivialis iranya. Adott s; t 2 U elemekre es X U reszhalmazra azt mondjuk, hogy X egy st-halmaz, ha s 2 X; t 62 X. X elvalasztja (szeparalja) s-t t-t}ol (vagy s-t es t-t), ha jX \ fs; tgj = 1. A 4.0 tetel bizonytasa Nash-Williams kiindulasi meg gyelese az, hogy a tetel trivialis Euler-grafokra, hiszen tetsz}oleges di-Euler iranytas jo lesz. (Di-Euler grafon olyan iranytott grafot ertunk, amelyben minden pontra a befok egyenl}o a kifokkal.) Ha a graf nem Euler-fele, akkor el}oszor hozzaadunk a paratlan foku pontoknak egy "alkalmas" M parostasat (aminek elei nem szuksegkeppen a grafbol valok), majd a keletkez}o Euler-grafnak veszunk egy di-Euler iranytasat, vegul kihagyjuk az M eleit. Termeszetesen az gy kapott iranytasrol csak akkor varhatjuk el, hogy kielegti (4.0)-t, ha az M parostas kielegt bizonyos kvanalmakat. Egy f egesz szamra vagy egeszertek}u fuggvenyre legyen f^ := 2bf=2:c De nialjuk az R = RG halmazfuggvenyt a kovetkez}okeppen. R(;) := R(V ) := 0 es ; X V -re legyen R(X) := max((x; y; G) : X elvalasztja x; y-t). Ugyanezt a fuggvenyt korabban hasznaltuk mar Mader leemelesi tetelenek bizonytasaban. Szuksegunk lesz a bG (X) := dG (X) ? R^ G(X) () halmazfuggvenyre, amely egyfajta ertelemben az X halmaz tobbletet meri. A Menger tetel iranytott el-valtozata alapjan (4.0) azzal ekvivalens, hogy %(X) R^ G(X)=2 minden X V -re, (4:1) ahol % jeloli a D iranytas befok fuggvenyet. Legyen M a G paratlan foku pontjainak egy parostasa. Az M-t megengedett paratlan-pont parostasnak nevezzuk, ha dM (X) bG (X) fennall minden X V halmazra,
(4:2)
ahol dM (X) jeloli azon M-beli elemek szamat, melyeknek pontosan egy vegpontja van X-ben. Vilagos, hogy bG 0 es dM (X) bG (X) (mod 2) minden X V -re. Ebb}ol (4.2) mindig igaz, ha jX j vagy jV ? X j legfeljebb egyelem}u. Ilyen X halmazt trivialisnak nevezunk. Marmost Nash-Williams parostasi tetele a kovetkez}o. PA ROSITA SI TE TEL 4.1 Minden iranytatlan grafnak van M megengedett paratlan-pont parostasa. El}oszor is lassuk be, hogy a 4.1 tetel implikalja az er}os iranytasi tetelt. Valoban, tekintsuk a G + M Euler-graf egy di-Euler-fele iranytasat, es jelolje %0 illetve % a D0 es D := D0 ? M digrafok befok fuggvenyet. (Itt D a G-nek egy iranytasa). Kapjuk: %(X) %0 (X) ? dM (X) = (dG (X) + dM (X))=2 ? dM (X) = (dG (X) ? dM (X))=2 R^ G(X)=2; amib}ol (4.1) es a 4.0 tetel kovetkezik. A 4.1 tetel bizonytasa. Feltehetjuk, hogy G osszefugg}o. S}ot azt is feltehetjuk, hogy G 2-elosszefugg}o, mert ha nem ez a helyzet, akkor minden elvago elt harom parhuzamos ellel helyettesthetunk. Konnyen ellen}orizhet}o, hogy a kapott graf megengedett parostasa egyuttal G-nek is megengedett parostasa. jE j + jV j 13
szerinti indukciot hasznalunk. Feltehet}o, hogy nincsen masodfoku pont, mert ha mondjuk u ilyen, akkor az u-ba men}o ux es uy elt egy uj xy elre csereljuk, a keletkez}o G0 grafnak indukcio alapjan mar van megengedett parostasa es ez nyilvan G-ben is megengedett lesz. A kovetkez}o lemma konnyen adodik az R^ de nciojabol.
LEMMA 4.2 Barmely ket X; Y V halmazra a kovetkez}o negy alltas kozul legalabb az egyik fennall. ^ R(X ^ [ Y ) es R(Y ^ ) R(X ^ \ Y ); R(X)
(4:3a)
^ ) R(X ^ [ Y ) es R(X) ^ R(X ^ \ Y ); R(Y ^ R(X ^ ? Y ) es R(Y ^ ) R(Y ^ ? X); R(X) ^ ) R(X ^ ? Y ) es R(X) ^ R(Y ^ ? X): R(Y
(4:3b) (4:3c) (4:3d)
Ebb}ol kapjuk:
LEMMA 4.3 Tetsz}oleges X; Y V halmazokra a kovetkez}o egyenl}otlensegek kozul legalabb az egyik
teljesul.
Tovabba, ha akkor (4.4 ) fennall.
^ + R(Y ^ ) R(X ^ \ Y ) + R(X ^ [ Y ); R(X) ^ + R(Y ^ ) R(X ^ ? Y ) + R(Y ^ ? X): R(X)
(4:4 ) (4:4 )
R(X) min(R(X \ Y ); R(X [ Y ));
(4:5)
El}oszor tegyuk fel, hogy van olyan nem-trivialis X V halmaz, amelyre bG (X) = 0: Jelolje G1 es G2 azokat a grafokat, amelyek G-b}ol az X illetve a (V ?X) halmazok egy pontra huzasaval keletkeznek. Konnyen latszik, hogy barmely Z V ? X halmazra RG1 (Z) RG(Z) es innen bG1 (Z) bG (Z). Hasonlokepp bG2 (Z) bG(Z) ervenyes minden Z X halmazra. Indukcio alapjan letezik Gi -nek egy Mi megengedett paratlan-pont parostasa (i = 1; 2). Mivel dG(X) paros, az osszehuzott pontok paros fokuak, es gy M := M1 + M2 paratlan-pont parostasa G-nek. Azt alltjuk, hogy M megengedett, vagyis hogy dM (Y ) bG(Y ) fennall minden Y V reszhalmazra. Ennek igazolasahoz feltehetjuk, hogy (4.4 ) van ervenyben, mert kulonben Y -t helyettesthetjuk a komplementerevel, es akkor (4.4 ) (4.4 )-ba transzformalodik. Felhasznalva (1.4)-t valamint R^ szimmetrikussagat, azt nyerjuk, hogy dM (Y ) = dM (X \ Y ) + dM (X [ Y ) = dM2 (X \ Y ) + dM1 (V ? (X [ Y )) bG2 (X \ Y ) + bG1 (X [ Y ) bG (X \ Y ) + bG (X [ Y ) bG (X) + bG (Y ) = bG (Y ), azaz M valoban megengedett paratlan-pont parostas G-ben Ily modon a kovetkez}o esetre jutottunk: bG (X) > 0 minden nem-trivialis X V -re.
(4:6)
Tegyuk most fel, hogy van egy olyan f = uv el G-ben, amely ket paratlan foku pontot kot ossze, es legyen G0 := G ? f. Indukcio alapjan G0-ben van egy M 0 megengedett paratlan-pont parostas. Azt alltjuk, hogy ^ (x; y; G0) = ^(x; y; G) minden x; y 2 V pontparra. Tegyuk fel ugyanis, hogy az x; y pontokra ^(x; y; G0) < ^(x; y; G). Ekkor (x; y; G0) = (x; y; G) ? 1 es (x; y; G) paros. Menger tetele szerint van olyan X xy-halmaz, amelyre dG(X) = (x; y; G) es X elvalasztja u-t es v-t. Feltehetjuk, hogy jX j jV ? X j, mert kulonben X-t kicserelhetjuk a komplementerevel. Most bG (X) = 0 es gy (4.6) miatt jX j = 1, tehat X = fug vagy X = fvg. De ez ellentmond a feltevesnek, hogy dG (u) es dG (v) paratlan. Tehat ^ (x; y; G0) = ^(x; y; G) valoban fennall minden x; y 2 V pontparra. Ekkor bG (X) = bG (X) ? 1 illetve bG (X) = bG(X) annak megfelel}oen, hogy az X V halmaz szeparalja vagy nem szeparalja u-t es v-t, es ezert M 0 + uv megengedett paratlan-pont parostas G-ben. 0
0
14
Ezek alapjan feltehetjuk, hogy minden elnek legalabb az egyik vegpontja paros foku.
(4:7)
Jelolje T a harmadfoku pontok halmazat es legyen S = V ? T. Hvjunk egy X V reszhalmazt lenyegtelennek, ha X trivialis, vagy ha van egy olyan v 2 T \ X csucs, amelyre () d(v; X ? v) 1, vagy pedig ha van egy olyan v 2 T ? X csucs, amelyre () d(v; X) 2. A tobbi halmazt nevezzuk lenyegesnek. Azt alltjuk, hogy az M paratlan-pont parostas megengedett, ha (4.2) a lenyeges halmazokra fennall. Valoban, (4.2) nyilvan igaz trivialis halmazokra. Legyen most X olyan halmaz, amelyre (4.2) nem all, es tetelezzuk fel, hogy dG(X) minimalis. A lltjuk, hogy X lenyeges. Ha ugyanis nem az, akkor vagy van egy olyan v 2 T \ X pont, amelyre () fennall, vagypedig van egy olyan v 2 T ? X pont, amelyre () all fenn. Legyen X 0 := X ? v az els}o esetben es X 0 := X + v a masodikban. Mivel X nem-trivialis, gy ; X 0 V . ^ 0 ) = R(X) ^ es ezert bG (X 0 ) + 1 bG (X): A dG (X) minimalis valasztasa Tovabba dG (X 0 ) dG(X) ? 1; R(X 0 miatt (4.2) fennall X -re, es gy dM (X) dM (X 0 ) + 1 bG(X 0 ) + 1 bG (X), ellentmondasban az indirekt feltevessel, miszerint X megserti (4.2)-t.
Legyen s az S-nek minimalis fokszamu pontja. Ha S egyetlen pontbol all, akkor s-t es minden T-beli t pontot harom parhuzamos el kot ossze, es ekkor G-nek nincs is mas ele. Ebben az esetben (4.7) miatt dG (s) paros, es konnyen lathatoan barmilyen paratlan-pont parostas megengedett. Ezert feltehetjuk, hogy jS j 2. Legyen S := min((x; y; G) : x; y 2 S). Nyilvan S dG(s).
1. ESET
S = dG (s):
(4:8)
Mader leemel}os tetele alapjan letezik olyan e = su; f = st elpar, amelyek leemelesevel keletkez}o G0 grafban (x; y; G0) = (x; y; G) minden x; y 2 V ? s pontparra fennall. LEMMA R^ G (X) = R^G(X) minden X lenyeges halmazra. 0
Biz. Mivel leemeleskor a lokalis elosszefugges sohasem n}o, RG (X) RG(X) nyilvan fennall. Feltehetjuk, hogy s 2 X, mert kulonben X-t helyettesthetjuk a komplementerevel. Mivel G0 is 2elosszefugg}o (hiszen s foka G-ben legalabb 4), a lemma igaz, ha R^ G (X) = 2. Igy R^ G(X) 4. Legyenek u 2 X; v 2 V ? X olyan pontok, amelyekre RG(X) = (u; v; G). R^ G(X) 4 miatt u; v 2 S. Ha RG(X) > S = dG (s), akkor u; v = 6 s; es gy RG (X) (u; v; G0) = (u; v; G) = RG(X), vagyis ilyenkor az lemma igaz. Feltehetjuk tehat, hogy RG(X) = S = dG(s). Azt alltjuk, hogy X \ S = 6 fsg. Ha ugyanis X \ S = fsg, akkor X ? s minden pontja harmadfoku, es (4.7) miatt ezen pontok kozott nincs el. Az X lenyegessege miatt minden X ? s-beli pontbol legalabb ket el megy s-be es legfeljebb egy el V ? X-be, amib}ol az kovetkezik, hogy dG (s) > dG(X); ellentetben az el}obbi egyenl}oseggel. Letezik tehat egy x 2 S \ X ? s elem, es ezert RG (X) (x; v; G0) = (x; v; G) S = RG(X), amib}ol a lemma kovetkezik. Indukcio alapjan G0-nek letezik egy M megengedett paratlan-pont parostasa. Mivel dG dG , a lemmabol kovetkezik, hogy bG bG , es ezert M a G-nek is megengedett paratlan-pont parostasa. 2. ESET 0
0
0
0
0
S < dG (s):
(4:9)
Legyen x; y 2 S ket olyan pont, amelyre (x; y; G) = S es legyen X olyan xy -halmaz, amelyre dG(X) = (x; y; G). (4.9) miatt X nem-trivialis. Tovabba RG (X) (x; y; G) = dG(X) RG(X) es ezert dG(X) = RG(X). Azt kapjuk (4.6)-bol, hogy RG(X) paratlan es gy bG (X) = 1. E rvenyes tovabba, hogy X lenyeges. 15
Jelolje G1 illetve G2 a G-b}ol az X illetve a (V ? X) halmazok egy pontra torten}o osszehuzasaval keletkez}o grafokat. Barmely Z V ? X halmazra RG1 (Z) RG (Z) es gy bG1 (Z) bG (Z). Hasonlokeppen bG2 (Z) bG(Z) fennall Z X-ra. Indukcio alapjan Gi-nek (i = 1; 2) van Mi megengedett paratlan-pont parostasa. Jelolje ei azt az elet Mi -nek, amely az osszehuzott pontot fedi es legyen vi az ei el masik vegpontja (i = 1; 2). Ekkor M := M1 + M2 ? e1 ? e2 + v1v2 paratlan-pont parostasa G-nek. Azt alltjuk, hogy M megengedett, azaz dM (Y ) bG (Y ) fennall minden Y V reszhalmazra. Amint mar korabban meg gyeltuk, ezt eleg lenyeges halmazokra igazolni. Amennyiben Y X, ugy dM (Y ) = dM2 (Y ) bG2 (Y ) = bG(Y ). Analog a helyzet, ha Y V ? X. Igy feltehetjuk, hogy X es Y keresztezik egymast. Az Y esetleges komplementalasa nyoman feltehetjuk, hogy dM (X; Y ) = 0. Miutan mind X, mind Y lenyeges, (4.7) felhasznalasaval kapjuk, hogy S \ X \ Y 6= ; es S \ (V ? (X [ Y )) 6= ;. Az X valasztasabol kovetkezik, hogy R(X) R(Z) minden olyan Z halmazra fennall, amely szeparalja S ket elemet. Ezert (4.5) van evenyben es gy (4.4 ) fennall X; Y -re. Felhasznalva (1.4)-t es R^ szimmetrikussagat azt kapjuk, hogy dM (Y ) = dM (X \ Y )+dM (X [ Y ) ? dM (X)+2dM (X; Y ) = dM (X \ Y ) + dM (X [ Y ) ? 1 = dM2 (X \ Y ) + dM1 (V ? (X [ Y )) ? 1 bG2 (X \ Y ) + bG1 (X [ Y ) ? 1 bG (X \ Y ) + bG (X [ Y ) ? 1 bG (X) + bG (Y ) ? 1 = bG (Y ), amint alltottuk.
5. IRA NYITOTT LEEMELE S E S ALKALMAZA SAI LEEMELE S Lovasz tetelenek iranytott grafokra vonatkozo ellenparja Madert}ol szarmazik.
5.1 TE TEL Legyen G = (V +s; E) iranytott graf, amelyben %(s) = (s). Tegyuk fel, hogy () (x; y; G) k minden x; y 2 V pontparra, ahol k 1 egesz. Ekkor minden e = st elhez letezik olyan f = us el, amelyekre (x; y; Gef ) k minden x; y 2 V pontparra. Biz. Menger tetel alapjan a () felteves azzal ekvivalens, hogy %(X) k; (X) k minden ; 6= X V reszhalmazra. (5:1) Leemeleskor minden halmaz befoka es kifoka is legfeljebb eggyel csokkenhet. Egy X V reszhalmazt nevezzunk be-pontosnak, ha %(X) = k es ki-pontosnak, ha (X) = k. Az X-t pontosnak hvjuk, ha ki-pontos vagy be-pontos. Egy fus; stg elpar akkor es csak akkor felel meg a tetel kvanalmainak, ha nincsen olyan pontos halmaz, amely tartalmazza t-t es u-t. Hasznalni fogjuk az alabbi azonossagokat. %(X) + %(Y ) = %(X \ Y ) + %(X [ Y ) + d(X; Y ):
(5:2)
Y ) + %(X \ Y ) ? (X \ Y ): %(X) + %(Y ) = %(X ? Y ) + %(Y ? X) + d(X;
(5:3)
5.2 LEMMA Legyen X es Y ket maximalis t-t tartalmazo pontos halmaz. Ekkor X [ Y is pontos. Biz. Nem lehet, hogy az egyik halmaz ki-pontos, a masik pedig be-pontos, mert ha peldaul %(X) = k es (Y ) = k, akkor az Y := V +s?Y es az X halmazra 2k = %(X)+%(Y ) = %(X [Y )+%(X \Y )+d(X; Y ) 2k+1
adodna. Tegyuk fel most, hogy X; Y ki-pontosak. (A bizonytas analog abban az esetben, ha X; Y be-pontosak). Nem lehet, hogy X [ Y = V , mert kulonben X \ Y = fsg, es ekkor felhasznalva, hogy %(s) = (s), (5.3) X; + %(Y ) = %(X ? Y ) + %(Y ? X) + d( Y ) k + k + 1. Ha viszont alapjan azt kapnank, hogy 2k = %(X) 16
X [ Y V , akkor (5.1) miatt 2k = (X)+(Y ) (X \ Y )+(X [ Y ) k +k, amib}ol a lemma kovetkezik.
Ha egyaltalan nincs t-t tartalmazo pontos halmaz, akkor e = st-vel barmely f = us leemelhet}o. Ha van ilyen pontos halmaz, akkor a lemma alapjan letezik egy M egyertelm}u maximalis t-t tartalmazo pontos halmaz. Azt kell kimutatnunk, hogy a grafban letezik olyan us el, amelyre u 2 V ? M. Tegyuk fel indirekt, hogy minden s-be lep}o el M-b}ol jon. Ha %(M) = k, akkor (V ? M) = %(M + s) %(M) ? 1 = k ? 1, ellentetben az (5.1) feltevessel. Ha (M) = k, akkor %(V ? M) = (M +s) (M) ? %(s)+ (s) ? 1 k ? 1, ismet ellentetben (5.1)-gyel.
Gyakorlat Mutassuk meg, hogy a %(s) = (s) kovetelmeny nelkul a tetel nem igaz. Feladat Igazoljuk az 5.1 tetel er}osteset, amelyben a %(s) = (s) feltetel helyett csak annyit teszunk fel, hogy (s) %(s) < 2(s). 5.3 TE TEL Legyen G = (V +s; E) iranytott graf, amelyben %(s) = (s). Tegyuk fel, hogy () (x; y; G) k minden x; y 2 V pontparra, ahol k 1 egesz. Ekkor az s-be belep}o es kilep}o elek egymassal parba allthatok ugy, hogy a parokat leemelve es a megmaradt s pontot elhagyva k-elosszefugg}o digrafot kapunk.
Biz. Alkalmazzuk egymas utan az 5.1 Tetelt %(s)-szer. SSZEFU GGO} IRA NYITOTT GRA FOK k-E LO Lovasz iranytatlan leemelesi tetelet arra lehetett hasznalni, hogy el}oalltsuk a 2k-elosszefugg}o iranytatlan grafokat (csoppnyi altalanostasat pedig a (2k + 1)-elosszefugg}o grafok el}oalltasara.) Hogyan hasznalhato Mader tetele iranytott k-elosszefugg}o digrafok el}oalltasara? Ehhez szuksegunk van a kovetkez}o szinten Madert}ol szarmazo tetelre.
5.4 TE TEL Legyen G = (V; E) olyan legalabb ket pontu k-elosszefugg}o digraf, amelyb}ol barmely elt elhagyva megsz}unik a k-elosszefugg}oseg. Ekkor G-nek van olyan v pontja, amelyre %(v) = (v) = k.
Biz. Nevezzunk egy X V halmazt be-pontosnak, ha %(X) = k es ki-pontosnak, ha (X) = k. A felteves szerint minden el belep be-pontos halmazba. Legyen L be-pontos P halmazoknak egy olyan csaladja, hogy minden el belelep az egyik tagjaba, jLj minimalis es ezen belul (jZ j2 : Z 2 L) maximalis. Ekkor alltjuk, hogy L keresztezes mentes. Ha ugyanis ket tagja, X es Y keresztez}o volna, akkor k + k = %(X) + %(Y ) = %(X \ Y ) + %(X [ Y ) + d(X; Y ) k + k + 0, amib}ol az adodik, hogy a metszetuk es az uniojuk is be-pontos es hogy d(X; Y ) = 0. De ekkor L-ben az X-t es Y -t a metszettel es az unioval kicserelve a keletkez} halmazokbol allna, amelyre igaz, hogy minden el belelep egy tagjaba, jL0j = jLj es P(jZ j2 o: ZL02be-pontos P 0 L ) > (jZ j2 : Z 2 L), ellentmondasban L valasztasaval. Legyen s a V -nek tetsz}oleges eleme. Legyen Fbe := fX V ? s; X 2 Lg es legyen Fki := fV ? X : s 2 X 2 Lg. Ekkor F := Fbe [ Fki olyan laminaris halmaz-csalad, hogy a digraf minden ele vagy belep egy be-pontos tagjaba vagy kilep egy ki-pontos tagjabol. () P Tegyuk fel, hogy F ilyen tulajdonsagu, es hogy (jZ j : Z 2 F ) minimalis. 1. ESET F minden tagja egyelem}u. Egy s-b}ol kilep}o el biztosan belep F egy be-pontos tagjaba, ezert Z := [(X : X 2 Fbe) nem-ures, de ekkor egy Z-b}ol kilep}o el megserti ()-t. 2. ESET F -nek letezik nem egyelem}u tagja. Legyen Z minimalis ilyen, es jelolje Zbe a Z-ben lev}o egypontu Fbe-beli halmazok uniojat, mg Zki a Z-ben lev}o egypontu Fki-beli halmazok uniojat. Szimmetria miatt feltehetjuk, hogy Z be-pontos. Termeszetesen keszen vagyunk, ha Zbe \ Zki = 6 ;, gy tegyuk fel, hogy Zbe \ Zki = ;. 17
Azt alltjuk, hogy Z er}osen osszefugg}o reszgrafot feszt. Ha ugyanis nem ez a helyzet, akkor letezik Z-nek egy olyan X valodi nem-ures resze, amelybe nem vezet el ZP? X-b}ol. De ekkor k %(X) %(Z) = k, amib}ol %(X) = k es gy F ? Z + fX g is jo rendszer, ellentetben (jZ j : Z 2 F ) minimalitasaval. Nem lehet az, hogy Zbe = Z, mert ekkor Z-t ki lehetne hagyni F -b}ol. Valojaban a Zbe halmaz ures, mert kulonben az er}osen osszefugg}oseg miatt lep ki el a Zbe halmazbol a Z ? Zbe halmazba, de ez az el szuksegkeppen megserti ()-t. Minden u 2 Z pontnak P Zki-ben kell lennie, mert kulonbenPegy uv el, v 2 Z, megserti ()-t. Tehat Zki = Z. De ekkor k = %(Z) = v2Z %(v) ? i(Z) kjZ j ? i(Z) = v2Z (v) ? i(Z) (Z) k, vagyis mindegyik egyenl}otlenseg egyenl}oseggel teljesul es gy Z minden pontjara %(v) = (v) = k. (Itt i(Z) a Z altal fesztett elek szamat jeloli).
Feladat Igazoljuk, hogy az el}oz}o tetel feltetelei mellett ket pont is letezik a kvant tulajdonsaggal. 5.5 TE TEL Egy G = (V; E) iranytott graf akkor es csak akkor k-elosszefugg}o, ha egy pontbol kiindulva el}oallthato az alabbi ket m}uvelet egymas utani ismetelt alkalmazasaval. (A) Ket letez}o pontot kossunk ossze egy ellel, (B) Valasszunk ki tetsz}olegesen k meglev}o elt, mindegyiket osszuk fel egy ponttal, es egyestsuk a k osztaspontot egyetlen uj pontta.
Biz. Gyakorlatkent hagyjuk annak igazolasat, hogy mind (A), mind (B) fenntartja a k-elosszefugg}oseget. A tetel nem-trivialis iranyanak bizonytasahoz jE j szerinti indukciot alkalmazunk. Az alltas semmitmondo, ha jV j = 1, gy legyen jV j 2. A felteves szerint G k-elosszefugg}o. Amennyiben letezik olyan e el, amelyre G0 := G ? e is k elosszefugg}o, akkor indukcio alapjan G0-nek mar letezik kvant el}oalltasa, es ezt kiegesztve az e el hozzaadasaval, a G keresett el}oalltasat kapjuk. Tegyuk most fel, hogy G el-elhagyasra nezve minimalis k-elosszefugg}o digraf. Az el}oz}o tetel szerint letezik egy s pontja, amelyre (s) = %(s) = k. Alkalmazzuk az 5.3 Tetelt. A keletkez}o G0 digraf k-elosszefugg}o, gy indukcio alapjan G0-nek mar letezik kvant el}oalltasa. Ebb}ol G el}oalltasat ugy kapjuk meg, hogy a G0-ben szerepl}o k leemelt elre alkalmazzuk a (B) operaciot.
Gyakorlat Igazoljuk, hogy a fenti (A) es (B) m}uveletek valoban k-elosszefugg}o digrafot eredmenyeznek. AZ E LO SSZEFU GGO} SE G NO VELE SE Ahogyan Lovasz iranytatlan leemel}os tetelet hasznaltuk iranytatlan elosszefugg}osegi problemak megoldasahoz, Mader iranytott leemelesi tetelenek segtsegevel megoldhatjuk az iranytott novelesi problemat. Tegyuk fel, hogy egy G = (V; E) iranytott graf nem k-szor elosszefugg}o, de uj elek hozzaadasaval azza akarjuk tenni.
5.6 TE TEL Adott G = (V; E) digraf es mbe : V ! Z+ , mki : V ! Z+ fokszam-el}orasok. Akkor es csak akkor letezik olyan H = (V; F) digraf, amelyre %H (v) = mbe (v) es H (v) = mki (v) teljesul minden v 2 V pontra es G + H k-elosszefugg}o, ha mbe (V ) = mki(V ),
es teljesul minden ; 6= X V reszhalmazra.
mbe (X) k ? %G (X)
(5:4a)
mki (X) k ? G (X)
(5:4b)
Biz. Ha letezik a kvant H digraf, akkor k %G+H (X) = %G (X)+%H (X) %G(X)+mbe (X), amib}ol (5.4a)
kovetkezik. (5.4b) analog modon lathato. Mivel mind mbe (V ), mind mki(V ) a H eleinek szamaval egyenl}o, gy mbe (V ) = mki (V ). Az elegend}oseg bizonytasahoz adjunk a grafhoz egy uj s pontot es minden v 2 V pontra mbe (v) parhuzamos elt s-b}ol v-be es mki(v) parhuzamos elt v-b}ol s-be. Az (5.4) feltetel szerint teljesul az 5.3 18
Tetel feltetele. Igy az s-be bemen}o es az s-b}ol kijov}o elek ugy parba allthatok, hogy az mbe (V ) darab par leemelesevel keletkez}o digraf k-elosszefugg}o. A leemelt elek H digrafja kielegti a tetel felteteleit.
5.7 TE TEL Egy G = (V; E) iranytott graf akkor es csak akkor tehet}o legfeljebb uj el hozzaadasaval k-elosszefugg}ove, ha a pontok minden fX1 ; : : :; Xtg resz-partciojara es
X(k ? %(X ))
(5:5a)
X(k ? (X )):
(5:5b)
i
i
i
i
Biz. A szuksegesseg bizonytasa egyszer}u gyakorlo feladat. Az elegend}oseghez legyen mbe : V ! Z+ olyan fuggveny, amelyre (5.4a) fennall es mbe(V ) minimalis.
LEMMA 5.8 mbe(V ) . Biz. Nevezzunk egy X V halmazt be-pontosnak, ha %(X) = mbe(X). Az mbe minimalitasa miatt minden v pont, amelyre mbe (v) > 0, benne van be-pontos halmazban. Tekintsuk a (tartalmazasra nezve) maximalis be-pontos halmazok M := fX1 ; : : :; Xt g csaladjat. Ha ennek letezik ket X; Y tagja, melyekre Y g resz-partciora felrva (ahol X := V ? X; Y := V ? Y ) azt kapjuk, hogy X [ Y = V , akkor (5.5b)-t az fX;
k ? (X) + k ? (Y ) = k ? %(X) + k ? %(Y ) = mbe (X) + mbe (Y ) mbe (V ), vagyis ilyenkor a lemma kovetkezik. Tegyuk fel, hogy M ket X; Y tagjara X [ Y = 6 V . Ekkor X \ Y = ;, mert kulonben k ? mbe (X) + k ? mbe (Y ) = %(X)+%(Y ) %(X \ Y )+%(X [ Y ) k ? mbe (X \ Y )+k ? mbe (X [ Y ) = k ? mbe (X)+k ? mbe (Y ), amib}ol az kovetkezik, hogy X [ Y is be-pontos ellentetben X vagy Y maximalitasaval. Azt kaptuk, hogy M be-pontos halmazokb P ol allo resz-partcio, amely P fedi az osszes olyan pontot, amelyre mbe (v) > 0. (5.5a)-t hasznalva mbe (V ) = (mbe (X) : X 2 M) = (k ? %(X) : X 2 M) . Teljesen analog modon kaphatunk egy (5.4b)-t kielegt}o mki fuggvenyt, amelyre mki (V ) . Az mbe es az mki esetleges megnovelesevel elerhetjuk, hogy mbe (V ) = es mki (V ) = . Az 5.6 Tetel alkalmazasaval a bizonytas teljes. Az elosszefugges novelesevel kapcsolatban erdemes meg megvizsgalni a novelesi feladatot, ha csak az mki fuggveny van el}orva (amivel nyilvan analog az az eset, amikor csak az mbe fuggveny el}ort).
5.9 TE TEL Adott G = (V; E) digraf es mki : V ! Z+ kifokszam-el}oras. Akkor es csak akkor letezik olyan H = (V; F) digraf, amelyre H (v) = mki (v) teljesul minden v 2 V pontra es G + H k-elosszefugg}o, ha mki (V )
X(k ? % i
G (Xi ))
(5:6)
teljesul V minden fXi g reszpartciojara es mki (X) k ? G (X)
(5:7)
teljesul minden ; 6= X V reszhalmazra.
Biz. Legyen := mki(V ). Ezen -ra alkalmazva az el}obbi tetel bizonytasat, most csak az mbe fuggvenyt kell megkonstrualnunk, hiszen az mki mar eleve adott. Tekintsuk tehat a minimalis mbe fuggvenyt, amely teljesti (5.4b)-t. Eleg igazolni, hogy az 5.8 Lemma ervenyben van. Ha a lemma bizonytasaban szerepl}o M-nek mki (X) letezik ket X; Y tagja, melyekre X [ Y = V , akkor (5.7) alapjan mbe (X) = k ? %G (X) = k ? G (X) 19
es mbe (Y ) = k ? %G (Y ) = k ? G (Y ) mki(Y ). Ezeket osszeadva kapjuk: mbe(V ) mbe (X) + mbe (Y ) + mki (Y ) mki(V ) = ; ami epp a Lemma alltasa. mki (X) Amennyiben M-benPnincs ket ilyen X;PY tag, ugy (amint azt mar lattuk) M reszpartcio, es ezert (5.6) szerint = mki (V ) i(k ? %G (Xi )) = i (mbe (Xi )) = mbe (V ), vagyis a Lemma ekkor is fennall.
Feladat Adott G = (V; E) digraf es pontjainak egy T reszhalmaza. Mutassuk meg, hogy a "Tegyuk G-t T-ben er}osen osszefugg}ove legfeljebb uj el hozzavetelevel" feladat NP-teljes. Ha viszont csak T pontjai kozott vezet}o uj eleket hasznalhatunk, akkor polinomialisan megoldhato. (A T-beli er}osen osszefugg}oseg azt jelenti, hogy T barmely pontjabol barmely masikba vezet iranytott ut.) DISZJUNKT FENYO} K Az 5.1 Tetel segtsegevel uj bizonytast adhatunk Edmonds diszjunkt feny}o tetelenek gyenge alakjara. A jelolesi kavarodas elkerulese erdekeben tegyuk fel, hogy D csucs halmaza U (V helyett) es a D gyoker-pontja r (s helyett).
Biz. (1.1 Tetel) E lszam szerinti indukciot hasznalunk. A tetel semmitmondo, ha jU j = 1, gy feltesszuk, hogy jU j 2. Feltehet}o, hogy barmely el elhagyasa utan (5.1) mar nem ervenyes. Ekkor persze %(r) = 0. Tovabba minden v 2 U ? r pont be-foka pontosan k. Ha ugyanis %(v) > k volna, akkor Menger tetele alapjan
van k elidegen ut r-b}ol v-be, es azokat a v-be lep}o eleket kihagyva, amelyeket ezen utak nem hasznalnak, (5.1) tovabbra is fennallna. Mivel %(r) < (r), letezik olyan s 2 U ? r pont, amelyre (s) %(s) = k. Legyen V := U ? s.
5.10 LEMMA Letezik egy olyan D0 = (V; A0 ) digraf, amelyre %0 (X) k teljesul minden X V ? r halmazra, es amely D-b}ol ugy all el}o, hogy (s) elpart leemelunk s-nel majd s-t (a fennmaradt k ? (s) darab s-be lep}o ellel egyutt) eltoroljuk.
Biz. Huzzunk be minden v 2 U ? r pontbol (k ? (v))+ uj elt r-be (ahol x+ := max(x; 0)). Alkalmazzuk az 5.3 Tetelt, majd toroljuk el az r-be vezet}o eleket. Az indukcios felteves szerint D0 -ben letezik k elidegen r gyoker}u feszt}o feny}o. Jeloljuk ezeket F1 ; : : :; Fkval. Tegyuk fel, hogy ezek kozul az els}o hasznal leemelt elt. Mindegyik ilyen Fi-b}ol valasszuk ki az egyik gyokerhez legkozelebbi leemelt elt es jeloljuk fi = ui vi -vel (1 i ): Modostsuk az Fi -t ugy, hogy fi -t helyettestjuk az eredeti uis es svi elekkel (amelyek leemelesevel keletkezett), az osszes tobbi leemelt uv elet pedig helyettestjuk az eredeti sv ellel. Ily modon kapunk elidegen feszt}o feny}ot D-ben. Ekkor meg fennmarad k ? darab eredeti s-be lep}o el, amelyeket az Fi (i = + 1; : : :; k) feny}ok kozott szetosztva megkapjuk az eredeti D digraf k elidegen feszt}o feny}ojet.
Feladat Nevezzunk egy digrafot r-b}ol k-elosszefugg}onek, ha r-b}ol minden pontjaba vezet k elidegen ut. Igazoljuk, hogy egy D digraf akkor es csak akkor r-b}ol k-elosszefugg}o, ha el}oallthato az r-b}ol kiindulva az alabbi ket m}uvelet egymas utani ismetelt alkalmazasaval. (A) Ket letez}o pontot kossunk ossze egy ellel, (B) Legyen s uj pont. Valasszunk ki tetsz}olegesen u1v1 ; : : :; uj vj kulonboz}o meglev}o eleket, ahol 0 j k, es mindegyik ui vi elt helyettestsuk az uis; svi el-parral. Adjunk a digrafhoz k ? j (meglev}o pontbol) s-be vezet}o uj elt. Feladat Adjuk meg az el}oz}ovel analog el}oalltasat az olyan iranytatlan grafoknak, amelyek tartalmaznak k elidegen feszt}o fat. 20
6. HALMAZOK E S HALMAZPA ROK LEFOGA SA E LEKKEL Adott egy G = (V; E) iranytott graf, valamint a V alaphalmaz reszhalmazainak egy olyan F keresztez}o rendszere, amelynek mindegyik tagjabol lep ki a digrafnak valamely ele, de semelyik tagjaba nem lep be el. Azt mondjuk hogy elek egy F reszhalmaza lefogja F -t, ha F mindegyik tagjabol lep ki F-beli el. Az F egy I reszrendszeret fuggetlennek nevezzuk, ha G-nek semelyik ele sem lep ki I -nek egynel tobb tagjabol. A kovetkez}o tetel a Lucchesi-Younger tetel altalanostasa, az Edmonds-Giles tetel kovetkezmenye.
6.1 TE TEL Az F -t lefogo elek minimalis (F ) szama egyenl}o a fuggetlen F -beli halmazok maximalis (F ) szamaval.
Biz. A egyenl}otlenseg trivialis ezert csak a fordtott irany bizonytasaval foglalkozunk. Figyeljuk meg, hogy a digraf barmely e elere F azon tagjaibol allo Fe rendszer, amelyeket e nem fog le, keresztez}o. szerinti indukciot alkalmazunk. Ha ez a szam 0, akkor F ures, es gy is nulla. Tegyuk most fel, hogy F nem ures.
1. ESET Letezik a digrafnak olyan e ele, amelyre (Fe) < (F ). Az indukcios feltevest (Fe)-re felhasznalva, es a trivialis (F ) (Fe ) + 1 egyenl}otlenseget meg gyelve nyerjuk, hogy (F ) (Fe ) + 1 = (Fe) + 1 (F ), amib}ol a kvant (F ) (F ) egyenl}otlenseg adodik. 2. ESET A digraf minden e elere letezik F -nek egy olyan Ie fuggetlen reszrendszere, amely := (F ) tagbol all, amely tagok egyikeb}ol sem lep e ki. Legyen ezen halmazrendszerek egyestese J 0 (ugy ertve, hogy egy X halmaz annyi peldanyban fordul el}o J 0 -ben, ahany olyan e el van G-ben, amelyre X 2 Ie.) Ekkor J 0 -nek jE j tagja van es G minden ele legfeljebb jE j ? 1 tagbol lep ki.
(6:1)
Alkalmazzuk a kikeresztezesi eljarast azaz, ha J 0 -nek van ket keresztez}o tagja, akkor helyettestsuk }oket a metszetukkel es az uniojukkal. Egy ilyen cserenel (1) fennmarad es tovabbra is egy F tagjaibol allo halmazrendszert kapunk. Miutan egy kikeresztezes soran az elemszamok negyzetosszege n}o, legfeljebb veges lepes utan egy olyan keresztezes mentes J rendszert kapunk, amely az F -nek jE j (nem feltetlenul kulonboz}o) tagjat tartalmazza, es amelyre (1) fennall. Ismeretes, hogy egy J keresztezes mentes rendszerhez letezik egy F = (U; A) iranytott fa valamint V pontjainak ' lekepezese U-ba ugy, hogy J tagjai es fa elei 1-1 ertelm}uen megfelelnek egymasnak, espedig olymodon, hogy tetsz}oleges a faelre '?1 (Ua ) az a-nak megfelel}o halmaz J -ben, ahol Ua jeloli az F fabol az a el kihagyasaval keletkez}o ket komponens kozul azt, amelybe a belep. Miutan J tagjaiba nem lep be a G digrafnak ele, az adodik, hogy minden uv 2 E elre a faban a '(u) es '(v) pontok kozott vezet}o egyertelm}u Pe ut szuksegkeppen iranytott ut, espedig '(u)-tol '(v) fele. E rvenyes tovabba, hogy az e el J -nek pontosan azon tagjaibol lep ki, amelyek a Pe ut eleinek felelnek meg. Igy (1) alapjan azt kapjuk, hogy a Pe utnak legfeljebb jE j ? 1 ele van. Egy iranytott fa eleit barmely k pozitv egeszre meg lehet ugy szinezni, hogy valamennyi iranytott reszutban mind a k szn lenyegeben ugyanannyiszor fordul el}o, azaz az elteres ket szn el}ofordulasi szama kozott legfeljebb egy lehet. (Ez azert van gy, mert teljesen unimodularis matrixoknak van egyenletes kszinezese es egy iranytott faban az iranytott reszutak 0 ? 1-es incidencia matrixa teljesen unimodularis. Masreszt, kozvetlenul is egy igen egyszer}u moho algoritmus segtsegevel meg lehet a fa eleinek egy ilyen egyenletes k-szinezeset talalni.) Ha most k-t jE j ? 1-nek valasztjuk, akkor az egyenletes k szinezes olyan lesz, hogy minden e 2 E elhez tartozo Pe ut elei kulonboz}o szn}uek lesznek. Ez azt jelenti, hogy J -t fel lehet bontani k osztalyba ugy, hogy mindegyik e 2 E el egy osztalynak legfeljebb csak egy tagjaba lephet be, vagyis, hogy az osztalyok fuggetlen reszei F -nek. De ekkor mindegyik osztaly legfeljebb csak tagbol allhat, gy J -nek legfeljebb csak k = (jE j ? 1) tagja lehet, holott J -nek jE j tagja van. Ez az ellentmondas mutatja, hogy a 2. eset valojaban nem fordulhat el}o. 21
A Lucchesi-Younger tetel eredeti alakjanak megfogalmazasahoz nevezzunk eleknek egy F reszhalmazat
kotesnek, ha osszehuzasaval er}osen osszefugg}o reszgrafot kapunk (ami azzal ekvivalens, hogy F minden iranytott vagast lefog.)
LUCCHESI E S YOUNGER TE TELE Legyen G = (V; E) iranytott graf. Az elidegen iranytott vagasok maximalis szama egyenl}o a minimalis kotes elemszamaval.
AZ E LIDEGEN UTAK PROBLE MA JA A Lucchesi-Younger tetel egy erdekes alkalmazasakent levezetunk egy elidegen utakra vonatkozo tetelt. G = (V; E) iranytott grafban adott k pontpar (s1 ; t1); : : :; (sk ; tk ). Keressunk a grafban k darab elidegen utat ugy, hogy az i-dik ut si -b}ol vezet ti -be. Bebizonytottak, hogy ez a problema meg k = 2 esetben is NP-teljes. Specialis esetekben azonban a feladat kezelhet}o. Minden i-re ti -b}ol vezessunk egy un. igenyelt si -be, es jeloljuk az igenyelek grafjat H = (V; F)-fel. Ekkor az elidegen utak problemaja azzal ekvivalens, hogy a G + H unio grafban kell keresni k olyan kort, melyek elidegenek es mindegyikuk pontosan egy igenyelt hasznal. Az ilyen kort nevezzuk F -jo kornek.
FEDE SI FELTE TEL Az F-jo koroket nem lehet k-nal kevesebb E [ F-beli ellel lefogni. Ekvivalens alakban: Barmely k0 (1 k0 k) terminal-parra az si -b}ol ti -be vezet}o utakat nem lehet 0 k -nel kevesebb G-beli ellel lefogni. A feltetel nyilvan szukseges a k elidegen F-jo kor, azaz a k elidegen ut
letezesehez.
6.2 TE TEL Amennyiben G aciklikus es G+H skgraf, ugy a fedesi feltetel szukseges es elegend}o az elidegen
utak problemajanak megoldasahoz.
Biz. Tekintsuk a G + H digraf skbeli dualisat, G0 + H 0-t. A lltjuk, hogy ebben letezik k elidegen iranytott vagas. Ha nem ez volna a helyzet, akkor a Lucchesi-Younger tetel alapjan letezne legfeljebb k ? 1 el, amely az osszes iranytott vagast lefogja. Ez eppen azt jelentene, hogy az eredeti G+H grafban az osszes iranytott kort le lehetne fogni k-nal kevesebb ellel, ellentetben a fedesi feltetellel. Tehat G0 +H 0 -ben van k elidegen iranytott vagasunk, azaz az eredeti G+H-ban van k elidegen iranytott korunk. Mivel a felteves szerint G aciklikus, ezen korok mindegyike tartalmaz legalabb egy igeny elt. Masreszt k igenyel van, gy a k kor mindegyike pontosan egy igenyelt tartalmaz, vagyis ezen korok F-jo korok. Megjegyezzuk, hogy altalaban meg aciklikus digrafra is NP-teljes az elidegen utak problemaja. Ilyenkor azonban eggyel jobb a helyzet mint altalanos G-re: ha k konstans, akkor a feladat P-ben van.
HALMAZPA ROK LEFOGA SA Az alabbiakban bemutatunk egy meglep}oen hatekony tetelt, amelynek a bizonytasa tobb ponton is emlekeztet a 6.1 tetel bizonytasara. Legyen V veges alaphalmaz, S es T a V -nek ket nemures reszhalmaza. Jelolje A := A(S; T) azon iranytott st elek halmazat melyekre s 2 S; t 2 T. Jelolje A := A(S; T) azon (X; Y ) parok halmazat, melyekre ; 6= X S; ; 6= Y T. Az X els}o tagot (illetve, az Y masodik tagot) a par tovenek (fejenek) nevezzuk. Egy e = st 2 A elre es az (X; Y ) 2 A parra azt mondjuk, hogy e fedi (X; Y )-t, ha s 2 X; t 2 Y , vagyis, ha e 2 A(X; Y ). Ket par t}o-diszjunkt (illetve, fej-diszjunkt), ha toveik (ill. fejeik) diszjunktak. Ha a 22
kett}o kozul legalabb az egyik fennall, akkor a parok felig-diszjunkt (vagy fuggetlenek ). A parok osszehasonlthatok, ha X X 0 ; Y 0 Y vagy X 0 X; Y Y 0. Az (X; Y ); (X 0; Y 0) parok nem-keresztez}ok, ha felig diszjunktak, vagy osszehasonlthatok. Maskulonben azt mondjuk, hogy (X; Y ); (X 0 ; Y 0 ) keresztezik egymast vagy hogy keresztez}oek. Halmaz-parok egy F A csaladja keresztezes mentes, ha F -nek nincs ket keresztez}o tagja. F -t keresztez}onek mondjuk, ha az F barmely ket (X; Y ); (X 0; Y 0 ) keresztez}o tagjara mind (X \ X 0 ; Y [ Y 0), mind (X [ X 0 ; Y \ Y 0) hozzatartozik F -hez. De nialjunk A -n egy P := (A ; ) reszbenrendezest a kovetkez}okeppen. (X; Y ); (X 0 ; Y 0) 2 A parokra legyen (X; Y ) (X 0 ; Y 0 ), ha X X 0 es Y Y 0 . Az A ket tagja nyilvan akkor osszehasonlthato, ha P-ben osszehasonlthatok. P megszortasat az A -nak valamely F reszhalmazara P(F )-fel fogjuk jelolni. 6.3 TE TEL Legyen L A(S; T) halmaz-parok keresztez}o csaladja. Az L -ben lev}o fuggetlen parok maximalis (L) (szama egyenl}o az L tagjait lefogo A -beli elek minimalis (L) szamaval.
Biz. Mivel ket fuggetlen part egy ellel nem lehet lefogni, ezert a egyenl}otlenseg kezenfekv}o es csak a fordtott irany bizonytasaval foglalkozunk. Figyeljuk meg, hogy barmely e 2 A elre az L azon tagjaibol allo Le rendszer, amelyeket e nem fog le, keresztez}o. szerinti indukciot alkalmazunk. Ha ez a szam 0, akkor L ures, es gy is nulla. Tegyuk most fel, hogy L nem ures. 1. ESET Letezik egy olyan e 2 A el, amelyre (Le) < (L). Az indukcios feltevest (Le)-re felhasznalva, es a trivialis (L) (Le)+1 egyenl}otlenseget meg gyelve nyerjuk, hogy (L) (Le)+1 = (Le)+1 (L), amib}ol a kvant (L) (L) egyenl}otlenseg adodik. 2. ESET Minden lehetseges e 2 A elre letezik L-nek egy olyan Ie fuggetlen reszrendszere, amely := (L) tagbol all, es amely tagok egyiket sem fogja le e. Legyen ezen halmazrendszerek egyestese J 0 (ugy ertve, hogy egy X halmazpar annyi peldanyban fordul el}o J 0-ben, ahany olyan e el van, amelyre X 2 Ie .) Ekkor J 0 -nek jA j tagja van es minden el legfeljebb jA j ? 1 tagba lep be.
(6:2)
Alkalmazzuk a kikeresztezesi eljarast azaz, ha J 0 -nek van ket keresztez}o tagja, akkor helyettestsuk }oket a metszetukkel es az uniojukkal. Egy ilyen cserenel (1) fennmarad es tovabbra is egy L tagjaibol allo halmazparok rendszeret kapjuk. P Legyen k(X; Y ) := jX j + jT ? Y j es k(I 0) := (k(X; Y ) : (X; Y ) 2 I 0). Konnyen ellen}orthet}o, hogy egy kikeresztezesi lepesnel a k(I 0 ) kiser}o parameter szigoruan novekszik, gy veges sok lepes utan olyan keresztezes mentes J rendszert kapunk, amely az L-nek jA j (nem feltetlenul kulonboz}o) tagjat tartalmazza, es amelyre (1) fennall. Ez utobbi azzal ekvivalens, hogy az J -n de nialt reszbenrendezesben nincsen jAj? 1nel hosszabb lanc. (Ezen a ponton hasznaljuk ki, hogy az A -ban minden lehetseges S-b}ol T-be men}o el benne van es A nem egyszer}uen egy el}ore megadhato digraf elhalmaza, amelynek elemeib}ol szabad csak a lefogashoz az eleket valasztani. Ugyanis az el}obbi megfontolas azon meg gyelesen mulik, hogy halmazparok egy tetsz}oleges lancanak a tagjait egyetlen iranytott ellel lefoghatjuk, nevezetesen egy olyannal, ami a tovek metszeteb}ol a fejek metszetebe vezet.) A Dilworth tetel dualisa szerint J felbonthato legfeljebb jA j ? 1 antilancra. De mivel J -nek jA j tagja van, az egyik antilanc bizonyosan legalabb (L) + 1 tgbol all. De ezen tagok paronkent fuggetlenek, ami ellentmond a (L) de niciojanak. Tehat a masodik eset valojaban nem fordulhat el}o.
ALAKZATOK MINIMA LIS FEDE SE TE GLALAPOKKAL Els}o alkalmazaskent levezetjuk Gy}ori tetelet. Legyen P = (v0 ; e1; v1; e2 ; v2; : : :; en; vn) egyszer}u iranytott ut, ahol az ei iranytott el tove vi?1 es feje vi . Jeloljuk a P csucs halmazat V -vel. Legyen F := fF1; : : :; Fkg a P reszutjainak egy rendszere. A kovetkez}okben uton mindig az ut elhalmazat ertjuk. 23
Azt mondjuk, hogy P reszutjainak egy B rendszere generalja F -t vagy hogy B generatora F -nek, ha F minden tagja el}oall nehany B-beli ut egyestesekent. Peldaul F sajat maganak generatora, az egyelem}u utakbol allo fe1; : : :; en g rendszer is generalja F -t. Jelolje (F ) az F generatorainak minimalis elemszamat. Azt mondjuk, hogy egy F utbol es annak egy e eleb}ol allo (F; e) par reprezentalt utat alkot. Jeloljuk Fr -vel az olyan (F; e) reprezentalt utak halmazat, amelyekre F 2 F . Legyen I := fI1; : : :; It g a P reszutjainak egy csaladja es legyen R := ff1 ; f2; : : :; ftg egy reprezentalo rendszer, azaz az fi iranytott elek kulonboz}o elemei P-nek es fi 2 Ii minden i = 1; : : :; t-re. Azt mondjuk, hogy R er}os reprezentalo rendszer, ha Ii \ Ij nem tartalmazza fi es fj mindegyiket (i; j, 1 i < j t). Ebben az esetben azt mondjuk, hogy a reprezentalt utak f(I1 ; f1 ); (I2; f2 ); : : :; (It ; ft)g csaladja fuggetlen. Az I := fI1 ; : : :; It g er}osen reprezentalhato, ha letezik er}os reprezentans rendszere. Jelolje (F ) az F -ben lev}o lev}o er}osen reprezentalhato utak maximalis szamat. Konnyen lathato, hogy ha R er}osen reprezentalhato utrendszer, akkor R-t nem lehet jRj-nel kevesebb uttal generalni. Ebb}ol kovetkezik, hogy utak tetsz}oleges F rendszerere (F ) (F ): Gy}ori tetele azt alltja, hogy itt valojaban egyenl}oseg szerepel:
6.4 TE TEL A P ut reszutjainak barmely F csaladjara fennall (F ) = (F ): Biz. A nem-trivialis egyenl}otlenseget igazoljuk. Jelolje Fr a reprezentalt utak halmazat. Fr egy (F; f) tagjat lenyegesnek mondjuk, ha nincs olyan F 0 (= 6 F) tagja F -nek, amelyre f 2 F 0 F. Fr minden (F; f) lenyeges tagjanak megfeleltetunk egy (A; B) halmaz-part, amely V diszjunkt reszhalmazaibol all, ahol (A; B) az F ut V (F) pont-halmazanak ket-reszes partcioja ugy, hogy A az F-nek azon pontjaibol all, melyek megel}ozik az f elt, mg B azokbol, melyek kovetik. Jelolje LF az gy kapott halmaz-parok csaladjat.
6.5 LEMMA LF keresztez}o. Biz. Legyen (A; B) es (A0; B 0) ket keresztez}o tagja LF -nek es legyen (F; f) illetve (F 0; f 0 ) a ket megfelel}o lenyeges lenyeges tagja Fr -nek. Mivel (A; B) es (A0 ; B 0) keresztez}o, ezert f 2 F 0 es f 0 2 F.
Azt alltjuk, hogy sem A es A0 , sem B es B 0 nem osszehasonlthato halmazok. Valoban, tegyuk fel indirekt, hogy peldaul A magaban foglalja A0 -t. Mivel (F; f) lenyeges, B 0 valodi reszhalmazkent tartalmazza B-t. De ez azt jelenti, hogy (A; B) es (A0 ; B 0 ) osszehasonlthato parok, szemben a feltevessel, hogy keresztez}oek. Kovetkezik, hogy (A \ A0 ; B [ B 0 ) az a par, amit az (F 0; f) reprezentalt utnak feleltettunk meg es (A [ 0 A ; B \ B 0 ) az a par, amit az (F; f 0 ) reprezentalt utnak feleltettunk meg. Annak igazolasara, hogy (A [ A0; B \ B 0 ) es (A \ A0 ; B [ B 0 ) az LF -hez tartozik, azt kell kimutatnunk, hogy a hozzajuk tartozo (F 0; f) es (F; f 0 ) reprezentalt utak lenyegesek. Ezt csak (F; f 0 )-re tesszuk meg, mert a bizonytas (F 0; f) eseteben hasonlo. Ha indirekt letezne F -nek olyan X tagja, amelyre f 0 2 X F, akkor f 62 X hiszen (F; f) lenyeges. De ekkor X F 0, ellentmondasban azzal, hogy (F 0; f 0 ) lenyeges. Vilagos, hogy LF -nek egy fuggetlen resz-csaladja megfelel az F egy er}osen reprezentalhato resz-csaladjanak. Legyen tovabba C := fc1 ; : : :; ct g az LF fedese, ahol c1 ; : : :; ct iranytott elek a V alaphalmazon. Legyen Bi a P-nek olyan reszutja, melynek els}o pontja a ci tove, az utolso pontja a ci feje. Legyen B := fB1; : : :; Bt g. Azt alltjuk, hogy B generalja F -t. Ha nem gy lenne, akkor letezne F -nek olyan minimalis F tagja, amely nem all el}o B-beli utak egyestesekent. Ekkor F-nek van olyan f ele, amelyre () B-nek semmilyen B tagjara sem f 2 B F. Miutan C fedi a lenyeges paroknak megfeleltetett halmaz-parokat, (F; f) nem lehet lenyeges. Vagyis letezik olyan F 0 az F -ben, amelyre f 2 F 0 F. Az F minimalis valasztasa miatt, F 0 el}oall B-beli halmazok egyestesekent, ellenmondasban a () tulajdonsaggal. Most Gy}ori tetele rogton kovetkezik a 6.3 tetelb}ol. Bemutatjuk Gy}ori tetelenek egy erdekes kombinatorikus geometriai kovetkezmenyet. Legyen T a sknak vzszintes es fugg}oleges szakaszokkal hatarolt (osszefugg}o, zart) tartomanya. T-t le akarjuk fedni T-be es}o (zart) teglalapokkal. Az alabbiakban teglalapon mindig olyan teglalapot ertunk melyek oldalai vzszintesek vagy fugg}olegesek. A szukseges teglalapok szama nyilvan legalabb akkora, mint T paronkent "fuggetlen" pontjainak maximalis szama, ahol ket pontot akkor nevezunk fuggetlennek, ha nem fedhet}ok le T-hez tartozo teglalappal (azaz a ket pont altal meghatarozott legsz}ukebb teglalap kilog T-b}ol). Letezik olyan pelda, ahol 24
ezen maximumnal tobb teglalapra van szukseg a fedeshez. Ennek fenyeben ertekes, hogy fugg}olegesen konvex alakzatokra a min-max tetel fennall. A T tartomanyt akkor nevezzuk fugg}olegesen konvexnek, ha T-nek es barmely vzszintes egyenesnek a metszete szakasz.
6.6 TE TEL Legyen T vzszintes es fugg}oleges szakaszok altal hatarolt zart, fugg}olegesen konvex tartomany
a skban. A T-t fed}o teglalapok minimalis szama egyenl}o T paronkent fuggetlen pontjainak maximalis szamaval.
Biz. Feltehet}o, hogy a hatarolo szakaszok fugg}oleges illetve vzszintes koordinatai egeszek, tovabba, hogy a bal szels}o hatarolo szakasz koordinataja 0, a jobb szels}oe pedig n. Legyen fv0; : : :; vng egy v0 -bol vn-be
vezet}o P ranytott ut ponthalmaza. Nevezzunk egy T-be es}o teglalapot eleminek, ha magassaga egysegnyi es vzszintes iranyban maximalis (azaz T valamely baloldali hatarolo oldalatol egy jobboldali hatarolo oldalaig terjed.) Az elemi teglalapok lefedik T-t es ket elemi teglalapnak csak az oldalukon lehet kozospontja. Minden Z elemi teglalaphoz rendeljuk hozza a P-nek egy vi -b}ol vj -be vezet}o PZ reszutjat, ahol i illetve j a Z baloldali illetve jobboldali hatarolo koordinataja. Legyen y(PZ ) a Z also vzszintes hatarolo szakaszanak koordinataja plusz 21 , es jelolje F a kapott reszut rendszert. Tekintsuk most az P egy maximalis er}osen reprezentalt rendszeret: f(I1 ; f1 ); (I2; f2 ); : : :; (It; ft)g, ahol t = (F ). Legyen yi := y(Ii ) es xi az fi el tovenek x-koordinataja plusz 21 . A konstrukcio miatt a Zi := (xi ; yi) pontok (i = 1; : : :; t) mind T-ben vannak. A lltjuk, hogy paronkent fuggetlenek. Valoban, ha Zi es Zj nem volna fuggetlen, akkor az o}ket tartalmazo legsz}ukebb teglalap T-hez tartozna, de ez ellentmondasban van az er}os reprezentans rendszer de nciojaval. Azt kaptuk tehat, hogy a T-b}ol kivalaszthato fuggetlen pontok maximalis szama legalabb (F ). Legyen B az F -nek minimalisgeneralo rendszere, amely tehat P-nek (F ) darab reszutjabol all. Mindegyik B 2 B uthoz egyertelm}uen hozzatartozik egy T-ben fekv}o fugg}oleges iranyban maximalis teglalap, amelynek "vzszintes vetulete" eppen a B ut. A lltjuk, hogy az gy kapott (F ) darab teglalap lefedi T-t. Valoban T tetsz}oleges S = (x; y) pontja benne van valamelyik Z elemi teglalapban. Az ehhez tartozo P -beli PZ ut el}oall B-beli utak egyestesekent. Tehat B-nek van olyan B tagja, amely PZ -ben van es tartalmazza a vbxc vdxe elt. A T fugg}oleges konvexitasabol kovetkez}oen a B-hez rendelt teglalap tartalmazza az S pontot. A 6.4 tetelb}ol adodoan = , amib}ol a 6.6 tetel kovetkezik.
IRA NYITOTT GRA FOK O SSZEFU GGO} SE GE NEK NO VELE SE EGGYEL Korabban mar lattuk, hogy legkevesebb hany uj el hozzaadasaval lehet egy digrafot k-eloszefugg}ove tenni. Kerdes, hogy mi mondhato a pont-osszefugg}oseg noveleser}ol. A 6.3 tetel lehet}oseget biztost arra, hogy a kerdesre valaszt adjunk abban a specialis esetben, amikor az osszefugg}oseget csak eggyel akarjuk novelni. Tegyuk fel, hogy a G = (V; E) digraf (k ? 1)-szer osszefugg}o, de k-szor mar nem. Ekkor van olyan (X; Y ) diszjunkt nemures reszhalmazokbol allo par, amelyre V ? (X [ Y ) = k ? 1 es nem vezet G-beli el X-b}ol Y -ba. Nevezzuk az ilyen parokat hianyosnak es legyen LG a hianyos parok csaladja. Ket hianyos part nevezzunk fuggetlennek, ha vagy a tovuk diszjunkt vagy a fejuk diszjunkt (vagy mindkett}o).
6.6 TE TEL Egy G = (V; E) (k ? 1)-szer osszefugg}o digraf akkor es csak akkor tehet}o legfeljebb uj el hozzaadasaval k-osszefugg}ove, ha a fuggetlen hianyos halmazparok maximalis szama legfeljebb .
Biz. U j eleknek egy F halmazat G-hez adva pontosan akkor kapunk k-osszefugg}o digrafot, ha F minden hianyos part lefog. A stndard szubmodularitasi technikat hasznalva konnyen igazolhato, hogy LG halmazparoknak egy keresztez}o csaladja. Ezert a 6.1 tetel alkalmazhato, es ebb}ol az eredmeny kozvetlenul adodik. Ha a digraf osszefugg}oseget tobb mint eggyel akarjuk novelni, akkor a 6.3 tetel immar kevesnek bizonyul. Az altalanostast a kovetkez}o szakaszban targyaljuk. 25
7. HALMAZPA ROK SU LYOZOTT LEFOGA SA E LEKKEL A D = (V; A) iranytott grafban az X; Y V reszhalmazokra jelolje D (X; Y ) := A (X; Y ) := (X; Y ) azon D-beli xy elek szamat, melyekre x 2 X; y 2 Y . Ha X = V ? Y , akkor legyen %A (Y ) := %D (Y ) := %(Y ) := A (X) := D (X) := (X) := D (X; Y ), vagyis %(Y ) (illetveP(X)) az Y -ba belep}o (ill. X-b}ol kilep}o) elek P szama). Egy x : A ! R fuggvenyre legyen %x(X) := (x(e) : e 2 A; e belep X-be) es x (X) := (x(e) : e 2 A; e kilep X-b}ol). Legyen F az A(S; T) resz-csaladja. Valamely pozitiv egesz h-ra azt mondjuk, hogy F h-fuggetlen, ha minden e 2 A(S; T) el legfeljebb h tagjat fedi F -nek. h = 1 eseten egyszer}uen fuggetlent mondunk. Ez azzal ekvivalens, hogy F tagjai paronkent felig diszjunkt. A ltalanosabban azt mondjuk, hogy az A -n ertelmezett nem-negatv w fuggveny h-fuggetlen, ha cw (e) h fennall minden e 2 A elre. P Az A -n ertelmezett f fuggvenyre es valamely F A -re hasznaljuk az f(F ) := (f(X; Y ) : (X; Y ) 2 F ) jelolest. Valamely x szamra legyen x+ := x, ha x 0 es x+ := 0, ha x < 0. Valamely f valos fuggvenyre f + jelolje az f + (x) := f(x)+ altal de nialt fuggvenyt. A ltalanostsuk az el}obbi fogalmakat halmaz-parokra is. Legyen S es T a V ket nemures reszhalmaza. Legyen A := A(S; T) es p nemnegatv egeszertek}u fuggveny A -n. Azt mondjuk, hogy p keresztez}o bi-szupermodularis, ha p(X; Y ) + p(X 0 ; Y 0) p(X \ X 0 ; Y [ Y 0 ) + p(X [ X 0 ; Y \ Y 0)
(7:1)
fennall ha X S; Y T; X \ X 0 ; Y \ Y 0 6= ; es p(X; Y ); p(X 0 ; Y 0) > 0. Ha a fordtott egyenl}otlenseg all (7.1)-ben, akkor keresztez}o bi-szubmodularis fuggvenyr}ol beszelunk. Egy e = st 2 A el segtsegevel de nialhatunk A -n egy (0 ? 1)-ertek}u be fuggvenyt a kovetkez}okeppen: be (A; B) := 1, ha e fedi (A; B)-t es 0 kulonben. Egy nemnegatv x : A ! R+ vektorra de nialjuk bx : A ! R+ fuggvenyt: bx(A; B) := x(A; B). A kovetkez}o alltas els}o resze nyilvanvalo, a masodik pedig rogton kovetkezik az els}ob}ol.
7.1 A LLITA S be bi-szubmodularis. bx bi-szubmodularis. Bevezetunk ket bi-szupermodularis fuggvenyekre vonatkozo egyszer}u operaciot. Valamely e = xy 2 A elre legyen pe := (p ? be)+ , vagyis pe(X; Y ) := p(X; Y ) ? 1, ha p(X; Y ) > 0, x 2 X; y 2 Y es pe (X; Y ) := p(X; Y ) kulonben. Mivel be bi-szubmodularis, p ? be keresztez}o bi-szupermodularis es ezert pe is az. Azt mondjuk, hogy pe a p redukaltja (az e menten). Legyen S 0 S; T 0 T ket nemures reszhalmaz. A p fuggvenynek az A(S 0 ; T 0 )-re torten}o p0 vettesen a kovetkez}ot ertjuk. (X 0 ; Y 0 ) 2 A(S 0 ; T 0)-re legyen p0 (X 0 ; Y 0 ) := max(p(X; Y ) : (X; Y ) 2 A(S; T); X \ S 0 = X 0 ; Y \ T 0 = Y 0). Konnyen latszik, hogy p0 keresztez}o bi-szupermodularis. Legyen w az A(S; T)-n ertelmezett nemnegatv, egeszertek}u fuggveny. A w fuggveny Sw tamaszan azon halmaz-parok csaladjat ertjuk, amelyekre w(X; Y ) P pozitv. Azt mondjuk, hogy w keresztezes mentes, ha a tamasza keresztezes mentes. P Legyen p(w) := (w(X; Y )p(X; Y ) : (X; Y ) 2 A(S; T)). De nialjuk a cw : A ! Z+ fuggvenyt: cw (e) := (w(X; Y ) : (X; Y ) 2 A(S; T); e fedi (X; Y )-t) ahol e 2 A .
7.2 LEMMA Adott w : A(S; T) ! Z+ ; fuggvenyre letezik olyan w : A(S; T) ! Z+ keresztezes mentes fuggveny, amelyre p(w) p(w) es cw cw . Valasszunk egy w : A(S; T) ! Z+ fuggvenyt ugy, hogy p(w) p(w), cw cw , es s(w) := PBiz.(w(X; Y )f(X; Y ) : (X; Y ) 2 A ) legyen a lehet}o legnagyobb, ahol is f(X; Y ) := (jX j ? jY j)2 . Ellen}orizhet}o, hogy f(X; Y )+f(X 0 ; Y 0 ) = f(X \X 0 ; Y [Y 0 )+f(X [X 0 ; X \Y 0)?2(jX ?X 0 j+jY 0 ?Y j)(jX 0 ? X j + jY ? Y 0j). Ezert f bi-szupermodularis es f(X; Y ) + f(X 0 ; Y 0 ) = f(X \ X 0; Y [ Y 0 ) + f(X [ X 0 ; X \ Y 0 ) akkor es csak akkor all fenn, ha (X; Y ) es (X 0 ; Y 0) osszehasonlthatoak. Azt alltjuk, hogy w keresztezes mentes. Tegyuk fel indirekt, hogy Sw -nek van ket keresztez}o tagja: (X; Y )
es (X 0 ; Y 0 ). Modostsuk w-t ugy, hogy csokkentjuk eggyel az erteket (X; Y )-n es (X 0 ; Y 0 )-n es noveljuk eggyel 26
(X \ X 0; Y [ Y 0)-n es (X [ X 0 ; Y \ Y 0 )-n A 7.1 alltas szerint cw cw . Mivel p keresztez}o bi-szupermodularis, p(w0 ) p(w). Mivel s(w0 ) > s(w), ellentmondasra jutottunk az w valasztasaval. 0
Legyen p nemnegatv egeszertek}u fuggveny A(S; T)-n. Azt mondjuk, hogy az A -n ertelmezett z nemnegatv fuggveny fedi p-t vagy hogy z a p-nek fedese, ha bz p, azaz z(X; Y ) p(X;PY ) fennall minden (X; Y ) 2 A(S; T)-re. Olyan egeszertek}u z fedesekre vagyunk kivancsiak, melyekre 1z = z(e) minimalis.
7.3 TE TEL Legyen p 0 egesz-ertek}u, keresztez}o bi-szupermodularis fuggveny. Ekkor p := min(z(A ) : z 0 egesz-ertek}u fedese p-nek) = p := max(p(F ): F fuggetlen). Biz. Lassuk be el}oszor a konny}u iranyt, vagyis hogy p p . Legyen z a p-nek fedese es legyen es F halmazparok fuggetlen csaladja. Mivel A -nak P P semmilyen ele sem fedi F -nek egynel tobb tagjat, azt kapjuk, hogy z(A ) (z(X; Y ) : (X; Y ) 2 F ) (p(X; Y ) : (X; Y ) 2 F ) = p(F ) es innen p p . Bizonytsuk be most a fordtott iranyt. Egy e 2 A elre legyen pe a p redukaltja. Mivel pe p, ervenyes, hogy p ? 1 pe p. Azt mondjuk, hogy az e el csokkent}o, ha pe < p . A kovetkez}o lemma a bizonytas kulcsa. 7.4 LEMMA Ha p > 0, akkor letezik csokkent}o el. Biz. Tegyuk fel indirekt, hogy nincs csokkent}o el, azaz pe = p minden e = xy 2 A elre fennall. Ez azt jelenti, hogy minden e elre letezik olyan Fe fuggetlen csalad, amelyre p(Fe ) = p es e nem fedi Fe egyik tagjat sem. Minden e 2PA elre legyen we olyan 0-1 fuggveny az A -n, amelyre we erteke 1 az Fe tagjain es 0 mashol. Legyen w := (we : e 2 A ), es legyen h := jS jjT j. Ha h = 1, akkor a lemma trivialis, gy legyen h 2. Most
p(w) = p h
es
(7:2a)
a w sulyozas (h ? 1) -fuggetlen. (7:2b) A 7.2 Lemma alapjan feltehetjuk, hogy w keresztezes-mentes. Legyen F 0 := Sw a w tamasza. Tekintsuk a P 0 := P(F 0) reszbenrendezest. Miutan F 0 keresztezes-mentes, ezert ha ket tagja nem osszehasonlthato P 0-ben, ugy azok felig diszjunktak. A (7.2) alapjan P 0-ben nincsen h ? 1-nel hosszabb lanc. A polaris Dilworth tetel (sulyozott valtozata) alapjan (:amely szerint ha adott a P 0 reszbenrendezett halmaz elemeinek egy w nem-negatv egesz sulyozasa, akkor egy maximalis sulyu lanc sulya egyenl}o azon antilancok minimalis szamaval, melyek minden v 2 P 0 elemet legalabb w(v)-szer fednek) kovetkezik, hogy van olyan antilanc, amelynek a sulya legalabb hp =(h ? 1) > p , ellentmondasban p de nciojaval. Ez az ellentmondas bizonytja a lemmat.
P
A p p egyenl}otlenseg igazolasat p(X; Y ) szerinti indukcioval vegezzuk. Ha ez az osszeg 0, akkor p = 0 = p . Ha az osszeg nem nulla, akkor alkalmazhatjuk az el}oz}o lemmat. Ennek alapjan letezik egy e = st 2 A csokkent}oPel. Ha z 0 fedi P pe -t, akkor z 0 (e) erteket eggyel novelve a p-nek fedeset kapjuk es innen e p pe + 1. Mivel p (X; Y ) < p(X; Y ), alkalmazhatjuk az indukcios feltevest, amib}ol azt nyerjuk, hogy p ? 1 pe = pe p ? 1, es innen p p , amit bizonytani akartunk.
IRA NYITOTT GRA FOK O SSZEFU GGO} SE GE NEK NO VELE SE Korabban lattuk, hogy iranytott grafot minimum hany ellel lehet k-szor elosszefugg}ove tenni, es az el}oz}o szakaszban megoldottuk a pont-osszefugg}oseg eggyel valo novelesenek problemajat is. A 7.3 tetel segtsegevel most megvalaszoljuk a pont-osszefugg}oseg novelesere vonatkozo altalanost kerdest. 27
Legyen D = (V; A) egyszer}u iranytott graf es tegyuk fel, hogy a k < jV j ? 1. A V diszjunkt nemures reszhalmazaibol allo (X; Y ) parra legyen h(X; Y ) := jV ? (X [ Y )j. Azt mondjuk, hogy (X; Y ) egyiranyu, ha nem megy el X-b}ol Y -ba, azaz (X; Y ) = 0, ahol (X; Y ) jeloli altalaban az X-b}ol Y -ba vezet}o elek szamat jeloli. Konnyen ellen}orizhet}o, hogy az egyiranyu parok keresztez}o par-rendszert alkotnak.
7.5 LEMMA A D+ = (V; A+ ) iranytott graf akkor es csak akkor k osszefugg}o, ha h(X; Y ) k
(7:3)
fennall minden (X; Y ) egyiranyu parra.
Biz. Ha D+ k-osszefugg}o, akkor letezik k bels}oleg diszjunkt ut minden x 2 X pontbol minden y 2 Y pontba. Mivel nincsen el X-b}ol Y -ba, a k ut mindegyike tartalmaz pontot V ? (X [ Y )-b}ol, amib}ol (7.3)
kovetkezik. Megfordtva, alljon fenn (7.3) es indirekt tegyuk fel, hogy nem letezik k bels}oleg diszjunkt ut valamely x pontbol egy masik y-ba. Amennyiben nincsen el x-b}ol y-ba, akkor a Menger tetel iranytott pont-valtozata alapjan letezik egy C V ? fx; yg reszhalmaz, amelynek kevesebb, mint k pontja van, es amely lefogja az osszes x-b}ol y-ba vezet}o iranytott utat. Legyen X a D+ ? C digrafban az x-b}ol elerhet}o pontok halmaza es Y := V ? X ? C. Ekkor az (X; Y ) par megserti (7.3)-t. Tegyuk most fel, hogy letezik az e = xy el. Ekkor a fenti ervelest a D+ ? e digrafra alkalmazva azt kapjuk, hogy letezik olyan (X; Y 0 ) par, amely V diszjunkt reszhalmazaibol all es x 2 X; y 2 Y 0, h(X; Y 0 ) k ? 2, tovabba e az egyetlen el D+ -ban, amely X-b}ol Y 0 -be megy. (7.3)-b}ol kovetkezik, hogy tetsz}oleges pont be-foka legalabb k, gy nem lehet, hogy Y 0 = fyg. Ekkor Y := Y 0 ? y nem ures es (X; Y ) olyan egyiranyu par, amely megserti (7.3)-t, amely ellentmondas a lemmat bizonytja. De nialjuk az (X; Y ) par hianyat: phi (X; Y ) = (k ? h(X; Y ))+ , ha (X; Y ) egyiranyu es := 0 kulonben. Vilagos, hogy phi (X; Y ) = (k ? kA (X; Y ) ? h(X; Y ))+ minden (X; Y ) parra fennall. Ezen utobbi formula mutatja, hogy phi keresztez}o bi-szupermodularis, miutan mind A (X; Y ), mind h(X; Y ) azok. Az alabbi lemma konnyen kovetkezik a 7.5 Lemmabol: eleknek egy F halmazat a D = (V; A) digrafhoz adva a keletkez}o D+ := (V; A+F) digraf 7.6 LEMMA Uj akkor es csak akkor lesz k-osszefugg}o, ha F (X; Y ) phi (X; Y ) fennall minden egyiranyu (X; Y ) parra. Diszjunkt reszhalmazokbol allo parok egy F csaladjat akkor neveztuk fuggetlennek, vagy felig diszjunktnak, ha F barmely ket (X; Y ); (X 0 ; Y 0 ) tagja felig diszjunkt, azaz X \ X 0 es Y \ Y 0 egyike legalabb ures.
7.7 TE TEL A D = (V; A) iranytott graf akkor es csak akkor tehet}o legfeljebb uj el hozzaadasaval
k-osszefugg}ove, ha
X(p
hi (X; Y ) : (X; Y ) 2 F )
fennall minden egyiranyu parokbol allo fuggetlen F csaladra.
Biz. A tetel rogton kovetkezik a 7.6 Lemmabol es a 7.3 Tetelb}ol az S = T = V es p := phi valasztas mellett.
28
8. POLIMATROIDOK E S ALKALMAZA SAIK I. Legyen S veges alaphalmaz. Az alabbiakban az S-en ertelmezett halmaz-fuggvenyekr}ol automatikusan feltesszuk, hogy egeszertek}uek es az ures halmazon az ertekuk 0. Legyen p; b ket halmaz-fuggveny, ahol b felvehet 1, p pedig ?1 erteket. A b : 2S ! Z [ f1g halmaz-fuggvenyr}ol azt mondjuk, hogy teljesen (metsz}o, keresztez}o) szubmodularis ha b(X) + b(Y ) b(X \ Y ) + b(X [ Y )
(8:1)
fennall minden (metsz}o, keresztez}o) X; Y S halmazra. Veges-ertek}u, monoton nov}o, teljesen szubmodularis fuggvenyt polimatroid fuggvenynek hvunk. A veges-ertek}u m halmaz fuggveny modularis, ha m(X) + m(Y ) = m(X \ Y ) + m(X [ Y ) fennall minden X;PY S-re. Ilyen fuggvenyt, (ha m(;) = 0) az egyelem}u halmazokon felvett ertekei meghataroznak: m(X) = (m(s) : s 2 X). A p halmaz-fuggveny szupermodularis, ha ?p szubmodularis. Azt mondjuk, hogy p nem-negatv fuggveny ferden szupermodularis, ha minden X; Y S-re, amelyre p(X) > 0; p(Y ) > 0, a kovetkez}o egyenl}otlensegek kozul legalabb az egyik teljesul: p(X) + p(Y ) p(X \ Y ) + p(X [ Y ); p(X) + p(Y ) p(X ? Y ) + p(Y ? X): Ebb}ol latszik, hogy metsz}o szupermodularis fuggveny ferden szupermodularis. Azt mondjuk, hogy a (p; b) halmaz-fuggveny par er}os par, ha p teljesen szupermodularis, b teljesen szubmodularis es osszeill}ok (compliant), azaz a b(X) ? p(Y ) b(X ? Y ) ? p(Y ? X)
(8:2)
un. kereszt egyenl}otlenseg fennall minden X; Y S halmazra. Ha p es b metsz}o szuper- illetve szubmodularis fuggvenyek es (8.2) fennall minden metsz}o X; Y -ra, akkor (p; b)-t gyenge parnak hvjuk. A p es b halmaz-fuggvenyekre de nialjuk az alabbi poliedereket: P(b) := fx 2 RS : x 0; x(A) b(A) minden A S g S(b) := fx 2 RS : x(A) b(A) minden A S g B(b) := fx 2 RS : x(S) = b(S); x(A) b(A) minden A S g C(p) := fx 2 RS : x 0; x(A) p(A) minden A S g Q(p; b) := fx 2 RS : p(A) x(A) b(A) minden A S g: Ha b polimatroid fuggveny, P(b) polimatroidnak hvjuk. Ha b teljesen szubmodularis, S(b) szubmodularis polieder. Ha b teljesen szubmodularis es b(S) veges, B(b) bazis polieder. Amennyiben b(S) = 0; 0-bazis poliederr}ol beszelunk. Ha p teljesen szupermodularis es monoton nov}o, akkor C(p) kontra-polimatroid. Vegul ha (p; b) er}os par, akkor Q(p; b) altalanostott polimatroid (vagy roviden g-polimatroid.) Megallapodunk abban, hogy az ures halmazt is g-polimatroidnak tekintjuk (bar latni fogjuk, hogy ez nem de nialhato er}os parral).
SZUBMODULA RIS A RAMOK Legyen D = (V; E) iranytott graf. Legyen f : E ! Z [ f1g es g : E ! Z [ f?1g also es fels}o korlatok, melyekre f g. Legyen b : 2V ! Z [ 1 teljesen szubmodularis fuggveny. Az x : E ! R vektort szubmodularis aramnak hvjuk, ha %x (A) ? x (A) b(A) (8:3) 29
P
P
fennall minden A V -ra. (Itt %x (A) := (x(e) : e belep A)-ba es x (A) := (x(e) : e kilep A-bol.) Az x szubmodularis aram megengedett, ha f x g. A megengedett szubmodularis aramok halmaza a szubmodularis aram polieder, melyet Q(f; g; b) jelol.
MEGENGEDETTSE GI TE TEL 8.1 Akkor es csak akkor letezik egeszertek}u megengedett szubmodularis aram, ha %f (A) ? g (A) b(A) (8:4) fennall minden A V -ra. Biz. Legyen x megengedett szubmodularis aram. Ekkor %f (A) ? g (A) %x (A) ? x(A) b(A) es (8.4) kovetkezik. A (8.4) elegend}osegehez szuksegunk van az alabbi lemmara.
LEMMA 8.2 Legyen p(A) := %f (A) ? g (A). Ekkor p(A) + p(B) p(A \ B) + p(A [ B) minden A; B V reszhalmazra es egyenl}oseg akkor es csak akkor all fenn, ha f(e) = g(e) minden olyan e elre, amelynek egyik vege A ? B-ban, a masik pedig B ? A-ban van.
Biz. A lemma kovetkezik az alabbi azonossagbol: p(A) + p(B) = p(A \ B) + p(A [ B) + P(f(e) ? g(e) : e egyik vege A ? B-ben van, masik vege B ? A-ban). Ez pedig azert igaz, mert minden elnek a ket oldalhoz konnyen ellen}orizhet}oen ugyanaz a hozzajarulasa. Az e elt pontosnak hvjuk, ha f(e) = g(e). Az A V reszhalmaz pontos, ha p(A) = b(A). Tegyuk fel, hogy a tetel nem igaz es legyen D olyan ellenpelda, amelyben pontos elek es a pontos halmazok egyuttes szama maximalis.
1. ESET Minden el pontos. Legyen x : f. Most %x (A) ? x(A) = %f (A) ? f (A) = %f (A) ? g (A) b(A),
vagyis x megengedett szubmodularis aram, ellentmondas. 2. ESET f(e0 ) < g(e0 ) valamely e0 elre. A lltjuk, hogy van olyan A pontos halmaz, amelybe e0 belep. Ha nem volna, akkor f(e0 )-t novelhetjuk (8.4) megsertese nelkul egeszen addig, amg vagy egy uj pontos halmaz keletkezik (amelybe e0 belep) vagy e0 valik pontossa. A modostott also korlat f 0 -ra nezve a pontos elek es halmazok egyuttes szama nagyobb, mint f-re nezve, gy ez mar nem ellenpelda, azaz letezik x szubmodularis aram, amelyre f 0 x g. Ekkor x megengedett f es g-re nezve is, ellentmondas. Hasonloan belathato, hogy letezik olyan B pontos halmaz, amelyb}ol e0 kilep. Most b(A) + b(B) = p(A) + p(B) p(A \ B) + p(A [ B) b(A \ B) + b(A [ B) b(A) + b(B). Ezert mindenhol egyenl}oseg all, specialisan p(A) + p(B) = p(A \ B) + p(A [ B). De ez ellentmond a lemmanak, mivel f(e0 ) < g(e0 ). Ezen ellentmondas mutatja, hogy nem letezhet ellenpelda.
Ha a 8.1 tetelt b 0-ra alkalmazzuk, Ho man tetelet kapjuk megengedett aramok letezeser}ol. Egy masik erdekes kovetkezmeny az alabbi.
DISZKRE T SZEPARA CIO S TE TEL 8.3 Legyen S alaphalmaz, p : 2S ! Z [ f?1g szupermodularis fuggveny es b : 2S ! Z [ f1g szubmodularis fuggveny, melyekre p (;) = b (;) = 0 es p b . Ekkor van olyan egeszertek}u m modularis fuggveny, amelyre p m b . Maszoval, az fx : x(A) b (A) minden A S-re, x(S) = 0g es az fx : x(A) p (A) minden A S-re, x(S) = 0g poliederek metszete akkor es csak akkor tartalmaz egesz pontot, ha p b . Biz. Legyen S 0 es S 00 az S-nek ket diszjunkt peldanya. Legyen V := S 0 [ S 00, E := fs0s00 : s 2 Sg es D = (V; E). Legyen ?f := g := 1 es X 0 S 0 ; X 00 S 00 -re b(X 0 [ X 00 ) := b (X) ? p (Y ). Nyilvan b tjuk, hogy (8.4) fennall. szubmodularis. Alkalmazzuk a 8.1 tetelt erre a szubmodularis aram problamara. All 0 00 Valoban, egy A = X [ Y halmazra, ahol X = 6 Y (X; Y S); %f (A) ? g (A) = ?1. Az A = X 0 [ X 00 (X S) halmazra %f (A) ? g (A) = 0, es akkor (8.4) kovetkezik a p (X) b (X) feltevesb}ol. A 8.1 tetel szerint van x megengedett szubmodularis aram, amely egeszertek}u, ha p es b azok. Most az m(s) := x(s0 s00 ) valasztassal megkapjuk a keresett modularis fuggvenyt. 30
Az els}o felevben hasznaltuk egy halmaz-fuggveny also es P fels}o reszeltjenek a folgalmat, es bebizonytottuk, hogy ha b metsz}o szubmodularis, akkor a b_ (X) := min( b(Xi ) : fXi g az X partcioja) (also) reszeltje teljesen szubmodularis. (Ezt az eredmenyt nemsokara kicsit altalanostva ujra bebizonytjuk). A reszelesi tetelt es a szeparacios tetelt osszevetve kapjuk:
DISZKRE T SZEPARA CIO S TE TEL 8.3B Legyen S alaphalmaz, p : 2S ! Z [ f?1g metsz}o szupermodularis fuggveny es b : 2S ! Z [ f1g metsz}o szubmodularis fuggveny, melyekre p (;) = b (;) = 0. Akkor es csak akkor van olyan egeszertek}u m modularis fuggveny, amelyre p m P b, ha barmely P ZS reszhalmazra es a Z-nek fX1 ; : : :; Xk g illetve fY1; : : :; Yl g partcioira fennall, hogy i (p(Xi ) j (b(Yj ). Az els}o felevben lattuk meg, hogy:
TE TEL 8.4 [Edmonds es Giles, 1977] A szubmodularis aram polieder egesz. LINKING Akkor mondjuk, hogy egy egesz Q poliedernek megvan a kapcsolasi vagy linking tulajdonsaga, ha barmely ket f; g (f g) egesz vektorra amennyiben fennall, hogy Q-nak van olyan x es y pontja, melyekre f x illetve y g, ugy Q-nak van olyan z egesz pontja is, amelyre f z g. Celunk annak kimutatasa, hogy g-polimatroidok rendelkeznek a linking tulajdonsaggal.
METSZET TE TEL 8.5 Legyen Q1 = Q(p1; b1) es Q2 = Q(p2 ; b2) ket er}os parral adott g-polimatroid (pi ; bi egeszertek}u). Q1 \ Q2 akkor es csak akkor tartalmaz egesz pontot, ha p1 b2 es p2 b1 . Biz. A feltetel nyilvan szukseges. Az elegend}oseg igazolasahoz egesztsuk ki az S alaphalmazt egy s ponttal es legyen S := S + s: De nialjuk a b es a p fuggvenyeket az S reszhalmazain a kovetkez}okeppen. Legyen b (X) := b1 (X), ha X S es b (X) := ?p1 (S ? X), ha s 2 X. Legyen p (X) := p2 (X), ha X S es p (X) := ?b2 (S ? X), ha s 2 X. A megkovetelt p1 b2 es p2 b1 egyenl}otlensegekb}ol kovetkezik, hogy p b . A diszkret szeparacios tetel miatt letezik egesz m : S ! Z vektor, amelyre p (X) m (X) b (X). A konstrukcio miatt az m megszortasa S-re olyan egesz m vektor, amely benne van Q1 \ Q2-ben. 8.6 KO VETKEZME NY Minden Q1 := Q(p1 ; b1) g-polimatroid rendelkezik a linking tulajdonsaggal. Biz. Legyen f; g ket olyan egesz vektor, melyekre f g es letezik Q1 -nek x f es y g eleme. Legyen p2 (X) = f(X) es b2(X) := g(X) es tekintsuk a Q2 := fx : f x gg = Q(p2 ; b2) "teglat". Most p2 (Z) = f(Z) x(Z) b1(Z) es b2(Z) = g(Z) y(Z) p1(Z), azaz p2 b1 es p1 b2 , es gy a metszet tetel miatt letezik Q1 \ Q2 -ben egesz z vektor. MOHO ALGORITMUS Legyen b teljesen szubmodularis es az egyszer}useg kedveert tegyuk fel, hogy veges ertek}u. Legyen c : S ! R linearis celfuggveny es tekintsuk (maxcx : x 2 B(b)) optimalizalasi feladatot. Az alabbi moho eljaras megad egy egeszertek}u optimumot valamint a dualisnak egy optimalis megoldasat, amely szinten egeszertek}u, amennyiben c az. Feltehet}o, hogy c komponensei nagysag szerint csokken}o sorrendben vannak elrendezve, azaz c(s1 ) c(s2 ) : : : c(sn ). Jelolje Si az els}o i elem halmazat. De nialjuk az x vektort a kovetkez}okepp. x1 := b(s1 ) es i = 2; : : :; n-re P xi := b(Si) ? b(Si?1). A de nciobol kovetkezik, hogy x(Si) = b(Si) minden i = 1; : : :; n, ahol x(Z) := z2Z x(z).
LEMMA az x vektor benne van a B(b) bazis poliederben. 31
Biz. Azt kell belatnunk, hogy minden Z halmazra x(Z) b(Z):
(1)
Jelolje m(Z) a legnagyobb i indexet, amelyre si 2 Z. m(Z) szerinti indukciot hasznalunk. Ha m(Z) = 1, akkor Z = fs1 g. Legyen most m(z) := i 2. A szubmodularitast hasznalva kapjuk, hogy b(Z) + b(Si?1 ) b(Z \ Si?1 ) + b(Z [ Si?1 ): Az indukciot Z \ Si?1 -re alkalmazva, es a Z [ Si?1 = Si egyenl}oseget meg gyelve kapjuk, hogy b(Z \ Si?1 )+b(Z [ Si?1) x(Z \ Si?1)+b(Si ), amib}ol b(Z) x(Z \ Si?1 )+b(Si ) ? b(Si?1 ) = x(Z \ Si?1 ) + x(si ) = x(Z) adodik. Az x tehat olyan egesz vektor, amely B(b)-ben van. Belatjuk, hogy x valojaban B(b)-nek optimalis eleme. Legyen y(Sn ) := c(sn ) es i = 1; 2; : : :; n ? 1-re y(Si ) := ci ? ci+1 , es S tetsz}oleges mas reszhalmazan legyen y(Z) P := 0. Konnyen latszik, hogy P az gy de nialt Py valoban megoldasa a dualis linearis programnak. Most cx = ci (b(Si ) ? b(Si?1 )) = (ci ? ci+1 )b(Si ) = y(Z)b(Z), ezert az x primal, az y pedig dual optimum.
MEGJEGYZE S Figyeljuk meg, hogy a fenti maximalizalasi problema dualisaban minden y(Z) valtozora
nem-negativitast kovetelunk, kiveve y(S)-re. Az algoritmus szerint ez pontosan akkor lesz negatv, ha a celfuggveny legkisebb, cn komponense negatv. Amennyiben az S(b) szubmodularis polieder felett akarjuk maximalizalni cx-t es cn 0, ugy a fent kapott primal es dual megoldas jo lesz. Ha viszont cn < 0, akkor a max(cx : x 2 S(b)) feladat nem is korlatos felulr}ol, hiszen S(b) tetsz}oleges x elemeb}ol kiindulva az x(n) komponenst tetsz}olegesen csokkenthetjuk es ezzel a celfuggveny erteke is tetsz}olegesen nagy lehet. A moho algoritmus kovetkezmenye, hogy a B(b) bazis polieder sohasem ures. Ha a moho algoritmust a c := (A) celfuggvenyre alkalmazzuk, ahol A S, akkor azt nyerjuk, hogy letezik olyan x0 eleme B(b)-nek, amelyre x0(A) = b(A), amib}ol kovetkezik, hogy:
8.7 KO VETKEZME NY Ha b teljesen szubmodularis, akkor b(A) = max(x(A) : x 2 B(b)), vagyis a bazis polieder egyertelm}uen meghatarozza az }ot de nialo teljesen szubmodularis fuggvenyt. 8.8 A LLITA S Polimatroid, szubmodularis polieder, kontra-polimatroid, bazis polieder mindegyike g-polimatroid.
Biz. Az els}o harom esetben az alltas vilagos. Legyen most B(b) bazis polieder. De nialjuk p-t a kovetkez}okeppen. p(X) := b(S) ? b(S ? X). Konny}u igazolni, hogy p teljesen szupermodularis, illeszkedik b-hez es Q(p; b) = B(b). Feladat Igazoljuk, hogy ha p teljesen szupermodularis, akkor az fx : x(A) p(A) minden A S-ra, x(S) = p(S)g polieder bazis polieder. Ha Q(p; b) g-polimatroid, akkor egy v vektorral valo eltoltja is az, espedig Q(p; b) + v = Q(p1; b1), ahol p1 (X) = p(X) + v(X); b1 (X) = b(X) + v(X). Q(p; b) origora valo tukorkepe is g-polimatroid, espedig Q(?b; ?p). Legyen s az S valamely eleme. Egy v vektor s menten torten}o vetuleten azt az eggyel kisebb dimenzios vektort ertjuk, amely v-b}ol az s-nek megfelel}o komponens eltorlesevel keletkezik. Egy Q polieder s-menten torten}o vetulete azt jelenti, hogy Q osszes elemet vettjuk s menten. Termeszetesen a vettes fogalmat kiterjeszthetjuk az S valamely Z reszhalmaza menten torten}o vettesre is. Legyen Q = Q(p; b) g-polimatroid, s 2 S es S 0 := S ? s. Jelolje a p illetve a b megszortasat S 0 -re rendre 0 p es b0. Ekkor (p0 ; b0) er}os part alkot, es gy Q(p0; b0) g-polimatroid.
8.9 TE TEL Er}os parral adott Q(p; b) g-polimatroid s menten valo Q0 vetulete a Q(p0; b0) g-polimatroid. Biz. Vilagos, hogy a Q0 barmely eleme benne van Q(p0; b0)-ben, azaz Q0 Q(p0; b0). 32
A fordtott iranyu tartalmazashoz belatjuk, hogy tetsz}oleges x0 2 Q(p0; b0) elem el}oall egy x 2 Q elem s-menti vetuletekent. Ennek erdekeben legyen X; Y ket s-t tartalmazo halmaz. A lltjuk, hogy () b(X) ? x0(X ? s) p(Y ) ? x0 (Y ? s). Valoban, a kereszt egyenl}otlenseget hasznalva kapjuk, hogy b(X) ? p(Y ) b(X ? Y ) ? p(Y ? X) x0 (X ? Y ) ? x0(Y ? X) = x0 (X ? s) ? x0 (Y ? s), azaz () fennall. Ebb}ol adodik, hogy m := min(b(X) ? x0 (X ? s) : s 2 X S) M := min(p(X) ? x0(X ? s). Most tetsz}oleges ertekre, amelyre m M az x := (x0; ) benne van Q-ban. Tegyuk most fel, hogy s az S-n kvul lev}o elem. Legyen adott az S reszhalmazain ertelmezett p es b fuggveny. De nialjuk az S := S + s reszhalmazain ertelmezett b fuggvenyt a kovetkez}okeppen; b (X) = b(X), ha X S es b (X) = ?p(s ? X), ha s 2 X. A de nciokbol rogton adodik a kovetkez}o:
8.10 A LLITA S b akkor es csak akkor teljesen szubmodularis, ha (p; b) er}os par. b akkor es csak akkor keresztez}o szubmodularis, ha (p; b) gyenge par. 8.11 KO VETKEZME NY Nemures Q := Q(p; b) g-polimatroid el}oall 0-bazis polieder vetuletekent, nevezetesen Q a B(b ) vetulete s menten. Ez a kapcsolat lehet}ove teszi, hogy bazis poliederekre megfogalmazott teteleket g-polimatroidokra atvigyunk.
8.12 KO VETKEZME NY Nemures Q = Q(p; b) g-polimatroid egyertelm}uen meghatarozza az }ot de nialo er}os part, espedig b(Z) = max(x(Z) : x 2 Q) es p(Z) = min(x(Z) : x 2 Q). Feladat A (p; b) er}os parral megadott Q(p; b) g-polimatroid akkor es csak akkor bazis polieder, ha p(S) = b(S).
9. POLIMATROIDOK E S ALKALMAZA SAIK. II. RESZELE S Legyen b : 2S ! R [ f1g az S alaphalmaz reszhalmazain ertelmezett fuggveny es de nialjuk a b_ (X) := min(
X b(X ) : fX g az X partcioja) i
i
fuggvenyt, amelyet a b reszeltjenek fogunk nevezni. (Ez tulajdonkeppen az un. also reszelt. Ha min helyett max szerepel, akkor fels}o reszeltr}ol beszelunk. Az also reszeltr}ol szubmodularis, a fels}o reszeltr}ol szupermodularis fuggvenyek eseten fogunk beszelni.) Tekintsuk a b-hez tartozo S(b) := fx 2 RS : x(Z) b(Z) minden Z S -re g poliedert. Konnyen latszik, hogy S(b) = S(b_ ), hiszen egyreszt b_ b, amib}ol S(b_ ) S(b). MasresztPlegyen x 2 S(b) es valamely ZP S halmazra tekintsuk Z-nak azt a fZi g partciojat, amelyre b_ (Z) = b(Zi ). P Most x(Z) = x(Zi ) b(Zi ) = b_ (Z), azaz x 2 S(b_ ), es gy S(b_ ) = S(b). Az X S reszhalmazt (b-re nezve) alulrol szeparalhatonak nevezzuk, ha X felbonthato ket olyan X1 ; X2 nemures reszhalmazra, amelyekre b(X1 ) + b(X2 ) b(X). Ellenkez}o esetben X nem-szeparalhato alulrol. Azt mondjuk, hogy b nagyreszt szubmodularis, ha barmely ket alulrol nem-szeparalhato X; Y halmazra, melyekre X \ Y 6= ;, fennall a szubmodularitasi egyenl}otlenseg. Peldaul metsz}on szubmodularis fuggveny nagyreszt szubmodularis.
9.1 TE TEL Nagyreszt szubmodularis b fuggveny b_ also reszeltje teljesen szubmodularis. 33
Biz. Valamely F halmazrendszerre hasznaljuk a b(F ) := P(b(X) : X 2 F ) jelolest. Legyen P A; B S. _ (A) = b(Ai ) es Letezik A-nak olyan f A ; : : :; A g e s B-nek olyan f B ; : : :; B g part ci o ja, melyekre b 1 k 1 l P b_ (B) = b(Bj ). Ekkor F = fA1 ; : : :; Ak ; B1; : : :; Bl g olyan, hogy b(F ) = b_ (A) + b_ (B) es () F az A \ B minden elemet ketszer fedi es (A ? B) [ (B ? A) minden elemet egyszer. Valasszunk most egy olyan F1 halmazrendszert, (amelyben egy halmaznak P ket paldanya is szerepelhet), amely kielegti ()-t, b(F1 ) minimalis, ezen belul jF1j maximalis, es ezen belul (jX j2 : X 2 F1) maximalis. Ekkor persze b(F ) b(F1). Konnyen latszik jF1j maximalitasabol, hogy F1 tagjai nem-szeparalhatok. Ekkor F1 barmely ket tagjara teljesul a szubmodularitasi egyenl}otlenseg. Most F1 laminaris, mert ha lenne ket metsz}o tagja, akkor helyettes Ptve ezeket a metszet Pukkel es az uniojukkal, a keletkez}o F2 kielegti ()-t, b(F1) b(F2), jF1j = jF2j , es (jX j2 : X 2 F1 ) < (jX j2 : X 2 F2). Mivel F1 laminaris, felbonthato ket diszjunkt reszre, P1 es P2 -re, ahol P1 az A \ B partcioja es P2 az A [ B partcioja. b_ de nciojabol b_ (A \ B) b(P1 ) es b_ (A [ B) b(P2 ). Ezert b_ (A) + b_ (B) = b(F ) b(F1) = b(P1) + b(P2 ) b_ (A \ B) + b_ (A [ B), tehat b_ valoban teljesen szubmodularis. Termeszetesen az el}obbi tetel ertelemszer}uen megfogalmazhato szupermodularis fuggvenykre is. Szuksegunk lesz ezen valtozatnak az alabbi kovetkezmenyere. Egy nem-negatv halmaz-fuggvenyr}ol azt mondtuk, hogy ferden szupermodularis, ha barmely ket X; Y halmazra, melyekre p(X); p(Y ) > 0 fennall a p(X) + p(Y ) p(X [ Y ) + p(X \ Y ) es a p(X) + p(Y ) p(X ? Y ) + p(Y ? X) egyenl}otlensegek kozul legalabb az egyik.
A LLITA S Ha p ferden szupermodularis fuggveny, akkor nagyreszt szupermodularis. Biz. Legyenek X; Y metsz}o halmazok, melyek nem szeparalhatok felulr}ol. Ekkor p 0 miatt p(X) > 0; p(Y ) > 0. Most p(X) > p(X ? Y ) + p(X \ Y ) p(X ? Y ) es p(Y ) > p(Y ? X) + p(X \ Y ) p(Y ? X). Tehat p(X) + p(Y ) > p(X ? Y ) + p(Y ? X) es gy p(X) + p(Y ) p(X [ Y ) + p(X \ Y ): 9.2 KO VETKEZME NY Ha p ferden szupermodularis, akkor a p^ fels}o reszelt monoton nov}o, teljesen szupermodularis fuggveny, es gy C(p) kontra-polimatroid. Vizsgaljuk most meg, hogy mit lehet egy olyan b fuggvennyel kezdeni, amely csupan keresztez}o szubmodularis. Tekintsuk a Q := B(b) := fx 2 RS : x(Z) b(Z) minden Z S-re, es x(S) = b(S)g poliedert.
9.3 TE TEL Amennyiben B(b) nemures, ugy letezik olyan b# teljesen szubmodularis fuggveny, amelyre Q = B(b# ).
Biz. Az el}oz}o reszelesi konstrukciot fogjuk ketszer alkalmazni. Legyen k := b(S) es de nialjuk p-t a p(X) := k ? b(S ? X) keplettel. Ekkor p keresztez}o szupermodularis es nyilvanvaloan Q = fx : x(S) = k; x(Z) p(Z); Z S g. Legyen p^ a p fuggveny fels}o reszeltje. Az el}oz}o tetel szupermodularis fuggvenyekre kimondhato analogonjat alkalmazva a p^ jX [ Y -ra, azt kapjuk, hogy p^ szupermodularis valahanyszor X es Y nem ko-diszjunkt (azaz X [ Y = 6 S). A lltjuk tovabba, hogy p^ (S) = p(S) = k. Valoban p^ (S) p(S) a fels}o reszelt de nciojabol adodik, de a felteves szerint Q = Q0 nem-ures, gy nem lehet p^ (S) > k: Legyen most b0(X) := k ? p^ (S ? X): Ekkor b0 metsz}o szubmodularis es B(b0 ) = Q0 = Q. Legyen # b := b0_ a b0 also reszeltje. A 9.1 tetel masodszori alkalmazasaval kapjuk, hogy b# teljesen szubmodularis es B(b# ) = B(b0 ) = Q. Mar lattuk korabban, hogy bazis polieder egyertelm}uen meghatarozza az }ot de nialo teljesen szubmodularis fuggvenyt (8.7 kovetkezmeny). Ebb}ol kapjuk, hogy ha b keresztez}o szubmodularis es B(b) nemures, akkor a 9.3 tetelben szerepl}o b# fuggveny egyertelm}uen meghatarozott. A b# -t a b fuggveny teljes (also) reszeltjenek nevezzuk. (Analog modon de nialhato egy keresztez}o szupermodularis fuggveny teljes fels}o reszeltje.) Ezzel kapcsolatban ket kerdes is felmerul. El}oszor is, hogy mi B(b) nemuressegenek feltetele, masodszor, hogy a teljes reszeltet hogyan lehet b segtsegevel szepen kifejezni. 34
Az utobbi megvalaszolasaval kezdjuk. Legyen A az S valodi, nemures reszhalmaza. Egy F reszhalmaz rendszerr}ol azt mondjuk, hogy A kompozcioja, ha valamely t egeszre S ? A minden eleme t darab F beli halmazban van es A minden eleme t + 1 darab F -beli halmazban van. A t szamot a kompozcio alap-fedesi szamanak hvjuk. Az S alaphalmaz kompozciojan olyan halmaz-rendszert ertunk, amely S minden elemet ugyanannyiszor fedi. Specialisan az A partcioja kompozcio, melynek alap-fedesi szama 0. Vagy altalanosabban, konnyen belathato, hogy az A-nak akkor is egy kompozciojat kapjuk, ha valamely fA1 ; : : :; Ak g partciojaban minden Ai halmazt kicserelunk paronkent ko-diszjunkt halmazoknak egy olyan rendszerere, melyek metszete eppen Ai . Az gy el}oallo kompozciot nevezzuk az A dupla-partciojanak. Konnyen kimutathato, hogy a 9.3 tetel bizonytasaban a b# (A)-ra adodo erteket explicit modon megadhatjuk az alabbi formulaval: b# (A) = min(b(F ) ? t(b(S)); ahol a minimum az A halmaz F dupla-partcioira megy es t az F alap-fedesi szama. Emlekezzunk vissza, hogy egy S reszhalmazaibol allo keresztezes mentes halmazrendszert lehet abrazolni egy F iranytott fa, valamint egy ' : S ! V (F) lekepezes segtsegevel. Az A S egy dupla partciojat fa-kompozcionak hvunk, ha keresztezes mentes, az }ot abrazolo iranytott fa mindegyik ele valamely '(S ? A)-beli pontbol vezet valamely '(A)-ban lev}o pontba, es a fa mindegyik pontjanak ' szerinti o}skepe nemures. (Masszoval A egy fa-kompozciojat az A-nak egy fA1 ; : : :; Ak g (k 1) partciojaval, az S ? Anak egy fB1 ; : : :; Bl g (l 1) partciojaval, valamint az fa1 ; : : :; ak ; b1; : : :; bl g ponthalmazon adott olyan iranytott faval lehet megadni, melynek minden ele egy bi pontbol vezet egy aj pontba.) Megallapodunk abban, hogy az S alaphalmaz fa-kompozciojan az S egy partciojat vagy ko-partciojat ertjuk.
9.4 TE TEL Legyen b olyan keresztez}o szubmodularis fuggveny, amelyre b(S) = 0 es B(b) nemures. Ekkor b# (Z) = min(b(F ) : F a Z fa-kompozcioja). Biz. Konnyen ellen}orizhet}o, hogy a Z tetsz}oleges F kompozciojara b#(Z) b(F ). Valoban, tudjuk, hogy B(b)-nek olyan x eleme, amelyre x(Z) = b# (Z): Legyen t az F alap-fedesi szama. Ekkor b(F ) P(x(X) : van X 2 F ) = tx(S) + x(Z) = x(Z) = b# (Z): Korabban lattuk, hogy b# (Z) = min(b(F ) : F a Z dupla partcioja), azaz Z-nek van olyan kompozcioja, amelyre b#(Z) = b(F ). A kikeresztezesi technika felhasznalasaval elerhetjuk, hogy F keresztezes-mentes legyen. Feltehet}o tovabba, hogy jFj minimalis. Miutan B(b) nemures, az alaphalmaz minden R kompozciojara b(R) 0. Ezert F nem foglalhatja magaban S-nek semmilyen kompozciojat, specialisan S-nek partciojat vagy resz-partciojat sem. (Ugyanis ezt ki lehetne hagyni F -b}ol.) Tekintsuk most az F -nek az (F; ') fa-reprezentaciojat. Az F fa pontjait szintekbe lehet rendezni ugy, hogy a fa minden ele egy szintr}ol az eggyel magasabb szint fele vezessen. Nevezzuk a fa egy v pontjat uresnek, ha '?1 (v) ures. Mivel F a Z-nek kompozicioja, a Z elemeinek (' szerinti) kepei egy szinten helyezkednek el, mg a tobbi elem kepe mind az eggyel alacsonyabb szinten helyezkedik el. Most a fanak valojaban csak ez a ket szintje lehet, mert ha volna meg mas szintje is, akkor F tartalmazna S-nek egy partciojat vagy ko-partciojat. Hasonlo meggondolas miatt latszik, hogy F-nek nincs ures pontja, ami epp azt jelenti, hogy F a Z-nek fa-kompozcioja. A bazis poliederek es g-polimatroidok kozotti, mar korabban emltett megfeleltetes az alabbi eredmenyt adja:
9.5 KO VETKEZME NY A (p; b) gyenge par altal de nialt polieder g-polimatroid. 9.6 KO VETKEZME NY Q g-polimatroid metszete egy fx : f x gg teglaval g-polimatroid. Q metszete egy fx : x(S) g savval g-polimatroid. Raterunk g-polimatroidok nemuressegenek a vizsgalatara.
9.7 TE TEL A Q(p; b) gyenge parral adott g-polimatroid akkor es csak akkor nemures, ha az S alaphalmaz minden fZ1; : : :; Zt g resz-partciora X (A1) b([i Zi ) p(Zi ) i
35
es
X b(Z ) p([ Z ): i
i
i i
(A2)
Biz. A feltetel szuksegessege nyilvanvalo. Az elegend}oseg bizonytasahoz hasznaljuk a diszkret szeparacios tetel metsz}o szub- illetve metsz}o szupermodularis fuggvenyekre vonatkozo alakjat (8.3B tetel). EPszerint, ha letezik egy T reszhalmaznak egy fXi g es egy fYj g partcioja, melyekre () i b(Xi ) < PQ(p;p(Yb) ju).res,Vaakkor lasszuk ezt ugy, hogy T minimalis legyen. Ekkor a ket resz-partcio egyutt egy F laminaris j rendszert alkot, mert ha nem, akkor az egyik Xi metszi valamelyik Yj -t es akkor a kereszt-egyenl}otlenseg alapjan Xi -t Xj ? Yj -vel, Yj -t pedig Yj ? Xi -vel helyettestve a T ? (Xi \ Yj ) halmaznak kapnank ket ()-t teljest}o resz-partciojat, ellentetben T minimalis valasztasaval. Tekintsuk most az F maximalis tagjait. Egy ilyen vagy Xi tpusu es ekkor felpartcionalodik Yj tpusu halmazokra, vagy Yj tpusu es akkor felpartcionalodik Xi tpusu halmazokra. Az els}o esetben a tetelbeli els}o feltetelt hasznalva, a masodik esetben pedig a masodikat, azt kapjuk, hogy () megsem teljesul. 9.8 TE TEL Legyen b keresztez}o szubmodularis, amelyre b(S) = 0. B(b) akkor es csak akkor nemures, ha S minden Z0 ; : : :; Zt partciojara
es
X b(Z ) 0 i
X b(S ? Z ) 0: i
(B1) (B2)
Biz. Legyen s az S tetsz}oleges pontja es de nialjuk az S 0 := S ? s reszhalmazain a p0 es b0 fuggvenyeket a kovetkez}okeppen. b0 (X) = b(X); p0 (X) = ?b(S ? X). Tudjuk, hogy (p0; b0) gyenge par es hogy Q(p0 ; b0)
g-polimatroid. Azt is lattuk korabban, hogy amennyiben Q(p0 ; b0) nemures, akkor vetulete B(b)-nek, gy B(b) sem ures. Ha Q(p0; b0) ures, akkor a 9.1 tetel szerint letezik egy Z1 ; Z2 ; : : :; Zt resz-partcio, amely megserti (A1)-t vagy (A2)-t. Legyen Z0 := S ?[(Zi ). A ket esetnek megfelel}oen a P = fZ0 ; : : :; Ztg partcio megserti (B1)-t vagy (B2)-t.
9.9 TE TEL (S. Fujishige) Legyen b keresztez}o szubmodularis, amelyre b(S) = k. B(b) akkor es csak akkor
nemures, ha S minden Z0 ; : : :; Zt (t + 1 reszes) partciojara
X b(Z ) k
(C1)
X b(S ? Z ) kt:
(C2)
i
es
i
Biz. Jeloljunk ki egy tetsz}oleges s pontjat S-nek. Jelolje b0 azt a fuggvenyt, amely ugy keletkezik b-b}ol, hogy minden s-t tartalmazo X halmazon b(X) erteket k-val csokkentjuk (azaz ilyen X-re b0(X) := b(X) ? b(S)). Alkalmazzuk a 9.9 tetelt a b0 fuggvenyre. IRA NYITA SOK Adott G = (V; E) iranytatlan graf. Egy h halmaz-fuggvenyt keresztez}o G-szupermodularisnak mondunk, ha h(X) + h(Y ) h(X \ Y ) + h(X [ Y ) + dG (X; Y ) fennall minden keresztez}o X; Y halmazra. Feltesszuk, hogy h(;) = h(V ) = 0.
9.10 TE TEL Legyen h nemnegatv (!) keresztez}o G-szupermodularis fuggveny. A G grafnak akkor es csak akkor van olyan iranytasa, amelyben %(X) h(X) minden X V reszhalmazra, ha V minden 36
FP:= fV0; : : :; Vt g (t + 1 reszes) partciojara a reszek kozott vezet}o elek i(F ) szama legalabb max(Pj h(Vj ); j (h(V ? Vj )). Biz. Kozismert lemma, hogy egy adott m : V ! Z vektorhoz akkor es csak akkor letezik G-nek olyan iranytasa, amelyben minden v pont befoka m(v), ha m(V ) = jE j es m(X) i(X) fennall minden XP V -re. De nialjuk p-t: p(X) := h(X) + P i(X). Ekkor p keresztez} P aris. PAz i(F ) P j h(Vj ) P o szupermodul egyenl}otlenseg azzal ekvivalens, hogy p(Vi ) p(V )Phiszen j p(Vj ) = h(Vj ) + j i(Vj ) = j h(Vj ) + jPE j ? i(F ) jE j = p(V ): Hasonl oan, az i(FP) j (h(V ?PVj )) egyenl}otlens eg azzal ekvivalens, hogy P P p(V ? V ) tp(V ), hiszen p(V ? V ) = h(V ? V )+ i(V ? V ) = j j j j j j j j j h(V ? Vj ) = tjE j? i(F ) tp(V ). Alkalmazva Fujishige tetelet a b := ?p fuggvenyre, azt kapjuk, hogy letezik egy m vektor, amelyre m(V ) = jE j es m(X) p(X) = h(X) + i(X) minden X V -re. Kihasznalva, hogy h 0, kapjuk, hogy m(X) i(X) es gy a bizonytas elejen emltett lemma P alapjan letezik G-nek olyan iranytasa, amelyre %(v) = m(v) teljesul minden pontra. De ekkor %(X) = (%(v) : v 2 X) ? i(X) = m(X) ? i(X) h(X).
Specialis esetkent a tetelt hasznalhatjuk olyan k-elosszefugg}o iranytasok letezesenek jellemzesere, amelyek meg a pontokban a befokra kirott also es fels}o korlat felteteleket is teljestenek.
Feladat Legyen G = (V; E) iranytatlan graf, s egy kijelolt pontja, es k l ket nemnegatv egesz. G-nek akkor es csak akkor letezik olyan iranytasa, amelyben s-b}ol minden pontba vezet k elidegen ut es s-be minden pontbol vezet l elidegen ut, ha V barmely t (t 2) reszes partciojara a reszek kozott vezet}o elek szama legalabb k(t ? 1) + l. Feladat Igazoljuk, hogy ha a 9.10 tetelben h raadasul szimmetrikus, akkor a tetelbeli feltetel azzal ekvivalens, hogy dG (X) 2h(X) minden X V -re. A fenti bizonytasbol az is kovetkezik, hogy a keresett iranytasokhoz tartozo m befok vektorok bazis poliedert fesztenek. Mivel g-polimatroidok rendelkeznek a linking tulajdonsaggal, ebb}ol kovetkezik, hogy ha egy G grafnak letezik olyan k-elosszefugg}o iranytasa amelyben minden pont v befoka legalabb f(v) es letezik olyan k-elof. iranytasa, amelyben minden v pont befoka legfeljebb g(v), akkor letezik olyan k-elof. iranytasa is, amelyre f(v) %(v) g(v) minden v pontra. Megjegyzend}o, hogy mar k = 1-re sem ervenyes a megfelel}o alltas, ha vegyes graf iranytasarol van szo. A tetel bizonytasaban kihasznaltuk, hogy h nemnegatv. Ez sajnalatos, mert egy vegyes graf k-eloszefugg}ove torten}o iranytasa csak olyan h segtsegevel fogalmazhato meg, amely ugyan keresztez}o G-szupermodularis, de lehet negatv is. Az alabbi pelda mutatja, hogy ilyenkor az el}obbi tetelben megfogalmazott feltetel nem is elegend}o.
A bra A graf ponthalmaza f1; 2; 3; 4g. Ket iranytatlan el van: 12 es 34. Kilenc iranytott el van: 14,14,41, 13,13,31,23,23,32. A Fujishige tetel es a b# -re adott fa-kompozcios formula segtsegevel most mar megadhatjuk a keresztez}o szubmodularis fuggvennyel megadott szubmodularis aram polieder nemuressegenek a feltetelet.
9.11 TE TEL Legyen D = (V; A) iranytott graf es legyen b keresztez}o szubmodularis fuggveny a V
reszhalmazain, amelyre, b(V ) = 0. A Q(f; g; b) szubmodularis aram polieder akkor es csak akkor nemures 37
(azaz letezik megengedett szubmodularis aram), ha %f (Z) ? g (Z) b(F ) fennall minden Z V nemures reszhalmazra es Z minden F fa-kompozciojara.
Biz. A feltetel szuksegessege konnyen ellen}orizhet}o, ezert csak az elegend}oseg bizonytasaval foglalkozunk. Mivel a V alaphalmaz minden R fa-kompozciojara (azaz minden partciojara es ko-partciojara) b(R) %f (V ) ? g (V ) = 0, Fujishige teteleb}ol kovetkezik, hogy B(b) nemures. Ezert b-nek letezik a b# also reszeltje
es B(b) = B(b# ). De nialjuk az x : A ! R vektorra a x : V ! R vektort: x (v) := %x (v) ? x (v) (v 2 V ). Konnyen latszik, hogy x pontosan akkor szubmodularis aram b-re nezve, ha x 2 B(b). Miutan B(b) = B(b# ), ez azt jelenti, hogy Q(f; g; b) = Q(f; g; b# ). Alkalmazhatjuk Q(f; g; b#)-re a 8.2 megengedettsegi tetelt, amely szerint Q(f; g; b#) akkor es csak akkor nemures, ha %f (Z) ? g (A) b# (Z) fennall minden Z V -re, ami a b# (Z)-re megadott korabbi formula alapjan epp a tetel feltetelevel ekvivalens. Ennek segtsegevel valaszt tudunk adni az altalanos iranytasi kerdesre is.
9.12 TE TEL Legyen G = (V; E) iranytatlan graf es h keresztez}o G-szupermodularis fuggveny, amelyre h(;) = h(V ) = 0.PG-nek akkor es csak akkor letezik olyan iranytasa, amelyre %(Z) h(Z) fennall minden Z-re, ha h(F ) j 2E ej (F ) fennall V minden Z reszhalmazanak minden F fa-kompozciojara, ahol ej (F ) annak a ket szamnak a maximumat jelzi, ahany F -beli halmazba a j el egyik illetve masik iranytasanal belep.
Biz. Tekintsuk a G grafnak egy tetsz}oleges iranytasat, amelyet D = (V; A) fogunk jelolni. Ez csak arra
szolgal, hogy segsegevel megadjuk a G keresett iranytasat. A megadas ugy tortenik, hogy meghatarozzuk, a D bizonyos eleit, amelyek megfordtasaval a vegs}o iranytast megkapjuk. A megfordtando eleket egy x : A ! f0; 1g vektor rja le, ahol x(a) = 1 jelenti azt, hogy az a elt megfordtjuk. Ezen konvencioval elve egy x : A ! f0; 1g vektor pontosan abban az esetben hataroz meg egy kvant iranytast, amikor %A (Z) ? %x (Z) + x (Z) h(Z) minden Z V halmazra fennall, ami azzal ekvivalens, hogy %x (Z) ? x (Z) b(Z) := %A (Z) ? h(Z):
(D)
Miutan az gy de nialt b halmazfuggveny keresztez}o szubmodularis, a f%x (Z) ? x (Z) b(Z); 0 x 1g rendszer egy Q szubmodularis aram poliedert hataroz meg. Konnyen latszik, hogy a 9.11 tetelben szerepl}o feltetel ekvivalens a 9.12 tetel feltetelevel. Igy Q nemures, de akkor letezik egesz pontja is (a 8.1 Tetel alapjan), ami viszont eppen a keresett iranytast adja meg.
Feladat Legyen G = (V; E) iranytatlan graf es h metsz}o G-szupermodularis fuggveny, amelyre h(;) = h(V ) = 0. G-nek akkor es csak akkor letezik olyan iranytasa, amelyre %(Z) h(Z) fenn P all minden Zre, ha V minden fV1; : : :; Vtg partciojara a reszek kozott men}o elek szama legalabb ti=1 h+ (Vi ) ahol h+ := max(h; 0). Feladat Adjuk meg annak (partcio tpusu) szukseges es elegend}o feltetelet, hogy egy vegyes graf iranytatlan eleinek letezzek olyan iranytasa, amelyre a keletkez}o iranytott graf egy el}ore adott s pontjabol minden mas pontba vezet k elidegen iranytott ut. IRA NYITOTT E LO SSZEFU GGO} SE G NO VELE S Legyen G = (V; E) iranytott graf, k pozitv egesz es mki : V ! Z+ fokszam el}oras. Korabban lattuk (5.9 Tetel), hogy akkor es csak akkor letezik olyan H = (V; A) digraf, amelyre G + H P k-elosszefugg}o es H (v) = mki , ha mki (X) k ? %G (X) minden X V -re es mki (V ) , ahol := max( i (k ? %G (Xi )) : fXi g reszpartcio). Nevezzuk az ilyen mki vektort novelesi kifok vektornak. Belatjuk, hogy ezek kontrapolimatroidot fesztenek. Ennek erdekeben de nialjuk a p fuggvenyt a kovetkez}okeppen. Legyen p(X) := pki(X) := (k ? G (X))+ ha X V es pki(V ) := . 38
A LLITA S Minden olyan metsz}o X; Y halmazra, melyeken pki(X) > 0; pki(Y ) > 0, teljesul a szupermodularitasi egyenl}otlenseg.
Biz. Mivel G szubmodularis, eleg azzal az esettel foglalkozni, amikor X [ Y = V; X \ Y 6= ;. Ekkor + (k ? %G (Y )) = p(V ) + 0 p(X [ Y ) + p(X \ Y ). p(X) + p(Y ) = (k ? %G (X)) Kovetkezik, hogy pki ferden szupermodularis. Lattuk korabban, hogy ilyen pki fuggvenyre C(pki) kontrapolimatroidot de nial. Tekintsuk most a novelesi feladatnak a minimal-koltseges valtozatat, amikor adott ket nemnegatv koltsegfuggveny a ponthalmazon, cki es cbe , es egy uj uv el koltsege legyen cki(v)+cbe (u). A cel minimalis koltseg}u elhalmaz hozzadasaval G-t k-elosszefugg}ove tenni. Ehhez csak az kell, hogy a C(pki) (es az analog modon de nialt C(pbe ) kontra-polimatroidnak egy-egy minimalis koltseg}u xki ill. xbe elemet megkeressuk, melyekre xki(S) = xbe (S), majd alkalmazzuk a Mader fele iranytott leemel}os tetelt. A moho algoritmus segtsegevel ez elvileg lehetseges volna, legalabbis akkor, ha a kontra-polimatroid teljesen szupermodularis, monoton nov}o fuggvennyel volna megadva. Sajnos most nem ez a helyzet, de nincs minden veszve. Tekintsuk a moho algoritmust egy bazis poliederen. Az algoritmust a kovetkez}okeppen lehet interpretalni. A celfuggveny altal meghatarozott sorrendben vegigmegyunk az elemeken es egymas utan megallaptjuk az x(si ) ertekeket. Az aktualis xi = x(si ) erteket a lehet}o legnagyobbra valasztjuk ugy, hogy letezzek olyan (x1; : : :; xi; y1; : : :; yn) vektor B(b)-ben. Itt x1 ; x2; : : :; xi?1 a mar kiszamtott komponenseket jeloli. Ennek az ertelmezesnek az az el}onye, hogy fuggetlen attol, hogy a bazis polieder milyen formaban van megadva es gy remenyt nyujt arra, hogy az aktualis xi-t esetleg akkor is ki tudjuk szamolni, ha az egyertelm}u de nialo teljesen szubmodularis fuggveny nem all rendelkezesre. Tudjuk, hogy kontra-polimatroid (is) el}oall bazis polieder vetuletekent, ezert a moho algoritmust erre is at lehet fogalmazni. Most minimalizalni akarjuk a cx celfuggvenyt a C kontra-polimatroid felett, ezert az el}obbi algoritmusgy hangzik. Rendezzuk c szerint csokken}o sorrendbe az S elemeit. Az aktualis xi = x(si ) erteket a lehet}o legkisebbre valasztjuk ugy, hogy letezzek olyan (x1 ; : : :; xi; y1 ; : : :; yn) vektor C-ben. (Ez a moho algoritmus a kozismert Kruskal fele algoritmus "ovatos" valtozatanak felel meg, ahol egy osszefugg}o graf minimalis koltseg}u feszt}o fajanak meghatarozasa ugy tortenik, hogy minden lepesben a legdragabb elt hagyjuk ki a grafbol arra ugyelve, hogy osszefugg}o maradjon.) Hogyan tudjuk meghatarozni az aktualis si -re a maximalis x(si ) erteket? Egy egyszer}u meg gyeles segt. Jelolje k a p(X) maximalis erteket. Konny}u igazolni, hogy ha (x1 ; : : :; xi; y1; : : :; yn) benne van C-ben, akkor (x1; : : :; xi; k; k; : : :; k) is benne van. Ennek megfelel}oen a moho algoritmus ugy modosul, hogy az aktualis xi -t minimalisra valasztjuk arra valo tekintettel, hogy (x1; : : :; xi; k; k; : : :; k) benne van C-ben. Az gy kapott algoritmus pedig pontosan az lesz, amivel korabban mar megismerkedtunk a novelesi problema megoldasa soran: ott egy extra pontbol minden regi pontba bevezettunk k parhuzamos elt, majd egymas utan elhagytuk o}ket, arra vigyazva csupan, hogy minden X V halmaz befoka legalabb k maradjon. A fenti meggondolas alapjan a minimalis koltseg}u novelest akkor kapjuk meg, ha az eleket nem akarmilyen sorrendben probaljuk meg kihagyni, hanem mindig azt, amelyiknek vegpontjanak a koltsege a lehet}o legnagyobb.
IRA NYITATLAN E LO SSZEFU GGO} SE G NO VELE S A fenti a megfontolas atvihet}o az iranytatlan elosszefugg}oseg novelesi problemara is. Ez a kovetkez}on mulik. Emlekezzunk vissza, hogy ott minden pontparra adott volt egy r(u; v) el}oras es ugy kellett minimalis szamu elt a megadott G = (V; E) osszefugg}o iranytatlan grafhoz adni, hogy a megnovelt grafban minden (u; v) pontpar lokalis elosszefugg}osege legalabb r(u; v) legyen. A megoldashoz bevezettuk az R(X) := max(r(u; v) : jfu; vg\ X j = 1 fuggvenyt es bebizonytottuk, hogy egy adott m egesz vektorhoz, amelyre m(V ) paros, akkor es csak akkor letezik olyan H graf, amelyre (u; v; G+H) r(u; v) minden fu; vg pontparra, ha m(X) p(X) fennall X V -re, ahol p(X) := (R(X) ? dG (X))+ (X V ). Egy ilyen m vektort nevezzunk a noveles fokszam vektor Panak. (Ebb}ol vezettuk le, hogy G-nek akkor es csak akkor letezik ellel torten}o kvant novelese, ha 2 i p(Xi ) fennall minden resz-partciora.) Legyen p(V ) := 2 . Lattuk korabban, hogy a p fuggveny ferden szupermodularis, ezert az fm : m(X) p(X) minden X V -re, m(V ) = 2 g polieder bazis polieder, amelynek az egesz elemei a el}u noveles fokszam vektorai. Ennek alapjan, ha c : V ! R+ koltsegfuggveny adott, akkor ugyanugy mint az iranytott esetben, a moho 39
algoritmus segtsegevel meg tudunk hatarozni egy minimalis koltseg}u novelest. Nevezetesen, egy uj pontbol minden pontba vezetunk k parhuzamos elt, ahol k az r(u; v) igenyek maximuma, majd sorra kihagyunk eleket csak arra vigyazva, hogy a meglev}o graf kielegtse az eredeti pontok lokalis elosszefugg}osegere vonatkozo el}orasokat. A minimal koltseges esetben a kihagyasokat ugy vegezzuk, hogy mindig azt az elt probaljuk elhagyni, amelyik vegpontjanak a legnagyobb a koltsege. Ezt addig csinaljuk, amg 2 uj elunk nem marad, majd alkalmazzuk Mader iranytatlan leemel}os tetelet.
FENYO} PAKOLA SOK Legyen G = (V; E) iranytott graf es m : V ! Z+ egeszertek}u vektor, amelyre m(V ) = k. Edmonds feny}o-teteleb}ol rogton kovetkezik, hogy akkor es csak akkor letezik G-ben k elidegen feszt}o feny}o ugy, hogy mindegyik v pont pontosan m(v) feny}onek a gyokere, ha %(X) k ? m(X) fennall minden X V nemures halmazra. (:Egy uj s pontbol vezessunk minden v pontba m(v) iranytott elt. A kib}ovtett grafban %0 (X) k teljesul, gy letezik k elidegen feszt}o s gyoker}u feszt}o feny}o. Miutan s-b}ol pontosan k el vezet ki, gy a k feny}ob}ol az s pontot kihagyva az eredeti grafnak kapjuk feszt}o feny}oit, amelyek a konstrukcio miatt a kovetelmenyt kielegtik.) Nevezzunk egy ilyen m vektort gyokervektornak. Legyen p(X) := k ? %(X) ha X nemures es p(;) = 0. p metsz}o szupermodularis fuggveny,gy C(p) := fx 0 : x(Z) p(X)g kontrapolimatroidot alkot, amelynek egyertelm}uen meghatarozott teljesen szupermodularis de nialo fuggvenye a p^ fels}o reszelt. A gyokervektorok tehat eppen a C(p) egesz pontjai. Korabban (1. resz 1.2 tetel) megvalaszoltuk azt a kerdest, hogy egy digrafban mikor letezik k elidegen feszt}o feny}o. Az ottani bizonytasban felvettunk egy uj pontot, ebb}ol minden mas pontba k parhuzamos elt huztunk, majd az uj eleket egymas utan elhagytuk, csak arra ugyelve, hogy a maradekban teljesuljon az Edmonds tetel feltetele. Ezt addig csinaltuk, amg az uj pontbol pontosan k el indult ki, es erre alkalmaztuk az Edmonds tetelt. Az elek kihagyasanal tehat ervenyesult egyfajta moho jelleg. A jelen feleptes vilagossa teszi, hogy ennek mi van a hattereben. Az a kerdes, hogy letezik-e k elidegen feszt}o feny}o azzal ekvivalens, hogy letezik-e olyan m gyokervektor, amelyre m(V ) = k. Magyaran kell keresnunk a C(p) kontrapolimatroidnak egy olyan x egesz pontjat, amelyre 1x legfeljebb k. Ezt viszont tudjuk, hogy mindig lehet a moho algoritmus segtsegevel.
10. E LIDEGEN UTAK A. Ho man megengedett aramok letezeser}ol szolo tetelenek egy onmagaban is erdekes, de az alabbiakban felhasznalasra kerul}o alkalmazasaval kezdjuk. 10.1 TE TEL Tegyuk fel, hogy a M = (V; E [ A) vegyes graf egy H~ = (V; A) iranytott es egy G = (V; E) iranytatlan grafbol all. M iranytatlan eleit akkor es csak akkor lehetseges ugy megiranytani, hogy a keletkez}o digraf Euler fele () (azaz minden pont be-foka egyenl}o a ki-fokaval), ha minden v pontra dG (v) + %H~ (v) + H~ (v) paros es dG (X) %H~ (X) ? H~ (X) minden X V halmazra.
(2)
Biz. A feltetel szuksegessege nyilvanvalo, ezert csak az elegend}oseggel foglalkozunk. Minden iranytatlan elt helyettestsunk ket ellentetesen megiranytott ellel, melyeknek also kapacitasa legyen 0, fels}o kapacitasa legyen 1. Az eredetileg is iranytott elek also es fels}o kapacitasa legyen 1. Alkalmazzuk Ho man tetelet megengedett aramok letezeser}ol. A (2) feltetel eppen a Ho man fele szukseges eselegend}o feltetel fennallasat jelenti. Igy letezik egeszertek}u megengedett aram, amely a kapacitasok specialis valasztasa miatt most 0 ? 1 ertek}u. Legyen J azon eredetileg iranytatlan elek halmaza, melyeknek megfeleltetett mindket (ellentetes iranyu) elen az aram vagy 0 vagy 1. A () felteves szerint minden pont paros sok J-beli ellel szomszedos, 40
gy J elidegen korok uniojara bomlik. Mindegyik ilyen kort iranytsuk korbe (mindegy melyik iranyban) Az E ? J elemeit iranytsuk aszerint, hogy a megfeleltett ket el melyiken 1 az aram. Az gy kapott iranytas Euler fele lesz. Egy alternatv lehet}oseg a fenti tetel bizonytasara a kombinatorikus algoritmusok jegyzetben szerepl}o 1.1 tetelre hivatkozni, amely specialis esetben arrol szol, hogy egy iranytatlan G = (V; E) grafnak mikor letezik olyan iranytasa, ahol minden v pont befoka egy el}ore megadott m(v) nemnegatv egesz. Akkor es csak akkor, ha m(V ) = jE j es m(X) i(X) minden X V -re. (2) Marmost az m(v) := (dG(v) + H~ (v) ? %H~ (v))=2 valasztas mellett (amely a felteves miatt egesz) (1) es (2) ekvivalens. Az elidegen utak problemaja a kovetkez}o. Adott egy G graf vagy digraf es G pontjaibol alkotott k darab pontpar: (s1 ; t1); (s2 ; t2); : : :; (sk ; tk ). Keressunk kparonkent elidegen utat, melyek a megfelel}o (si ; ti) pontokat kotik ossze. Hasznos ezen osszekotend}o pontparokat egy un. igenyellel megjelolni. Az igenyelek altal alkotott H = (U; F) grafot igeny grafnak nevezzuk, mg az eredeti graf a teljest}o graf . Ha G es H iranytott, akkor a ti si (iranytott) igeny el azt jelzi, hogy G-ben si -b}ol ti -be szeretnenk utat. Ekkor az elidegen utak problemaja avval ekvivalens, hogy G + H-ben keressunk jF j elidegen kort, melyek mindegyike pontosan egy igenyelt tartalmaz. Az ilyen koroket nevezzuk jo kornek. Az iranytatlan elidegen utak problemaja NP-teljes mar akkor is, ha G + H Euler fele, vagy ha G + H skbeli. Ugyanakkor polinom id}oben megoldhato, ha G + H Euler E S skbeli: a megoldas Seymour egy tetelen es a parostas elmeleten alapul. Akkor is megoldhato, ha k = 2 (ez szinten nem trivialis). Iranytott grafokra mar a k = 2 eset is NP-teljes. Mind az iranytott mind az iranytatlan esetben adodik egy termeszetes szukseges feltetel.
VA GA S KRITE RIUM
dG (X) dH (X) minden X V -re.
(3)
IRA NYITOTT VA GA S KRITE RIUM %G~ (X) H~ (X) minden X V -re.
(4)
Ezen feltetelek altalaban nem elegend}oek, de vannak erdekes specialis esetek, amikor igen. Peldaul Menger tetelenek iranytott illetve iranytatlan el-valtozata szerint ez a helyzet, amikor s1 = : : : = sk es t1 = : : : = tk : A kovetkez}o erdekes igenygraf, amikor H ket csomag parhuzamos elb}ol all azaz, H-nak ki ele van ti b}ol si -be (i = 1; 2). Meg ez a feladat is NP-teljes, de B. Rothschild es A. Whinston [1966], kisse kiterjesztve T.C. Hu egy korabbi eredmenyet a kovetkez}ot bizonytotta be.
10.2 TE TEL Iranytatlan esetben ha a H igenygraf ket csomag parhuzamos elb}ol all es G + H Euler-fele, akkor a vagas kriterium az elidegen utak letezesenek szukseges es elegend}o feltetele. A tetel kovetkez}o iranytott ellenparjanak a bizonytasa egeszen egyszer}u.
10.3 TE TEL Iranytott esetben, ha a H~ igenygraf ket csomag parhuzamos (egy iranyba men}o) elb}ol all
es G~ + H~ Euler-fele, akkor az iranytott vagas kriterium az elidegen utak letezesenek szukseges es elegend}o feltetele.
Biz. Az iranytott vagas feltetelt csak a t1 -b}ol s1 -be vezet}o k1 igenyelre alkalmazva, a Menger tetel alapjan ~ ~ ol kihagyva iranytott letezik G-ben k1 elidegen iranytott ut s1 -b}ol t1-be. Ezen k1 utat es k1 igenyelt G~ + H-b Euler grafot kapunk, amely elidegen korok uniojara bomlik,gy ezek tartalmaznak k2 jo kort. 41
A 10.3 tetel bizonytasokhoz ket egyszer}u meg gyelesre van szuksegunk.
1. LEMMA Legyen G iranytatlan teljest}o graf es H tesz}oleges igenygraf ugy, hogy G + H Euler fele.
Legyen G~ + H~ egy Euler iranytasa G + H-nak. Akkor es csak akkor teljesul az iranytatlan vagas feltetel ~ G + H-ra, ha az iranytott teljesul G~ + H-ra.
Biz. Az iranytott Eulerseg miatt %G~ (X) + %H~ (X) = G~ (X) + H~ (X):
(5)
Most a (3) iranytatlan vagas feltetellel ekvivalens feltetelt kapunk, ha (3)-t a %G~ (X) + G~ (X) %H~ (X) + H~ (X)
(30 )
alakban rjuk, es ezt (5)-hoz adjuk. Ekkor pont (4) ketszereset, tehat az iranytott vagas feltetelt kapjuk. 2. LEMMA Tegyuk fel, hogy G + H iranytatlan graf, melyre a vagas feltetel teljesul. Legyen H~ a H tetsz}oleges iranytasa. Ekkor G iranythato ugy, hogy G~ + H~ Euler fele.
Biz. A vagas feltetel szerint dG(X) dH (X) = %H~ (X) + H~ (X) %H~ (X) ? H~ (X) gy (1) teljesul, es az 10.1 tetel alapjan letezik a keresett iranytas. A 10.3 tetel bizonytasahoz iranytsuk az si ti igenyeleket ti -t}ol si fele (i = 1; 2). A 2. lemma alapjan G elei iranythatok ugy, hogy G~ + H~ Euler fele legyen. Az 1. Lemma alapjan fennall az iranytott vagas feltetel, gy 10.3 tetelb}ol a 10.2 tetel kovetkezik. A Lucchesi-Younger tetel egy erdekes alkalmazasakent levezetunk egy elidegen utakra vonatkozo tetelt. G = (V; E) iranytott grafban adott k pontpar (s1 ; t1); : : :; (sk ; tk ). Keressunk a grafban k darab elidegen utat ugy, hogy az i-dik ut si -b}ol vezet ti -be. Bebizonytottak, hogy ez a problema meg k = 2 esetben is NP-teljes. Specialis esetekben azonban a feladat kezelhet}o. Minden i-re ti -b}ol vezessunk egy un. igenyelt si -be, es jeloljuk az igenyelek grafjat H = (V; F)-fel. Ekkor az elidegen utak problemaja azzal ekvivalens, hogy a G + H unio grafban kell keresni k olyan kort, melyek elidegenek es mindegyikuk pontosan egy igenyelt hasznal. Az ilyen kort nevezzuk F -jo kornek.
FEDE SI FELTE TEL Az F-jo koroket nem lehet k-nal kevesebb E [ F-beli ellel lefogni. Ekvivalens alakban: Barmely k0 (1 k0 k) terminal-parra az si -b}ol ti -be vezet}o utakat nem lehet
k0 -nel kevesebb G-beli ellel lefogni. A feltetel nyilvan szukseges a k elidegen F-jo kor, azaz a k elidegen ut letezesehez.
10.4 TE TEL Amennyiben G aciklikus es G + H skgraf, ugy a fedesi feltetel szukseges es elegend}o az elidegen utak problemajanak megoldasahoz. Biz. Tekintsuk a G + H digraf skbeli dualisat, G0 + H 0-t. A lltjuk, hogy ebben letezik k elidegen iranytott vagas. Ha nem ez volna a helyzet, akkor a Lucchesi-Younger tetel alapjan letezne legfeljebb k ? 1 el, amely az osszes iranytott vagast lefogja. Ez eppen azt jelentene, hogy az eredeti G+H grafban az osszes iranytott kort le lehetne fogni k-nal kevesebb ellel, ellentetben a fedesi feltetellel. Tehat G0 +H 0 -ben van k elidegen iranytott vagasunk, azaz az eredeti G+H-ban van k elidegen iranytott korunk. Mivel a felteves szerint G aciklikus, ezen korok mindegyike tartalmaz legalabb egy igeny elt. Masreszt k igenyel van, gy a k kor mindegyike pontosan egy igenyelt tartalmaz, vagyis ezen korok F-jo korok. Megjegyzes. A ltalaban meg aciklikus digrafra is NP-teljes az elidegen utak problemaja. Ilyenkor azonban eggyel jobb a helyzet, mint altalanos G-re: ha k konstans, akkor a feladat P-ben van. 42
11. IRA NYITATLAN GRA FOK KONZERVATIV SU LYOZA SAI Legyen a G = (V; E) iranytatlan graf elhalmazan adva egy w sulyfuggveny. A w sulyozasrol azt mondjuk, hogy konzervatv, ha w(C) 0 teljesul G minden C korere, azaz nincs negatv kor. Korabban mar lattuk, hogy iranytott grafok eseten egy sulyozas akkor es csak akkor konzervatv, ha letezik megengedett potencial, tovabba a minimalis utkeres}o algoritmus segtsegevel viszonylag egyszer}u eldonteni, hogy melyik eset all fenn. Az iranytatlan eset meglep}o modon sokkal nehezebb es erdekesebb. Az alabbiakban azt a specialis esetet tekintjuk, amikor w csak +1; ?1 ertekeket vesz fel, miutan tobb alkalmazas erre az esetre vezethet}o vissza. A kovetkez}o artatlanul hangzo lemma, mint kiderul, az egesz elmelet sarkkove.
11.1 LEMMA (SEBO} LEMMA) Legyen G = (V; U; E) egyszer}u paros graf, amelynek legalabb harom pontja van es legyen w : E ! f+1; ?1g olyan konzervatv sulyozas, hogy barmely ket olyan pont kozott, amely G-nek ugyanabban a pontosztalyaban van, letezik negatv ut. Ekkor G fa es w ?1. Biz. Pontszam szerinti indukciot hasznalunk. Konnyen latszik, hogy a lemma alltasa igaz, ha a grafnak harom pontja van. Tegyuk ezert fel, hogy jV [ U j 4: Legyen P olyan ut, amelynek w-sulya a legnegatvabb,
es ezen belul, P-nek minimalis szamu ele van. Mivel a grafban van negatv ut, P-nek legalabb egy ele van. Jelolje t a P ut egyik vegpontjat es xt az ezzel szomszedos elet.
A LLITA S Az xt el a graf egyetlen t-vel szomszedos ele. Biz. A P valasztasa miatt P-nek mindegyik t-b}ol indulo P[y; t] reszutja negatv, specialisan w(xt) = ?1: Tegyuk fel indirekt, hogy letezik egy masik t-vel szomszedos el es jeloljuk ezt tz-vel. Ekkor w(tz) nem lehet negatv, mert ha z 2 P, akkor P[z; t] + tz negatv kort alkotna, ellentetben a w konzervativitasaval, ha pedig z 62 P, akkor P 0 := P + tz olyan ut lenne, amelyre w(P 0) < w(P), ellentetben w(P) minimalitasaval. Igy tehat w(tz) = 1. Mivel x es z szomszedja t-nek, gy G ugyanazon pontosztalyaban vannak, ezert a lemma feltevese szerint letezik kozottuk egy R negatv ut. Az R szuksegkeppen hasznalja a t pontot, mert kulonben R + xt + tz negatv kor volna. Az R-nek valojaban az xt elt is hasznalnia kell, mert ha nem, akkor R[x; t] + xt kor, gy w(R[x; t]) 1, tovabba a tz el miatt w(R[t; z]) ?1, es ez gy egyutt lehetetlen, mert 0 > w(R) = w(R[x; t]) + w(R[t; z]) 1 + (?1) = 0. Tehat R hasznalja az xt elt. Miutan a graf paros, gy w(R[x; z]) paros szam, tehat legfeljebb ?2. Ezert w(R[t; z]) ?1 es gy a C := R[t; z] + tz kor sulya 0. Ha a P utnak es az R[t; z] utnak van t-t}ol kulonboz}o kozos pontja, akkor legyen y a P uton t-b}ol indulva a legels}o ilyen. Miutan w(P[t; y]) < 0, gy a C koron mindket t es y kozotti ut pozitv, ellentmondasban azzal, hogy w(C) = 0. Igy tehat P +R[t; z] ut, de ez megint csak lehetetlen, mert w(R[t; z]) < 0 miatt ekkor nem P volna a legnegatvabb ut, es ezzel az A lltas bizonytasa teljes. Toroljuk el a grafbol a t pontot. Mivel t-b}ol csak egy el megy ki, a Lemma feltetelei tovabbra is fennallnak, ezert indukcioval a Lemma kovetkezik.
11.2 TE TEL Legyen G = (V; U; E) paros graf es w : E ! f+1; ?1g sulyozas. A kovetkez}ok ekvivalensek: (1) w konzervatv. (2) Letezik a V -nek olyan V1 ::Vk partcioja nemures halmazokra, hogy minden i = 1::k eseten a G ? Vi valamennyi kompnensebe legfeljebb egy negatv el lep be. (3) G-ben leteznek olyan elidegen vagasok, amelyek mindegyike egyetlen negatv elt tartalmaz es mindegyik negatv el benne van egy ilyen vagasban. 43
(Figyeljuk meg, hogy a (3) feltetel, G parossaga miatt azzal ekvivalens, hogy G elhalmaza felpartcionalhato olyan vagasokra, melyek mindegyike legfeljebb egy negatv elt tartalmaz.)
Biz. (3) ! (1). Legyen C kor es tekintsuk a szobanforgo elidegen vagasokat. C barmely negatv ele benne van az egyik vagasban. De ekkor C-nek ugyanabban a vagasban van egy masik, szuksegkeppen pozitv ele is, vagyis C minden negatv elehez hozzarendelhetunk egy pozitv elet, kulonboz}ohoz kulonboz}ot. Ebb}ol w(C) 0 adodik. (2) ! (3). Tekintsuk az osszes olyan vagast, amelyet G ? Vi (i = 1::k) egy komponense hataroz meg. Ezek a vagasok partcionaljak E-t es mindegyikuk legfeljebb egy negatv elt tartalmaz. (1) ! (2). Pontszam szerinti indukcio. Feltehetjuk, hogy G osszefugg}o. Amennyiben jV [ U j 2, ugy (2) fennall, gy tegyuk fel, hogy jV [ U j 3. Ha van V -ben ket olyan u es v pont, melyek kozott nincs negatv ut, akkor ezen ket pontot osszehuzva nem keletkezik negatv kor. Jelolje V 0 a V -b}ol az osszehuzassal keletkez}o halmazt. Idukcio alapjan az osszehuzott grafban a V 0 -nek letezik kvant partcioja es ez konnyen lathatoan az eredeti V -nek egy kvant partciojat hatarozza meg. Ha van U-ben ket olyan u es v pont, melyek kozott nincs negatv ut, akkor ezen ket pontot osszehuzva nem keletkezik negatv kor. Idukcio alapjan az oszehuzott grafban a V -nek letezik kvant partcioja, es ez a partcio konnyen lathatoan az eredeti grafban is teljesti a kvanalmakat. Az az eset maradt hatra, amikor barmely ket egy osztalyban lev}o pont kozott vezet negatv ut. A Seb}o lemma szerint ilyenkor a graf fa. Ebb}ol kovetkezik, hogy V -nek az elemeire torten}o partcioja teljesti a (3)-ban lert kvanalmakat. 11.3 TE TEL Legyen G = (V; E) iranytatlan graf es w : E ! f+1; ?1g sulyozas. A kovetkez}ok ekvi-
valensek:
(1) w konzervatv. (2) Letezik V -nek egy olyan V1 ::Vk partcioja nemures halmazokra, hogy semelyik Vi sem feszt negatv elt, minden i = 1::k eseten a G ? Vi valamennyi komponensebe legfeljebb egy negatv el lep be. (3) G-ben leteznek olyan (nem feltetlenul kulonboz}o) vagasok, amelyek mindegyike egyetlen negatv elt tartalmaz, minden pozitv el legfeljebb ket vagasban van es minden negatv el pontosan ket vagasban van.
Biz. A graf minden elet osszuk fel egy uj ponttal, es jeloljuk az osztopontok halmazat U-val. Alkalmazzuk a megel}oz}o tetelt a keletkez}o grafra. BERGE-TUTTE A Berge-Tutte formula azt alltja, hogy egy G = (V; E) iranytatlan grafban a foggetlen elek maximalis (G) szama egyenl}o a min(jV j ? jX j + q(X))=2 : X V ) ertekkel, ahol q(X) jeloli a G ? X paratlan pontszamu komponenseinek a szamat. Konnyen latszik, hogy a Berge-Tutte formula azzal ekvivalens, hogy
11.4 TE TEL G-ben letezik olyan M parostas es X V reszhalmaz, amelyekre fennall, hogy
(A) M fedi X minden pontjat, (B) X nem feszt M-beli elt, (C) G ? X minden komponenseben legfeljebb egy olyan pont van, amelyet nem fed M.
Biz. Legyen M tetsz}oleges maximalis parostas. Vegyunk fel egy uj s pontot es kossuk ossze az M altal fedetlen pontokkal. Legyen w az a sulyozas, amely ?1 az M elemein valamint az uj eleken es +1 a tobbi
elen. Ez konzervatv, mert ha volna negatv kor, akkor az szuksegkeppen tartalmazna az s pontot, es az s-t kihagyva bel}ole egy novel}o alternalo utat kapnank, ellentetben M maximalis valasztasaval. Tekintsuk az el}oz}o tetel altal biztostott partciojat V -nek, es legyen X +s az s pontot tartalmazo partcio resz. A (2)-ben felsorolt tulajdonsagokbol kovetkezik, hogy X teljesti az (A), (B), (C) kvanalmakat. 44
E LIDEGEN UTAK SIKGRA FBAN A kovetkez}o alkalmazas az elidegen utak problemajara vonatkozik. Korabban mar lattuk, hogy ha a G graf a H igenygraf eleivel kiegesztve Euler-fele es H ket csomag parhuzamos elb}ol all, akkor a vagas feltetel nemcsak szukseges, hanem elegend}o is. Az alabbi tetelben G + H Eulersege mellett G+ H skbeliseget rjuk el}o.
11.5 TE TEL (Seymour) Legyen a G = (V; E) es H = (V; F graf olyan, hogy G + H = (V; E + F) skbarajzolhato Euler-graf. Ekkor a H igenygraf altal a G grafban meghatarozott elidegen utproblemanak akkor es csak akkor letezik megoldasa, ha a vagas feltetel teljesul, azaz ha dG(X) dH (X) minden X V -re. Biz. Tekintsuk a G + H graf skbeli dualis grafjat. Ez G + H Eulersege miatt paros graf. A dualisban az E-nek megfelel}o elek sulyat de nialjuk 1-nek, mg az F-nek megfelel}o elek sulyat de nialjuk ?1-nek. A vagas feltetel pontosan azzal ekvivalens, hogy az gy de nialt w sulyozas konzervatv. A 11.2 tetel szerint letezik a dualisban jF j elidegen vagas ugy, hogy midegyik egy negatv elt tartalmaz. Ez azt jelenti, hogy G + H-ban letezik jF j elidegen kor ugy, hogy mindegyik pontosan egy F-beli elt tartalmaz, de ez eppen azt jelenti, hogy a szobanforgo elidegen ut problemanak van megoldasa. KINAI POSTA S: T-KO TE SEK; T-VA GA SOK Harmadik alkalmazaskent megvizsgaljuk a knai postas problemajat. Egy G = (V; E) osszefugg}o iranytatlan graf eleit kell bejarnunk megadott pontbol kiindulva es vegul oda visszaterve ugy, hogy a tobbszor bejart elek szama minimalis legyen. Kozismert, hogy amennyiben a graf Euler fele, ugy letezik olyan bejarasa, amelyben minden elen pontosan egyszer haladunk vegig. Ilyenkor tehat nincs mit optimalizalni. Ha a grafban leteznek paratlan foku pontok, akkor szuksegkeppen nehany elen tobbszor kell vegighaladnunk. Kepzeljunk el egy bejarast, es helyettestsunk minden elt annyi parhuzamos ellel, ahanyszor vegigmentunk rajta. Ekkor nyilvan Euler grafot kapunk. Megfordtva, ha minden elt pozitv szamu parhuzamos ellel helyettestunk ugy, hogy Euler grafot kapjunk, akkor a kapott Euler graf egy Euler-setaja az eredeti graf olyan bejarasanak felel meg, amelyben minden elen pontosan annyiszor haladunk vegig, ahany ellel helyettestettuk. Ezen meggondolas alapjan a knai postas problemaja a kovetkez}ovel ekvivalens: Adott osszefugg}o grafot tegyunk Eulerra minimalis szamu parhuzamos el behuzasaval. Figyeljuk meg, hogy nem erdemes egy elnek egynel tobb parhuzamos peldanyat bevenni, mert ekkor ket uj parhuzamos elt kihagyva az Eulersagot nem rontjuk el es egy kisebb novelest kapunk. Tehat a feladat azzal ekvivalens, hogy adott osszefugg}o grafot tegyunk Eulerra minimalis szamu el parhuzamos megduplazasaval. A kerdest meg egy kicsit altalanostjuk, es ugy valaszoljuk meg. Legyen most a V ponthalmazon H = (V; F) egy masik graf, amely osszefugg}o. Az altalanostott feladatban a H grafot kell Eulerra tenni minimalis szamu G-beli el hozzavetelevel. (Ehhez a G osszefugg}oseget nem is kell feltetelezni). Vilagos, hogy G = H eseten visszakapjuk a knai postas problemat. A feladat megoldasahoz gyeljuk el}oszor is meg, hogy a G eleinek egy J reszhalmazat H-hoz adva pontosan akkor kapunk Euler grafot, ha dJ (v) es dF (v) paritasa minden v pontra megegyezik. Ez azt jelenti, hogy a H grafot nem is kell ismernunk, csupan a H-ban paratlan foku pontok T halmazat. Ez indokolja a kovetkez}o fogalmak bevezeteset. Legyen G = (V; E) iranytatlan graf es T V a pontok egy paros elemszamu reszhalmaza. A (G; T) part neha graft -nak nevezik. Pontok X reszhalmazat T -paratlannak (T -parosnak) nevezunk, ha jX \ T j paratlan (paros). A T elemei a T-pontok. E lek J reszhalmazat T -kotes-nek hvjuk, ha dJ (v) pontosan akkor paratlan, ha v 2 T. Itt dJ (v) azon J-beli elek szamat jeloli, melyek szomszedosak v-vel. A G egy [X; V ? X] vagasat a T -vagasnak hvjuk, ha X T-paratlan. A minimalis T-kotes elemszamat jelolje (G; T). A ltalanosabban, egy tesz}oleges w : E ! R sulyfuggvenyre w (G; T) jeloli a T-kotesek minimalis sulyat. Az alabbi eredmeny valaszt ad az el}obbi problemara. 45
11.6 TE TEL G = (V; E) osszefugg}o grafban akkor es csak akkor letezik legfeljebb elem}u T-kotes, ha V barmely fV1 ::Vk g nemures reszekb}ol allo partciojara
X(q (V ) : i = 1::k) 2 ; T i
(11:1)
ahol qd (X) jeloli az X elhagyasaval keletkez}o T-paratlan komponensek szamat.
Biz. Elegend}oseg. Tetelezzuk fel, hogy (11.1) teljesul es legyen J minimalis elemszamu T-kotes. Legyen wJ (e) = ?1 ha e 2 J es wJ (e) = 1 ha e 2 E ? J. ()
Ekkor wJ konzervatv, mert ha letezne C negatv kor, akkor C es J szimmetrikus di erenciaja T kotes lenne, amelynek elemszama kisebb volna mint J elemszama. A 11.3 tetel szerint letezik V -nek egy olyan V1 ::Vk partcioja, hogy semelyik Vi sem feszt negatv elt es minden i = 1::k eseten a G ? Vi valamennyi komponensebe legfeljebb egy negatv el lep be. Az gy keletkez}o komponensek kozul pontosan azok T paratlanok, amelyekbe egy negatv el megy (ugyanis paritasi megfontolas miatt tetsz}oleges ponthalmaz pontosan akkor T-paratlan, ha J paratlan sok ellel lep bele.) Mivel jJ j negat P v el van, es ezek mindegyike ket olyan komponenst hataroz meg, amelybe belelep, azt kapjuk, hogy (qT (Vi ) : i = 1::k) = 2jJ j, amib}ol (11.1) alapjan jJ j adodik. Figyeljuk meg, hogy a knai postas eseteben, amikor T a G paratlan foku pontjainak halmaza, egy C halmaz pontosan akkor T-paratlan, ha dG (C) paratlan. Igy nyerjuk:
11.7 KO VETKEZME NY G = (V; E) osszefugg}o grafot akkor es csak akkor lehet legfeljebb elenek p megduplazasaval Euler-feleve tenni, ha V barmely fV1::Vk g nemures reszekb}ol allo partciojara Parhuzamos (qd (Vi ) : i = 1::k) 2 , ahol qd (X) jeloli az X elhagyasaval keletkez}o paratlan fokszamu (!) komponensek szamat. 11.8 TE TEL (Seymour) Paros grafban az elidegen T-vagasok maximalis T szama egyenl}o a T-kotesek minimalis T elemszamaval.
Biz. Mivel minden T-kotesnek es T-vagasnak paratlan sok kozos eleme van (, T T fennall. Legyen most J minimalis T-kotes es tekintsuk a ()-ban de nialt wJ konzervatv sulyozast. A 11.2 tetelb}ol az eredmeny adodik. Feladat Igazoljuk, hogy egy G = (V; E) sk Euler grafban az elidegen paratlan korok maximalis szama egyenl}o min(i(X) + i(V ? X) : X V )-vel, ahol i(X) az X altal fesztett elek szama. Feladat Igazoljuk, hogy tetsz}oleges graf eseten a a T-kotesek minimalis T elemszama egyenl}o felig diszjunkt
modon pakolhato T-vagasok maximalis T szamanak felevel. (A felig diszjunktsag azt jelenti, hogy minden el legfeljebb ket vagashoz tartozhat.
T-KO TE SEK ELEMI TULAJDONSA GAI Minimalis T-kotesek es konzervatv f+1; ?1g sulyozasok kapcsolatat mutatja a kovetkez}o meg gyeles. 1. A LLITA S Egy J T-kotes akkor es csak akkor minimalis elemszamu, ha wJ konzervatv. Biz. Az el}obb mar lattuk, hogy ha J minimalis elemszamu, ugy wJ konzervatv. Megfordtva, azt igazoljuk, hogy ha letezik J-nel kisebb elemszamu I T-kotes, akkor wJ nem konzervatv. Valoban barmely ket T-kotes szimmetrikus di erenciaja ciklus (azaz minden pontjaban paros foku reszgraf), gy elidegen korok unioja. Mivel jI j < jJ j, az egyik ilyen C korben szuksegkeppen tobb J-beli el van I-beli, ami epp azt jelenti, hogy a C kor wJ sulya negatv, vagyis wJ nem konzervatv. 46
Nemsokara latni fogjuk ezen alltas sulyozott esetre vonatkozo altalanostasat is. A kovetkez}okben attekintjuk a T-kotesek nehany egyszer}u tulajdonsagat.
ITA S Elek egy J reszhalmaza akkor es csak akkor T-kotes, ha J el}oall elidegen korok es jT j=2 olyan 2. ALL ut egyestesekent, melyek vegpontjai mind kulonboz}oek es T-ben vannak. Biz. Vilagos, hogy ha J az adott alakban van, akkor T-kotes. Megfordtva, legyen J T-kotes. Adjunk G-hez egy s uj pontot es uj elek egy N := fst : t 2 T g halmazat. Ekkor J [ N Euler graf, gy elidegen korok uniojara bomlik. Kihagyva N elemeit megkapjuk J kvant felbontasat. 3. A LLITA S Ha J T-kotes es B T-vagas, akkor kozos reszuk paratlan sok elemb}ol all. Biz. Legyen B =P[X; V ? X] az X ponthalmaz altal meghatarozott T-vagas. Mivel jX \ T j paratlan es J T-kotes, az S := (dJ (v) : v 2 X) osszeg paratlan. Tovabba S = 2jE(X) \ J j + jJ \ B j es ezert jJ \ B j is paratlan. 4. A LLITA S G grafban akkor es csak akkor letezik T-kotes ha G minden komponense T-paros. Biz. Legyen K T-paratlan komponense G-nek. Ekkor a [K; V ? K] vagas ures T-vagas. Az el}oz}o alltas szerint G-nek nem letezhet T-kotese. A fordtott irany bizonytasahoz feltehetjuk, hogy G osszefugg}o. jT j=2 szerinti indukciot hasznalunk. If T = ;, az ures halmaz T-kotes. Legyen jT j 2, s; t 2 T es T 0 := T ? fs; tg. Az indukcios felteves alapjan letezik G-ben T 0 -kotes. Miutan G osszefugg}o, letezik egy P ut s es t kozott. Konnyen belathato, hogy J 0 es P szimmetrikus di erenciaja T-kotes. 5. A LLITA S E leknek egy olyan F reszhalmaza, amely minden T-kotest metsz, tartalmaz T-vagast. Biz. A felteves alapjan a G ? F reszgrafban nincsen T-kotes. Az el}obbi alltas szerint G ? F valamely K komponense T-paratlan. Vagyis [K; V ? K] G-nek T-vagasa, amely teljesen F-ben van. A kovetkez}o alltas igazolasa szinten egyszer}u gyakorlat.
6. A LLITA S Legyen T1 es T2 ket paros elemszamu reszhalmaza V -nek es legyen Ji Ti-kotes (i = 1; 2). Ekkor J1 J2 (T1 T2 )-kotes. Specialisan, ket T-kotes szimmetrikus di erenciaja ciklus, tovabba egy T-kotes es egy ciklus szimmetrikus di erenciaja T-kotes. MINIMA LIS SU LYU T-KO TE SEK E S ALKALMAZA SAIK T-kotesekkel kapcsolatban fentebb valaszt adtunk a minimalis elemszamu T-kotes problemajara. A ltalanosabb celunk minimalis sulyu T -kotes meghatarozasa. (11:2) Ezt a feladatot minimalis sulyu teljes parostas meghatarozasara vezetjuk majd vissza. El}obb azonban bemutatunk nehany peldat, ami a (11.2) feladat specialis esete.
1. KONZERVATIV SU LYOZA SOK Adott G = (V; E) grafban a w : E ! R sulyozasra dontsuk el, hogy konzervatv-e vagy sem. Legyen T := ;. Ekkor a T-kotesek pontosan a ciklusok (:=Euler-grafok= elidegen korok unioja). Mivel az ures halmaz T-kotes, amelynek sulya 0, w pontosan akkor konzervatv, ha a minimalis T-kotes sulya 0. 47
2. MAX CIKLUS E S MAX VA GA S PROBLE MA Adott G es w, hatarozzuk meg a maximalis w-sulyu Euler reszgrafot (ciklust). Ez a feladat a T = ;-ra a maximalis sulyu T-kotes problemaja, amely a sulyok negalasaval (11.2) alakuva valik. Sk grafokra, a graf dualisat veve, a maximalis sulyu ciklus problemaja ekvivalens a maximalis sulyu vagas meghatarozasaval (amely feladat amugy tetsz}oleges grafra NP-teljes). Ez viszont olyan minimalis sulyu elhalmaz meghatarozasaval ekvivalens, amelynek elhagyasa a grafot paros gra a teszi, azaz, amely minden paratlan kort lefog.
3. LEGRO VIDEBB UTAK Legyen G = (V; E) grafban s es t ket adott pont es w : E ! R konzervatv
suly-fuggveny. Keressunk minimalis sulyu egyszer}u utat s es t kozott. Ha semmilyen megkotest sem teszunk w-re, akkor a feladat NP-teljes, mert a (kozismerten NP-teljes) Hamilton ut feladat specialis esetkent megfogalmazhato. Iranytott grafban a legrovidebb ut problema kezelhet}o, ha a sulyozas konzervatv. Ezert kezenfekv}o az iranytatlan esetben is a legrovidebb ut feladatot konzervatv sulyozasra tekinteni. Ha olyan szerencsesek vagyunk, hogy w nem-negatv, akkor a feladat visszavezethet}o az iranytott esetre ugy, hogy minden elt ket ellentetesen megiranytott ellel helyettestunk melyek sulya az eredeti iranytatlan el sulya. Ez a redukcio azonban tetsz}oleges konzervatv sulyzas eseten nem m}ukodik, mert akkor egy negatv elt egy negatv ket-el}u korrel kellene helyettestenunk, elrontva ezaltal a konzervativitast. Legyen T := fs; tg. Ekkor tetsz}oleges T-kotes egy s-t es t-t osszekot}o utbol all es nehany elidegen korb}ol. Mivel azonban w konzervatv, van olyan minimalis w-sulyu T-kotes, amely egyetlen utbol all.
4. A KINAI POSTA S KO LTSE GES PROBLE MA JA Egy postasnak vegig kell mennie egy varosresz
minden utcajan ugy, hogy a postahivatalbol indul es oda er vissza. Keressunk olyan bejarast, amelynek az ossz-hossza a lehet}o legkisebb. A fentiek alapjan a knai postas koltseges problemaja azzal ekvivalens, hogy megadott G grafot minimalis ossz-sulyu olyan el hozzaadasaval kell Euler-feleve tenni, amely eredeti ellel parhuzamos, ez pedig egy minimalis sulyu T-kotes feladat.
5. TELJES PA ROSITA SOK Vegul valasszuk T-t az egesz V -nek. Ekkor egy teljes parostas T-kotes, bar lehetnek mas T-kotesek is. Mindenesetre G-nek akkor es csak akkor van teljes parostasa, ha a minimalis elemszamu T-kotes elemszama jV j=2. Vagyis a (11:2) feladat altalanostja a teljes parostas letezesenek
problemajat.
MINIMA LIS SU LYU T-KO TE SEK MEGHATA ROZA SA A (11.2) problemat el}oszor abban az esetben oldjuk meg, amikor w 0. Az x; y 2 T pontokra jelolje (x; y) az x es y-t osszekot}o utak w-sulyanak minimumat. Legyen KT a T halmazon de nialt teljes graf es legyen M := fx1y1 ; x2y2 ; : : :; xkyk g minimalis sulyu teljes parostas KT -ben a sulyozasra vonatkozolag. Legyen Pi a G-ben az xi es yi pontokat osszekot}o utak w-sulyanak minimuma (azaz, w(Pi ) = (xi ; yi ) (i = 1; : : :; k)). Legyen vegul JM := E(P1 ) E(P2) : : : E(Pk ); ahol a szimmetrikus di erenciat jeloli.
(2)
11.9 TE TEL JM minimalis sulyu T-kotes. Biz. Vilagos, hogy JM T-kotes. Legyen J egy tetsz}oleges T-kotes. A 2. alltas szerint J felbonthato korokre es Ri (i = 1; : : :; k) utakra. Jelolje si es ti az Ri ket P vegpontjat es legyen M 0 := fs1 t1; s2 t2; : : :; sk tk g. Ekkor P P 0 w(J) w(Ri ) (si ; ti) = (M ) (M) = w(Pi) w(JM ), ami mutatja JM minimalitasat. (Itt az els}o egyenl}otlenseg azert igaz, mert w nem-negatv.) 48
Terjunk most ra (11.2) megoldasara tetsz}oleges (tehat nem feltetlenul konzervatv) w sulyozas eseten. De nialni fogunk egy ekvivalens problemat, amelyben azonban a sulyozas mar nem-negatv. Jelolje jwj azt a sulyozast, amelyre jwj(e) := jw(e)j minden e 2 E elre. E lek valamely F reszhalmazara jelolje w0 := w[F] a kovetkez}o sulyozast w0 (e) = w(e) ha e 62 F es 0 w (e) = ?w(e) ha f 2 F. Jelolje Nw a negatv elek halmazat es Tw := fv : dNw (v) paratlang, azaz Tw azon pontok halmaza, melyek paratlan sok negatv ellel szomszedosak. Figyeljuk meg, hogy Nw Tw kotes. De nialjuk a 'w : 2E ! 2E fuggvenyt gy; 'w (X) := X Nw . Vilagos, hogy 'w idempotens, azaz 'w ('w (X)) = X.
7. A LLITA S 'w bijekciot alkot a T-kotesek es a es (T Tw )-kotesek kozott. Tovabba, ha J T-kotes es J 0 (T Tw )-kotes egymasnak felelnek meg, akkor w(J) = jwj(J 0) + w(Nw ) (2) Biz. Az els}o resz kovetkezik a 6. alltasbol. Miutan J 0 = J Nw , kapjuk, hogy w(J) = w(J ? Nw ) + w(J \ Nw ) = jwj(J 0 ? Nw )+w(J \ Nw ) = jwj(J 0) ?jwj(Nw ? J)+w(J \ Nw ) = jwj(J 0)+w(Nw ? J)+w(J \ Nw ) = jwj(J 0) + w(Nw ); es ebb}ol (2) kovetkezik. Rogton kapjuk:
8. A LLITA S Tetsz}oleges w sulyfuggvenyre a J elhalmaz akkor es csak akkor minimalis w-sulyu T-kotes ha J 0 := J Nw minimalis jwj-sulyu (T Tw )-kotes. Ennek segtsegevel tehat a minimalis sulyu T-kotes problemaja visszavezethet}o a nem-negatv sulyokra vonatkozo minimalis sulyu T-kotes feladatra. Specialisan el tudjuk donteni, hogy egy w sulyozas konzervatve vagy sem, hiszen w pontosan akkor konzervatv, ha a T = ;-re nezve az ures halmaz minimalis w-sulyu T-kotes. Vizsgalatainkat minimalis sulyu T-kotesek egy fontos tulajdonsagaval zarjuk.
9. A LLITA S Tetsz}oleges w sulyozasra a J T-kotes akkor es csak akkor minimalis w-sulyu, ha w[J] konzervatv.
Biz. Ha w[J] nem konzervatv, akkor letezik egy olyan C kor, amelyre w[J](C) < 0, azaz, w(C \ J) > w(C ? J). Ekkor viszont J 0 = C J olyan T-kotes, amelyre w(J 0 ) = w(J) ? w(C \ J) + w(C ? J) < w(J). Megfordtva, legyen J olyan T-kotes, amelyre w[J] konzervatv, es legyen J 0 egy tetsz}oleges T-kotes. Miutan a J J 0 szimmetrikus di erencia ciklus, gy felbomlik elidegen korok uniojara. Ha indirekt w(J 0 ) < w(J) volna, akkor ezen korok kozul legalabb egyre w(C \ J 0 ) < w(C \ J) allna, azaz w[J](C) < 0, ellentmondas.
49
