Matematika | Felsőoktatás » Élek leemelése és csúcsok szétszedése iránytalan gráfokban

lek leemelse s cscsok sztszedse irnytatlan grfokban SZAKDOLGOZAT Fleiner Balzs Tmavezet: Frank Andrs az ELTE vgzs matematikus hallgatja egyetemi tanr 1996. Tartalomjegyzk 1. 2. 3. 4. Bevezets : : : : : : : : : : : : Denci k, jel lsek, alapvet Leemelnk egy 3-csillagot : : T bbsz r s leemels : : : : : : :::::::::::::::::::::::::::: llt sok : : : : : : : : : : : : : : : : : : : : : : :::::::::::::::::::::::::::: :::::::::::::::::::::::::::: 1 2 4 7 4.1 Nhny sz a huroklekrl 13 5. Alkalmaz sok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14 l sszefggsg n vels fokszm elrssal . 14 5.11 Egy eszttikai igny kielgtse 15 5.2 l sszefggsg n velse adott szm llel 17 5.1 6. Sztszedsek : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19 7. Sejtsek : : : : : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : : 22 1. Bevezets Jelen szakdolgozat specilis grfelmleti konstrukcikkal s azok felhasznlsval foglalkozik. A kombinatorikus optimalizls tmak rben szmos olyan problma merlt fel, melyek megoldsban tipikus eljrsok nyomaira bukkanhatunk. K zelebbrl nhny l sszefggsggel kapcsolatos krdssel, s a megvlaszolsukban szerepl n lleemelsi konstrukcikkal ismerkednk meg. Grfoknak sokat vizsglt alapvet tulajdonsga az l sszefggsg, amely egy k-l sszefgg grf esetben azt jelenti, hogy legalbb k lt kell elhagyni a grfbl, hogy t bb komponensre essen. A kl nb z optimalizlsi feladatokhoz nlkl zhetetlen a fokfggvny behat vizsglata Ez a fggvny azt rja le, hogy a grf cscsainak adott rszhalmazhoz hny olyan l van, amely egyarnt tartalmaz a halmazbl s a komplementerbl cscsot. Az derlt ki,hogy a legfontosabb tulajdonsg a szubmodularits, amely lehetv teszi a kibontakoz elmlet polideres eszk z kkel

t rtn megk zelitst. Ezzel az eljrssal kombinatorikus optimalizlsi feladatokat akr k ltsgfggvnnyel neheztett esetekben is tudunk kezelni. Mindazonltal ms hatkony eszk z k is ismertek. Ilyen lehet egy olyan egyszer vltoztats a grfon, amelynek az l sszefggsgre gyakorolt hatst jl nyomon k vethetjk, de iterlt alkalmazsa gy keresen vltoztathat a grf egyb tulajdonsgain. Az s pontra illeszked su s sv l t rlst s uv l behzst az su, sv lpr s-rl t rtn leemelsnek mondjuk. Lovsz 2] ttele k 2 esetben olyan leemelsek ltezst igazolja, amely az s-tl kl nb z cscsok halmazra megtartja a k-l sszefggst. Ez a ttel komoly feladatok megoldshoz jrul hozz. Ilyen pl a 2-l sszefgg grfok ellltsra hasznlt flfelbonts 2k-l sszefgg grfok ellltsra vonatkoz ltalnostsa 2]. Polideres megfontolsok helyett leemelsek alkalmazsval is bizonythat Nash-Williams eredmnye 4], mely szerint minden 2k-l sszefgg irnytatlan

grfnak van k-l sszefgg irnytsa. Grfok k-l sszefggv n velsnek minimlis lszm ignyt is Lovsz ttelvel lehet igazolni 6] Mindez igen hatkony eszk z abban az esetben, ha a cscsokra fokszm elrs is adott. 1 Ha az leken szerepl k ltsgfggvny alapjn szeretnnk optimalizlni, akkor k nnyen NP-teljes problmkba botlunk. Amennyiben az lek k ltsgt vgpontokon rtelmezett fggvny denilja, a leemels technika s a moh algoritmus egyttes alkalmazsa vezethet minket sikerre. Bevezetnk egy jabb leemels fogalmat, nevezetesen a 3-csillag leemelst. Ez az su, sv, sz lek t rlst s az s u, s v, s z lek behzst jelenti, ahol s egy extra pont. Erre a leemelsre Lovsz ttelvel rokon ttel igaz, mellyel a mr kitaposott utat k vetve a rgi eredmnyek j kiterjesztst nyerhetjk. A 3-csillag leemels s az lpr leemels tulajdonsgait kihasznlva egyszer eljutni a nagyobb fok csillagok k-l sszef ggst megtart leemelshez is. Mindezek a ttelek k 2

esetre rvnyesek, k = 1 esetben a megfelel llts s bizonyts ltalban kl nb z, esetleg trivilis. Mindezek alapjn dolgozatunk felptse a k vetkez: A szksges dencik utn megvizsgljuk, hogy mikor lehet egy 3-csillagot a k-l sszefggsg megtartsval leemelni. Ezt az eredmnyt kiterjesztjk t bb 3-csillag leemelsre 2-3 hipergrfokban. Kl n fejezet foglalkozik az alkalmazsokkal, ahol az lpr leemels k vetkezmnyeivel analg lltsokat mondunk ki. Az l sszefggsg n vels huroklektl mentes vltozatt is lerjuk, majd igazoljuk a tetszleges mret csillagok leemelsvel foglaloz alapvet ttelt. Utbbi felhasznlsnak j fejezetet szentelnk, melyben rmutatunk Nash-Williams sztszeds elmlethez fzd kapcsolatra. Vgezetl a bizonyitott ttelekkel kapcsolatos lokl-l sszefggsg megtart leemelsrl fogalmazunk meg sejtst. K sz nettel tartozom tmavezetmnek, Frank Andrsnak, aki mindvgig rszletesen gyelemmel ksrte munkmat, elltott a

szksges irodalommal s fontos szakmai tmutatsokat adott. K sz n m mg Hidvgi Zoli rendszergazda segtsgt is, aki lelkiismeretesen oldotta meg a munkmat nehezt szmtstechnikai jelleg problmkat. Nem utols sorban Varga Dnielnek s Wiener Gbornak jr mg k sz net, hogy megk nnytettk a sz vegszerkeszts nehzsgeinek lekzdst. 2. Dencik, jel lsek, alapvet llt sok G = (V E ) irnytatlan grfot jel l. s 2 V leemelse az su, sv, sz lek t rlse s az s u, s v, s z lek behzsa, ahol s egy jonnan felvett pont. Az u, v, z vgpont 3-csillagot fu v zg mdon jel ljk. s s uvz s* uvz Egy X  V halmaz az a, b pontokat elval sztja, ha a 2 X 63 b vagy b 2 X 63 a. Azt mondjuk, hogy fa b cg 3-csillag vagy egy l lefog egy X 2 V halmazt, ha X az a, b, c illetve az l vgpontjai k zl kettt elvlaszt. X  V halmaz fokt d(X ) jel li s azokat az leket szmolja, amelyek X -et lefogjk. Ha X -re illeszkednek huroklek, akkor minden egyes pldny az X fokt 2-vel n

veli. x y 2 V pontokra (x y) lok lis l sszefgg sget 2 G(x y) := (x y) := minfd(X ) : x 2 X 62 yg denilja, mg a globlisat: (G) := minf(x y) : x y 2 V g: Egy s cscs s a tle diszjunkt X halmaz k z tti leket d(X s) jel li. Utbbi jel lseknl ha szksges jelezni, hogy a G grfban rtelmezett fogalomrl van sz, akkor ezt dG (X ) mdon tesszk. Szhasznlatunkban az s k zpponttal rendelkez 3-csillag leemelhet az s pontrl, ha a leemelssel kapott G grfban x y 2 V ; s pontokra G (x y) = G (x y). A grfra, amelyet G-bl az s cscs s a belle indul lek elhagyasval kapunk, a G ; s jel lst hasznljuk. Az s szompszdjait N (s) := fx : x 2 V sx 2 E g jel li 0 0 2-3 hipergrfon olyan hipergrfot rtnk, amely lei 2 ill. 3 pont lek Ebben az rtelemben teht a hagyomnyos grfok is 2-3 hipergrfok 2.1 Lemma (Szubmodularitsi lemma) G = (V E ) grf vagy hipergrf A d : 2V ! N fggvny szubmodulris, azaz ahol X Y  V . d(X ) + d(Y ) d(X Y ) + d(X Y

) biz. Az leket csoportosthatjuk aszerint, hogy pontjaik az X ; Y , Y ; X , X Y s V ; X Y halmazok k zl melyekbe esnek. K nny ellenrizni, hogy az ilyen rtelemben azonos tpus leket az egyenltlensg bal oldala legalbb annyiszor szmolja, mint a jobb. Hrom halmazra is ltezik hasznos egyenltlensg: 2.2 Lemma G = (V E ) irnytatlan grf (nem hipergrf!), X Y Z  V Az igaz, hogy d(X ) + d(Y ) + d(Z ) d(X Y Z ) + d(X ; (Y Z )) + + d(Y ; (Z X )) + + d(Z ; (X Y )) + 2d(X Y Z V ; (X Y Z )): Ez az egyenltlensg kulcsszerephez jutott Lovsz ttelnek bizonytsban s a bemutatsra kerl tteleknl is alapvet lesz. 2-3 hipergrfokra csak a gyengtse igaz: 2.3 Lemma G(V E ) 2-3 hipergrf, X Y Z  V d(X ) + d(Y ) + d(Z ) d(X Y Z ) + d(X ; (Y Z )) + + d(Y ; (Z X )) + + d(Z ; (X Y )) + d(X Y Z V ; (X Y Z )): 3 Utbbi kt lemmnak a bizonytsa a szubmodularitsi lemma bizonytsban mutatott eljrssal t rtnik. A kt lemma k z tti kl nbsget az

