Matematika | Felsőoktatás » Szalkai Ákos - Keresés matroidokban

Keress matroidokban Szakdolgozat Szalkai kos Tmavezet: Katona O. H Gyula 1996. 2 Tartalom 1. Keress 1.1 Dencik 1.11 Keressi feladatok 1.12 D ntsi f k 1.2 Keress az F = f0 1 : : : q ; 1gS esetben 1.21 A legrosszabb eset 1.22 tlagos eset 1.3 Nemadaptv algoritmusok 1.4 J tkelmleti megk zelts 1.5 Bin ris keress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A feladat . Als korl t . Algoritmus . Alkalmaz sok . 3.41 Keress legfeljebb k elem kereshalmazokkal 3.42 Egy egyszer

speci lis eset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Matroidok 2.1 Dencik 2.11 Pld k matroidokra 2.2 A rangfggvny 2.3 Polimatroid fggvnyek 2.4 Rado ttele s k vetkezmnyei 2.5 Matroidok partcis algoritmusa 3. Keress matroidokban 3.1 3.2 3.3 3.4 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 8 10 10 12 18 19 21 25 25 26 28 30 32 35 37 37 39 41 44 44 45 4 1. Keress 1] 1.1 Dencik 1.11 Keressi feladatok Mieltt pontosan deni ln nk, hogy mit fogunk keress alatt rteni, tekintsnk nh ny mindenki ltal ismert klasszikus pld t. Termszetesen olyan dencit szeretnnk majd, amelybe az al bbiak mindegyike beletartozik. 1. Tal n a legk zismertebb keressi feladat a Barkochba j tk 2. Egy m sik rgrl ismert problmak r a hamis rme keresse Ennek t bb v ltozata is ltezik. Az alapv ltozatban azt tudjuk, hogy n rme k z tt pontosan 1 hamis van, r ad

sul ez k nnyebb, mint a t bbi, melyek egyforma t megek. Ezek ut n egy ktkar mrleg segtsgvel kell a lehet legkevesebb mrssel megtal lni a hamis rmt. Ebbl az egyszer problm bl egyszeren kaphatunk jval nehezebbeket is, ha t bb hamis rme is van, illetve, ha nem tudjuk elre, hogy a hamis rme k nnyebb, vagy nehezebb8, 9]. E problma egy m sik, lnyegesen kl nb z v ltozat t kapjuk, ha van nh ny egyforma t meg valdi rmnk s nh ny, ugyancsak egyforma t meg hamis rmnk, r ad sul ismerjk is ezeket a t megeket. Most egy egykar (azaz a t lk j ba tett rmk sszt megt jelz) mrleg segtsgvel kell minl kevesebb mrssel meghat rozni a hamis pnzeket. 3. Az elzekkel ellenttben egy komoly gyakorlati jelentsg feladat a k vetkez: adott egy line risan rendezett sorozat s egy a sorozat tagjaival sszehasonlthat elem. A lehet legkevesebb sszehasonlt s elvgzsvel tegyk a helyre az elemet a sorozatban 4. A k vetkez problma tal n kevsb k zismert, pedig

t rtnetileg az els matematikailag vizsg lt keressi feladat 2]: a lakoss gbl nh ny 5 embert megfertz tt egy betegsg, amelyet vrvtel ut n k ltsges vizsg lattal lehet csak kimutatni. Ezrt a k vetkez tesztet alkalmazzuk: egy ltalunk kiv lasztott csoport tagjaitl vett vrt ssze ntjk, s az gy kapott mint ra csak egyszer elvgezve a vizsg latot, meg llapthatjuk, hogy a vizsg lt csoportban fertz tt volt-e valaki. A clunk a szok sos: a lehet legkevesebb ilyen teszt felhaszn l s val elkl nteni a fertz tteket. L that, hogy a fenti pld k mindegyikben egy adott alaphalmazon kell megtal lnunk egy vagy t bb ismeretlen elemet, bizonyos megengedett tesztek segtsgvel. Mindezek alapj n k nnyen addik az ltal nos denci: 1. De n ci Legyenek S 6=  egy adott halmaz (a keress alaphalmaz a), benne egy r gztett x 2 S elem tov bb F egy S -en rtelmezett fggvnycsal d. F elemeit keresfggvny eknek nevezzk Az els lps sor n krdsknt kiv laszthatunk egy f1 2 F

keresfggvnyt, amire v laszul f1(x )-ot kapjuk. A k vetkez lpsekben m r az addig kapott v laszok gyelembevtelvel v laszthatunk j keresfggvnyeket Az f1 f2 f3  2 F fggvnyek egy olyan sorozat t, melyre az f1(x ) f2(x ) f3(x ) : : : rtkek egyrtelmen meghat rozz k x -ot, (sikeres) keresalgoritmus nak nevezzk. (Hallgatlagosan mindig feltesszk, hogy legal bb egy ilyen algoritmus ltezik) Vgl, az (S F ) rendezett p rt keressi feladat nak hvjuk. Meg llapodunk abban, hogy b r a k-adik keresfggvny (fk 2 F ) kiv laszt sa fgg a az elzleg kapott f1(x ) f2(x ) f3(x ) : : : rtkektl, legt bbsz r mgis az ezt nem tkr z (f1 f2 f3 : : : ) jel lst fogjuk alkalmazni a keresalgoritmusokra. A szok sos mdon deni lhatjuk a kl nb z keressi bonyolults gokat is, vges S alaphalmaz s F keresfggvny-csal d mellett. 2. De n ci Tegyk fel, hogy adott egy L(S F ) keressi feladat, s ehhez egy A = (f1 f2 : : : ) sikeres keresalgoritmus, azaz amelyre a kapott f1(x )

f2(x ) : : : fl(x )(x ) rtkek egyrtelmen meghat rozz k x -ot. Ekkor a ! termszetesen x -tl fgg ! l(x ) sz mot az x (A algoritmus melletti keressi) hossz nak nevezzk, L(A) := max l(x )-gal pedig az A x 2S algoritmus hossz t jel ljk. Ha emellett mg S -en P adott egy p = (p(x ) : x 2 S ) valsznsgeloszl s is, akkor az L(A p) := p(x ) l(x ) sz mot az A algoritmus (p eloszls x 2S melletti) tlagos hossz nak nevezzk. Ha nincs elre megadott eloszl sunk S -en, akkor tlagos hossz alatt az egyenletes eloszl s melletti tlagos hosszt 1 P rtjk. (Teh t ekkor L(A) = n l(x ).) x 2S 6 Vgl legyen L(S F ) := min L(A), illetve egy adott p eloszl s mellett A L(S F  p) := min L(A p). Ezeket rendre az (S F ) keressi feladat (legA rosszabb esetbeli) komplexits nak, illetve tlagos komplexits nak nevezzk. Egy A algoritmust, melyre L(A) = L(S F ), illetve L(A p) = L(S F  p), rendre (L)-optim lis, illetve (L)-optim lis algoritmusnak fogunk hvni. Mivel a keressre adott

fenti denci mg rendkvl t g, rdemes a keressi feladatok t bb tpus t megkl nb ztetnnk. 1. S sz moss ga szerint: ha S vges vagy megsz ml lhat, akkor diszkrt, egybknt folytonos feladatrl beszlnk. 2. A megengedett F -beli keresfggvnyek szerint is oszt lyozhatjuk a feladatokat Ez t rtnhet a keresfggvnyek rtkkszletnek elemsz ma szerint is, de termszetesen F kl nb zteti meg pld ul a rendezsi feladatokat a hamis rmt keres feladatoktl. 3. Nagyon fontos kl nbsget tehetnk az algoritmusok tpusa alapj n Egy A algoritmust adapt v nak neveznk, ha az fk keresfggvny kiv laszt sa fgg az addig v laszul kapott f1(x ) : : : fk;1(x ) rtkektl. Ha viszont az f1 f2 : : : fggvnyeket elre r gztjk, akkor A-t nemadapt v algoritmusnak hvjuk. Nyilv nvalan l tszik, hogy a nemadaptv algoritmusok az adaptvak speci lis esetei, gy persze legal bb olyan hosszak lesznek, mint az optim lis adaptv algoritmusok. A nemadaptv algoritmusok hossz t Lpre(S F )-fel

fogjuk jel lni. 4. Vgl optimaliz l si szempontbl is sztv laszthatjuk a feladatokat Lehet az a clunk, hogy a minim lis hossz legrosszabb esetbeli algoritmust tal ljuk meg, de lehet az is, hogy a minim lis tlagos hossz algoritmust. K nnyen l that, hogy ezek tnylegesen kl nb z feladatok B r a ksbbiekben nem foglalkozunk ezzel, rdemes megemlteni, hogy rtelmes problm kat kapunk akkor is, ha a denciban nem tesszk fel, hogy az algoritmusnak egyrtelmen meg kell hat rozni x -ot. Ehelyett a szok sos mdon itt is beszlhetnk val sz n sgi algoritmus okrl, ha csak majdnem egyrtelmen, azaz mondjuk  1 ; " valsznsggel kell x -ot megtal lnunk. Egy m sik lehetsg az, hogy az algoritmus akkor fejezdik be, ha tudjuk, hogy x az alaphalmaz egy kis rszhalmaz ban van. (Teh t pld ul, ha a 0 1] intervallumban keresnk, akkor elegend lehet meghat rozni ! elre adott  > 0 esetn ! egy   hossz intervallumot, amely tartalmazza x -ot.) Ezt k zel t algoritmus

nak hvjuk 7 Mieltt tov bblpnnk, r gztjk, hogy a dolgozat h tralv rszben milyen tpus keressi feladatokrl lesz sz. 1. Az S alaphalmaz vges, S elemsz m t legt bbsz r n-nel jel ljk 2. Az F fggvnycsal d vges Mivel S vgessge miatt minden f 2 F fggvny csak vges sok rtket vehet fel, gy feltehetjk, hogy f (S ) f0 1 : : : q ; 1g, tetszleges f 2 F esetn. Egy (S F ) feladatot, ahol jS j = n  1 s minden f 2 F esetn f (S ) f0 1 : : : q ; 1g, q  2, egyszeren (n q)-feladatnak is fogunk nevezni. A keressi feladatok legfontosabb s legjobban tl tott esete a q = 2 eset, azaz amikor egy keresfggvny legfeljebb kt kl nb z rtket adhat (mint pld ul a Barkochb ban). Az ilyen feladatokat binris keressi feladat oknak nevezzk. K nnyen l that, hogy ekkor egy f 2 F keresfggvny s a hozz tartoz A = fx 2 S : f (x) = 1g halmaz egyrtelmen meghat rozz k egym st. "gy F -et azonosthatjuk egy A 2S halmazcsal ddal, egy adott algoritmust pedig az A1 A2 : : :

halmazsorozattal. A tov bbiakban ezeket az A1 A2 : : : halmazokat kereshalmaz oknak fogjuk nevezni. 1.12 Dntsi fk Egy (S F ) feladathoz tartoz A = (f1 f2 : : : ) algoritmusnak szemlletes s jl haszn lhat ler s t adhatjuk (gy keres) f k segtsgvel. Els clunk ennek a pontos deni l sa lesz, azonban elsz r l ssunk egy elnevezst: 3. De n ci A T gy keres f t (n q)-f nak nevezzk, ha pontosan n levele van, s minden bels cscsnak legfeljebb q a van (nak a k zvetlen lesz rmazottakat, azaz a gy krtl t volabbi szomszdokat fogjuk nevezni). T regulris (n q)-fa, ha minden bels cscsnak pontosan q a van. (q = 2 esetn binris f rl beszlnk.) Figyeljk meg, hogy az els k teszt elvgzse ut n a k vetkez inform ci ll rendelkezsnkre: a keresett x elem az Sk (x ) := fx 2 S : f1(x) = f1(x ) : : : fk (x) = fk (x )g halmazhoz tartozik. L that, hogy l(x ) dencija alapj n S = S0(x ) S1(x )  Sl(x )(x ) = fx g: St, rdemes kicsit kiterjeszteni az elz jel lst.

