Matroid

A Wikipédiából, a szabad enciklopédiából

A matroid a modern matematika egy igen újnak számító fogalma, melyet 1935-ben vezetett be Hassler Whitney amerikai matematikus; maga a szó latin-görög szóösszetétel, melynek jelentése: „mátrix-szerű”. Némileg, bár elég pontatlanul tényleg a mátrix-fogalom egy általánosításáról van szó (ha a mátrixokat mint oszlopaik vagy soraik halmazait és ezek részhalmazait tekintjük), de pontosabb és hasznosabb, ha a matroid fogalmát egy olyan, halmazokból álló, axiómarendszerrel leírt konstrukciónak tekintjük, mely a lineáris függetlenség / lineáris összefüggőség fogalmát próbálja absztrahálni.

Egy véges U halmaz (alaphalmaz) feletti matroidon lényegében olyan nem üres leszálló halmazrendszert (azaz U részhalmazai P(U) halmazának egy részhalmazát) érthetünk – tagjait független halmazoknak nevezzük – melyre igaz, hogy bármely két különböző számosságú független halmaz esetén a kisebb számosságú bővíthető úgy egy rajta kívüli, a nagyobb számosságúban lévő elemmel, hogy az így bővített halmaz is független. A matematikailag pontosabb leírás lentebb található.

A matematikában a lineáris algebra és a gráfelmélet régóta jegyben járnak: a matroidelmélet eme kapcsolat egyik törvényesítésének vagy gyermekének tekinthető, és legfontosabb fogalmai, eredményei az e két területről származóak némileg új szemléletben való megfogalmazásai és általánosításai. A matroidelmélet leginkább a kombinatorika alterületének számítható, bár fontos számítógéptudományi vonatkozásai is vannak. A kombinatorikus optimalizálás szakemberei szerint ugyanis a matroidok meghatározhatóak olyan „leszálló” halmazrendszerekként is, melyekre egy, a halmazrendszer alaphalmazán értelmezett súlyfüggvény meghatározta, pontosan definiált értelemben mohó algoritmus tetszőleges súlyfüggvényt véve is megadja ennek optimumát (a pontos meghatározást ld. lent).

A felfedezés óta elmúlt évtizedekben több könyv is megjelent e tárgykörben. A matroidelmélet sok alkalmazásra talált az áramkörök analízisében, a kapcsoláselméletben, a lineáris programozásban, a hálóelméletben és a gráfelméletben.

Definíció(k)[szerkesztés | forrásszöveg szerkesztése]

A leggyakoribb definíció[szerkesztés | forrásszöveg szerkesztése]

Matematikailag, a kombinatorikus felépítést választva, egy  U véges halmaz feletti matroid egy olyan  \mathfrak{M} = \left( U, \mathcal{F} \right) párból álló struktúra, ahol  \mathcal{F} \subseteq \mathcal{P}(U) pedig egy  U feletti halmazrendszer, a matroid tagjainak halmaza; melynek elemeit független halmazoknak szokás nevezni; s mely rendelkezik az alábbi tulajdonságokkal:

  1. a halmazrendszer nem üres;
  2. a halmazrendszer leszálló, azaz egy független halmaz összes részhalmaza is független;
  3. a független halmazok kölcsönösen bővíthetőek: ha két független halmaz számossága eltérő, akkor a nagyobból (a több elemet tartalmazóból) ki tudunk választani egy, a kisebb halmazban nem szereplő elemet úgy, hogy azt a kisebbe téve az így „bővített kisebb” halmaz is független.

Ez az az axiómarendszer, melyet leginkább „bővíthetőségi axiómarendszernek” nevezhetnénk. Formálisan a következőképp adhatjuk meg a fenti axiómákat:

1. nem-üresség: \mathcal{F} \ne \empty ;
2. leszállóság:  \forall X,Y \! \in \! \mathcal{P}(U) : \; \left[ \ \left( X \subseteq Y \ \wedge \ Y \! \in \! \mathcal{F} \right)  \ \Rightarrow \ X \! \in \! \mathcal{F} \ \right]
3. kölcsönös bővíthetőség:  \forall K,N \! \in \! \mathcal{F} :  \; \left[ \ \left| K \right| < \left| N \right| \ \Rightarrow \ \exist x \! \in N \! - \! K : \ \left( K \cup \left\{ x \right\} \in \mathcal{F} \right) \ \right]

Megjegyzések:

  • formálisan, pontosabban a matroid tehát nem halmazrendszer, hanem egy halmazból és egy felette értelmezett halmazrendszerből álló rendezett pár.
  • a harmadik axiómát, talán elnevezési/fordítási hiba vagy tanácstalanság miatt vagy más okból, „kölcsönös felcserélhetőségi axiómának” is nevezik (ld. Cormen-Leiserson-Rivest-Stein: Új algoritmusok 346. o.) .

Ezeket a tulajdonságokat (illetve, ha a matroid fogalmát máshogy építjük fel, a velük ekvivalens tulajdonságokat) matroidaxiómáknak nevezzük. A fenti matroid-definíció számos "ekvivalens" alakban megfogalmazható.