indokolja, hogy ha egy 3-hiperl X ; (Y Z ), X Y Z , V ; (X Y Z )-beli pontokra illeszkedik, akkor t a 2.2 lemma bal oldala kevesebbszer szmolja, mint a jobb. X Y Z A szubmodularitsi lemma, mint ltni fogjuk, olyan halmazokon alkalmazhat eredmnyesen, amelyekre X ; Y , Y ; X , X Y s V ; X Y halmazok egyike sem res. Ekkor X , Y keresztez halmazok. Ha V ; (X Y ) = megengedett, akkor X , Y halmazok csak metsz ek. Ez utbbi halmazpr tpusra egy msik egyenltlensg lesz jl hasznlhat: 2.4 Lemma X Y  V esetn d(X ) + d(Y ) d(X ; Y ) + d(X ; Y ): biz. A d : 2V ! N fggvny nyilvn szimmetrikus, vagyis d(X ) = d(V ; X ) A szubmodularitssal egytt hasznlva: d(X ) + d(Y ) = d(V ; X ) + d(Y ) d((V ; X ) Y ) + d((V ; X ) Y ) = = d(Y ; X ) + d(V ; (X ; Y )) = = d(Y ; X ) + d(X ; Y ) 3. Leemelnk egy 3-csillagot Kiindulsul az lpr leemelsekre vonatkoz alapvet ttelt mondjuk ki: 3.1 Ttel (Lovsz 2]) s a G = (V E ) irnytatlan grf egy pontja, d(s) 6= 3 s minden V ;

s-beli x y-ra (x y) k 2, akkor s-nl van leemelhet lpr. Egy 3-csillag leemelshez szigortani kell a gral kapcsolatos elvrsainkat: 3.2 Ttel G = (V E ) irnytatlan grf, s 2 V pontra nem illeszkedik hurokl, d(s) 5 s minden x y 2 Vj; s pontprra (x y) k 2. Pontosan akkor van leemelhet 3-csillag, ha k d s ; (G ; s) k ; . ( ) 1 2 4 Bizonyts. Elsz r a szksgessget ltjuk be Tfh a leemels utn kapott G grfra (G ) k, mg s a harmadfok s1 s s0 pontokra bomlik. G ; s egy minimlis vgsnak kt partja az s1 s s0 pontokbl indul leket kt-kt nyalbba sorolja. Az emltett minimlis vgs leit kiegsztve az s1 s s0 pontok kisebbik nyalbjaival a G grf egy vgsnak j lhalmazt k  j d(s);3 k 3 kapjuk. Mivel a kt kisebbik nyalbban sszesen legfeljebb 2 + 2 = d(s2);1 darab l volt, gy rtrhetnk az elgsgessg bizonytsra. Indirekt bizonytunk. Tfh brmely 3-csillag leemelse rossz gy minden leemelssel keletkezik G -ben egy k-nl kisebb vgs.

s0 -t s s1 -t a vgs mindenkppen elvlasztja, mert kl nben ezt a kt pontot sszehzva azt kapnnk, hogy G-ben van k-nl kisebb vgs. Az sem lehet, hogy a leemelt 3-csillag vgpontjait egy k-nl kisebb X vgs s1 -tl elvlasztja, mert ekkor (X fs1 g) k ; 3 < k is igaz lenne s X fs1 g nem vlasztja el s0 s s1 pontokat. Ezen megfontolsok miatt tetszleges 3-csillag leemelsekor a k vetkez esetek valamelyiknek kell teljeslnie: 1. Van olyan X $ V ; s halmaz, amelyre dG (X ) = k s X a 3-csillagnak legalbb kt vgpontjt tartalmazza. 2. Van olyan X $ V ; s halmaz, amelyre dG (X ) k + 2 s X a 3-csillagnak mindhrom vgpontjt tartalmazza, azaz X fedi a 3-csillagot. Azokat a 3-csillagokat, amelyeknl az 1. eset nem fordul el, leglis 3-csillagnak nevezzk Tekintsk a k vetkez halmazrendszert: 0 0 0 0 K = fX : X $ V ; s dG(X ) = k d(X s) 1g : Nyilvnval, hogy egy 3-csillag pontosan akkor leglis, ha nincsen olyan K-beli halmaz, ami legalbb kt vgpontjt

tartalmazza. Felmerl a krds, jhogy ltezik-e leglis 3-csillag. Mivel minden G-ben k j k -fok k halmaz d (s);1 d (s);1 G ; s-ben legalbb k ; 2 fok, ezrt kt K-beli nem tartalmazhatja 2 2 -nl t bb s-bl indul l vgpontjt. gy kt maximlis K-beli halmaz nem lehet metsz, mert akkor az elzek szerint egyttal keresztezek is lennnek, s ekkor az unijuk egy nagyobb K-beli lenne a szoksos k + k dG (X ) + dG (Y ) dG (X Y ) + dG (X Y ) k + k szubmodularitsi egyenltlensg miatt. Ezek szerint a maximlis K-beliek diszjunktak s kettvel nem lehet lefedni az sszes s-bl indul l vgpontjt. Ezentl csak leglis 3-csillagokkal foglalkozunk, amelyekre a fentiek szerint a 2. eset ll fent Legyen G egy olyan halmazrendszer, hogy minden leglis 3-csillaghoz van X 2 G halmaz, hogy a 3-csillagot fedi az X s dG (X ) Pk + 2. Az indirekt feltevs miatt G jldenilt Feltehet, hogy jGj minimlis s ezen bell X 2G jX j maximlis. 3.3 llt s Ha X 2 G s Y 2 K s dG(X Y s) 1, akkor

Y  X j k d s ; + 2, d(Y s) biz. Nyilvn X Y 6= Ha X Y = V ; s lenne, akkor d(X s) j k j k ( ) 2 d(s);1 1 miatt d(X Y s) 2 d(s2);1 + 1. Teht d(X Y s) = d(s) akkor lehet, ha az j k elzekben mindenhol egyenlsg szerepel. Ekkor dG;s (X ) = dG;s (Y ) = k ; d(s2);1 , gy ha X Y metszk, akkorj dG;s(kX ) + dG;s (Y ) dG;s(X ; Y ) + dG;s(Y ; X ) egyenltlensgbl dG;s (Y ; X ) = k ; d(s2);1 addna, ahonnan dG(Y ; X ) k ; 1, hiszen Y ; X -ben legfeljebb eggyel kevesebb s-bl indul l vgzdik, mint Y -ban. Ez ellentmonds 2 5 Emiatt, a k vetkez szubmodularitsi egyenltlensgben szerepl becslsek helytllak: d| G{z(X}) + d| G{z(Y }) d| G (X{z Y }) + d| G(X{z Y }) : k+2 k= k k gy dG (X Y ) k + 2. G vlasztsa miatt Y  X szksges 3.4 Lemma Ha X 2 G , akkor d(X s) = 3 Bizonyts. d(X s) 3 trivilis, hiszen X fedi valamelyik 3-csillagot Elsz r is beltjuk, hogy nem diszjunkt G -beliek metszete legfeljebb kt darab s-bl indul l vgpontjt tartalmazhatja,

ui. legyenek X Y G -beli halmazok, amelyekre d(X Y ) 2 (G vlasztsa miatt X s Y valdi metsz halmazok.) dG;s(X ) + dG;s (Y ) dG;s(X ; Y ) + dG;s(Y ; X ) (1) Feltehet, hogy pl. dG;s (X ) dG;s(X ; Y ) Ekkor k + 2 dG (X ) = dG;s (X ) + d(X ; Y s) + d(X Y s) dG;s(X ; Y ) + d(X ; Y s) + 2 dG(X ; Y ) + 2 k + 2: Mivel mindenhol egyenlsg teljesl, ezrt d(X Y s) = 2 s dG(X ; Y ) = k: (2) Vegyk szre, hogy dG;s (X ) = dG;s (X ; Y )-bl k vetkezik (1) gyelembe vtelvel, hogy dG;s (Y ) dG;s (Y ; X ) is igaz, ahonnan a fenti mdon levezethet dG(Y ; X ) = k is. Legyen teht X 2 G , s fa b cg egy olyan leglisj 3-csillag k vgpontjai, amelyre fa b cg  X d (s);1 (G denicija miatt van ilyen). Mivel d(X s) + 2 < d(s) (mert d(s) 5),ezrt 2 az X -en kvl van s-bl indul lnek vgpontja. Legyen d egy ilyen pont Ekkor 33 llts miatt s fa b cg legalitsa miatt fa b dg leglis, azaz semelyik kt vgt nem fedi K-beli. Az indirekt feltevs szerint van G -beli