Tetszleges e1 : : : ek 2 f0 1 : : : q ; 1g esetn legyen S (e1 : : : ek ) := fx 2 S : f1(x) = e1 : : : fk (x) = ek g 8 azaz S (e1 : : : ek ) jel li azon x 2 S elemek halmaz t, amelyek mg lehetnek az ismeretlen elem, ha az els k teszt eredmnye rendre e1 : : : ek volt. K nnyen l that, hogy ezen halmazok k zl az sszes nemreset, valamint mg S -et vve, egyrtelmen lertuk az A algoritmust. A d ntsi fa megkonstru l s hoz minden nemres S (e1 : : : ek ) halmazhoz, illetve az S -hez rendeljnk egy cscsot, az S (e1 : : : ek)-hoz tartoz cscs ai pedig legyenek az S (e1 : : : ek e), (e 2 f0 1 : : : q ; 1g) cscsok. (#rtelemszeren az S lesz fa gy kere, s a lesz rmazottai az S (e) cscsok lesznek) Nyilv nval, hogy ekkor a levelek ppen az egyelem halmazoknak (azaz S elemeinek) felelnek meg. L that, hogy ha adott az (S F ) (n q)-feladat s egy hozz tartoz A algoritmus, akkor az ehhez konstru lt fa is (n q)-fa lesz az x elemhez rendelt levl mlysge ppen l(x ), s gy persze

a fa mlysge (amit ezentl L(T )-vel jel lnk) is egyenl az algoritmus hossz val. Tov bb , egy v bels cscshoz rendelt S (e1 : : : ek ) halmaz is egyszeren meghat rozhat a fa segtsgvel, hiszen ppen azon levelekhez tartoz elemekbl fog llni, melyek v lesz rmazottai. $sszefoglalva, azt l ttuk teh t, hogy minden (n q)-feladathoz tartoz A algoritmushoz egyrtelmen hozz rendelhet egy (n q)-fa, amit az A algoritmus d ntsi f j nak hvunk. #rdemes megnzni a megfordt st is, azaz, hogy egy tetszleges (n q)f hoz ltezik egy (n q)-feladat s egy hozz tartoz A algoritmus, amelynek ppen T a d ntsi f ja. Ennek bel t s hoz lljon S a T fa leveleibl, a T bels cscsaibl kivezet leket pedig tetszlegesen cmkzzk meg a 0 1 : : : q ; 1 sz mokkal (arra kell csak gyelnnk, hogy egy cscsbl kiindul teh t a  fel men] kt l ne kapja ugyanazt a cmkt). Ekkor az fk : S ! f0 1 : : : q ; 1g (k = 1 : : : L(T )) keresfggvnyeket a k vetkezkppen deni lhatjuk: 8 > < j ha

k  l(x ) s az r-bl x -ba vezet ton fk (x ) = > a k-adik l cmkje j : 0 ha k > l(x ) Azonnal l tszik, hogy ezzel egy nemadaptv algoritmust kaptunk: a kadik lpsben, fggetlenl az addigi v laszoktl ! hacsak meg nem tal ltuk m r x -ot, azaz vget nem rt az algoritmus !, mindig fk -t krdezzk meg. Nyilv nval, hogy az ehhez tartoz d ntsi fa ppen T . A fentiekbl az is r gt n addik, hogy ha minden keresfggvny meg van engedve, azaz F = f0 1 : : : q ; 1gS , akkor minden adaptv algoritmust talakthatunk ugyanolyan hossz nemadaptvv (persze csak a legrosszabb esetben igaz ez, az tlagosban nem), teh t L(S F ) = Lpre(S F ). 9 Mg nh ny elnevezs f kra illetve algoritmusokra: 4. De n ci Egy (n q)-feladathoz tartoz A algoritmust regulris nak neveznk, ha jS (e1 : : : ek)j  2 esetn S (e1 : : : ek e) 6=  teljesl minden e 2 f0 1 : : : q ; 1g-re. Az A algoritmus irreducibilis, ha minden nemres S (e1 : : : ek ) esetn S (e1 : : : ek ) % S (e1 : : : ek e)

teljesl. Analg mdon egy (n q)-f t irreducibilis nek hvunk, ha minden bels cscs nak legal bb kt a van. 1.2 Keress az F = f0 1 1.21 A legrosszabb eset ::: q ; 1gS esetben Az elz rsz vgn tett meg llapt sainkat gyelembe vve, most elg (n q)tpus keressi feladatok helyett csak (n q)-f kkal foglalkoznunk. Elsz r egy egyszer, de a keressben alapvet fontoss g llt st l tunk be. Jel ljk ehhez T (n q)-val az sszes (n q)-fa halmaz t. 5. ll ts Legyen T 2 T (n q), s jel ljk I = I (T )-vel T bels cscsainak halmazt. Ekkor   i) jI j  nq;;11 , ii) T pontosan akkor regulris, ha jI j = nq;;11 . Specilisan, egy regulris fra q ; 1jn ; 1. Megford tva, minden (n q) prhoz (n  1 q  2) ltezik egy (n q)-fa,  amelyre jI j = nq;;11 . (gy persze ez az (n q )-fa regulris, s jI j = nq;;11 , ha q ; 1jn ; 1.) Bizony ts. Legyen T 2 T (n q) $sszesz moljuk ktflekppen a fa leit Egyrszt minden cscsba pontosan egy l megy be, kivve termszetesen a gy keret. M

sfell minden bels cscsbl legfeljebb q l vezet ki Ezek alapj n n + jI j ; 1  jI j q amibl i) s ii) azonnal k vetkezik.   A megfordt shoz teljes indukcit alkalmazunk k = nq;;11 -re. k = 0, azaz n = 1 esetn az llt s trivi lis. k = 2-re a fa a gy krbl s n  q levlbl ll, melyek mind a gy krrel szomszdosak. Legyen teh t k  2 s n ; 1 = k(q ; 1) ; r, ahol 0  r < q ; 1. Ekkor n ; q = (k ; 1)(q ; 1) ; r, 10 teh t az indukcis feltevs szerint ltezik egy T 0 (n ; q + 1 q)-fa, amelyre jI (T 0)j = k ; 1. Kiv lasztva T 0 egy tetszleges levelt, s ezt kicserlve a trivi lis (q q)-f ra (azaz amelyben a gy kren kvl q vele levl  n;szomszdos  1 van), egy T 2 T (n q) f t kapunk, amelyre jI (T )j = k = q;1 teljesl.   Az al bbiakban az jI j = nq;;11 egyenlsget teljest (n q)-f k egy nagyon fontos tpus t fogjuk deni lni. Egy r gztett T 2 T (n q) f ra E jel lje a levelei halmaz t, Sk a k-adik szinten lv cscsait (azaz Sk := fv 2 V : l(v) = kg, ahol k = 0

1 : : : L), s L(T ) helyett rjunk csak L-et. 6. De n ci Egy T 2 T (n q) f t teljes nek neveznk, ha i) Tetszleges k  L ; 2 esetn minden v 2 Sk cscsnak pontosan q a van. ii) T -nek az i) ltal megengedett lehet legt bb levele van SL;1-ben. (Persze i)-bl k vetkezik, hogy E SL;1 SL) L = 0-ra a felttelek trivi lisan teljeslnek, gy feltehetjk, hogy L  1. i) miatt k = 0 1 : : : L ; 1 esetn jSk (T )j = qk . Tegyk fel, hogy az SL;1 halmaz a darab levelet tartalmaz, vagyis gy b = qL;1 ; a bels cscsot, ahol b > 0, hiszen azt feltteleztk, hogy a fa mlysge L. Ekkor az Ledik szinten persze n ; a levlnek kell lennie, viszont m srszt semmikppen sem lehet qb levlnl t bb it. Ezek alapj n a qb  n ; a egyenltlensgbl (q ; 1)b  n ; a ; b  n ; qL;1-et kapjuk, amibl pedig l L;1 m b  n q;;q 1 k vetkezik.   Ezek szerint b-re a lehet legkisebb rtk a b = n;qq;L1;1 , amibl a legLP ;2  feljebb qqL;;1n lehet. Most m r l that, hogy jI j = qk + b = qqL;;11 + k=0 

n;qL;1   n;1  L ; = q;1 . Mivel b > 0 s a  0, ezrt q 1 < n  qL, azaz q;1 L = dlogq ne, ami azt jelenti, hogy i) s ii) egyrtelmen meghat rozz k L-et.  $sszefoglalva, egy teljes (n q)-f nak L = dlogq ne a mlysge, qqL;;1n  levele van SL;1 -ben, s nqq;;q1L levele van SL-ben. Ezek ut n k nnyedn megoldhatjuk a legrosszabb esetbeli problm t az (n q)-f kra. A r vidsg kedvrt alkalmazni fogjuk az L(n q) := minfL(T ) : T 2 T (n q)g jel lst. 11 7. Ttel Legyen n  1, q  2 Ekkor L(n q) = dlogq ne Bizony ts. Legyen T 2 T (n q), s legyen L := L(T ) Mivel minden bels cscsnak legfeljebb q a lehet, l thatjuk, hogy a k-adik szintre jSk (T )j  qk (k = 0 1 : : : L): Ha v egy olyan levele T -nek, amelyre l(v) < L, akkor v-t cserljk ki egy v00 bels cscsra, melynek lesz rmazottai v10 v20 : : : vL0 ;l gy, hogy l(vi0) = l(v)+ i, s vL0 ;l ismt egy levl lesz. Ezzel az elj r ssal egy olyan T 0 2 T (n q) f t kapunk, amelyre E (T 0) SL(T 0). A fenti

egyenltlensgbl azt kapjuk, hogy n = jE (T )j = jE (T 0)j  qL, s gy L  dlogq ne, hiszen L egsz. Vgl azt, hogy ez az als korl t el is rhet, a fent deni lt teljes f k vizsg lat n l l ttuk. A fenti ttelbl azonnal addik az al bbi llt s tetszleges (n q)-feladatokra (teh t most nem tesszk fel, hogy minden keresfggvny megengedett). 8. Kvetkezmny Legyen (S F ) egy (n q)-feladat Ekkor L(S F )  dlogq ne Bizony ts. L ttuk, hogy minden algoritmus reprezent lhat egy d ntsi f val A 8. k vetkezmnybeli als korl tot az (S F ) feladatra vonatkoz informci elmleti als korlt nak nevezzk 1.22 tlagos eset Ak rcsak a legrosszabb esetben, itt is egy igen fontos lemm val kezdjk: 9. Lemma (Kraft-egyenltlensg) Legyen T 2 T (n q), s l1 : : : ln len P gyenek T leveleinek a mlysgei. Ekkor q ;li  1 Egyenlsg pontosan i=1 akkor ll, ha T regulris. n P Megford tva, ha az l1 : : : ln nemnegat v egszek kielg tik a q ;li  1 i=1 egyenltlensget, akkor ltezik egy (n q

)-fa, melynek levelei rendre l1 : : : ln mlysg ek. 12 Bizony ts. Az els llt s bel t s hoz vegyk szre, hogy egy tetszleges (n q)-f bl teltett (n0 q)-f t gy rthatunk gy, P hogy teltetlen bels cscsaira leveleket akasztunk. Ezzel az elj r ssal Pq;li csak nhet, gy elg azt igazolnunk, hogy egy T regul ris (n q)-f ra q;li = 1. Alkalmazzunk indukcit k = nq;;11 szerint (k az 5. llt s miatt egsz) k = 0, vagyis n = 1 esetn az llt s trivi lisan teljesl, gy most tegyk fel, hogy k  1. Most T -bl t r ljnk le q levelet, amelyek egyetlen k z s szomszddal rendelkeznek (teh t mostantl ez a k z s szomszd egy j levl lesz). "gy a T 0 f t kapjuk. Feltehet, hogy ppen az els q levelet t r ltk le, s a k z s mlysgk l1 =  = lq =: l volt Ekkor a T 0-re az indukcis felttelt alkalmazva kapjuk, hogy n X i=1 q;li = | {z } T n X i=q+1 q;li + q  q;l = n X i=q+1 | q;li + q;(l;1) = 1: {z } T0 n P Megfordtva, ha adottak l1 : : : ln 2 N0, amelyekre q;li

 1, akkor i=1 legyen wk := jfi : li = kgj, ahol k = 0 1 : : : L = max l , azaz wk jel li a k i i mlysg levelek sz m t a konstru land T f ban. A lemma felttele a wk -k segtsgvel trhat: L X k=0 wk q;k  1 vagy m skppen, w0qL + w1qL;1 +  + wL;1q + wL  qL: (1.1) Rekurzvan konstru ljuk meg a f t. Ha w0 = 1, akkor (11) alapj n L = 0, azaz T egyetlen pontbl ll. Tegyk fel most, hogy m r kszen vagyunk a konstrukcival a k-adik szintig. Jel ljk ezt a szintet Sk -val Ha a felsbb szinteken minden pontnak q a lett volna, akkor az Sk -ban most qk cscsunk lenne. Az Si szinten (i = 1 : : : k ; 1) azonban m r wi cscsot ki kellett jel lnnk levlnek, ezrt persze az ezek alatti cscsokat elvesztettk. "gy k P Sk -ban csak qk ; wiqk;i bels csccsal gazd lkodhatunk. (11) szerint i=0 wk+1 qL;k;1  qL ; 13 k X i=0 wiqL;i azaz wk+1  qk+1 ; k X i=0 wiqk+1;i = q(qk ; k X i=0 wiqk;i ): Ebbl az l tszik, hogy a k + 1-edik szintre elrt wk+1 levl mindegyikt

