Matroidaxiómák

A matroid egy axiómákkal definiált matematikai struktúra. A matroidok speciális halmazrendszerek (pontosabban egy $U$ véges halmazból és egy felette értelmezett ${\mathcal {F}}$ halmazrendszerből álló ${\mathfrak {M}}=\left(U,{\mathcal {F}}\right)$ struktúrák), konkrétan nem üres leszálló halmazrendszerek, melyekre egyéb tulajdonságok is teljesülnek. Ezeket sokféle ekvivalens alakban lehet megadni, melyek egyenértékűségét e szócikk tárgyalja.

Az $U$ alaphalmaz vagy univerzum feletti ${\mathcal {F}}\subseteq {\mathcal {P}}(U)$ halmazrendszer a matroid tagjainak halmaza; melynek elemeit független halmazoknak szokás nevezni.

A matroidok leggyakoribb standard definíciója az a három axiómából álló axiómarendszer szokott lenni, melyet bővíthetőségi axiómarendszernek fogunk nevezni.

Nemüresség

Mindenekelőtt belátjuk, hogy egy leszálló halmazrendszer akkor és csak akkor nem üres, ha tartalmazza az üres halmazt. Ugyanis ha leszálló, akkor amennyiben tartalmaz egy halmazt, akkor annak minden részhalmazát is, tehát az üres halmazt is, és mivel nem üres, ezért tartalmaz is egy halmazt, és így a leszállóságból következően az üres halmazt is. Fordítva, ha egy halmazrendszer tartalmazza elemként üres halmazt, akkor maga nyilván nem üres.

Tehát ekvivalens a következő két axiómarendszer egy $U$ halmaz feletti ${\mathcal {F}}$ halmazrendszerre:

• I. „nemürességi axiómarendszer”:
  • nem üres, azaz ${\mathcal {F}}\neq \emptyset$
  • leszálló, azaz $\forall X,Y\!\in \!{\mathcal {P}}(U):\;\left[\ \left(X\subseteq Y\ \wedge \ Y\!\in \!{\mathcal {F}}\right)\ \Rightarrow \ X\!\in \!{\mathcal {F}}\ \right]$

• II. „alternatív nemürességi axiómarendszer”:
  • Tartalmazza az üres halmazt, azaz $\emptyset \in {\mathcal {F}}$
  • leszálló, azaz $\forall X,Y\!\in \!{\mathcal {P}}(U):\;\left[\ \left(X\subseteq Y\ \wedge \ Y\!\in \!{\mathcal {F}}\right)\ \Rightarrow \ X\!\in \!{\mathcal {F}}\ \right]$

A következőkben a matroidok meghatározására a „nemürességi” a.r.-t használjuk.

A bővíthetőségi axiómarendszer

E szerint 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 a matroidok definiálására leginkább használt axiómarendszer.

B1.	nem-üresség:	${\mathcal {F}}\neq \emptyset$;
B2.	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]$
B3.	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és: 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.)

Halmaz bővítője és maximális függetlensége

A szóban forgó $x\in N-K$ elemet egyébként a $K$ halmaz bővítőjének nevezzük. Célszerű ezt általánosabban is megfogalmazni: legyen $X\subseteq U$ az alaphalmaz tetszőleges részhalmaza. Ha van olyan $x\in U-X$ elem, melyre $X\cup \left\{x\right\}\in {\mathcal {F}}$, akkor ezt az elemet az $X$ bővítőjének, ha pedig olyan $y\in U-X$, melyre $X\cup \left\{y\right\}\not \in {\mathcal {F}}$, akkor utóbbit $X$ antibővítőjének nevezzük.

Ha $F\in {\mathcal {F}}$ független halmaz, és nincs bővítője, akkor maximális független halmaznak nevezzük, vagy pedig a matroid bázisának. Tehát a maximalitást a tartalmazásra ($\subseteq$) értjük a matroidelméletben (nem pedig a számosságok rendezésére, $\leq$-re), hiszen ez pontosan azt jelenti, hogy nincs olyan $Y$ halmaz, melyre $X\leq Y\wedge Y\in {\mathcal {F}}$.

A fenti fogalmak általánosítása: Legyen most is $A\subseteq X\subseteq U$ az alaphalmaz két részhalmaza. Ha van olyan $x\in X-A$ elem, melyre $A\cup \left\{x\right\}\in {\mathcal {F}}$ (s ekkor $A\cup \left\{x\right\}\subseteq X$, akkor ezt az elemet az $A$ halmaz $X$-re vonatkozó relatív bővítőjének nevezzük.

Ha $A\in {\mathcal {F}}$ független, és nincs $X$-re vonatkozó relatív bővítője, akkor nevezzük $X$-ben, X-re vonatkozóan (relatíve) maximálisan függetlennek, vagy X-ben nem bővíthetőnek.

A maximalitási axiómarendszer és a rang

Az előkelő „maximalitási” szó arra utal, hogy a nem bővíthető független (maximális független) halmazok számossága ugyanaz.

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.	maximalitási tulajdonság:	$\forall X\!\in \!{\mathcal {P}}\!\left(U\right):\ \forall F,G\!\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|=\left|G\right|\ \right]$