Y , amely fedi fa b dg-t. Mivel a b 2 X Y , ezrt (2) miatt c 2 X ; Y . Hasznos szrevtel, hogy a 33 llts miatt fc a dg leglis Ezt fedi egy Z 2 G halmaz. Mivel dG (X ; Y ) = k s c 2 X ; Y , ezrt X ; Y 2 K, teht a 33 llts miatt X ; Y  Z . Mindezek miatt: c2 z }| { z a2 }| { 2 = d(Z X s) = d(Z (X ; Y ) s) + d(Z (X Y ) s) = d| (X ; Y  s}) + d| (Z (X{z Y ) s}) : {z 1 1 Mivel mindenhol egyenlsg teljesl, d(X ; Y s) = 1. Felidzve, hogy d(X Y s) = 2, kapjuk, hogy d(X s) = 3. A 3.4 lemma miatt fa b cg leglis 3-csillagot fed G -beli X -en kvl mg legalbb kt s-bl indul l vgpontja megtalalhat, legyenek ezek d s e. fa b cg-n tl a 33 llts 6 miatt fa b dg s fa b eg is leglis 3-csillagok s a 3.4 lemma miatt d 6= e Az emltett csillagokhoz tartoz G -beli halmazok legyenek X Y s Z . Az is igaz, hogy dG (X Y Z ) 6= k, mert kl nben X Y Z 2 K lenne, amibl a 3.3 llts miatt k vetkezne, hogy a fa c dg leglis

3-csillagot fed G -beli W halmazra d(W s) 4 teljeslne, ami ellentmonds. A 34 lemma miatt s felhasznlva, hogy brmelyik kett halmaz metszete a-t s b-t mindenkppen tartalmazza, a hrom halmaz k zl semelyik kett unija nem tartalmazhatja a harmadikat, gy a k vetkez ltalnos rvny egyenltlensgben nem szerepelnek res halmazok: (k + 2) + (k + 2) + (k + 2) dG (X ) + dG (Y ) + dG (Z ) z ab2 }| z { c2 }| { z d2 }| { z (3) e2 }| { dG(X Y Z ) + dG (X ; (Y Z )) + dG (Y ; (Z X )) + dG (Z ; (X Y ))+ z ab2 }| { z s2 }| { +2d(X Y X V ; (X Y Z )) (k + 1) + k + k + k + 4: Innen pedig k 1 addik. Megjegyzs. Amennyiben illeszkedik az s pontra hurokl, k nny dolgunk van, hiszen Lovsz ttele biztost egy leemelhet lprt, aminek a k zps pontjhoz bek tve a hurokl egyik vgt, j leemelst kapunk. A fenti bizonyts kis mdostssal akkor is rvnyes, ha G ; s 2-3 hipergrf, ugyanis a fokfggvny hipergrfokon is szimmetrikus s szubmodulris.

Vltoztatst csak a (3) egyenltlensgben kell tenni, ahol is a d(X Y Z V ; (X Y Z )) tagot csak egyszeres egytthatval kell szerepeltetni. Ekkor persze k 3 addik, s a k = 2 3 esetekben a 3-hiperleket 3-csillagokra kell cserlni. Ltni fogjuk, hogy ha egy hiperlt gy mdostunk, akkor a 2- ill. 3-l sszefggsg meg rzdik, s a cserk utn kapott grfban egy leemelhet 3-csillag az eredeti 2-3 hipergrfban is leemelhet lesz. Ezentl a 32 ttelnek ez utbbi, hipergrfos vltozatt fogjuk hasznlni. 4. T bbsz r s leemels Az emltett Lovsz-fle ttelnek megvan az a j tulajdonsga, hogy iterlhat, azaz ha egy lpr leemelse utn mg marad 3-nl t bb l, akkor mindig leemelhetnk egy jabb prt. Amennyiben a 3-csillag leemelseket kvnjuk ismtelni, j fajta problmkat kell thidalnunk. Meg kell vizsglnunk, hogy a 32 ttelben a (G ; s)-re vonatkoz felttel mikppen vltozik a leemelsek sorn s ez mit jelent a kezdeti grfra vonatkozan. Ezutn persze igazolni kell,

hogy az gy kapott felttel elgsges is az ismtelt leemelsek elvgzshez Egy msik nehzsg abbl addik, hogy egy adott helyzetben az addig leemelt 3-csillagok k zps pontjaira nyilvn nincs olyan megk tsnk, hogy brmely msik pontbl k darab ldiszjunk t vezet hozz. Mivel egy leemelt csillag k zps pontja 3 fok, ezrt k 4 esetekben erre a pontra biztosan srl a k-l sszefggsgi k vetelmny. Megnyugtat, hogy k = 2 3-ra a leemelt csillagok k zppontjaira nzve is teljesl a 2- ill. 3-l sszefggsg Ez szinte nyilvnval, hiszen megtehetjk, hogy egyenknt emeljk le a csillagokat Ekkor pedig indukcival bizonytunk: Legyen a leemelt csillag k zppontja s1 . Mivel a leemels megtartotta V ; s ; s1 pontprjaira a 2- ill 3-l sszefggsget, ezrt csak azokat a vgsokat kell ellenrizni, amelyek az egyik partjukon nem tartalmaznak V ; s ; s1 -bl pontot. Ilyen vgsbl csak kett van, 7 az egyik az fs1 g egy pont vgs, ami ugye 3-fok, a msik pedig az fs s1 g

vgs, amely radsul legalbb 5-fok, hiszen a leemels eltt s-nek ennyi volt a foka. Clunk az, hogy a mr bizonytott 3.2 ttelre hivatkozzunk, de ez csak akkor lehetsges, ha nincsenek a grfban a k-l sszefggsgre vonatkozan kivteles pontok. Az emltett baj orvoslsra hasznos szrevtel, hogy egy leemelt 3-csillag helyettesthet a 3 vgpontja ltal meghatrozott 3-hiperllel. Feltve, hogy G-ben az fa b cg 3-csillagot helyettestve az abc 3-hiperllel a H grfhoz jutunk, tekintsnk H -ban egy olyan ZH vgst, amely elvlasztja az x, y pontokat, melyekre G (x y) k megk ts rvnyes. Amennyiben abc szerepel a ZH vgsban, akkor az ltalnossg megszortsa nlkl feltehet, hogy x a 2 ZH 63 y b c. Ekkor G-ben a ZH -nak megfelel, az fa b cg 3-csillag k zppontjt nem tartalmaz ZG vgs olyan, hogy x, y-t elvlasztja s dH (ZH ) = dG (ZG ). Innen k vetkezik, hogy G (x y) = = H (x y). Ezzel belttuk, hogy a hiperl becserlse megtartja a lnyeges pontprok k z

tti l sszefggst. Az ellenttes irny csere l sszefggst meg rz tulajdonsga is hasonlan lthat. Ezt az eljrst most csak k 4-re alkalmazzuk, mert k = 2 3 esetben a fentiek szerint ez szksgtelen, msrszt csak a (3) egyenltlensg fog k 1-gyel ellentmondst adni, mg a hipergrfokra vonatkoz (5)- s gyengts k 3 k vetkezmnye semmitmond lenne. Megjegyzs. A vzolt egyenrtksg csak a 3-csillag s 3-hiperl k z tt van, egy 4vagy annl nagyobb csillagot a vgpontok ltal meghatrozott hiperlre cserlve romolhat a minimlis vgs mrete. 4.1 Ttel G = (V E ) irnytatlan 2-3 hipergrf, s 2 V pontra nem illeszkedik hurokl s 3-hiperl, d(s) 3p + 2 s minden x y 2 V ; s pontprra k 2. Pontosan akkor j k(x y ) d s ;p . van p darab leemelhet 3-csillag, ha (G ; s) k ; ( ) 2 Bizonyts. k = 2 3 esetben feltehet, hogy a grf nem tartalmaz 3-hiperlt, mert a 3-hiperleket 3-csillagokra cserlve a 2- ill 3-l sszefggsg megmarad A kapott grfban egy j leemels az

eredeti hipergrfban is j a mr lert 3-hiperl  3-csillag egyenrtksg alapjn. Megint a szksgessg beltsa az egyszerbb. Tfh p darab 3-csillag leemelhet s a G grfot kapjuk. A 3-csillagok k zppontjai legyenek s1  : : :  sp , mg a maradk s-bl indul l k z s vgpontja legyen s0 . A 32 ttel bizonytshoz hasonlan most is G -nek azt a vgst vizsgljuk, amit G ; s egy minimlis vgsa s az ltala meghatrozott kisebbik nyalbokban  3  j d(s);3p k j d(s);p k szerepl lek jel lnek ki. Az utbbiakbl legfeljebb p 2 + 2 = 2 sok van, gy k j G ; s-nek legalbb k ; d(s2);p db. l szerepel egy vgsban 0 0 s1 s2 s3 s4 s0 V-s 8 A ttel felttelnek elgsgessgt p-re vonatkoz teljes indukcival bizonytjuk. p = 1-re az llts nem ms, mint a 3.2 ttel Feltesszk, hogy p = 1 2 : : :  (pj0 ; 1)-rek igaz az llts, szeretnnk p0 -ra beltni. Ekkor a felttel szerint (G ; s) k ; d(s)2;p0 Amennyiben p0 db. 3-csillag leemelhet, akkor ezt gy is

megtehetjk, hogy leemelnk egyet (gy kapjuk a G grfot), majd a t bbi p0 ; 1 darabot. Az indukcis felttel miatt ez akkor tehet meg, ha 0     (G ; s) k ; (d(s) ; 3)2; (p0 ; 1) = k ; d(s)2; p0 + 1 0 j (4) k Az egyszerbb rsmd kedvrt a tovbbiakban := d(s)2;p0 jel lssel lnk. (G ; s) > k ; esetn k nny dolgunk van, hiszen az els 3-csillag leemelsekor (G ; s) nem cs kkenhet, gy a (4) felttel automatikusan teljesl. (G ; s) = k ; esetben az els 3-csillag leemelsekor nem csak a k-l sszefggsg megtartsra kell gyelnnk, hanem (G ; s)-t is muszj 1-gyel n velni. Ezen n vels nyomon k vetse cljbl vegyk szemgyre az albbi halmazrendszert: B = fB : B $ V ; s dG;s(B ) = k ;  s ezen tulajodonsgokra B minimlisg 4.2 llt s B elemei diszjunkt halmazok s jBj = 2 vagy jBj = 3 biz. Legyenek X Y 2 B s X Y = 6 . Mivel X Y tovbb nem szkthet legkisebb vgsok V ; s-ben, ezrt X ; Y = 6 s Y ; X =6 . 2 (k ; ) = dG;s (X ) + dG;s (Y ) dG;s (X ;

Y ) + dG;s(Y ; X ) 2 (k ; ) (Az utbbi egyenltlensg (G ; s) k ; miatt igaz.) Azt kaptuk, hogy dG;s (Y ; X ) = k ; , ellenttben X szkthetetlensgvel, gy X Y = kell, hogy legyen. jBj 2 r gt n ltszik, hiszen ha X 2 B, akkor dG;s(X ) = k ; , gy X tartalmaz B-beli elemet. jBj 4 nem lehet, mert felhasznlva, hogy B elemei diszjunktak s X 2 B halmazra dG(X ) k, lthat, hogy X legalbb db. s-bl indul l vgpontjt tartalmazza, gy azon s-bl indul lek szma, amelyek vgpontjai ngy kl nb z B-belibe esnek, legalbb 4 4 d(s)2; p0 ; 2 = d(s) + (d(s) ; 2p0 ; 2) d(s) + p0 > d(s): Ez lehetetlen. Nyilvnval, hogy az els 3-csillag akkor n veli eggyel (G;s)-t, ha G;s legkisebb vgsait lefogja, specilisan a B-beli halmazokat is. Mivel egy legkisebb vgs s az  komplementere tartalmaz B-beli halmazt, ezrt elegend olyan 3-csillagot tallnunk, amely lefogja a B-belieket s leemelse a k-l sszefggsget megtartja. A B-belieket lefog 3-csillagokat lefog-csillagnak

nevezzk. Most is felhasznljuk a 3.2 ttelben bevezetett K s G halmazrendszereket Ismt indirekt bizonytunk, azaz feltesszk, hogy a lefog-csillagokat vagy egy G -beli tartalmazza, vagy legalbb kt vgpontja egy K-belibe esik. Azon lefog-csillagokat, amelyekre ez utbbi 9 nem teljesl, leglis csillagnak hvjuk. F t rekvsnk most is az, hogy olyan G -beli X Y Z halmazokat talljunk, amelyekre k 4-re a 3.2 ttel bizonytsnl is jl bevlt dG(X ) + dG (Y ) + dG(Z ) (5) dG(X Y Z ) + dG (X ; (Y Z )) + dG (Y ; (Z X )) + dG (Z ; (X Y ))+ +dG (X Y Z V ; (X Y Z )) 2-3 hipergrfokra rvnyes egyenltlensg rdemben alkalmazhat ill. k 3-ra ennek ersebb, (3) formja. Ehhez az kell, hogy (5)-ben a dG fggvny argumentumban sehol sem szerepelnek res halmazok. Ekkor k 4 esetben k 4 addna, st, dG (X Y Z ) k + 1 esetn megint k 3 adna ellentmondst. A msik esetben, teht amikor k 3 s nem hipergral dolgozunk, k 1-t kapnnk. Ezen program vgigvitelhez a K G s B

halmazrendszerek viszonyait fogjuk feltrni. 4.3 Lemma Ha Y 2 K s B 2 B s d(B Y s) 1, akkor Y s B nem metszk, vagyis Y  B vagy B  Y . biz. Mi van, ha mgis valdi metszk? d| G;{zs (Y }) + d| G;{zs (B}) k; k;  d| G;s ({z Y ; B}) + d| G;s({z B ; Y }) k; =  k;  Innen azt kapjuk, hogy dG;s (Y ) dG;s (Y ; B ), ahonnan dG (Y ) = k s d(B Y s) 1 miatt ellentmondsul dG (Y ; B ) k ; 1 addik. Megjegyzs. A 43 lemma d(B Y s) 1 felttele felesleges, mert d(B Y s) = 0 esetben k vetkez mdon jutunk ellentmondsra: d| G{z(Y }) + d| G{z(B}) d| G (Y{z; B}) + d| G(B{z; Y }) k= k k k teht dG (B ) dG (B ; Y ) s d(B Y s) = 0 miatt dG;s (B ; Y ) legkisebb vgsok k z tt nem volt szkthet. k ; , viszont B a 4.4 Lemma Ha Y 2 K s X 2 G s d(X Y s) 1, akkor Y  X biz. Pont ugyanaz, mint a 33 llts bizonytsa, csak itt mg egyszerbb X Y 6= V ; s igazolsa, mert X Y sszesen legfeljebb + + 1 < d(s) darab s-bl indul l vgpontjt tartalmazhatja, mert p0

2. 4.5 llt s Nincsen kt olyan B  B 2 B halmaz, amelyekre dG (B ) = dG (B ) = k biz. Indirekt bizonytunk, azaz legyenek B  B 2 B olyan halmazok, amelyekre dG (B ) = = dG (B ) = k. Ekkor B  B 2 K 1 2 1 1 2 1 2 2 2 1 Vegynk egy olyan lefog-csillagot, amelynek a vgpontjai rendre B1  B2 s B1 B2 halmazokba esnek. (Mivel B1 B2 nem tartalmazhatja az sszes s-bl indul l vgpontjt, ilyen lefog-csillag ltezik.) Az gy megvlasztott lefog-csillag egyben leglis is, mert ha kt 10 vgpontjt egy Y 2 K halmaz lefogja , akkor a 4.3 lemma miatt pl B1  Y teljesl, gy d(Y s) + 2, azaz dG;s (Y ) k ; ; 2, ellentmondva (G ; s) k ; -nak. Ezt a leglis csillagot tartalmazza egy X 2 G halmaz, s 4.4 lemma miatt B1  B2  X , azaz d(X s) + +1 + 3, k vetkezskppen dG;s (X ) k ; ; 1# s ez ismt ellentmonds. 4.6 llt s jBj = 2 biz. Feltve, hogy B1  B2  B3 2 B kl nb z halmazok, a 45 llts miatt d(s) d(B1  s) + d(B2  s) + d(B3  s) ( + 1) + ( + 1) + 3 + 2 > 3

d(s)2; p0 > d(s) ami nyilvn lehetetlen. 4.5 llts alapjn feltehet, hogy dG (B1 ) > k, ami ugyanaz, mint d(B1  s) > Megmutatjuk, hogy vlaszthat olyan leglis csillag, amelynek B1 -ben kt vgpontja is van (Nyilvn a harmadiknak B2 -be kell esnie.) Ehhez a k vetkez lemmt kell igazolni: 4.7 Lemma Minden a 2 B ponthoz van b 2 B pont, hogy a b-t nem tartalmazza K-beli halmaz. 1 1 biz. Tegyk fel az ellenkezjt! Ez azt jelenti, hogy van olyan K-beliekbl ll KB1 halmazrendszer, hogy brmely B1 -beli pontprhoz van X 2 KB1 halmaz, amely ket tartalmazza Feltehet, hogy jKB1 j minimlis. A gyakran alkalmazott kikeresztezsi eljrssal megmutatjuk, hogy jKB1 j = 1 Legyen a 2 B1 r gztett. Amennyiben az sszes a b 2 B1 prt ugyanaz az X 2 KB1 halmaz fedi, r gt n kszen vagyunk, hiszen ekkor B1  X . Kl nben van olyan b c 2 B1 pontpr, hogy az a b-t ill. a c-t fed Xb ill Xc halmazok kl nb znek KB1 vlasztsa miatt ez a kt halmaz nem tartalmazkod. Tovbb a 43

lemma miatt Xb  Xc  B1 s termszetesen a 2 Xb Xc Mindezeket sszegezve az addik, hogy Xb s Xc keresztez halmazok, gy az albbi egyenltlensg teljesl rjuk: k + k = dG (Xb ) + dG(Xc ) dG (Xb Xc ) + dG (Xb Xc) k + k R gt n lthat, hogy dG (Xb Xc ) = k, teht KB1 -ben Xb s Xc lecserlhet Xb Xc -re, ellentmondva KB1 megvlasztsnak. gy van olyan K 2 K halmaz, amelyre B1  K . Mivel d(B1  s) > , ezrt d(K s) > , ami nem lehet K 2 K miatt. Ha minden c 2 N (s) B2 ponthoz van olyan C 2 G halmaz, hogy B1  C s c 2 C , akkor kszen vagyunk, hiszen x y z 2 N (s) B2 pontokhoz a megfelel X Y Z 2 G -t kivlasztva olyan halmazokat kapunk, amelyek az (5) egyenltlensghez kvnatosak. Ehhez persze ltni kell, hogy pl. d(X B1  s) + 1 miatt d(X B2  s) 1 s hasonlan d(Y B2  s) 1 d(Z B2  s) 1. Ezen tulajdonsgokbl k vetkezik, hogy x 2 X s x 62 Y Z s az analg lltsok igazak az y s z pontokra. (5)-h z mg az is jl j tt, hogy dG (X Y Z ) k + 1, ami most

azrt igaz, mert B1  X Y Z miatt d(X Y Z s) > . Baj csak akkor van, ha az elbb emltett kzenfekv mdon nem vlaszthatunk X Y Z halmazokat. Hvjuk ezt az esetet nehz esetnek Tovbbi meggyelseket kell tennnk: 11 4.8 llt s Nincsen olyan X 2 K halmaz, amelyre X  B s d(X s) 2 teljesl biz. Ha mgis, akkor legyen fa b cg olyan leglis 3-csillag, amelyre a 2 X b 2 B A 47 lemma szerint ez megtehet. Mivel a nehz esetben vagyunk, c 2 B megvlaszthat gy, hogy az fa b cg csillagot fed C 2 G halmazra B 6 C teljeslj n. A 44 lemma miatt X  C . B  C nem lehet, kl nben d(C s) d(B  s) + d(C B  s) + 3, azaz dG;s (C ) k ; ; 1. Teht C s B keresztez halmazok, azaz d| G;{zs (C}) + d| G;{z B }) + d| G;s(C{z B }) (6) s (B }) d| G;s (C {z 1 1 2 1 2 2 1 2 2 k;  k; 2 k; = 2 k;   egyenltlensg alapjn dG;s (C ) dG;s (C B2 ). Mivel d(C B1  s) 3, az is teljesl, hogy d(C B2  s) d(C s) ; 3. dG (C ) = d(C s) + dG;s (C ) k + 2-bl kapjuk:

dG(C B2 ) = d(C B2 s) + dG;s (C B2 ) d(C s) ; 3 + dG;s (C ) dG (C ) ; 3 k ; 1: Ez lehetetlen. 4.9 llt s Legyen fa b cg leglis-csillag, melynek vgpontjaira a b 2 B , c 2 B Ekkor a megfelel C 2 G halmazra d(C B  s) = 1 teljesl. biz. B  C nem fordulhat el, mert ekkor a b 2 C s d(B  s) miatt d(C s) +2 1 2 2 2 2 lenne. Felhasznlva, hogy dG (C ) = dG;s (C ) + d(C s) k + 2, azt kapjuk, hogy dG;s (C ) = = dG;s (C ) = k ; . Az viszont r gt n ltszik B2  C s B1 C 6= miatt, hogy C nem tartalmaz B-belit, ami ellentmond B dencijnak. Teht B2 6 C B1  C esetn kszen vagyunk, mert d(B1  s) + 1, gy d(C B2  s) 1 szksges d(C s) + 2-h z. Maradk esetben teht B1  B2 6 C , ami annyit tesz, hogy B1 s C keresztezek. (6)-t B2 helyett B1 -re alkalmazva addik, hogy dG;s(C ) dG;s(C B1 ), s d(C B2  s) 2-bl dG(C B1 ) k, teht C B1 2 K. Mivel a b 2 C B1 , ez nem lehet a 48 llts miatt A 4.9 llts megadja a kulcsot az X Y Z halmazok megtallshoz

p0 2 miatt 3, gy r gztve az a b 2 B1 pontokat, B2 -ben van hrom pont  x y s z , hogy az fa b xg, fa b yg s fa b zg csillagok leglisak. A 49 llts miatt az ket fed X Y Z 2 G halmazok a kvnt tulajdonsgak. A 48 llts s a 43 lemma miatt dG (X Y Z ) = k nem fordulhat el. Vgezetl k 4 esetben (5) egyenltlensgbl k 3 eredmnyre jutunk,k 3-ra pedig (3)-bl k 1, ami ellentmonds. j k A 4.1 ttel alkalmazsakor elfordulhat, hogy felttelknt k ; d(s2);p 0 addik Mivel ez nem jelent rdemi felttelt (G;s)-re, ekkor a p db. 3-csillag leemelse biztosan elvgezhet Az elzekben bizonytott 4.1 ttel s Lovsz ttele akr egyszerre is hasznalhat Pldul ha egy s pontbl lprokat s 3-csillagokat egyarnt le kell emelnnk, akkor az ehhez szksges s elgsges felttelt k nnyen megadhatjuk. A 41 ttel akkor is igaz, ha az s-en kvli grf 2-3 hipergrf. J lenne tudni, hogy ez lpr leemelse esetn feltehet-e A 41 bizonytsa sorn alkalmazott technikk

ismtelt bevetsvel k nnyen igazolhat, hogy Lovsz ttele akkor is igaz, ha a grfban vannak s-en kvl 3-hiperlek. Mindez azon mlik, hogy Lovsz ttel bizonytsban hasznlt sszefggsek hipergrfokra is igazak, kivtelt megint a 12 (3) egyenltlensg jelent. k 3 esetn a 3-hiperleket 3-csillagra cserlve, k 4-re pedig a (3) helyett a hipergrfokra vonatkoz (5) egyenltlensget alkalmazva az eredeti bizonyts 2-3 hipergrfokra is mk dkpes lesz. A ksbbiekben Lovsz ttelnek ezen ltalnosabb alakjra fogunk hivatkozni. 4.1 Nhny sz a huroklekrl Htra van mg annak a tisztzsa, hogy ha s pontra illeszkedik hurokl, akkor a (G ; s)-re tett megk ts mikppen vltozik. Azt fogjuk tapasztalni, hogy ekkor egyszer konstrukcikkal a leemelsek elvgezhetek s a (G ; s)-re tett feltteleket sem kell szigortani. Mindezek a meggyelsek a k = 2 3 esetekben is igazak lesznek. A vzolt eljrsoknl az elzekben ltalnostott Lovsz ttelre fogunk tmaszkodni. Jel

lje az s pontra illeszked huroklek szmt h. Kt esetet lehet megkl nb ztetni aszerint, hogy sok vagy kevs hurokl van a leemelni kvnt 3-csillagok szmhoz kpest. 1. eset: 2h < p Mivel egy hurokl legfeljebb 2 darab 3-csillaghoz jrulhat hozz, ezrt legalbb p ; 2h darab olyan csillag van, amely szrai nem huroklekbl szrmaznak. Feltve, hogy a p darab leemels elvgezhet, k vetkezik, hogy elhagyva a h darab huroklt, van p ; 2h darab leemelhet pedigj a 4.1kttel szerint szksges k j 3-csillag. Ennek (d(s);2h);(p;2h) = k ; d(s2);p legyen, ami formjt felttele, hogy (G ; s) k ; 2 tekintve ugyanaz, mint a 4.1 ttel elrsa Az elgsgessg bizonytsa a 2 esethez tartozik. 2. eset: 2h p p = 1 esetn Lovsz ttele garantl egy leemelhet lprt, amely nem huroklekbl keletkezik, feltve, hogy d(s V ; s) 6= 3 1, mert s-bl k 2 miatt nem indulhat elvg l. Ezen lpr k z s pontjt s-sel sszek tve s egy s-re illeszked huroklt t r lve ppen j leemelst kapunk. d(s

V ; s) = 3 esetben a hrom darab nem hurokl k zl tetszleges kettt leemelve, majd k z s vgpontjaikat s-sel sszek tve s egy s-beli huroklt t r lve megint szablyos leemels addik. d(s V ; s) = 1-re mg k nnyebb dolgunk van, hiszen ekkor d(s) 5 miatt kt hurkl is illeszkedik s-re. Ezeknek kt vgt s a nem hurokl s-beli vgt egy j s1 pontba k tve ismt egy j leemelst mutattunk. Feltve, hogy p 2, indukcival bizonytunk, s olyan eljrst adunk, melynek sorn egy vagy kett 3-csillagot emelnk le. A leemels elvgzse utn a megmarad huroklek s a tovbbiakban leemelend 3-csillagok szma alapjn mindannyiszor a 2. esetben maradunk. d(s V ; s) 6 feltevssel lve Lovsz ttele megad 2 darab hurokleket nem tartalmaz leemelhet lprt. Ezeknek k z s pontjait sszek tve s egy s-re illeszked huroklt t r lve ppen kt darab 3-csillag megkvnt tulajdonsg leemelshez jutottunk. A maradk esetekben csak egy leemelst hajtunk vgre. d(s V ; s) = 1 2 3 5-re a p = 1

esetben lertak alapjn jrunk el. d(s V ; s) = 4-re d(s) 8 miatt gy is leemelhetnk, hogy Lovsz ttelvel leemelnk egyy lprt, aminek k z s pontjt egy hurokl t rlse utn s-sel sszek tjk. Mindegyik esetben k nnyen igazolhat, hogy ha mg maradt leemelend 3-csillag, akkor a 2. esetben vagyunk, gy az indukcis bizonytst befejeztk 13 Mint az az elzekbl is lthat, huroklek jelenlte esetn nagyon k nny leemelhet 3-csillagot tallnunk, st, gyakran t bb kzenfekv megolds is knlkozik. A lert eljrsok szndkosan olyanok voltak, hogy leemelt 3-csillag nem tartalmazott huroklt s a grf sszefgg maradt. Ksbbi alkalmazsokkal szmolva ennl ersebb, technikai jelleg k vetelseket is teljesthetnk Ha a leemelsek utn d(s V ; s) az eredetihez kpest cs kkent s s-re mg illeszkedik hurokl, akkor ezen helyzeten javthatunk. Ekkor ugyanis egy si k zppont Sp 3-csillagbl megy l V ; j =0fsj g halmazba. Ezt az lt az si helyett s-be k tve, egy huroklt s-bl

t r lve , majd ssi lt behzva szintn j leemelst kapunk. Mindezek alapjn feltehet, hogy a p darab leemelt 3-csillag nem tartalmaz huroklt, a kapott grf sszefgg maradt s s-re csak akkor illeszkedik hurokl, ha a leemelsek sorn d(s V ; s) nem vltozott. A tovbbiakban mindig ilyen leemelseket tartunk szem eltt %sszefoglalsul megllapthatjuk, hogy 2h < p esetn a 4.1 ttel vltoztats nlkl igaz, 2h p esetben pedig p darab leemels mindig elvgezhet. 5. Alkalmaz sok 5.1 l sszef ggsg n vels fokszm el rssal Adott grfban gy szeretnnk j leket elhelyezni, hogy a kapott grf k-l sszefgg legyen, s minden v 2 V cscsra m(v) j l illeszkedjen, aholXm : V ! N fggvny, amit 6= X  V halmazra a szokott mdon terjesztnk ki: m(X ) := m(x). x2X A k vetkez ttel igaz: 5.1 Ttel G = (V E ) irnytatlan grf, k 2, m : V ! N fggvny Pontosan akkor ltezik H = (V F ) grf, amelyre 8v 2 V : dH (v) = m(v) s G + H = (V E F ) k-lsszefgg, ha (i) 2 j m(V )

(ii) m(X ) k ; dH (X ) minden 6= X  V halmazra. Az ltalnosabb ttel kimondsa eltt a tisztnlts vgett megjegyezzk, hogy az 5.1 ttel ltal garantlt lbvtsben elfordulhat, hogy egy jonnan berakott l hurokl. Ez az l a megfelel cscs fokszm k vetelmnyhez kettvel jrul hozz. 3-hiperleknl is elfordulhatnak hurokszer jelensgek Pldul ha egy j 3-hiperl csak kt kl nb z pontbl ll, de az egyik pontot ktszeres multiplicitssal hasznlja, akkor ez utbbi pont fokszm elrst kettvel elgti ki. Hasonl a helyzet akkor is, ha a hiperl csak egy pontot hasznl hromszoros multiplicitssal Ebben az esetben a pont fokszmhoz a hozzjrulsa hrom Ezeket a konvencikat nem elfelejtve ltalnostjuk az elz ttelt: 5.2 Ttel G = (V E ) 2-3 hipergrf, k 2, m : V ! N fggvny Pontosan akkor van p db 3-hiperlt tartalmaz H = (V F ) grf, amelyre 8v 2 V : dH (v) = m(v) s G + H = (V E F ) k-lsszefgg, ha (i) 3p m(V ) (ii) 2 j m(V ) ; 3p (iii) m(X ) k ;j dH

(X ) kminden 6= X  V halmazra (iv) (G) k ; m(V2);p . 14 Bizonyts. Az (i) felttel azt mondja ki, hogy az j 3-hiperlek fokszm ignye kisebb, mint a teljes fokszm kszlet, (ii) pedig azt, hogy a nem 3-hiperlek fokszm ignyeinek sszege pros. Mindezek trivilisan szksgesek (iii) annyit jelent, hogy egy adott hinyos, azaz k-nl kisebb fok halmaz k-fokv tehet olyan lek behzsval, amelyek a halmazon belli fokszm elrst nem haladjk meg. Ez is elengedhetetlen felttel (ii) miatt (iv)-ben az egszrsz akr el is hagyhat, s ekkor (iv) gy is rhat, hogy (G) k ; m(V2);3p + p . Ez a felttel nyilvnvalan szksges, hiszen a zrjelen belli kifejezs a felhasznlt j lek szma, s egy j l behzsa legfeljebb eggyel n velheti az l sszefggsget. Az elgsgessg bizonytshoz adjunk a grfhoz egy j s pontot, amelybl minden egyes addigi v 2 V ponthoz m(v) db. lt hzunk A kapott grfban minden 6= X  V halmaz foka d(X ) + m(X ) lesz, ez (iii) miatt legalbb

k. Ezek szerint olyan grfhoz jutottunk, amelyre alkalmazhat a 41 ttel, melyk j m (V );p szerint az s pontbl p db. 3-csillag leemelhetsgnek a felttele, hogy (G) k ; 2 legyen, amit (iv) biztost. A leemelt 3-csillagokat 3-hiperlekre cserljk A maradk leket Lovsz ttelvel pronknt leemelve megkapjuk a fokszm elrt bvts nem hiperleit. A konstrukcibl lthat, hogy a bevett lek eleget tesznek a fokszm elrsnak. 5.11 Egy eszttikai igny kielgtse Jogos elvrs lehet, hogy a bvtsben szerepl lek ne legyenek elfajulak, azaz ne forduljon el k z ttk hurkold l. Ez egy jabb felttelt k vetel az 52 ttelben, ami trivilisan szksges, de nem nyilvnvalan elgsges. Ez a felttel alkalmas lesz arra is, hogy lerja azokat a grfokat, amelyekre a 4.1 ill Lovsz ttel ltal biztostott teljes leemelsek akr olyanok is lehetnek, hogy egy leemelt 3-csillag ill. lpr vgpontjai kl nb zek Lssuk a medvt! 5.3 Kiegszts Amennyiben az 52 ttel felttelein

kvl mg az is igaz, hogy (v) minden v 2 V pontra m(v) m V ;p , ( ) 2 akkor az 5.2 ttel ltal garantlt fokszm elrt bvts megvlaszthat olyannak is, hogy az j lek ne hurkoldjanak. biz. Mr lttuk, hogy m(V2);p ppen az j lek szma Feltve, hogy egy pontnak ennl nagyobb az ignye, egy szablyos bvtskor mindenkppen lesz egy olyan l, amelyik erre a pontra hurkoldik, azaz t bbsz r sen hasznlja. Nem ennyire k nny az elgsgessg megmutatsa. Beltjuk, hogy ha egy bvts tartalmaz hurkold lt, akkor a bvts sorn bekerlt lek sszs lya n velhet, ahol egy l s lya az ltala hasznlt kl nboz pontok szma. A bvtett grfot G jel li Legyen f egy olyan hurkold l, amely az a pontot t bbsz r is hasznlja. (v) miatt van a bvtssel bevett lek k z tt az a pontot elkerl l. Legyen ez g, melynek az egyik cscsa c &gyes cserket hajtunk vgre: Az f l multiplicitst az a ponton eggyel cs kkentjk s a c ponton eggyel n veljk. A fokszm elrs betartsa

vgett az f lnek a multiplicitst a c-n eggyel cs kkentjk, az a-n pedig eggyel n veljk. A G1 grfhoz s f1, g1 lekhez jutottunk Ha f s g valamelyike egy pont volt, akkor k nnyen ellenrizhet, hogy nincsen olyan vgs, aminek az rtke cs kkent volna, azaz G1 k-l sszefgg. Ellenkez esetben az f s g l ktkt kl nb z pontot is hasznl. A mg el nem nevezett pontok legyenek b, ami az f lhez s d, ami a g lhez tartozik 0 0 0 15 Ha g nem hurkold 3-hiperl, akkor mg tartalmaz egy e pontot. Feltesszk, hogy a csere sikertelen volt, azaz van olyan X vgs, amelynek rtke k al esett. G’ e g d c f b a G’2 G’1 e e Y c c d g1 g2 d f2 X f1 a b a b X vgs rtke csak akkor cs kkenhetett, amikor a g l multiplicitst a c-n cs kkentettk. Ez azt jelenti, hogy X a c pontot a d s e pontoktl elvlasztja. Amikor a-t a g-hez adtuk, az X vgs rtke nem n vekedett, ezrt az a s d pontokat az X nem vlasztja el. Ezek utn mg ltni kell, hogy X az

a s b pontokat elvlasztja, mert kl nben a konstrukci miatt dG (X ) = dG1 (X ) < k lenne, ami tagadja G k-l sszefggsgt. Esetleges komplementlssal mindezek alapjn feltehet, hogy c b 2 X 63 a d e. Prbljunk ki G -n egy msik javtsi eljrst, ami az elztl csak abban kl nb zik, hogy a c s d pontok szerept felcserljk. G2 -h z jutunk Ha ez sem j, akkor G2 -ben van egy Y vgs, amely rtke k al esett s az elz gondolatmenet alapjn b d 2 Y 63 a c e. Az X s Y vgsok rtke az egyes eljrsok sorn legfeljebb eggyel cs kkenhetett, teht dG1 (X ) = dG2 (Y ) = k ; 1, azaz dG (X ) = dG (Y ) = k. Legyen G;f az a grf, amelyik G -bl az f l elhagysval keletkezik. gy (G;f ) = k ; 1 s dG f (X ) = dG f (Y ) = k ; 1 X s Y az a b c d e ismertetett elhelyezkedse alapjn keresztez, ezrt dG f (X Y ) = = k ; 1. No de az f l elkerli X Y -t, ami miatt dG (X Y ) = k ; 1 < k, meghazudtolva G k-l sszefggsgt. Ez utbbi eredmny rmutat arra is,hogy

a 4.1 ttelben megadott grfokban mikor lehet olyan teljes leemmels, amelyikben minden leemelt csillagra teljesl, hogy a vgpontjai kl nb zek. Az egysges szhasznlat miatt egy leemelt lprt is csillagnak teekintnk  2-csillagnak , s egy teljes leemels olyan leemelst jelent, ahol az s pont 2- s 3-fok cscsokra bomlik. A 41 s Lovsz ttelnek szintzisbl, valamint az 53 kiegsztsbl a k vetkez ttel nyilvnval: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ; ; 0 ; 0 0 16 5.4 Ttel G = (V E ) 2-3 hipergrf, s 2 V pontra nem illeszkedik hurokl s 3-hiperl, d(s) = 3p + 2b s minden x y 2 V ; s pontprra (x y) k 2. Pontosan akkor van p 3-csillagot s b lprt tartalmaz teljes leemels, amelyben minden egyes leemelt csillag klnbz vgpontokatjhasznl, k ha d (s);p (i) (G ; s) k ; 2 (ii) Minden v 2 V pontra d(v s) b + h. 5.2 l sszef ggsg n velse adott szm llel lpr leemelssek segtsgvel vlaszolhat meg az a krds, hogy adott grf hny j

l hozzadsval tehet k-l sszefggv . Az idevg ttel kimondshoz szksgnk van egy dencira: 5.5 Denci fX1  : : :  Xt g halmazrendszer a V halmaz rszpartci ja, ha 6= Xi  V minden i-re s Xi Xj = i 6= j . 5.6 Ttel (Watanabe-Nakamura 6]) k 2 esetn egy G = (V E ) irnytatlan grf pontosan akkor tehet  l hozzvtelvel k-lsszefggv, ha 2 X i (k ; d(Xi )) V minden fX1  : : :  Xt g rszpartcijra. Ezt a ttelt kl n nem bizonytjuk, hanem r gt n a 2-3 hipergrfokra vonatkoz ltalnostst ltjuk be. A bizonytsbl egyszeren kiolvashat Watanabe-Nakamura ttelre adhat standard bizonyts. 5.7 Ttel G = (V E ) 2-3 hipergrf pontosan akkor tehet  j l s p j 3-hiperl hozzadsval k-lsszefggv (kk 2), ha j 2 +3p;p = k ; ( + p) (i) (G) k ; 2 X (ii) 2 + 3p (k ; d(Xi )) minden V -beli fX1  : : :  Xt g rszpartcira. i Bizonyts. Tudjuk, hogy egy j l hozzvtelvel a grf l sszefggsge legfeljebb eggyel n vekedhet, tovbb

egy 3-hiperl illetve egy (2-hiper)l legfeljebb 3 illetve 2 diszjunkt hinyos halmaz fokszmhoz jrulhat hozz. Ezek szerint az (i) s (ii) felttelek szksgesek Az elgsgessg bizonytst az 5.2 ttelre szeretnnk visszavezetni m : V ! N legyen olyan fggvny, amelyre m(V ) minimlis s minden 6= X  V halmazra k ; d(X ) m(X ): 5.8 Lemma m(V ) 2 + 3p Bizonyts. Egy X  V halmazt pontos halmaznak hvunk, ha k ; d(X ) = m(X ) m-t gy v- lasztottuk, hogy minden v pontot, ammelyre m(v) > 0, tartalmaz egy pontos halmaz. Ezeknek a v pontoknak megfeleltetjk a legszkebb, v-t tartalmaz Yv pontos halmazt. Megmutatjuk, hogy fYv : m(v) > 0g laminris halmazrendszer. Legyen Yu , Yv kt metsz halmaz Ekkor 17 m(Yu ) + m(Yv ) = k ; d(Yu) + k ; d(Yv ) k ; d(Yu ; Yv ) + k ; d(Yv ; Yu) m(Yu ; Yv ) + + m(Yv ; Yu ) = m(Yu ) + m(Yv ) ; 2m(Yu Yv ) m(Yu ) + m(Yv ). Teht az egyenltlensgek egyenlsggel teljeslnek, azaz m(Yu Yv ) = 0 s Yu ; Yv valamint Yv ; Yu pontos halmazok.

Mindez rcfol Yu s Yv vlasztsra Vegyk szemgyre az fYi g halmazrendszer maximlis X1  : : :  Xt tagjait! Ezek lefedik az sszes v pontot, amelyre mP (v) > 0 s a laminarits miatt diszjunktak. gy a (ii) felttel P alapjn m(V ) = i m(Xi ) = i (k ; d(Xi )) 2 + 3p. Amennyiben m(V ) < 2 +3p, egy v ponton n veljk meg m(v) rtkt annyira, hogy hogy m(V ) = 2 + 3p legyen. Ekkor az 52 ttel minden k vetelmnye teljesl, gy a garantlt H grfnak ppen  le s p 3-hiperle van. Most k nnyen biztosthat, hogy az j lek k z tt ne legyenek hurkold lek, mert a fokszmok elrsnak hinya miatt egy hurkold l kicserlhet olyan lre, amelyik t bb cscsot hasznl, feltve, hogy jV j 3. Watanabe-Nakamura ttelnek ekvivalens formja a k vetkez: 5.9 Ttel Azon lek minimlis szma, melyek hozzadsval G = (V E ) k-lsszefggv tehet, nem ms, mint P  ( k ; d ( X )) i i max : 2 fXi ga V rszpartcija Tegyk fel, hogy most kizrlag 3-hiperleket szeretnnk a

bvts sorn felhasznlni. Ekkor az 5.7 ttel alapjn egy jabb ttel addik: 5.10 Ttel G = (V E ) 2-3 hipergrf k-lsszefggv ttelhez szksges 3-hiperlek minimlis szma P    ( k ; d ( X )) i i max max  k ; (G) : fXi ga V 3 rszpartcija 5.11 Ttel G = (V E ) irnytatlan 2-3 hipergrf, s 2 V cscsra nem illeszkedik hurokl s 3-hiperl s minden x y 2 V ; s pontprra (x y) k 2. Feltve, hogy d(s) = d + d + + : : : + dt , ahol 2 di 2 N 8i pontosan akkor emelhet le s-rl egy d -csillag s egy d -csillag 1 : : : s egy dt -csillag, ha 1 (G ; s) k ; X i 2 2  di : 2 Bizonyts. A szksgessget a 32 s 41 ttelek bizonytsban mutatott gondolatmenet itt is igazolja. Az elgsgessg megmutatsa az eddigiek utn nem okoz nehzsget. Feltehet, hogy 2 - di , ha i p s 2 j di , ha p < i t. A ttel felttele mskppen felrva: P   d ; p d ( s ) ; p i i (G ; s) k ; 2 = k ;  2 ahol az egszrsz kirsa puszta formalits. Jl ltszik, hogy a 41

ttel alkalmazhat, azaz p db. 3-csillag leemelhet A 3-csillagokat 3-hiperlekre cserlve a maradk s-bl indul 18 pros sok lt a 2-3 hipergrfokra vonatkoz Lovsz ttellel prokba rendezzk s leemeljk. A hiperlek behozatalra csak a Lovsz ttel alkalmazhatsga miatt volt szksg, ezrt ez a lps igazbl felesleges. Az i-edik leemelt 3-csillag k z s pontjt di2;3 leemelt lpr k z s pontjval sszehzva kapjuk a leemelt di -csillagot i p-re, mik zben a grf l sszefggsge nem cs kkent. i > p esetben pedig csak d2i db leemelt lpr k z s pontjt kell sszehzni a keresett di -csillag megkonstrulshoz. P j k Most is igaz, hogy ha k ; i d2i nem pozitv rtk, akkor ez nem jelent semmifle megk tst a (G ; s) rtkre. Ekkor a t db d1 -, d2 -, : : : dt -csillag leemelse elvgezhet (persze ez nem jelenti azt, hogy tetszleges leemels j is lesz). A huroklekre vonatkoz 41 fejezetbeli megjegyzsek alapjn, ha s-re illeszkednek huroklek, akkor csak olyan

leemelseket vesznk gyelembe, amelyben csak az s1 k zpponttal rendelkez leemelt csillagra illeszkedhet S hurokl, de r is csak akkor, ha dG (s1  V ; ti=1 si ) = dG (s V ; s), ahol G a leemelsek elvgzsvel keletkezett grfot jel li. Ez esetben 511 gy mdosul, hogy h db s-re illeszked hurokl esetn a csillagok leemelsei a (G ; s)-re tett felttelek nlkl is elvgezhetek, ha 2h p. 0 0 6. Sztszedsek Az 5.11 ttel ltalnostja a 32 s 41 tteleket Alkalmazsval olyan ismert erdmnyekre adhatunk j bizonytst, amelyeknl Lovsz ttele nem hasznlhat Nash-Williams t bb cikkben is foglalkozik grfok sztszedsvel 5]. G = (V E ) grfban egy v 2 V cscs sztszedse nem ms, mint a v cscsot helyettestnk a v1  : : :  vt cscsokkal, s minden v-re illeszked lt a v1  : : :  vt cscsok valamelyikbe k tjk. Huroklekbl ezltal keletkezhetnek nem huroklek. Legyen g : V ! N egy fggvny A D grf a G gr fnak a g-sztszedse, ha D elll a G cscsainak olyan