el tudjuk rni Sk -beli bels pontbl, amivel bel ttuk a lemm t. Ahhoz, hogy meghat rozzuk a komplexit st az tlagos esetben, szksgnk lesz egy technikai jelleg lemm ra: 10. Lemma Legyenek s1 : : : sn s y1 : : : yn pozit v val s szmok, amen n P P lyekre si  yi. Ekkor i=1 i=1 n X i=1 yi loga ysi  0 minden a > 1 esetn (1.2) i s egyenlsg pontosan akkor ll, ha si = yi minden i-re. Bizony ts. Mivel a kl nb z alap logaritmusok csak egy konstans szorzban trnek el egym stl, ezrt elg csak a termszetes alap logaritmusra bel tnunk a lemm t. Felhaszn lva azt a k zismert tnyt, hogy ln x  x ; 1 minden x > 0 esetn, s egyenlsg pontosan akkor ll, ha x = 1 r gt n addik az llt s, hiszen X  X X s s i X i yi ln y  yi y ; 1 = si ; yi  0: i i Itt egyenlsg pontosan akkor ll, ha si=yi = 1 minden i-re. A most k vetkez ttel 1-nl kisebb hib val megoldja az tlagos esetbeli problm t. Legyen p = (p1 : : : pn ) egy valsznsgeloszl s az (n q)-f k levelein, s

most is vezessk be a k vetkez jel lst: L(n q p) := minfL(T  p) : T 2 T (n q)g. 11. Ttel (Shannon 7]) Legyen n  1, q  2 Ekkor ; n X i=1 pi logq pi  L(n q p) < ; 14 n X i=1  pi logq pi + 1 Bizony ts. Feltehetjk, hogy minden i-re pi > 0 A bal oldali egyenltlensg bizonyt s hoz azt kell megmutatnunk, hogy minden T 2 T (n q) f ra, melynek levlmlysgei l1 : : : ln, teljesl, hogy n X i=1 pi li  ; n P n X i=1 pi logq pi : n P A Kraft-egyenltlensg miatt q;li  1 = pi, gy alkalmazhatjuk az i=1 i=1 ; l ; l n i 10. Lemm t a q : : : q , illetve a p1 : : : pP n sorozatokra. Azt kapjuk, P P hogy pi logq (pi qli )  0, azaz ; pi logq pi  pi li. A jobb oldali szigor egyenltlensg igazol s hoz deni ljuk az li termszetes sz mokat minden i-re a ; logq pi  li < ; logq pi +1 egyenltlensggel. L that, hogy ez rtelmes s egyrtelm. A denci szerint 1=pi  qli , azaz q;li  pi minden i-re, s gy n X i=1 q;li  n X i=1 pi = 1: Ekkor a

Kraft-egyenltlensg megfordt s bl k vetkezik, hogy ltezik egy T (n q)-fa, amelynek a levlmlysgei l1 : : : ln, s gy az tlagos mlysge, n P L(T  p) = pili fellrl becslhet a k vetkezkppen: i=1 X X ; X  pi li < pi (; logq pi + 1) = ; pi logq pi + 1 A pi > 0 feltteltl megszabadulhatunk, ha kik tjk, hogy 0  logq 0 = 0. n 12. De n ci A H (p1 : : : pn ) := ; P pi log2 pi kifejezst a (p1 : : : pn ) i=1 eloszl s entr pi j nak nevezzk. A denci alapj n a 11. Ttelt a k vetkez alakba rhatjuk: H (p1 : : : pn )  L(n q p) < H (p1 : : : pn ) + 1 log2 q log2 q Ak rcsak a legrosszabb esetben, a 11. Ttel tetszleges (S F ) keressi feladat tlagos bonyolults g ra is als korl tot jelent: 13. Kvetkezmny Legyen (S F ) egy (n q)-feladat, p = (p1 : : : pn) pedig tetszleges eloszls. Ekkor n X 1 : : : pn ) L(S F  p)  ; pi logq pi = H (plog : 2q i=1 15 Ha m r egy 1-nl kisebb hiba erejig meghat roztuk L(n q p)-t, foglalkozhatunk pontosabb rtk megtal

l s val is. Tekintsk elsz r a p1 =    = pn = 1=n egyenletes eloszl st. Ekkor a 11. Ttel szerint logq n  L(n q n1 : : : n1 ) < logq n + 1: P Legyen T 2 T (n q), s jel lje T leveleinek halmaz t E . Az e(T ) := l(v) v2E sszeget a T fa kls mlysg nek nevezzk. "gy e(T ) = nL(T  n1 : : : n1 ), teh t a feladatunk e(T ) minimum nak a meghat roz sa. Bel tjuk, hogy a minimum pontosan a 6. Denciban szerepl teljes f kon vtetik fel A teljes f kra vonatkoz i) felttel k nnyen addik, hiszen ha ltezne w 2 Sk , k  L ; 2 bels cscs, amelynek kevesebb, mint q a van, akkor egy, az L-edik szinten lv levelet felhozhatn nk w  nak, amivel e(T )-t cs kkentennk. Ha pedig i) teljesl, ii) trivi lisan szksges az optimalit shoz. Jel ljk teh t a minim lis kls mlysget e(n q)-val. Ezt k nnyen ki is L ;n q sz molhatjuk. Egy teljes f nak a = b q;1 c levele van az L ; 1-edik szinten, s n ; a levele az L-ediken. Figyelembe vve, hogy L = dlogq ne, a k vetkez ttelt kapjuk:

14. Ttel Legyen n  2 Ekkor az e(n q) := minfe(T ) : T 2 T (n q)g jel lssel: j dlogq ne k e(n q) = ndlogq ne ; q q ; 1; n j dlogq ne k L(n q n1 : : : n1 ) = dlogq ne ; n1 q q ; 1; n : Bizony ts. A ttel eltti megjegyzsek alapj n k q ; n e(n q) = a(L ; 1) + (n ; a)L = nL ; a = ndlogq ne ; q ; 1 : j L #rdemes mg megnzni, hogy a fent kapott rtk mennyiben trhet el a 11. Ttelben kapott logq n als korl ttl Legyen dlogq ne = logq n + , ahol 0   < 1, valamint legyen b qqL;;1n c = qqL;;1n ; r, ahol 0  r < 1. Ekkor 16 L = dlogq ne = logq n +  miatt: L L(n q n1 : : : n1 ) = logq n +  ; n1 q q; 1 + q ;1 1 + nr =  = logq n +  ; q q; 1 + q ;1 1 + nr = ; = logq n + q ;1 1 (q ; 1) ; q + 1) + nr : Az f () := (q ; 1) ; q + 1 fggvnyrl k nnyen bel that, hogy a 0 1] intervallumon nemnegatv, s a maximum t a 0 = ln(q;1)ln;q ln ln q pontban veszi fel. Mindezeket sszefoglalva: 15. Kvetkezmny n  1, q  2 esetn logq n  L(n q n1 : : : n1 )  logq n + q ;1 1 ;

1 + ln ln qln;q ln(q ; 1) + nr ne ne ahol b q qq;1 ;n c = q qq;1 ;n ; r, 0  r < 1. Specilisan, binris fkra q = 2 s r = 0, gy   log2 n  L n 2 n1 : : : n1  log2 n + 1 ; 1 +lnln2ln 2 = log2 n + 0:086 dlog dlog ttrve az egyenletesrl tetszleges eloszl sra, igen keveset tudunk mondani L(n q p) rtkrl (ugyanakkor rdemes megemlteni, hogy adott p esetn ltezik hatkony algoritmus az optim lis d ntsi fa megkonstru l s ra 5]). Most csak azt l tjuk be, hogy az egyenletes eloszl s extrem lis tulajdons g (Mint az v rhat is volt, az egyenletes eloszl s hordozza a legt bb inform cit, gy ebben az esetben a legnagyobb az tlagos bonyolults g). 16. ll ts Legyen p = (p1 : : : pn ) tetszleges eloszls Ekkor L(n q p1 : : : pn )  L(n q n1 : : : n1 ): Bizony ts. Feltehetjk, hogy p1  p2    pn Bel tjuk, hogy ekkor k P minden k = 1 : : : n esetn pi  nk teljesl. Ha ugyanis nem gy lenne, azaz ltezne k < n, amelyre i=1 k P i=1 pi < nk volna, akkor pk =

minfp1 : : : pk g < n1 17 teljeslne, s gy pj < n1 is igaz lenne minden j > k esetn. Viszont ebbl n n P P pj < n;n k k vetkezne, s gy pi < 1, ami ellentmond s. i=1 j =k+1 M r l ttuk, hogy egyenletes eloszl s esetn egy optim lis f nak a = dlog q ne ;n q b q;1 c levele van dlogq ne ; 1 mlysgben, s n ; a levele dlogq ne mlysgben. Rendeljk most az a legnagyobb valsznsget a dlogq ne ; 1-edik szinten lv levelekhez, a t bbit pedig a t bbi levlhez. Az gy megadott T fa tlagos mlysge ekkor L(T  p) = a X i=1 pi(dlogq ne ; 1) + = dlogq ne ; a X i=1 n X j =a+1 pj dlogq ne pi  dlogq ne ; na j q dlogq ne ; n k 1 = dlogq ne ; n q ; 1 = L(n q n1 : : : n1 ): Mivel nyilv nvalan L(n q p)  L(T  p), ezrt az llt st bel ttuk. 1.3 Nemadaptv algoritmusok R viden foglalkozunk a nemadaptv algoritmusokkal is. Ekkor a d ntsi f val val reprezent l s helyett egyszerbben is lerhatjuk az algoritmusokat. Tekintsk ugyanis az (S F ) (n q)-feladatot, s

egy ehhez tartoz A = (f1 : : : fL) algoritmushoz rendeljnk hozz egy MA m trixot. A m trix oszlopai feleljenek meg az S halmaz elemeinek, a sorok pedig az f1 : : : fL tesztfggvnyeknek. A m trix (i j ) koordin t j mezjbe az fi(xj ) sz mot rjuk. "gy teh t MA egy L n-es m trix a f0 1 : : : q ; 1g halmaz felett Az is r gt n l tszik, hogy ha A sikeres algoritmus, akkor az MA m trix oszlopai kl nb zek. A megfordt s is nyilv nval, csak meg kell fogalmazni: ha M egy n oszlopos m trix, melynek sorai megengedettek (F szerint), tov bb p ronknt kl nb zek, akkor M -nek megfelel egy sikeres nemadaptv algoritmus az (S F ) feladatra. Egyszeren csak gy kell megv lasztani az f1 : : : fL fggvnyeket (ahol teh t L az M m trix sorainak a sz m t jel li), hogy megfeleljenek M sorainak. Ekkor persze ak rmilyen v laszokat is kapunk, M oszlopainak kl nb zsge biztostja azt, hogy x -ot egyrtelmen meg tudjuk hat rozni. 17. De n ci Legyen S = fx1 : : : xng, s (S F ) egy (n q)-tpus

keressi feladat. Egy n oszlopos, a f0 1 : : : q ; 1g halmaz feletti M m trixot az 18 (S F ) feladathoz tartoz keresmtrix nak hvunk, ha M oszlopai p ronknt kl nb zek, tov bb minden sora (f (x1) : : : f (xn )) alak valamilyen f 2 F tesztfggvnyre. Ezzel a nemadaptv legrosszabb esetbeli problm t minim lis sz m sorral rendelkez keresm trixok keressre reduk ltuk. 1.4 J tkelmleti megk zelts Egy (S F ) keressi feladat legrosszabb esetbeli megold s t keressi jtk knt is felfoghatjuk, melyben kt j tkos vesz rszt, A s B . A j tk sor n A f1 f2  2 F tesztfggvnyeket v laszt ki, s megkrdezi B -tl fi(x ) rtkt. A minl kevesebb krds segtsgvel akarja meghat rozni x -ot Egy f1 f2 : : : sorozatot, amely meghat rozza az ismeretlen x 2 S elemet, szok s szerint az A j tkos egy algoritmus nak fogunk nevezni. A m sik oldalon azonban B arra akarja knyszerteni A-t, hogy minl t bb krdst fel kelljen tennie. Ezrt B -nek nem kell elre kiv lasztania egy x

-ot, hanem A krdseire kedve szerint adhat rtelmes v laszokat, azaz olyanokat, amelyek egyrszt benne vannak az ppen megkrdezett fi keresfggvny rtkkszletben, m srszt a mg x -knt szba j het elemek halmaz t nem teszik ress. Egy ilyen v laszsorozatot B stratgi j nak neveznk A j tk termszetesen akkor r vget, ha A meghat rozza x -ot, a jtk hossz nak pedig a feltett krdsek sz m t nevezzk. Tegyk fel, hogy A az A0 algoritmust, mg B az S0 stratgi t alkalmazza. Az ekkor lezajl j tk hossz t L(A0 S0)-lal jel ljk. Bevezetjk a k vetkez szok sos j tkelmleti jel lseket is: L(A0) := max L(A0 S ) S L(S0) := max L(A S0): A L(A0)-t s L(S0)-t rendre A0 illetve S0 hossz nak nevezzk. 18. ll ts Legyen (S F ) egy keressi feladat Ekkor min max L(A S ) = max min L(A S ) A S S A vagy ami ezzel ekvivalens min L(A) = max L(S ): A S (1.3) Tovbb, ez a k z s hossz ppen L(S F ), azaz az (S F ) feladat legrosszabb esetbeli bonyolultsga. 19 Bizony ts.

