Matroid

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)

A leggyakoribb definíció

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}}\neq \emptyset$;
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 \ \exists 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

Nemüresség

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

1': $\emptyset \in {\mathcal {F}}$;

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

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

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:

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

$\ \forall F\!\in \!{\mathcal {F}}\cap {\mathcal {P}}(X):\ \left[\ \ \left(\ \exists 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

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

Izomorfia

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)\ |\ \exists 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

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'\neq \emptyset$, 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

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\{\emptyset \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

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á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 (1909–2005) é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 Korte – L. 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. Korte – L. Lovász: Greedoids – A 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

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

Lásd még

• matroidelmélet
• lineáris függőség
• lineáris függetlenség

Irodalom

• Cormen – Leiserson – Rivest – Stein: Új algoritmusok . Scolar Kiadó, Bp., 2003. ISBN 963-9193-90-9
• Frank András: (jegyzetek) Matroidelmélet jegyzet (Post Script)
• Lovász László: A matroidelmélet rövid áttekintése, Matematikai Lapok, 22(1971), 249-267.
• A brief introduction to matroid theory (Joseph E. Bonin) (PS)
• Történelem (angol nyelven)

Angolul

• L. Lovász – A. Recski (szerk.): Matroid Theory,. Colloquia Mathematica Societatis János Bolyai, 40. Bolyai Társulat, Bp,, 1985; ISBN 0-444-87580-8 ; ISBN 963-8021-80-2 .
• Oxley, James G.: "Matroid Theory", Oxford University Press, New York, 1992
• A PlanetMath cikke a matroidokról.
• Steven R. Pagano: Matroids and Signed Graphs