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]

A leggyakoribb definíció[szerkesztés]

Matematikailag, a kombinatorikus felépítést választva, egy véges halmaz feletti matroid egy olyan párból álló struktúra, ahol pedig egy 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: ;
2. leszállóság:
3. kölcsönös bővíthetőség:

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]

Nemüresség[szerkesztés]

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

1': ;

hiszen ha nem üres, akkor tartalmaz egy független halmazt, és ekkor 2. miatt ennek részhalmaza, is független; míg nyilván .

A rang és a maximális független halmazok[szerkesztés]

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 X 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 érteni, hogy S-beli elemmel bővítve vagy nem lesz független, vagy nem lesz X-beli). Formálisan:

.

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]

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]

Izomorfia[szerkesztés]

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 és matroid esetén jelölheti. Tehát ez azt jelenti, hogy létezik olyan bijekció az alaphalmazok között, melyre tetszőleges esetén az jelöléssel .

Részmatroid vagy törlés[szerkesztés]

Ha és két olyan matroid, melyre és , 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 halmaz törlésével (vagy elhagyásával) keletkezik, vagy hogy megszorítása az U' halmazra, azaz

Típusok és példák[szerkesztés]

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 halmaz feletti triviális matroidok az üres matroid és teljes matroid, ezek olyan párok, ahol az üres matroid esetében , a teljes matroid esetében pedig , ahol 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 pár matroid, melyet n-edrendű k-adosztályú uniform matroidnak nevezünk. Megjegyezzük: a triviális matroidok is uniform matroidok, mikor is ill. .
  • 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 gráf. E felett értelmezünk egy matroidot, melynek U alaphalmaza az élek 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]

A matroid fogalmát Hassler Whitney (19071989) 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átrixmatroidokat 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 Mac Lanenek (19092005) és Gian-Carlo Rotának (19321999). 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]

Lásd még[szerkesztés]

Irodalom[szerkesztés]

Angolul[szerkesztés]