Tetszleges r gztett A0 s S0 esetn nyilv nvalan L(A0) = max L(A0 S )  min L(A S0) = L(S0) S A s gy min L(A)  max L(S ) A S amibl (1.3) bel t sa ut n r gt n k vetkezik a ttel utols llt sa (1.3) igazol s hoz indukcit alkalmazunk n-re n = 1 esetn mindkt oldal null val egyenl Tegyk most fel, hogy (S F ) egy (n q)-feladat Egy A0 algoritmust optimlis nak neveznk, ha L(A0) = min L(A). Hasonlan, az A S0 stratgia optimlis, ha L(S0 ) = max L(S ). Ha f az A0 algoritmus ltal elS sknt megkrdezett keresfggvny, akkor jel lje (f ) = fS0 S1 : : : Sq;1g az S -en f ltal induk lt partcit, azaz Si := fx 2 S : f (x) = ig, i = 0 1 : : : q ; 1. Feltehetjk, hogy f legal bb kt kl nb z rtket felvesz, azaz minden i esetn Si $ S . Tegyk fel, hogy A(Si) egy optim lis algoritmus az (Si Fi) rszfeladathoz (ahol persze Fi az F megszort sa Si-re) Az A(Si) feladatokat trivi lis mdon sszekombin lva, s gy v lasztva az els tesztfggvnyt, hogy a rszfeladatok hossza a lehet

legkisebb legyen, nyilv nvalan egy optim lis A0 algoritmust nyernk az (S F ) feladathoz, amelyre L(A0) = 1 + min maxfL(A(Si)) : Si 2 (f )g: f Analg mdon, legyen S (Si) optim lis stratgia az (Si Fi) rszfeladathoz. Ismt sszekombin lhatjuk az S (Si) stratgi kat, illetve olyan v laszt adhatunk az els krdsre, hogy a rszfeladat hossza a lehet legnagyobb legyen. Ekkor egy S0 optim lis stratgi t nyernk az (S F ) feladatra, amelyre L(S0) = 1 + min maxfL(S (Si)) : Si 2 (f )g: f Mivel az A(Si) illetve S (Si) stratgi k mind optim lisak, alkalmazhatjuk az indukcis felttelt, amibl minden i s f esetn L(A(Si)) = L(S (Si)), s gy L(A0)  L(S0). A0-t s S0-t gy konstru ltuk meg, hogy L(A0) = L(A0 S0) = L(S0) gy azt mondhatjuk, hogy a feladat legrosszabb esetbeli bonyolults ga ppen a hozz tartoz keressi j tk hossza, amikor mindkt j tkos optim lisan j tszik. 20 Az elbbi ttelben lnyegben bel tott L(S )  L  L(A) tetszleges A s S esetn egyenltlensget gyakran fel

lehet haszn lni arra is, hogy korl tokat bizonytsunk L = L(S F )-re. A jobb oldali rsz miatt egy tetszleges algoritmus fels korl tot szolg ltat L-re. Persze ez nem jdons g az viszont rdekesebb, hogy a bal oldal szerint egy S stratgia L(S ) hossza als korl tot ad L-re. Ennek egyszer alkalmaz saknt ismt bel tjuk a 8. K vetkezmnyt Ehhez nem is kell m st tennnk, mint az (S F ) (n q)-feladatot keressi j tkknt felfognunk. Ekkor k vesse B a k vetkez stratgi t: ha a k-adik lpsben Sk a mg szba j het x -ok halmaza, f pedig A aktu lis krdse, akkor az Ski = fx 2 Sk : f (x) = ig, i = 0 1 : : : q ; 1 halmazok k zl v lassza a legnagyobb elemsz mt. Ekkor jSk+1j  jSqk j , amibl 1 = jSLj  jS j , azaz L  dlog ne. q qL Termszetesen teljesen hasonlan deni lhatunk keressi j tkokat az tlagos hosszra, st, a nem-adaptv esetben is (ekkor A nylt k rty kkal j tszik). 1.5 Bin ris keress A keressi feladatok legfontosabb s legjobban ismert esete a q = 2 eset, azaz a bin

ris keressi feladatok. Ekkor az 5 llt sbeli q ; 1jn ; 1 felttel trivi lisan teljesl, s a regularit s illetve az irreducibilit s is egybeesnek. M r emltettk, hogy egy f : S ! f0 1g tesztfggvnyt azonosthatunk egy A = fx 2 S : f (x) = 1g halmazzal, s gy az F halmazt egy A halmazrendszerrel. Ezrt a bin ris keressi feladatokat legt bbsz r (S A)-val fogjuk jel lni. "gy mindenTA algoritmushoz tartozik egy U = (A1 A2 : : : ) halmazsorozat, amelyre A = fx g Egy U = (A1 A2 : : : AL) nem-adaptv A2U algoritmust pedig elvlaszt (szeparl ) halmazrendszer nek fogunk nevezni, mivel minden x 6= y 2 S elemp r esetn ltezik Ai 2 U , amelyik elv lasztja x-et y-tl, azaz amely x s y k zl pontosan az egyiket tartalmazza. Eddigi eredmnyeinket a k vetkez ttelben foglaljuk ssze: 19. Ttel Legyen n  1, p = (p1 : : : pn ) adott eloszls, (S A) pedig egy tetszleges binris keressi feladat. Ekkor i) L(n 2) = Lpre (n 2) = dlog2 ne ii) L(n 2 n1 : : : n1 ) = Lpre (n 2 n1 : : : n1

) = dlog2 ne ; n1 2dlog2 ne + 1 21 iii) H (p1 : : : pn )  L(n 2 p) = Lpre (n 2 p) L(n 2 p) < H (p1 : : : pn ) + 1 L(n 2 p)  dlog2 ne ; n1 2dlog2 ne + 1 iv) dlog 2 ne  L(S A)  Lpre (S A). v) H (p1 : : : pn )  L(S A p)  Lpre (S A p): Most j tt el az id, hogy megvizsg ljunk egy viszonylag egyszer bin ris keressi feladatot, ami azonban a dolgozat tov bbi rsznek f tm ja lesz. Egy S halmazon keresnk, azzal a megk tssel, hogy a kereshalmazaink elemsz ma legfeljebb egy elre r gztett k sz m lehet azaz egy (S Ak ) feladatrl van sz, ahol Ak = fA S : jAj  kg. 20. Ttel Legyen jS j = n, k  n Ekkor i) L(S Ak ) = dlog2 ne, ha k  n2 ii) L(S Ak ) = t + dlog2(n ; tk)e, ahol t = d nk e ; 2, ha k < n2 . Bizony ts. Ha k  n2 , az persze semmi megk tst nem jelent sz munkra, hiszen mindegy, hogy egy halmazt, vagy a komplementert teszteljk. "gy i) trivi lis. ii) bizonyt s hoz legyen fk (n) = L(S Ak ), ahol n = jS j. L that, hogy ez a denci rtelmes,

hiszen L(S Ak ) csak jS j-tl fgg. Bel tjuk, hogy r gztett k esetn fk (n) monoton n. Legyen ugyanis T $ S , U pedig legyen egy L hossz optim lis algoritmus a (S Ak ) feladatra. Ekkor persze U 0 := fAT : A 2 Ug egy sikeres, s legfeljebb L hossz algoritmus a (T A0k ) feladatra. Tegyk most fel, hogy A1 az els kereshalmaz egy optim lis algoritmus sor n, s legyen jA1j = l  k. Ekkor A1-ben illetve S ; A1-ben optim lisan keres algoritmusokat tekintve felrhatjuk a k vetkez rekurzit: ;  fk (n)  1 + max fk (l) fk (n ; l)  1 + fk (n ; l)  1 + fk (n ; k) ahol k zben kihaszn ltuk az fk fggvny monotonit s t. A rekurzit iter lva a k vetkezt kapjuk: fk (n)  1 + fk (n ; k)    t + fk (n ; tk) = t + dlog2(n ; tk)e ahol i) alapj n t a legkisebb olyan sz m, amelyre k  n;2tk , vagyis t = d nk e;2. Ezzel teh t bel ttuk, hogy L(S Ak )  t + dlog2(n ; tk)e. Pontosan ennyi krdsbl ll algoritmust viszont m r k nnyen konstrulhatunk. Az els t kereshalmazunk a k vetkez lesz:

A1 = fx1 : : : xk g A2 = fxk+1 : : : x2k g : : : At = fx(t;1)k+1 : : : xtk g: 22 t S Ha ezek ut n x 2 Ai, akkor x -ot meghat rozhatjuk dlog2 ke tov bbi i=1 krds segtsgvel, hiszen az Ai halmazokban semmi megszort sunk nincs t S m r a kereshalmazokra. Ha viszont x 62 Ai, azaz x 2 fxtk+1 : : : xng, i=1 akkor dlog2(n ; tk)e tov bbi krds segtsgvel megtal lhatjuk x -ot, hiszen k  n;2tk . Ha mg gyelembe vesszk, hogy t dencij bl k vetkezen k < n;(t2;1)k , azaz n;tk > k, azt kapjuk hogy az algoritmusunknak legfeljebb t + dlog2(n ; tk)e krdsre van szksge. Ugyanezen problma nemadaptv esetben m r nmikpp bonyolultabb, de kezelhet 6, 10]. 23 24 2. Matroidok 3] 2.1 Dencik A matroidok olyan absztrakt kombinatorikus struktr k, amelyek a fggetlensg, kl n skppen a line ris fggetlensg fogalm t ltal nostj k. (A matroidokat H. Whitney vezette be 1933-ban) Ezrt a k vetkezkppen deni ljuk ket: kiv lasztjuk a line ris fggetlensg nh ny

algebr ban bizonytott tulajdons g t, s ezeket tesszk meg axim knak. 21. De n ci (Fggetlensgi axi mk) Legyen S egy vges halmaz F pedig S rszhalmazaibl ll halmazrendszer. Az M = (S F) p rt matroid nak nevezzk, ha a k vetkezk teljeslnek: I1)  2 F. I2) Ha Y 2 F, s X Y , akkor X 2 F. I3) Minden X S halmazra az F halmaz tartalmaz sra nzve maxim lis X -beli tagjai azonos elemsz mak. (Azaz az X -ben fekv elemsz mra maxim lis F-beliek azonosak a tartalmaz sra maxim lisakkal.) Az F halmaz tagjait fggetlen halmaz oknak nevezzk, S t bbi rszhalmaz t pedig fgg nek. I3) szerint egy X rszhalmazban lv nem bvthet fggetlenek elemsz ma ugyanaz csak X -tl fgg. Ezt a sz mot r(X )-szel jel ljk, s X rang j nak nevezzk. r(S )-et a matroid rangj nak hvjuk S egy maxim lis fggetlen rszhalmaz t S bzis nak nevezzk. L that, hogy ezzel tulajdonkppen egy r : 2S ! N fggvnyt deni ltunk, amit rangfggvny nek neveznk. R gt n l tszik, hogy I1) helyett az F 6=  felttelt is

kik thettk volna. Ennl sokkal fontosabb, hogy ha I3)-at kicserljk az al bbi I3) axim ra, akkor ekvivalens aximarendszert kapunk: I3) Legyen K N 2 F, amelyekre jK j < jN j. Ekkor ltezik olyan x 2 N ;K , amelyre K + x 2 F. 25 22. ll ts Az {I1), I2), I3)} axi marendszer ekvivalens a {I1), I2), I3)} axi marendszerrel. Bizony ts. =): Legyenek K N 2 F, jK j < jN j, s legyen S 0 := K N Ekkor I3) miatt S 0 minden nem bvthet rszhalmaza legal bb jN j elem, amibl I3) k vetkezik. (=: Tegyk most fel, hogy A B X fggetlenek, s jAj < jB j. Ekkor I3) miatt ltezik x 2 B ; A, amelyre A + x fggetlen, s gy A nem lehetett (tartalmaz sra) maxim lis. 23. De n ci A 21 dencibl azonnal k vetkezik, hogy ha M = (S F) matroid s S 0 S , akkor M0 = (S 0 F0) is matroid, ahol F0 := fF S 0 : f 2 Fg. Az gy deni lt M0-t az M rszmatroid j nak nevezzk Azt is mondhatjuk, hogy az M0 matroid az M matroidbl a Z := S ; S 0 halmaz elhagys val keletkezik. Ezt M0 = M ; Z -vel jel

ljk 2.11 Pldk matroidokra A legegyszerbb matroidok a trivi lisak: egy matroid teljes vagy szabad, ha minden rszhalmaza fggetlen, illetve res vagy trivilis, ha csak az res halmaz fggetlen. Mtrix-matroid Ez plda azt hivatott mutatni, hogy tnyleg jl sikerlt absztrah lni a line ris fggetlensg fogalm t, azaz egy vektortr nh ny vektora a line ris fggetlensggel tnyleg matroidot alkot. Legyen teh t adott egy A m trix (tetszleges test felett), s jel lje S az A oszlopainak halmaz t. Egy F S halmaz pontosan akkor tartozzk F-hez, ha az F -beli oszlopvektorok line risan fggetlenek. Ekkor (S F) matroidot alkot, hiszen I1) s I2) trivi lisan teljesl, mg I3) egy elemi ttel line ris algebr bl. Az is l that, hogy egy X halmaz rangja ppen az X -beli oszlopvektorok ltal alkotott m trixok rangja Uniform matroid Ezek nagyon egyszer szerkezet matroidok. Legyen S tetszleges, jS j = n, tov bb 0  k  n egsz sz m. lljon F az S sszes legfeljebb k elem rszhalmaz bl.