sztszedsvel, ahol a G minden v cscsa g(v) j cscsra bomlik. Amennyiben az is adott, hogy (d(v1 ) : : :  d(vt )) = (v1  : : :  vt ) = v (vi 2 N X i vi = g(v)) legyen, akkor fv : v 2 V g a G-nek g-foksz m specik ci ja s a denilt sztszeds a G fv : v 2 V g-sztszedse. Ebben a terminolgiban elemi grfelmleti ttelek fogalmazhatak jra. Euler ttele alkalmas megsz vegezsben gy szl: 6.1 Ttel (Euler) G = (V E ) grfnak pontosan akkor van sszefgg sztszedse melyben minden v 2 V cscs d v db. 2-fok pontra oszlik, ha G sszefgg s 2 j d(v) (8v 2 V ) ( ) 2 A megfogalmazs t bb ltalnostsi lehetsget sugall: Mi a szksges s elgsges felttele annak, hogy G-nek legyen olyan k-l sszefgg sztszedse, hogy v 2 V cscs adott szm, megadott fok cscsra bomlik? k = 1-re vonatkoz ttelt bizonyts nlkl k z ljk: 6.2 Ttel (Nash-Williams 5]) G = (V E ) grfnak pontosan akkor van sszefgg g-sztszedse, ha minden X  V halmazra 19 g(X ) +

