Matroid

A Wikipédiából, a szabad lexikonbó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övé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ó 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.

Tartalomjegyzék

1 Definíció(k)
2 Egyéb fogalmak
- 2.1 Izomorfia
- 2.2 Részmatroid vagy törlés
3 Típusok és példák
4 Matroidtörténelem
5 Általánosítások és változatok
6 Lásd még
- 6.1 Irodalom
- 6.2 Angolul

[szerkesztés] Definíció(k)

[szerkesztés] 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:

a halmazrendszer nem üres;
a halmazrendszer leszálló, azaz egy független halmaz összes részhalmaza is független;
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) egy elemet 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ó.

[szerkesztés] A kombinatorikus definíció átfogalmazásai

Fő szócikk: Matroidaxiómák

[szerkesztés] -) Nemüresség

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$ .

[szerkesztés] -) 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 pl.: 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 pl. 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.

[szerkesztés] -) 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.

[szerkesztés] Egyéb fogalmak

[szerkesztés] 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) \ | \ \exist x \in X : f(x)=y \right\}$ jelöléssel $X \in \mathcal{F} \Leftrightarrow f[X] \in \mathcal{F}'$ .

[szerkesztés] 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' \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'$

[szerkesztés] 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\{ \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=2^{ \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.

[szerkesztés] 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á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élet 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 alkalmazásra került. 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., Spronger-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.

[szerkesztés] Általánosítások és változatok

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

[szerkesztés] Lásd még

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

[szerkesztés] Irodalom

Cormen – Leiserson – Rivest – Stein: Új algoritmusok . Scolar Kiadó, Bp., 2003. ISBN 9639193909
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)

[szerkesztés] Angolul

Oxley, James G.: "Matroid Theory", Oxford University Press, New York, 1992

A PlanetMath cikke a matroidokról. Amikor hajlandó bejönni, számtalan ekvivalens definíció található benne. Figyelmeztetés: általában lassú.
Sandra Kingan: Matroid theory. Linkgyűjtemény, sok jó linkkel.
Steven R. Pagano: Matroids and Signed Graphs

A lap eredeti címe "http://hu.wikipedia.org../../../m/a/t/Matroid.html"

Kategória: Kombinatorika