Ekkor nyilv nval, hogy mindh rom axima fenn ll Az gy kapott uniform matroidot Unk -val jel ljk L that, hogy egy X S halmaz rangja r(X ) = min(jX j k). 26 Krmatroid Legyen G = (V E ) ir nytatlan gr f. A deni land matroid alaphalmaza legyen S := E . Az lek egy halmaz t fggetlennek deni ljuk, ha nem tartalmaz gr fbeli k rt, azaz ha erd. Az els kt axima itt is trivi lis, s I3) is k vetkezik abbl a jlismert llt sbl, hogy egy gr fban egy nem bvthet erd lsz ma ppen a pontok s a komponensek sz m nak a kl nbsge. Matroidok direkt sszege Legyen adott k matroid, Mi = (Si Fi), gy, hogy az alaphalmazaik diszjunktak. Legyen S := Si s F := fI S : I Si 2 Fi i = 1 : : : kg, vagyis egy I halmaz pontosan akkor legyen fggetlen, ha minden Si-be es rsze fggetlen az Mi matroidban. A fggetlensgi axim k ismt k nnyen ellenrizhetek. Az gy deni lt matroidot az Mi matroidok direkt sszegnek nevezzk. Rangfggvnye is egyszeren megadP hat: r(X ) = ri(X Si). A

direkt sszeghez a szok sos mdon kapcsoldik az sszefggsg fogalma: 24. De n ci Egy matroidot sszefgg nek neveznk, ha nem lehet direkt sszegknt el lltani. Part ci s matroid Legyen fS1 : : : Sk g az S alaphalmaz egy partcija, s legyenek g1 : : : gk nemnegatv egszek. Egy I halmaz pontosan akkor legyen fggetlen, ha jI Sij  gi minden i-re. Itt ellenriznnk sem kell az axim kat, ugyanis r gt n l tszik, hogy a partcis matroid P tulajdonkppen uniform matroidok direkt sszege. A rangfggvny r(X ) = i min(gi jX Sij). Pros ts-matroid Legyen G = (V E ) egyszer ir nytatlan gr f. A k r- matroiddal ellenttben most legyen S := V . Egy U V rszhalmaz pontosan akkor legyen fggetlen, ha ltezik G-ben olyan p rost s, amely U -nak minden pontj t fedi. 25. ll ts Az gy denilt (V F) pr matroidot alkot Bizony ts. I1) s I2) ismt trivi lis I3) helyett most I3)-t fogjuk igazolni Legyenek K N 2 F, jK j < jN j, s tegyk fel, hogy a PK p rost s fedi K -t, a PN p rost s

pedig fedi N -et. Feltehetjk azt is, hogy PK minim lis abban az rtelemben, hogy minden elemnek legal bb az egyik vgpontja K -ban van. Ha ltezik olyan PK -beli l, melynek m sik vgpontja egy N ; K -beli x pontban vgzdik, akkor kszen is vagyunk K + x is fggetlen. Tegyk fel teh t, hogy nincs ilyen l. 27 Tekintsk most a PN  PK szimmetrikus di&erenci t. Ebben minden pont foka legfeljebb 2, gy PN  PK altern l utakbl s altern l k r kbl ll. Mivel N ; K mindegyik pontj t fedi PN , de egyiket sem fedi PK , ezrt N ;K minden pontja vgpontja egy altern l tnak. Ha van olyan x 2 N ;K pont, amelybl indul R altern l t m sik vge is N ;K -ba esik, akkor ismt kszen vagyunk, mert PK  R egy olyan p rost s, amely fedi K + x-et, azaz K + x fggetlen. "gy vgl az az eset maradt, amikor az N ; K -ban vgzd altern l utak mind kl nb zek. Ekkor ezek k z tt biztosan van olyan R t, aminek a m sik vge nem K ; N -beli, hiszen a felttel szerint jK ; N j < jN ;

K j. R nem vgzdhet K N -ben sem, hiszen ott egy ltal n nem vgzdhet altern l t. "gy R-nek mindkt szls le PN -beli, de akkor PK  R megint olyan p rost s, amely fedi K + x-et. Prhuzamos tbbszrzs Az M matroid egy s fggetlen elemnek p rhuzamos t bbsz r zsn azt rtjk, hogy s-et helyettestjk az S -tl diszjunkt S 0 = fs1 : : :sk g halmazzal, s az gy kapott S ; s S 0 alaphalmazon egy X S ; s S 0 halmazt akkor deni lunk fggetlennek, ha X S ; s s X fggetlen M-ben, vagy ha jX S 0j = 1 s X ; S 0 + s fggetlen M-ben. K nnyen l that, hogy ezzel matroidot kaptunk. (Gr f k rmatroidj ban ez nyilv nvalan annak felel meg, hogy egy lt k p rhuzamos llel helyettestnk.) 2.2 A rangf ggvny Legelsz r vegyk szre, hogy kl nb z matroidok rangfggvnye kl nb z, hiszen egy halmaz pontosan akkor fggetlen, ha elemsz ma egyenl a rangj val. "gy a fggetlen halmazok csal dja a k vetkez: F = fX S : r(X ) = jX jg: (2.1) Most bel tjuk a rangfggvny egy

alapvet tulajdons g t: 26. ll ts A rangfggvny (teljesen) szubmodulris, azaz minden X Y S esetn kielg ti a k vetkez egyenltlensget: r(X ) + r(Y )  r(X Y ) + r(X Y ) Bizony ts. Legyen X Y egy b zisa F Ekkor jF j = r(X Y ), m srszt F kibvthet X Y -ban egy N b ziss , amelyre persze jN j = r(X Y ) teljesl. F maximalit sa miatt N X Y = F , s gy jN X j + jN Y j = jF j + jN j. 28 Viszont jN X j fggetlen X -ben, gy r(X )  jN X j, s hasonlan r(Y )  jN Y j. Mindezeket sszevetve kapjuk, hogy r(X ) + r(Y )  jN X j + jN Y j = jF j + jN j = r(X Y ) + r(X Y ). $sszefoglalva, a rangfggvny nh ny lnyeges tulajdons ga: 27. ll ts Legyen M = (S F) egy matroid, r a rangfggvnye Ekkor r-re teljeslnek a k vetkezk: R1) r() = 0 R2) X Y esetn r(X )  r(Y ) (monotonits) R3) r(X )  jX j (szubkardinalits) R4) minden X Y S halmazra r(X ) + r(Y )  r(X Y ) + r(X Y ) (szubmodularits) Bizony ts. R1), R2) s R3) a rangfggvny dencij bl k vetkeznek,

R4)et pedig ppen az elbb l ttuk be Clunk (2.1) megfordt sa bizonyos rtelemben Azt krdezzk, hogy melyek a rangfggvny azon tulajdons gai, amelyeket megk vetelve a (2.1) ltal deni lt F halmazrendszer kielgti a fggetlensgi axim kat. Elsz r azonban l ssunk kt elnevezst, s egy hozz juk kapcsold lemm t: 28. De n ci Az X halmaz lezrt ja a k vetkez halmaz: cl(X ) := fx 2 S : r(X + x) = r(X )g azaz mindazon elemek halmaza, amelyek X -hez vtele nem n veli a rangot. X -et zrt nak nevezzk, ha cl(X ) = X . 29. Lemma Legyen A S s e1 : : : ek 2 S ; A Ha r(A + e1) =  = r(A + ek ) = r(A), akkor r(A fe1 : : : ek g) = r(A). (Azaz, ha bizonyos elemek egyiknek hozzvtele sem n veli egy halmaz rangjt, akkor az sszes hozzvtele sem n veli. Specilisan, r(cl(X )) = r(X )) Bizony ts. Indukcit alkalmazunk k -ra k = 1 esetn az llt s trivi lis Tegyk fel, hogy az llt s k ; 1-re rvnyes, azaz az A0 := A fe1 : : : ek;1g jel lssel r(A0) = r(A). Ekkor R2) s R4) alapj n r(A) +

r(A) = r(A + ek) + r(A0)  r((A + ek ) A0) + r((A + ek ) A0) = r(A) + r(A fe1 : : : ek g)  r(A) + r(A), amibl a lemma azonnal k vetkezik. Most m r kimondhatjuk s bebizonythatjuk a ttelt arrl, hogy mikor lesz egy halmazfgvny egy matroid rangfggvnye: 29 30. Ttel Az r : 2S ! Z+ (nemnegat v, egszrtk ) halmazfggvny pon- tosan akkor egy matroid rangfggvnye, ha kielg ti az R1), R2), R3), R4) rangaxi mkat. Bizony ts. Azt, hogy a rangfggvny kielgti a rangaxim kat, m r l ttuk Megfordtva, tegyk fel, hogy r kielgti a rangaxim kat, s l ssuk be, hogy ekkor a (2.1) ltal deni lt F halmazrendszer kielgti a fggetlensgi axim kat. I1) k vetkezik R1)-bl I2) igazol s hoz vegyk szre, hogy r(A + e)  r(A) + 1 ha A S , e 2 S ; A: (2.2) Valban, R1)-et s R4)-et haszn lva r(A) + 1  r(A) + r(e)  r(A feg) + r(A feg) = r() + r(A + e) = r(A) addik. Legyen most Y 2 F s X Y Ekkor (2.2) ismtelt alkalmaz s val kapjuk, hogy r(Y )  r(X ) + jY ; X j, amibl r(Y )

= jY j miatt r(X )  jX j. Figyelembe vve R3)-at, r(X ) = jX j, azaz X 2 F addik. I3) igazol s hoz legyen K N 2 F, jK j < jN j. Ekkor r(K ) = jK j s r(N ) = jN j. Ha valamely x 2 N ; K elemre K + x 62 F, akkor r(K + x) = r(K ). Ha ez minden x 2 N ; K elemre fenn llna, akkor a 29 Lemma s R2) szerint jK j = r(K ) = r(K (N ; K )) = r(K N )  r(N ) = jN j, ami ellentmond s. Ezzel bel ttuk, hogy M = (S F) matroid. Be kell mg bizonytanunk, hogy M-nek tnyleg r a rangfggvnye. Jel lje teh t rM az M rangfggvnyt Tekintsnk egy X S halmazt, s legyen ebben K egy maxim lis fggetlen. Ekkor R2) miatt rM(X ) = jK j = r(K )  r(X ) Viszont itt nem lehet, hogy rM(X ) < r(X ), mert akkor a 29. Lemma miatt ltezne e 2 X ; K elem, amelyre r(K + e) = r(K ) + 1, amibl jK j + 1 = jK + ej  r(K + e) = r(K ) + 1 = jK j + 1. Ez pedig azt jelenten, hogy jK + ej = r(K + e), vagyis K + e is fggetlne volna X -ben, ami ellentmond K maximalit s nak. 2.3 Polimatroid f ggvnyek 31. De n ci Legyen

b : 2S ! N+ (nemnegatv, egsz rtk) fggvny Azt mondjuk, hogy b polimatroid fggvny, ha kielgti az R1), R2), R4) axim kat (de az R3) szubkardinalit s nincs megk vetelve). A k vetkez clunk annak igazol sa, hogy nemcsak a rangfggvnyek, de a polimatroid fggvnyek is alkalmasak matroidok deni l s ra. (Termszetesen a matroidbl m r nem lesz kiolvashat az t deni l polimatroid fggvny.) 30 32. Ttel Legyen Fb := fI S : b(Y )  jY I j minden Y S -reg: Ekkor M = (S Fb ) matroid, amelynek rangfggvnye rb(Z ) = minfb(X ) + jZ ; X j : X Z g: (2.3) (2.4) Bizony ts. Mindenekeltt jegyezzk meg, hogy b monotonit sa miatt (23) a k vetkez, ekvivalens alakba rhat: Fb := fI S : b(Y )  jY j minden Y I -reg: (2.5) I1) s I2) ismt trivi lisan teljesl. A bizonyt s sor n I3)-at s a (24) egyenlsget egyszerre fogjuk bel tni. Vegyk szre, hogy minden I Z , I 2 Fb esetn jI j  b(X ) + jZ ; X j, ahol X Z , hiszen (2.3) szerint jI X j  b(X ), amibl jI j = jI X j + jI ;