c(G ; X ) d(X V ) + 1 ahol c(G ; X ) az X elhagysval ltrejtt grf komponenseinek szma, d(X V ) pedig azon lek szma, amelyek X -beli pontot V -belivel ktnek ssze. A bizonyts Edmonds matroid metszet ttelt hasznlja ki. k 2-re a felttel s a bizonyts is ms. A ttelt most 5]-tl eltr, az eddigi leemelsi eredmnyeket kihasznal bizonytssal mondjuk ki: 6.3 Ttel (Nash-Williams) G = (V E ) irnytatlan grf, jV j 2 s k 2 egsz szm. G-nek pontosan akkor van k-lsszefgg g-sztszedse, ha G maga is k-lsszefgg s d(v) k g(v) minden v 2 V cscsra, s nem fordulnak el a kvetkez esetek: (i) k pratlan s G-nek van egy v elvg cscsa, hogy d(v) = 2k s g(v) = 2. (ii) k pratlan s jV j = 2, jE j = 2k, G-ben nincsenek huroklek s g(v) = 2 8v 2 V . Tovbb ha G k-lsszefgg, d(v) k g(v) minden v 2 V cscsra s az (i) s (ii) esetek nem fordulnak el, s ha fv : v 2 V g olyan g-fokszm-specikcija G-nek, hogy minden v-re v minden tagja k, akkor G-nek van