Halmaz rangja

Az $F,G,...\subseteq X$ nem bővíthető független halmazok esetén az $\left|X\right|=\left|Y\right|=...=r_{X}\in ;\mathbb {N}$ jelölést bevezetve a harmadik axióma nyilván teljesen ugyanaz, mint a következő:

$\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]$

Az $r_{X}$ természetes számot, mely a matroidelméletben lényeges szerepet játszik, az $X(\subseteq U)$ (nem feltétlenül független) halmaz rangjának nevezzük. Az U halmaz rangját a matroid rangjának nevezzük.

Ekvivalencia a bővíthetőségi axiómarendszerrel

Belátjuk, hogy a bővíthetőségi tulajdonságból következik a maximalitási, ill. fordítva.

• Legyen $\left(U,{\mathcal {F}}\right)$ bővíthetőségi tulajdonsággal rendelkező nem, üres leszálló halmazrendszer. Legyen $M,N\subseteq X$ két maximális („nem bővíthető”) független halmaz X-ben. Ha az egyik szigorúan kisebb számosságú lenne, mint a másik, mondjuk $\left|M\right|<\left|N\right|$ lenne (indirekt bizonyítás), akkor ez ellentmondana a bővíthetőségi tulajdonságnak, hiszen feltevéseinkből adódóan biztos, hogy van olyan $x\in N-M$, amelyre $M\cup \left\{x\right\}\in {\mathcal {F}}$ független, de mivel $x\not \in M$ és M véges (mivel az alaphalmaz is véges), ezért $M\subset M\cup \{x\}$, ami ellentmond annak, hogy maximális, azaz nem bővíthető. Tehát (< trichotom tulajdonsága miatt) bármely két maximális független halmaz azonos számosságú, tetszőleges $X\subseteq U$ esetén.
• Legyen $\left(U,{\mathcal {F}}\right)$ izokardinalitási tulajdonsággal rendelkező halmazrendszer. Legyen ekkor $K,N$ két független halmaz úgy, hogy $\left|K\right|<\left|N\right|$. Ekkor $K$ nem lehet maximális független halmaz az $N\cup K\subseteq U$ (nem felt. független) részhalmazban, mert az ellentmondana annak, hogy az ilyenek egyenlő számosságúak, hiszen van egy nála nagyobb számosságú független részhalmaz ($N$). Tehát van olyan $x\in K\cup N,x\not \in K$ elem, hogy ezzel bővítve $K$-t független halmazt kapjunk. Egyszóval $\left(K\cup N\right)-K=N-K$-beli, mert könnyen láthatóan e két halmaz egyenlő, így tehát $K$ bővíthető egy $N$-beli elemmel, és pont ezt akartuk belátni.

A bővíthetőségi axiómarendszer gyengítései

A bővíthetőségi axiómarendszer harmadik axiómáját meg lehet fogalmazni számos „gyengébb” változatban is, melyekből önmagukban (tetszőleges halmazrendszerben) nem következne a harmadik axióma, azonban a leszálló tulajdonsággal együtt már igen.

Néhány ilyen gyengítés:

Kicsi (1) számosságkülönbségű függetlenek

Ha egy független halmazhoz van csak eggyel nagyobb elemszámú független halmaz, akkor létezik ez utóbbiban egy elem, mely a kisebbnek nem eleme, s mellyel a kisebbet bővítve az még független marad.

$\forall F,F'\!\in \!{\mathcal {F}}:$

$\left[\ \ \left|F\right|+1=\left|F'\right|\ \Rightarrow \ \left(\ \ \exists x\!\in \!F'-F:F\cup \left\{x\right\}\in {\mathcal {F}}\ \ \right)\ \ \right]$

• Ennek igazolása:
  • ha ez igaz, akkor a bővíthetőségi axióma is teljesül, hiszen ha $\left|K\right|<\left|N\right|$ független halmaz, akkor amennyiben $M\subseteq N$, úgy $M$ is független a leszállási axióma szerint, és létezik olyan $M$ is, hogy $\left|M\right|=\left|K+1\right|$ legyen, és ekkor a gyengített axióma szerint van egy $K$-t függetlenné bővítő $M-K\subseteq N-K$-beli elem, tehát ez a bővítő elem $N-K$-beli is.
  • Fordítva pedig, ha az eredeti, erősebb bővíthetőségi axióma teljesül, azaz tetszőleges $\left|N\right|>\left|K\right|$ független halmazok esetén bővíthető a $K$, akkor nyilván olyan $N$-ekre is, melyekre $\left|N\right|=\left|K\right|+1$. A két állítás tehát egyenértékű (pontosabban, a bővíthetőség egyenértékű a gyenge bővíthetőség és a leszálló tulajdonság együttesével).

Források

• Cormen – Leiserson – Rivest – Stein: Új algoritmusok . Scolar Kiadó, Bp., 2003. ISBN 9639193909
• Frank András: (jegyzetek) Matroidelmélet jegyzet (Post Script).