X j  b(X ) + jZ ; X j (2.6) k vetkezik. L that, hogy (26)-ban pontosan akkor ll egyenlsg, ha jI X j = b(X ) s Z ; X I (2.7) "gy ha I kielgti (2.7)-et valamely X halmazra, akkor jI j ppen a (24) jobb oldal n ll minimummal egyenl. Tetszleges X Z rszhalmazra vezessk most be az m(X ) := jI X j jel lst. Nyilv nval, hogy m(X ) + m(Y ) = m(X Y ) + m(X Y ) Az I 2 Fb felttel azzal ekvivalens, hogy minden X Z -re m(X )  b(X ). Nevezzk X -et (I -re nzve) pontosnak, ha m(X ) = b(X ). Nyilv nval, hogy az res halmaz pontos. Bel tjuk, hogy kt pontos halmaz metszete s unija is pontos. Valban, legyenek X s Y pontos halmazok Ekkor m(X ) + m(Y ) = b(X ) + b(Y )  b(X Y ) + b(X Y )  m(X Y ) + m(X Y ) = m(X ) + m(Y ), amibl k vetkezik az llt s. Legyen most I Z , olyan Fb -beli halmaz, amely (Fb-ben maradva) m r nem bvthet Z -beli elemmel. Ez azt jelenti, hogy Z ; I minden elemhez ltezik egy Xz I + z halmaz, amelyre b(Xz )  m(Xz ). Persze Xz -nek tartalmaznia

kell z-t, gy m(Xz ) = jXz j ; 1, tov bb b(Xz )  b(Xz ; z)  jXz ; zj = jXz j ; 1  b(Xz ). Ezzel bel ttuk, hogy Xz pontos Ekkor viszont az sszes Xz halmaz unija is pontos lesz, teh t egy olyan pontos X halmazt tal ltunk, amely tartalmazza Z ; I sszes elemt, vagyis kielgti (2.7)-et, azaz (26) egyenlsggel teljesl Ebbl k vetkezik, hogy egy nem bvthet I halmaz elemsz ma mindig ugyanaz a Z -tl fgg sz m, azaz I3) is fenn ll, s egyttal (2.4)-et is bel ttuk 31 2.4 Rado ttele s k vetkezmnyei Polimatroid fggvnyek el llt s ra egy lehetsges md a k vetkez. Legyen M = (S F) matroid r rangfggvnnyel, T tetszleges halmaz, : S ! T pedig egy szrjekci. Deni ljuk a br : 2S ! N+ a k vetkezkppen: br(X ) := r(;1(X )) . 33. ll ts Az gy denilt br polimatroid fggvny Bizony ts. Elsz r is br () = r(;1()) = r() = 0 M sodszor, br monoton, hiszen r monoton, s X Y esetn ;1(X ) ;1(Y ) Vgl br szubmodul ris, hiszen br(X ) + br(Y ) = r(;1(X )) + r(;1 (Y ))  r(;1(X )

;1(Y )) + r(;1 (X ) ;1(Y )) = r(;1(X Y )) + r(;1(X Y )) = br (X Y ) + br(X Y ). 34. De n ci A fent deni lt br fggvnyhez tartoz matroidot (M)-mel jel ljk, s az M homomorf kp nek nevezzk. (2.5) alapj n (M)-ben egy I halmaz pontosan akkor fggetlen, ha minden X I esetn r(;1 (X ))  jX j Ebbl persze r gt n k vetkezik, hogy egy olyan X I halmaz, amelyre r(;1 (X )) < jX j, tan I fggsgre. A k vetkez ttel tant szolg ltat a fggetlensgre is: 35. Ttel (R Rado) I T pontosan akkor fggetlen (M)-ben, ha ltezik M-ben egy fggetlen F halmaz, amelyre I = (F ), jI j = jF j (Vagyis az M-beli fggetlen halmazok kpeknt elll halmazok a fggetlenek (M)ben.) Bizony ts. (M) dencij bl nyilv nval, hogy egy M-ben fggetlen F halmaz (F ) kpe fggetlen (M)-ben. A m sik ir ny igazol s hoz legyen I T fggetlen Indukcit alkalmazunk j;1(I )j-re Ha minden t 2 I -re ;1(t) egyelem, akkor legyen F := ;1 (I ). Ekkor jI j = jF j, s r(F ) = r(;1(I ))  jI j = jF j, azaz I tnyleg

el ll M-beli fggetlen halmaz, nevezetesen F kpeknt. Feltehet teh t, hogy lteznek t 2 I s a b 2 S elemek gy, hogy (a) = (b) = t. Ha az M matroidbl a-t elhagyva I fggetlen marad, azaz r(;1 (X ))  jX j minden X I esetn (2.8) akkor indukcival kszen vagyunk. Ugyangy kszen vagyunk, ha b-t elhagyva marad fenn (2.8) Azt kell teh t bel tnunk, hogy nem lehet, hogy mind a, mind b t rlse megsrtse (2.8)-at Ha a t rlse ut n ltezik X I , amelyre (2.8) m r nem ll fenn, akkor jX j  r(;1(X ))  r(;1 (X ) ; a) + 1  jX j, azaz itt vgig egyenlsg ll. 32 "gy egyrszt jX j = r(;1(X )), azaz X pontos, m srszt r(;1(X )) ; 1 = r(;1(X ) ; a), vagyis a a ;1(X ) minden maxim lis fggetlenjben benne van m sszval az a elem a ;1 (X ) h d ja. L ttuk a 32. Ttel bizonyt s ban, hogy pontos halmazok metszete is pontos, gy ltezik egy legszkebb P pontos halmaz, amely tartalmazza t-t. Mivel a hdja egy t-t tartalmaz halmaz skpnek, ezrt hdja az ennl nem bvebb ;1(P )-nek is

Ugyanezek a meggondol sok rvnyesek b-re is, gy azt kaptuk, hogy a s b is hdja ;1 (P )-nek. Ekkor azonban P 0 := P ; t-re r(;1(P 0))  r(;1(P ) ; fa bg) = r(;1(P )) ; 2 = jP j ; 2 = jP 0j ; 1, ami ellentmond annak, hogy I fggetlen (M)-ben. Rado eredetileg kicsit ltal nosabb form ban mondta ki ttelt: 36. Ttel Legyen G = (A B  E ) pros grf, M egy A alaphalmaz matroid r rangfggvnnyel. Pontosan akkor ltezik olyan B -t fed pros ts G-ben, amelynek A-beli vgponthalmaza fggetlen M -ben, ha minden X B esetn r(;(X ))  jX j, ahol ;(X ) A az X szomszdainak halmazt jel li. Bizony ts. Deni ljuk E -n a k vetkez ME matroidot Legyen F E fggetlen ME -ben, ha az F -fel rintkez A-beli pontok halmaza fggetlen M ben. K nnyen l that, hogy gy tnyleg matroidot kaptunk, hiszen semmi m st nem csin ltunk, mint minden a 2 A elemet d(a)-szor p rhuzamosan megt bbsz r ztnk az M matroidban. Jel lje rE az ME rangfggvnyt, s deni ljuk a : E ! B lekpezst gy, hogy (e) legyen az

e l B -beli vgpontja. B pontosan akkor fggetlen (ME )-ben, ha ltezik olyan B -t fed Gbeli p rost s, amelynek A-ba es vgponthalmaza fggetlen M-ben. Vegyk mg szre, hogy minden X B halmazra teljesl, hogy rE (;1(X )) = r(;(X )). Ekkor az llt s k vetkezik a 35 Ttelbl 37. Kvetkezmny Legyen adott a G = (S T  E ) pros grf S pontosztlyn egy M matroid Egy T I halmazt deniljunk fggetlennek, ha ltezik olyan I -t fed G-beli pros ts, amelynek S -beli vgponthalmaza fggetlen M ben. gy egy MT matroidot kapunk, amelynek rangfggvnye rT (Z ) = minfr(;(X )) + jZ ; X j : X Z g: 38. De n ci Legyen adott az S alaphalmazon k matroid, r1 : : : rk rangk P fggvnyekkel, s legyen b := ri. K nnyen ellenrizhet, hogy b polii=1 matroid fggvny. A hozz tartoz Mo matroidot a k kiindul si matroid 33 sszeg nek nevezzk. Ennek rangfggvnye a 32 ttel alapj n k X ro(Z ) = minf i=1 ri(X ) + jZ ; X j : X Z g: (2.9) 39. ll ts Az M1 : : : Mk matroidok sszegben egy F

halmaz pontosan k S akkor fggetlen, ha elll F = Fi alakban, ahol Fi fggetlen az Mi matroidban. i=1 Bizony ts. Ksztsk el az S alaphalmaz k egym stl s S -tl is diszjunkt kpi j t (legyenek ezek S1 : : :Sk ), s tekintsk az Si alaphalmazon az Mi matroidot. Deni ljuk az S := Si alaphalmazon az Mi matroidok M direkt sszegt, s vegyk azt a : S ! S lekpezst, amely minden Si-beli elemhez a neki megfelel S -beli elemet rendeli. Ekkor l that, hogy (M ) ppen Mo lesz, gy Rado ttelbl addik az llt s. 40. Kvetkezmny (Part ci s ttel) Adott az S alaphalmazon k mat- roid. S pontosan akkor bomlik fel k halmaz egyes tsre gy, hogy az i-edik k P halmaz fggetlen az i-edik matroidban, ha ri (X )  jX j teljesl minden i=1 X S rszhalmazra. 41. Kvetkezmny Adott az S alaphalmazon egy matroid S pontosan akkor bomlik fel k fggetlen halmaz egyes tsre, ha kr(X )  jX j teljesl minden zrt, sszefgg X (2.10) S halmazra. Bizony ts. Csup n azt kell bel tnunk, hogy

(210)-et elg z rt s sszefgg halmazokra megk vetelni. Tegyk teh t fel, hogy ltezik X 0 S halmaz, amelyik megsrti (2.10)-et Ekkor persze X := cl(X ) is megsrti L ttuk, hogy X egyrtelmen felbomlik X1 : : :Xt diszjunkt, nemres, sszefgg rszekre X z rts g bl k vetkezik, hogy az Xi halmazok is z rtak t P Ezek egyike meg kell, hogy srtse (2.10)-et, kl nben r(X ) = r(Xi )  t P i=1 kjXij = kjX j miatt X sem srten meg. 34 i=1 2.5 Matroidok partcis algoritmusa Legyenek Mi = (S Fi ), k = 1 : : : k matroidok. Az Mi matroid rangfggvnye legyen ri, s jel lje Mo a matroidok sszegt A partcis algoritmus clja az sszegmatroid maxim lis F1  Fk alak fggetlenjnek el llt sa, ahol az Fi halmazok p ronknt diszjunktak, s Fi fggetlen Mi-ben. (2.9)-et az X = S esetben alkalmazva: ro(S ) = min Y S k X i=1  ri(Y ) + jS ; Y j : (2.11) Az, hogy (2.11) bal oldala legfeljebb akkora, mint a jobb oldal, k vetkezik abbl, hogy Mo egy maxim lis F1  Fk alak

fggetlenje legjobb esetben kit lti S ; Y -t, s teljesti az jFi Y j = ri(Y ) egyenltlensget. (Ez a legjobb eset szerepel ppen a jobb oldalon.) "gy az algoritmus sor n ppen egy ilyen Y fogja tanstani sz munkra, hogy megtal ltuk a maxim lis fggetlen halmazt. Az algoritmus le rsa V lasszunk ki elsz r tetszleges diszjunkt Fi halmazokat, amelyek rendre fggetlenek az Mi matroidokban. Ha esetleg F1   Fk = S , akkor az Y =  v laszt ssal kszen is vagyunk. Tegyk teh t fel, hogy ez nem teljesl Deni lunk egy ir nytott gr fot az S t1  tk ponthalmazon, ahol t1 : : : tk j (azaz eddig nem szerepl) pontok. !i l, ha x 2 Fi, s Fi + x fggetlen Mi-ben. i) Legyen ; xt ! l, ha y 2 Fi valamilyen i-re, x 62 Fi, s Fi + x ; y fggetlen ii) Legyen ; xy Mi-ben, de Fi + x nem az. E gr f segtsgvel fogjuk bvteni az eddig megkonstru lt fggetlen halmazunkat, illetve, ha ez nem megy, akkor megadni Y -t. Legyen R := S ; (F1  Fk ). Ir nytott utat szeretnnk tal lni R egy

pontj bl valamelyik ti-be, s;!egy ilyen t mentn fogjuk bvteni a matroidot gy, hogy az tban lv xti lekre x-et hozz vesszk Fi-hez, mg az ; x!y lekre (ahol y 2 Fi), x-et hozz vesszk Fi-hez, y-t pedig elhagyjuk belle. Az gy kapott F10  Fk0 halmaz persze nagyobb elemsz m lesz az elznl, gy csak arra kell gyelnnk, hogy az utat gy v lasszuk meg, hogy a kapott halmaz fggetlen maradjon Mo-ben. I. eset Ltezik ir nytott t R-bl a T = ft1 : : : tkg halmazba Ekkor bel tjuk a k vetkez llt st: 35 42. ll ts Ha egy legr videbb irny tott L utat vesznk R-bl T -be, akkor a fenti cserlgetssel kapott F10  Fk0 halmaz fggetlen lesz az sszegmatroidban. Bizony ts. Azt igazoljuk, hogy tetszleges i-re Fi0 fggetlen lesz Mi ben Ehhez az ir nytott ton visszafel haladva fogjuk cserlgetni az ; ! elemeket. Ha van xti l L-en, akkor x-et nyugodtan hozz vehetjk Fi-hez. Legyenek ; x;1! y1, : : : , ;! xlyl, az Fi-be belp L-beli lek, gy sorsz mozva, ahogy R-bl ti