k-lsszefgg fv : v 2 V g-sztszedse. Bizonyts. Ha G-nek valamely sztszedettje k-l sszefgg, akkor G is az kell, hogy legyen A g-re ill.  -ra tett elrsok is szksgesek, mert k-l sszefgg grf minden cscsa legalbb k-fok. Megmutatjuk, hogy (i) esetben a G grfnak nincsen k-l sszefgg g-szteszedse. A v pont elhagysval a grf A, B sszefgg komponensekre esik. Azrt nem t bbre, mert a k-l sszefggsg miatt d(A s) k s d(B s) k, s v-nek csak 2k a foka. Ebbl az is k vetkezik, hogy v-re nem illeszkedik hurokl Szedjk szt a v pontot teszlegesen a k-fok v1 s v2 pontokra. A s B a v1 -bl s v2 -bl indul leket ktkt nyalbba sorolja Vegyk a v1 -hez tartoz kisebbikben s a v2 -h z tartoz kisebbikben szerepl leket. k pratlansga miatt k-nl kevesebb lt vlasztottunk ki, melyek elhagysval a grf sztesik. Teht a sztszedssel kapott grf nem lehet k-l sszefgg. v1 v A B A v2 B (ii) esetben a grf egyik pontjt sztszedve 3 cscs grfot