A kombinatorikus definíció átfogalmazásai[szerkesztés | forrásszöveg szerkesztése]

-) Nemüresség[szerkesztés | forrásszöveg szerkesztése]

Az 1. axióma helyettesíthető a következővel:

1':  \empty \in \mathcal{F} ;

hiszen ha  \mathcal{F} nem üres, akkor tartalmaz egy független halmazt, és ekkor 2. miatt ennek részhalmaza,  \empty is független; míg nyilván  \empty \in \mathcal{F} \Rightarrow \mathcal{F} \ne \empty .

-) A rang és a maximális független halmazok[szerkesztés | forrásszöveg szerkesztése]

A 3. matroidaxióma a lineáris algebra egy alaptételének (kicserélési lemma) általánosítása. Számtalan erősebb, többet mondó és gyengébb változatban is megfogalmazható úgy, hogy a fent megadott axiómarendszerben a 3. axiómát az átfogalmazottjára cserélve a kapott új axiómarendszer szintén a matroidfogalmat írja le. Ezek a sorozatos gyengítések és átfogalmazások azért fontosak, mert amikor általános, absztrakt matroidokkal dolgozunk, akkor célszerű erős axiómákat használni, melyek sok információt tartalmaznak; amikor viszont egy konkrétabb struktúráról kell belátni, hogy matroid, a gyengébb axiómák teljesülésének belátása sokkal kevesebb munkát jelent.

Egy igen fontos, a rang fogalmához vezető átfogalmazás, a maximalitási axióma például: Minden S-beli részhalmazra az e részhalmazban legbővebb független halmazok azonos elemszámúak, azaz létezik a részhalmaz rangja (az „ebben nem bővíthetőt” úgy kell-e érteni, hogy s-beli elemmel bővítve vagy nem lesz független, vagy nem lesz X-beli). Formálisan:

 \forall X \! \in \! \mathcal{P} \! \left( U \right) : \ \exist r_{X} \! \in \! \mathbb{N}:

 \ \forall F \! \in \! \mathcal{F} \cap \mathcal{P}(X): \ \left[ \ \ \left( \ \exist x \! \in \! X: \ F \cup \left\{ x \right\} \not\in \mathcal{F} \ \right) \Rightarrow \left| F \right| = r_{X} \ \right] .

Természetesen ez abból következik, hogy ha a kölcsönös bővíthetőség axiómája alapján egy független halmazt bővíteni kezdünk, az nem folytatható a végtelenségig (mivel például maga az alaphalmaz is véges!). Tehát előbb-utóbb nem tudjuk úgy bővíteni a független halmazt, hogy független maradjon, hanem valamilyen r(F) számnál abba kell hagynunk. A matroidok érdekessége (ti. egy lehetséges definíciója), hogy bármelyik független halmazból is induljunk ki, ez a számosság ugyanannál az r számnál stabilizálódik, ugyanis ha lenne két ilyen r<r' szám, az ellentmondana a bővíthetőség axiómájának. Egy szigorúbb bizonyítás itt található; további átfogalmazások és ezek egyenértékűségének bizonyításai pedig a matroidelmélet és a matroidaxiómák cikkekben.

Közvetett felépítések[szerkesztés | forrásszöveg szerkesztése]

A rang illetve a bázis fogalmának segítségével még további axiómarendszerekkel is lehet közvetve a matroid fogalmához jutni, melyek a rangaxióma-rendszerhez, a bázisaxióma-rendszerhez vagy egyéb hasznos felépítésmódokhoz vezetnek. ezek a közvetett axiómarendszerek abban különböznek az egyszerű átfogalmazásoktól, hogy nem közvetlenül matroidot, hanem másfajta struktúrát adnak meg, melyből azonban matroid konstruálható. Ld. matroidelmélet ill. matroidaxiómák.

Egyéb fogalmak[szerkesztés | forrásszöveg szerkesztése]

Izomorfia[szerkesztés | forrásszöveg szerkesztése]

Két matroid akkor izomorf, ha létezik alaphalmazaik között olyan kölcsönösen egyértelmű leképezés, melynél pontosan a független halmazok képe független.

Ezt két  \mathcal{M} = \left\{ U, \mathcal{F} \right\} és  \mathcal{M}' = \left\{ U', \mathcal{F}' \right\} matroid esetén  \mathcal{M} \cong \mathcal{M}' jelölheti. Tehát ez azt jelenti, hogy létezik olyan  f: U \mapsto U' bijekció az alaphalmazok között, melyre tetszőleges  X \subseteq U esetén az  f[X] := \left\{ y \in R(f) \ | \ \exist x \in X : f(x)=y \right\} jelöléssel  X \in \mathcal{F} \Leftrightarrow f[X] \in \mathcal{F}' .

Részmatroid vagy törlés[szerkesztés | forrásszöveg szerkesztése]

Ha  \mathcal{M} = \left\{ U, \mathcal{F} \right\} és  \mathcal{M}' = \left\{ U', \mathcal{F}' \right\} két olyan matroid, melyre  U' \subseteq U és  U' \ne \empty , akkor a második matroidot az első részmatroidjának nevezzük. Könnyen igazolható, hogy a részmatroid is mindig matroid.