fel haladva elhelyezkednek az ton. L that, hogy xl-et betve Fi-be, s yl-et kivve onnan, a t bbi xj elem Fi-re vonatkoz alapk re nem v ltozik, hiszen nincs ;! xiyl, i < l l, mivel L-nek az egyik legr videbb utat v lasztottuk. Ezt a cserlgetst folytatva, a vgl kapott Fi0 halmaz is fggetlen lesz. Ezt az elj r st ismteljk addig, amg el nem ll a II. eset Nem ltezik ir nytott t R-bl T -be Bel tjuk, hogy ekkor az Rbl ir nytott ton elrhet pontok halmaza (ebbe R-et is belertjk) megfelel Y -nak. Jel ljk teh t a fenti halmazt Y -nal. Az nyilv nval, hogy F1    Fk kit lti S ; Y -t, gy csak azt kell bel tnunk, hogy minden i-re jFi Y j = ri (Y ). Mivel Y -bl a felttel szerint nem lp ki l, ezrt tetszleges x ;2 Y ; Fi elemnek az Fi-re vonatkoz alapk re Fi Y -ban van. "gy  ri (Fi Y ) + x = ri(Fi Y ) = jFi Y j. Ebbl r gt n k vetkezik (29. Lemma), hogy ri(Y ) = ri(Fi Y ) = jFi Y j L that, hogy az algoritmus polinomi lis (ha a matroidokn l szok

sos mdon van egy fggetlensgi or kulumunk, ami tetszleges halmazrl egy lpsben eld nti, hogy fggetlen-e vagy sem), hiszen ha jS j = n, akkor a segdgr f felptshez legfeljebb n(n ; 1)+ nk  2n2 lpsre van szksgnk. Egy lps sor n szintn O(n2) idben kereshetnk ir nytott utat R-bl T be, s minden lps sor n eggyel cs kken jRj, teh t legfeljebb n lpsre lehet szksgnk. "gy az algoritmus lpssz ma O(n3) 36 3. Keress matroidokban 3.1 A feladat Ha valaki tal lkozik a keresssel foglalkoz fejezet vgn tal lhat feladattal (l sd 20. Ttel), r ad sul tudja, hogy mi az a matroid, akkor k nnyen feltnhet neki, hogy a feladatban tulajdonkppen egy matroidrl van sz. Hiszen adott az S alaphalmaz, valamint ezen adott az Unk uniform matroid, s ekkor a k vetkez keressi feladattal llunk szemben: az S alaphalmazon bin risan keresnk egy elemet gy, hogy a kereshalmazok ppen a matroid fggetlen rszhalmazai. 43. De n ci Az (S F) matroid egy egyelem rszhalmaz

t hurok nak nevezzk, ha a rangja 0 (S F) hurokmentes, ha nem tartalmaz hurkot 44. De n ci Egy (S F) bin ris keressi feladatot (azaz most F 2S ) matroidban val keress nek neveznk, ha az (S F) p r hurokmentes matroidot alkot. K nnyen l that, hogy a hurokmentessgre lnyegben szksgnk van. Ha az M matroidban van legal bb kt hurok, akkor ezeket keressi szempontbl nem tudjuk megkl nb ztetni, mivel egyikk sem lehet benne egyik kereshalmazban sem. "gy csak az az eset ad rtelmes feladatot, amikor pontosan egy hurkot tartalmaz M, de ezzel nem fogunk foglalkozni (Ekkor egy olyan keressi feladatot kapunk, amikor nem tudjuk, hogy pontosan egy x elemet kell megkeresnnk, csak azt, hogy legfeljebb egyet.) A tov bbiakban matroidon mindig hurokmentes matroidot fogunk rteni. A feladatot a dolgozat h tralv rszben a legrosszabb esetben vizsg ljuk. Els pld nak megemltjk azt a nyilv nval tnyt, hogy ha maga az S alaphalmaz fggetlen, akkor termszetesen semmi megk tsnk

nincs a kereshalmazokra, teh t a keress dlog2 ne lpsben elvgezhet (meg llapodunk abban, hogy a tov bbiakban is mindig jS j = n). Mindenekeltt azt vizsg ljuk meg, hogyan kell kinznie egy optim lis algoritmusnak. Az els lpsben nyilv n nem tehetnk m st, mint hogy r krdeznk egy F S fggetlen halmazra Ha azt a v laszt kapjuk, hogy a 37 keresett elem benne van F -ben, akkor szinte kszen is vagyunk F -ben a felezses elj r s segtsgvel dlog2 jF je lpsben megtal lhatjuk x -ot. Ha viszont a v lasz az, hogy x 62 F , akkor nyilv nval, hogy F -rl ak r el is felejtkezhetnk: a feladatot egy krds elhaszn l s val az S ; F rszmatroidban val keressi feladatra vezettk vissza. Ebbl r gt n l that, hogy csak azok a sikeres algoritmusok rdekesek a sz munkra, amelyek lerhatk egy (F1 F2 : : : Fk ) rendezett k-assal, ahol F1    Fk az S alaphalmaz partcija fggetlen halmazokra. Itt a keress sor n elsz r az F1 halmazra krdeznk r , ha ebben nincs a keresett elem, akkor

az F2-re, s gy tov bb. Vgl, ha Fk;1 sem tartalmazza x -ot, akkor persze m r tudjuk, hogy Fk -ban van, gy erre nem kell kl n krdst elpazarolni. Megfordtva, az is nyilv nval, hogy M egy tetszleges, csupa nemres fggetlen halmazra val partcij hoz (ezeket a tov bbiakban r viden csak partciknak fogjuk nevezni) a fent lert mdon egyrtelmen tartozik egy sikeres keresalgoritmus is. Az egyszersg kedvrt mostantl azonostani fogjuk a sz munkra rdekes algoritmusokat a hozz juk tartoz partcikkal. egy (F1 : : : Fk ) partcij hoz rendeljk hozz az ; Most az M matroid  L(F1) : : : L(Fk ) sz m-k-ast, ahol ( ha i < k L(Fi) = i + dlog2 jFije k ; 1 + dlog2 jFk je ha i = k: Itt L(Fi)-t az Fi halmaz (az adott algoritmushoz tartoz) hossz nak nevezzk. L that, hogy ekkor az (F1 : : : Fk) algoritmus hossza ppen 1max L(Fi) ik lesz. Vegyk szre azt is, hogy egy r gztett (F1 : : : Fk) partci tagjait permut lva kl nb z algoritmusokat kapunk, amelyeknek a hosszuk is

kl nb z lehet. Nyilv nval, hogy ez a hossz akkor lesz a legkisebb, ha jF1j  jF2j    jFk j teljesl. "gy teh t csak a k vetkez halmazban lv algoritmusokkal kell foglalkoznunk: P := n  f(F1 : : : Fk) 2 Fk : F1 : : : Fk partci M-ben jF1j    jFkjg: k=1 A tov bbiakban algoritmuson csak P-beli algoritmusokat rtnk. Ezzel bel ttuk a k vetkez llt st: 45. ll ts Az M = (S F) matroidhoz tartoz keressi feladat bonyolultsga a k vetkez: L(S F) = 1min min max L(Fi) (3.1) kn (F :::F )2P 1ik 1 38 k Az eddigiekben l thatan csak trivi lisan tfogalmaztuk a dencikat, s gy persze pontos, de haszn lhatatlan rtket kaptunk a keressi bonyolults gra. A tov bbiakban a clunk egy picivel jobban haszn lhat, de m r nem felttlenl egybees als s fels korl tokat tal lni. 3.2 Als korl t Az als korl thoz elsz r megszabadulunk a (3.1)-beli els minimumtl Mindenekeltt jegyezzk meg, hogy L(S F)  1min min L(Fk;1): kn (F :::F )2P 1 k "gy elg

azt vizsg lnunk, hogy M egy partcij ban mekkora a m sodik legkisebb fggetlen halmaz (azaz Fk;1) hossza. 46. De n ci Az M = (S F) matroid part ci s szm nak azt a legkisebb K = K (M) sz mot nevezzk, amelyre M felbonthat K fggetlen rszhalmaz nak diszjunkt unij ra. Egy pontosan K halmazbl ll partcit minimlis part ci nak fogunk hvni. Jegyezzk meg, hogy a denci rtelmes, hiszen csak hurokmentes matroidokkal foglalkozunk, s gy 1  K  n. A 41 K vetkezmny szerint   j X j K = max : X S r(X ) A tov bbiakban, ha egyrtelm, hogy melyik matroidrl van sz, K (M) helyett csak K -t fogunk rni.   S halmazt pontos nak nevezzk, ha rj(XXj) = K   teljesl r . ltal nosabban, X S majdnem pontos, ha K ;1  rj(XXj)  K Jel lje rendre H, illetve H0 a pontos, illetve a majdnem pontos halmazokbl ll halmazrendszereket. (A HM illetve H0M jel lseket haszn ljuk, ha fel akarjuk tntetni, hogy melyik matroidrl van sz.) 48. Ttel Legyen M = (S F) matroid, F 2 F tetszleges

fggetlen halmaz 47. De n ci Az X Pontosan akkor ltezik M-nek olyan minimlis part ci ja, amelynek egyik eleme F , ha F lefogja H-t. Bizony ts. Nyilv nval, hogy pontosan akkor ltezik M-nek olyan minim lis (teh t K halmazbl ll) partcija, amelynek egyik eleme F , ha az M0 = 39 M ; F rszmatroidnak ltezik K ; 1 halmazbl ll (persze szksgkppen minim lis) partcija, azaz ha minden X S ; F -re  jX j   K ; 1 (3.2) r0(X ) teljesl. Mivel X S ; F esetn r0(X ) = r(X ), ezrt (32) pontosan akkor lesz igaz, ha minden P 2 HM pontos halmazra P 6 S ; F , vagyis F minden pontos halmazt metsz. 49. Kvetkezmny Legyen F1  FK+r egy part ci ja az M matroidnak, ahol r  0. Ekkor tetszleges r+1 (illetve r +2) halmazt kivlasztva az uni juk lefogja H-t (illetve H0-t). Bizony ts. A bizonyt s teljesen hasonl az elz ttelhez Az als korl trl szl ttelhez szksgnk lesz a k vetkez igen egyszer lemm ra, ami a keressi feladat megold sa egy igen speci lis esetben. 50.

Lemma Ha az M = (S F) matroid elll kt fggetlen halmaznak uni jaknt, akkor keressi bonyolultsga L(S F) = dlog2 ne: (3.3) Bizony ts. Az inform cielmleti als korl t miatt L(S F)  dlog2 ne "gy elg bel tnunk, hogy tudjuk a felezses elj r st alkalmazni. Ehhez azt igazoljuk, hogy M felbonthat egy d n2 e s egy b n2 c mret fggetlen halmaz unij ra. (Persze ebbl k vetkezik, hogy a halmazok diszjunktak lesznek) Ez viszont azonnal addik a matroidokra vonatkoz I3) axim bl, hiszen ha az egyik fggetlen mrete nagyobb, mint d n2 e, akkor ebbl ttehetnk egy elemet a m sikba gy, hogy tov bbra is mindketten fggetlenek maradjanak. 51. Ttel Legyen M = (S F) hurokmentes matroid Ekkor a hozz tartoz keressi feladatra L(S F)  K (M) ; 2 + dlog2 (H0)e (3.4) ahol (H0) a H0 halmazt lefog pontok minimlis szmt jel li. Bizony ts. A 14 fejezetben l tottak alapj n elg egy stratgi t megadnunk a v laszol sz m ra, amely legal bb K (M) ; 2 + dlog2 (H0)e krdsre

knyszerti a keres j tkost. Ez a k vetkez lesz: az els K ; 2 krdsre nemmel v laszolunk. Ekkor a 49 K vetkezmny miatt, ak rmilyen gyes volt is a 40 krdez, legal bb (H0) elem maradt, amelyekrl semmi egyebet nem tud, mint hogy k ztk van x . Az inform cielmleti als korl t szerint gy mg legal bb dlog2 (H0)e krdsre lesz szksge (s innentl kezdve gy v laszolunk, hogy a kt halmaz k zl mindig a nagyobban kelljen folytatnia a keresst). B r ltal ban nem lnyeges, hogy egy als korl t algoritmikusan meghat rozhat legyen, s r ad sul az is k zismert 4], hogy tetszleges halmazrendszer esetn kisz mt sa NP-nehz, mgis a fenti ttelbeli als korl t rtke polinom idben meghat rozhat a partcis algoritmus segtsgvel. (H0) kisz mt s hoz hat rozzuk meg elsz r a matroid K partcis sz m t (l sd a k vetkez fejezetet), majd az Edmonds-algoritmus segtsgvel egy maxiKS ;2 m lis K ; 2 elem rszpartcit. Ekkor nyilv n a kimarad R = S ; Fi i=1 halmaz elemsz ma