kapunk, s az egyik cscs olyan lesz, amelyre (i) teljesl, teht itt sincs g-sztszeds. Az elgsgessg igazolshoz induktv eljrst mutatunk. Vesszk a grfnak az egyik v cscst s sztszedjk a v elrsnak megfelel fok cscsokra. Mindezt gy csinljuk, hogy k-l sszefgg grfot kapjunk, amire (i) s (ii) nem teljesl. Kezdetben azokat a v cscsokat szedjk szt, amelyekre d(v) = 2k s g(v) = 2. Ha egy ilyen v cscs v1 s v2 -re t rtn sztszedse utn keletkezik egy elvg 2k-fok w cscs, akkor javtunk. A sztszeds utn a G grfhoz jutunk, mely w elhagysval az A s B sszefgg komponensekre bomlik, s a v1 -bl indul sszes l az A-ban, a v2-bl indulk pedig a B -ben vgzdnek. A G grfot gy mdostjuk, hogy az egyik v1 -bl indul e lt v1 0 0 20 helyett v2 -be k tjk, mg egy msik tetszleges v2 -bl indul f lt v2 helyett v1 -be k tnk. Azt kne beltni, hogy az gy barkcsolt G grf k-l sszefgg s nem tartalmaz 2k-fok  elvg pontot, amelyre g() =