Ilyenkor azt is mondjuk, a második matroid az elsőből a  D = U-U' halmaz törlésével (vagy elhagyásával) keletkezik, vagy hogy megszorítása az U' halmazra, azaz  \mathcal{M} ' = \mathcal{M} | U'

Típusok és példák[szerkesztés | forrásszöveg szerkesztése]

A matroidok legfontosabb példái a mátrixmatroidok, fontos példák az affin matroidok, a grafikus (gráfokból konstruált) matroidok és az uniform (n,k)-matroidok.

  • Az  A halmaz feletti triviális matroidok az üres matroid és teljes matroid, ezek olyan  \left( A, \mathcal{F} \right) párok, ahol az üres matroid esetében  \mathcal{F}= \left\{ \empty \right\} , a teljes matroid esetében pedig  \mathcal{F}= \mathcal{P} \left(A \right) , ahol  \mathcal{P} \left( A \right) az A halmaz részhalmazainak halmazát, azaz hatványhalmazát jelöli.
  • Fenti kombinatorikus definíciónk alapján a legegyszerűbb példákat a matroid fogalmára az uniform matroidok jelentik: Adott egy n elemű A halmaz, és egy k szám, melyre 0≤k≤n. Legyen F az összes legfeljebb k elemű A-beli részhalmaz halmaza. Ekkor az  U_{n,k} = \left( A, \mathcal{F} \right) pár matroid, melyet n-edrendű k-adosztályú uniform matroidnak nevezünk. Megjegyezzük: a triviális matroidok is uniform matroidok, mikor is  k=0 ill.  k={ \left | A \right|} .
  • Mátrixmatroid: Adott v.milyen test feletti n×m-es mátrix, ennek oszlopainak halmaza legyen A. Az A egy részhalmazát, azaz néhány oszlopot nevezzük akkor függetlennek, ha mint n-dimenziós vektorok lineárisan függetlenek. A független oszlophalmazok halmaza legyen F, ekkor az (A, F) pár matroid, melyet a test és az A feletti mátrix-matroidnak nevezünk. Ha az alaptest kételemű; akkor bináris matroidról beszélünk.
  • Körmatroid, gráfmatroid vagy grafikus matroid: adott egy véges V halmaz feletti  V, E gráf. E felett értelmezünk egy matroidot, melynek U alaphalmaza az élek  E halmaza, független halmazoknak pedig azokat az élhalmazokat nevezzük, melyek körmentesek, azaz erdőt alkotnak.

Konkrétabb példák az egyes típusokat tárgyaló cikkekben találhatóak.

Matroidtörténelem[szerkesztés | forrásszöveg szerkesztése]

A matroid fogalmát Hassler Whitney (1907-1989) Wolf-díjas amerikai matematikus vezette be 1935-ben írt, „A lineáris összefüggőség absztrakt tulajdonságai” („On the abstract properties of linear dependence”) c. dolgozatában. Ebben leginkább a mátrix-matroidokat tárgyalja, tehát a kombinatorikus definíció szerepel benne; a mohó algoritmusra alapozó definíció Jack Edmonds kutatásai nyomán született meg 1971-ben („Matroids and the greedy algorithm”, Mathematical Programming, 126.-136., 1971). Whitney cikke sokáig nem váltott ki különösebb hatást, de William Tutte cikkei hatására (akit helytelenül tartanak a matroidok újrafelfedezőjének, mivel ismerte Whitney munkásságát, hivatkozott rá) újból elindult a kutatásuk. A felfedezés óta elmúlt évtizedekben több könyv is megjelent e tárgykörben.

A matroidelméletnek a gráfelméleten kívüli geometriai kapcsolataira is rábukkantak, ebben nagy szerepe volt Saunders MacLanenek (1909–) és Gian-Carlo Rotának (1932-1999). Utóbbi foglalkozott a Whitney által felvetett reprezentálhatóság kérdésével is.

A matroidelméletet a matematikában a kombinatorikában (gráfelmélet), az operációkutatásban (kombinatorikus optimalizálás, lineáris programozás, lineáris kódelmélet), és az informatikában (áramkörök analízise, kapcsoláselmélet) is alkalmazzák. A matroidfogalom általánosításában („mohoid”/„greedoid”) úttörő szerepet játszott Lovász László magyar matematikus is (B KorteL. Lovász: Mathematical structures underlying greedy algorithms, in F. Gécseg (szerk.): Fundamentals of Computation theory, Lecture notes on Computer Science, 117., 205.-209., Springer-Verlag, 1981.; B. KorteL. Lovász: GreedoidsA structural framework for the greedy algorithms; in W. Pulleybank (szerk.): Progress in combinatorial optimization, 221.-243.; Academic Press, 1984.

Általánosítások és változatok[szerkesztés | forrásszöveg szerkesztése]

  • Gammoid
  • Mohoid/Greedoid
  • Delta-matroid
  • Multimatroid (ld. még [1])
  • Antimatroid
  • Irányított matroid

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Irodalom[szerkesztés | forrásszöveg szerkesztése]

Angolul[szerkesztés | forrásszöveg szerkesztése]