lesz (H0). L tni fogjuk, hogy nh ny speci lis esetben az als korl t pontos, s ltal ban is k zel van a keresalgoritmus ltal adott fels korl thoz ! a kt korl t k z tti kl nbsg ugyanis a matroid szab lytalans g bl addik, s pld ul az uniform matroid esetben teljesen el is tnik. 3.3 Algoritmus Az elz kt fejezetbl tulajdonkppen addik is a keresalgoritmus, csak nh ny technikai nehzsggel kell megbirkznunk. Az algoritmus lnyegben gy fog kinzni, hogy a matroidot pontosan K darab fggetlenre particion ljuk, ezeket nagys g szerint cs kken sorrendbe rakjuk, s ebben a sorrendben krdeznk r juk. Ha egyszer azt a v laszt kapjuk, hogy valamelyikkben benne van a keresett elem, akkor abban a halmazban a felezses elj r ssal folytatjuk a keresst. Termszetesen a partciban szerepl fggetlen halmazok megv laszt s ban szabadok vagyunk. Azt, hogy ez mennyire fontos lpse az algoritmus megtervezsnek, a k vetkez egyszer plda illusztr lja. 52. Plda Tekintsk az R1996

vektortr k vetkez elemeit: e1 = (1 0 : : : 0), : : : , e1996 = (0 : : : 0 1) f1 = (0 : : : 0 2), : : : , f4 = (0 : : : 0 5). L ttuk m r, hogy ezek a line ris fggetlensggel matroidot alkotnak, ami persze hurokmentes is K nnyen ellenrizhet, hogy a matroid egy minim lis partcija 5 fggetlenbl ll. Ha gy bontjuk fel, hogy az els fggetlen halmaz az e1 : : : e1996 elemekbl ll, mg t bbi elem egyelem fggetleneket alkot, akkor l that, hogy a keress hossza (a legrosszabb esetben) 1 + dlog2 1996e = 12. Vegyk azonban szre, hogy ha az e1996 f1 f2 f3 f4 41 elemeket kl n halmazokba tesszk, akkor a t bbi elemet tetszsnk szerint oszthatjuk el ezekbe a halmazokba, gy elg csak az elemsz mokat tekinteni. "gy pld ul ha az mindegyik halmazba 400 elemet tesznk, akkor az gy kapott algoritmus hossza m r 4+ dlog2 400e=13 lesz. Viszont ha az elemsz mokat a k vetkezkppen v lasztjuk meg: 1000 500 250 125 125, akkor a hossz csak 4 + dlog2 125e=11. B r az ltal nos esetben nem

lesz ekkora szabads gunk az elemek megv laszt s val (hiszen a pldabeli matroid majdnem szabad matroid volt), sz munkra mgis a halmazok elemsz mai lesznek a kezelhetek. Azt fogjuk igazolni, hogy nagyon kl nb z elemsz m fggetlen halmazokra val felbont sbl (mint az els eset az elz pld ban) legy rthatunk egy keressi szempontbl egyenletes partcit (mint a harmadik eset a pld ban). Elsz r azonban foglalkozzunk K meghat roz s val. Az Edmonds-fle partcis algoritmus ismeretben ez igen egyszer, hiszen csak egy olyan sz mot kell keresnnk, hogy annyi fggetlenre mg ppen felbonthat a matroid, de kevesebbre m r nem. Tudjuk, hogy 1  K  n, s gy K -ra a felezses elj r st alkalmazhatjuk, minden lpsben lefuttatva a partcis algoritmust. Mivel a partcis algoritmus lpssz ma O(n3), ezrt K -t meghat rozhatjuk O(n3dlog2 ne) lpsben. Ek zben persze kapunk is egy K elem partcit A pld bl l that, hogy gondot az okozhat, ha a partcibeli fggetlen halmazok mretei

k z tt tl nagy ugr sok vannak. Ennek kiksz b lshez megadunk egy elj r st, ami az algoritmus szempontj bl egyenletess teszi a mreteket. 53. Lemma Ha egy (F1 : : : FK ) sikeres algoritmusban valamilyen 1  i  K ; 2 indexre jFij > 2jFi+1j, akkor gyrthatunk egy legfeljebb ilyen hossz (F1 : : : Fi0 Fi0+1 : : : FK ) sikeres algoritmust, amelyre jFij  2jFi+1j. Bizony ts. Legyen jFi j = 2a + b, jFi+1j = a, ahol a, b egszek, s b > 0 Az I3) fggetlensgi axima ismtelt alkalmaz s val kapjuk, hogy ekkor Fibl ttehetnk d 3b e elemet Fi+1-be, gy, hogy az gy kapott Fi0 illetve Fi0+1 halmazok is fggetlenek lesznek. K nnyen bel that, hogy tetszleges egsz b-re b 23b c + d 3b e = b, gy jFi0j  2jFi+1j tnyleg teljesl. Az j algoritmus nyilv n sikeres lesz, ha az eredeti is az volt, gy azt kell mg bel tnunk, hogy tnyleg nem lett hosszabb, azaz l l mm   ; i + log2(2a + b)  i + 1 + log2 a + 3b : Ez trivi lisan teljesl, ha a s b olyanok, hogy (2a + b)  2(a + d 3b e).

Ez pontosan akkor nem ll fenn, ha b = 1, teh t azt kell igazolnunk, hogy dlog2(2a + 1)e  1 + dlog2(a + 1)e (3.5) 42 tetszleges a  0 egsz esetn. Ez viszont igaz, hiszen ha az l  0 egsz sz m olyan, hogy 2l < 2a + 1  2l+1, akkor 2a + 1 p ratlans ga miatt 2a + 1  2l+1 ; 1, de gy a + 1  2l, azaz (3.5) bal oldal n pontosan l + 1, mg a jobb oldal n legfeljebb l + 1 ll. 54. De n ci Egy (F1 : : : FK ) algoritmust egyenletes nek neveznk, ha jFK;1j ; jFK j  1, tov bb minden 1  i  K ; 2 esetn jFij  2jFi+1j. 55. Ttel Egy nem egyenletes algoritmus O(Kn) lpsben egyenletess tehet Bizony ts. A k vetkez algoritmus addik az eddigiek alapj n: 0. lps Legyen i = 1 1. lps Ha jFij > 2jFi+1j, akkor az 53 Lemm ban lert mdszerrel ezt javtsuk ki, s n veljk meg i-t 1-gyel. Ha i  K ; 2, akkor vissza az 1 lps elejre, kl nben tov bb a 2. lpsre 2. lps Ha jFK;1j;jFK j > 1, akkor az I3) fggetlensgi axima alapj n trakhatunk FK;1-bl FK -ba annyi elemet, hogy

jFK;1j ; jFK j  1 legyen, s persze fggetlenek maradjanak a halmazok. 3. lps Ha az algoritmus mg nem egyenletes, akkor vissza a 0 lpsre, kl nben pedig kszen vagyunk Az algoritmus vgessge s a lpssz mra vonatkoz llt sunk is k vetkezik abbl az egyszer meggyelsbl, hogy a matroid minden eleme az algoritmus minden lpse sor n csak nagyobb index halmazba kerlhet. Mivel az I3) axima minden alkalmaz sa sor n legal bb 1 elem nagyobb index halmazba kerl, gy az axim t legfeljebb Kn-szer alkalmazzuk. Ezek alapj n a keresalgoritmusunk a k vetkezkppen nz ki. I. lps Vesznk egy tetszleges K elem partcit, majd elksztjk a matroidot a 55 Ttel alkalmaz s hoz Ehhez elsz r F1-et M b zis v bvtjk F2  FK -beli elemekkel, majd F1-et m r nem v ltoztatva F2-t M ; F1 b zis v , s gy tov bb. K nnyen l that, hogy ezt egy fggetlensgi or kulum segtsgvel mindenfle trkk k nlkl is O(Kn) idben megtehetjk. (Megjegyezzk, hogy az algoritmus itt ersen javthat

lenne ! ugyanis a k vetkez lps szempontj bl nem mindegy, hogy milyen partcibl indulunk ki. Nyilv nvalan l that lesz, hogy igaz bl egy olyan partcis algoritmusra lenne szksgnk amennyiben egy ltal n ltezik ilyen], amely a kiindul si matroid egy olyan (F1 : : : FK ) partcij t adja meg, hogy minden i-re Fi 43 rangja a lehet legnagyobb (azaz b zis), de ko-rangja a lehet legkisebb M ; (F1  Fi;1)-ben.) II. lps Az gy kapott partcit a 55 Ttel alapj n egyenletess tesszk, s m ris rendelkezsnkre ll egy rezheten elg j algoritmus a matroidban val keressre. (Fleg ha sikerlne egy olyan algoritmust tal lni, amely megfelel az elbbi z rjeles megjegyzsben szerepl kv nalmaknak.) Ezzel megadtunk egy algoritmust matroidokban val keressre. Szok s azt is megkrdezni, hogy mit tudunk elre, azaz algoritmus nlkl mondani a keressi bonyolults grl. Erre egyelre csak egy trivi lis fels becslst tudok mondani: nyilv nvalan mindig ki tudjuk gy egyenlteni

az algoritmust, hogy a fggetlen halmazok elemsz mai d Kn e, illetve b Kn c legyenek, teh t az keressi bonyolults g (s persze a fenti algoritmus hossza is) legfeljebb K ;1+   n log2d K e . Ez termszetesen abbl a szempontbl pontos is, hogy rengeteg olyan matroid ltezik, amelyre a legjobb algoritmus pontosan ilyen hossz. 3.4 Alkalmaz sok Elsz r a 20. Ttelben szerepl keressi feladatot oldjuk meg Erre persze elv rjuk, hogy pontos rtket kapjunk. 3.41 Keress legfeljebb k elem keres halmazokkal Mint m r l ttuk, ez tulajdonkppen az Unk uniform matroidban val keress problm ja. (Az egyszersg kedvrt feltesszk, hogy n > 2k) Az als korl thoz most k nnyen meg tudjuk hat rozni a H0 halmazrendszert. Elsz r is, K = d nk e lesz, s mivel egy X S halmaz rangja min(jX j k), ezrt  H0 = X S : jX j > k(K ; 2)g azaz az sszes legal bb k(K ; 2) + 1 elem halmazt kell lefognunk. K nnyen l that, hogy ekkor (H0) = n ; k(K ; 2), teh t a 51. Ttel alapj n azt kaptuk, hogy  

L  K ; 2 + dlog2 n ; k(K ; 2)e ahol K = nk : M r most l thatjuk, hogy az als korl t megegyezik a 20. Ttelben kapott (pontos) als korl ttal. (Csak ott K ; 2-t t-vel jel ltk) Az elz rszben megadott keresalgoritmust tekintve is k nny a dolgunk ennl a feladatn l, hiszen tetszleges K halmazbl ll partcit vve 44 az I. lpsben, az elkszts ut n lnyegben (azaz az elemsz mokat tekintve) mindig ugyanazt a partcit kapjuk: jF1j =  = jFK;1j = k, s jFK j = n mod k lesz. Mivel a II lps sor n csak az FK;1 s FK k z tti ugr st kell kiegyenlteni, s jFK j  1 miatt ez nem rontja el sehol m shol az egyenletessget, ezrt ppen a 20. Ttelben lert algoritmust kapjuk vissza 3.42 Egy egyszer specilis eset Az ltal nos eredmnyeink igen jl viselkednek abban az esetben, amikor a matroid eleget tesz az al bbi egyenletessgi k vetelmnynek:  jS j  (3.6) r(S ) = K: Ekkor nyilv nval, hogy a t := n mod r(S ) jel lssel az als korl t legal bb K ;2+dlog2(r(S )+t)e lesz.

(Hiszen ha az els K ;2 halmaz mindegyike r(S ) elem, az utols kt halmazba mg akkor is be kell frnie r(S ) + t elemnek.) M srszt k nnyen l that, hogy ak rmilyen K elem partcit kapunk is az algoritmus I. lpsben, csak az utols kt halmaz mrett kell kiegyenlteni (ezt pedig mg az als korl t is tartalmazza). A (3.6) felttelt kielgt matroidra plda egy teljes gr f k rmatroidja Erre kisz molva az als korl tot, s megnzve az algoritmus mk dst, tnyleg l that, hogy ebben az esetben meglehetsen k zel vannak egym shoz a korl tok. 45 46 Felhaszn lt irodalom 1] M. Aigner Combinatorial Search Wiley(Teubner Series in Computer Science. Wiley(Teubner, 1988 2] R. Dorfman The detection of defective members of large populations Ann. Math Statist, 14:436(440, 1943 3] A. Frank Matroidok Sokszorostott jegyzet, 1995 4] M. R Garey and D S Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979 5] D. A Hu&man A method for the

construction of minimum redundancy codes. Proc I R E, 40:1098(1101, 1952 6] G. O H Katona On separating systems of a nite set J Combinatorial Theory, 1:174(194, 1966. 7] C. E Shannon A mathematical theory of communication Bell System Techn. J, 27:379(424, 623(657, 1948 8] R. To)i*. Two counterfeit coins Discrete Math, 46:295(298, 1983 9] R. To)i*. Four counterfeit coins Review of Research Fac Sci Univ Novi Sad, 14:99(108, 1984. 10] I. Wegener On separating systems whose elements are sets of at most k elements. Discrete Math, 28:219(222, 1979 47