2. 6.4 llt s G k-lsszefgg biz. Tfh G tartalmaz egy X vgst, amelyre dG (X ) < k Az A halmazt az X vgs nem vgja kett, mert ha mgis kett vgn, akkor tekintsk G -nak azt a fesztett rszgrfjt, melyet az A halmaz s a v1 , w pontok fesztenek. Vegyk mg ehhez a grfhoz a G -beli e s f leket, valamint az f B -beli vgpontja s v2 k z tt vezet B -beli P utat. Mivel B fesztett rszgrfja sszefgg, ezrt ilyen P t van. A kapott grfban az e , f s P latal alkotott utat lecserlve a v1 -t e A-beli vgpontjval sszek t lre egy olyan GA grfot kapunk, amelyet az X halmaz elvg, s dGA (X ) < k. Vegyk szre, hogy ez azrt lehetetlen, mert GA izomorf a G -ben lv, a w s v1 pontok valamint az A ltal fesztett rszgral. Ez pedig k-l sszefgg, mert egy k-l sszefgg grfban egy elvg pont elhagysval keletkezett komponens s az elvg pont k-l sszefgg grfot feszt.   0 v v1 v2 e G A w B A v1 v2 f* f G’ B e* G* A w P B w X nem

vghatja kett a B halmazt sem az elbbi gondolatmenet miatt. Az sem lehet, hogy az X a w pontot elvlasztja az A s B halmazok valamelyiktl, mert ekkor pl. k > > dG (X ) dG (w A) k lenne. gy az X halmaz vagy a komplementere a fv1 g, fv2 g, fv1  v2 g halmazok k zl kerlhet ki. Ez a hrom halmaz viszont lthatan semmikppen sem kisebb fok, mint k, s ez megint ellentmonds.   6.5 llt s G -ban nincsen olyan elvg  pont, amelyre dG () = 2k s g() = 2  Bizonyts. Kihasznlva, hogy A s B fesztett rszgrfjai sszefggek, a konstrukci miatt w, v1 s v2 egyike sem lehet elvg pont. Mivel az A s B ltal fesztett rszgrfok sszefggek, ezrt a w s v1 k z tt kt pontdiszjunkt t is van. Ugyanez igaz a w, v2 pontprra Ezek szerint G egy  elvgpontjt elhagyva a w, v1 s v2 pontok egy komponensbe kerlnek. Emiatt a v1 s v2 pontokat egy pontt sszehzva semelyik kt komponens sem egyesl, azaz  mr G-ben is 2k fok elvg pont volt, ami ellentmond az indukcis

feltevsnek. Vgezetl azt kell megmutatni, hogy a 2k-nl nagyobb fok pontok sztszedhetek a k-lsszefggsg megtartsval. Mivel a 2k fok pontok sztszedsn tl vagyunk, a maradk pontok sztszedse utn nem kerlhetnk az (i) vagy (ii) ltal jellemzett bajos esetekbe. Vlasszunk egy 2k-nl nagyobb fok s pontot, s az 5.11 ttel felhasznlsval emeljnk le rla a g-fokszm-specikci ltal meghatrozott mret csillagokat! Ennek felttele, hogy (G ; s) k ; 21 t  i X  s i=1 2 P s (G ; s) rtelmezhetsge miatt jV j 3 legyen. Mivel si k 8i s i si = d(s) > 2k, ezrt a felttel jobb oldala 0, teht az 5.11 ttel ltal garantlt leemelsek elvgezhetek jV j = 2-re k nnyen ellenrizhet, hogy mivel nem az (i) eset ll fent, ezrt az egyik cscs sztszedhet gy, hogy ne jussunk a (ii) bajos esetbe. Egyenknt leemelve a csillagokat mindig k-l sszefgg grfhoz jutunk, mert egy X vgs vagy elvlaszt kt V ; s-beli pontot s ekkor az 5.11 ttel miatt X legalbb

k-fok, vagy pedig X , esetleg a komplementere az fs1 g, fs2 g, fs1  s2 g halmazok valamelyike. Felhasznlva, hogy s minden tagja k-nl nagyobb s gyelembe vve az 5.11 ttel bizonytsa utn a huroklekkel kapcsolatos megjegyzst, k nnyen lthat, hogy X legalbb k-fok. Ezzel a bizonytst befejeztk. 7. Sejtsek Lovsz ttelnek ltezik komoly ltalnostsa is, melyet Mader bizonytott: 7.1 Ttel (Mader 3]) G=(V,E) irnytatlan grf, s 2 V pontra nem illeszkedik elvg l s d(s) = 6 3. Ekkor s-nl van olyan leemelhet lpr, hogy a leemelsvel elll G grfban G (x y) = G (x y) 8x y 2 V ; s. 0 0 Ezek szerint nem csak a globlis, hanem a loklis l sszefggsget is meg lehet tartani egy lpr leemelsvel. Msik rzkletes pldja a globlis s loklis ttelproknak Nash-Williams kt irnytsi ttele : 7.2 Ttel (Nash-Williams gyenge irnytsi ttele 4]) G = (V E ) irnytatlan 2k-lssze! fgg grfnak van k-lsszefgg G irnytsa. 7.3 Ttel (Nash-Williams

ers irnytsi ttele 4]) G = (V E ) irnytatlan grfnak van j k ! olyan G irnytsa, melyre G (x y) ! G (xy) 2 . Mader s Nash-Williams loklis ttelei az R(X ) := maxf(x y) : x 2 X 63 yg (X $ V ) fggvny vizsglatval bizonythatak hatkonyan (1]). R legfontosabb tulajdonsga a ferde szupermodularits, azaz X Y $ V halmazokra R(X ) + R(Y ) R(X Y ) + R(X Y ) vagy R(X ) + R(Y ) R(X ; Y ) + R(Y ; X ) teljesl. A 3-csillag leemelsekre is megfogalmazhat loklis vltozat: 7.4 Sejts G = (V E ) irnytatlan 2-3 hipergrf, s 2 V , d(s) 3p + 2, s s-re nem illeszkedik 3-hiperl s hurokl. Pontosan akkor van p db leemelhet 3-csillag, amelyek leemelse a loklis lsszefggsget x y 2 V ; s pontprokra megrzi, ha   d ( s ) ; p G;s(x y) G (x y) ; : 2 22 Eme sejtsbl s Mader ttelnek felhasznlsbl k vetkezik az albbi sejts. Az 511 ttel bizonytsban mutatott mdon csak Mader ttele s a 7.4 sejts ltal biztostott lprokat s 3-csillagokat kne

a di -csillagok megkonstrulshoz felhasznlni Ezek alapjn az elz sejts ekvivalens a k vetkezvel. 7.5 Sejts A G = (V E ) 2-3 hipergrf egy s 2 V pontjra nem illeszkedik elvg l s 3-hiperl, d(s) = d + : : : + dt , 2 di 2 N 8i. Akkor s csak akkor szedhet szt az s pont 1 d1 -, : : : ,dt -fok csillagokra a tbbi pontprra vonatkoz loklis lsszefggsg megtartsval, ha X  di  (8x y 2 V ; s):  (x y)  (x y) ; G;s G i 2 Mindkt sejts szksgessgt a mr t bbsz r hasznlt vgsmegvlasztssal lehet igazolni. Mivel Mader ttele a loklis l sszeggsget rzi meg, ezrt nem baj, hogy 2-3 hipergral llunk szemben, mert Mader ttel alkalmazshoz a 3-hiperleket 3-csillagokra cserljk, s az lpr leemelsek elvgzse utn ket visszacserljk. Mint lttuk, ez az l sszefggsre nincs kedveztlen hatssal. Az s-re illeszked h db hurokl esetn az eddigiekkel sszhangban mondhatjuk, hogy 2h < p-re a k z lt sejtsek nem vltoznak. 2h p esetben a leemelsek

biztosan elvgezhetek, mert a 4.1 fejezetben vzolt konstrukcik most is alkalmasak, ha Lovsz ttele helyett Mader ttelt alkalmazzuk. Irodalom 1] A. Frank: Applications of submodular functions, Report No 93806 Research Institute for Discrete Mathematics, Institute for Operation Research, University of Bonn 1993. 2] L. Lovsz: Combinatorial Problems and Exercises, North-Holland 1979 3] W. Mader: A reduction method for edge-connectivity in graphs, Ann Discrete Math, Vol.3, 1978, pp 145-164 4] C. St J A Nash-Williams: On orientations, connectivity and odd vertex pairings in nite graphs, Canad. J Math, Vol12, 1960, pp 555-567 5] C. St J A Nash-Williams: Connected detachments of graphs and generalized Euler trails, J. London Math Soc, Vol31, 1985, pp 17-29 6] T. Watanabe and A Nakamura: Edge-connectivity augmentation problems, J Comp System Sci., Vol35, 1987, pp 96-144 23