Matroidaxiómák
A Wikipédiából, a szabad lexikonból.
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
halmazrendszerből álló
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
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.
Tartalomjegyzék |
[szerkesztés] 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
halmazrendszerre:
- I. „nemürességi axiómarendszer”:
- nem üres, azaz

- 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]](../../../math/5/5/2/552920324e40c93c1eee0b65ce7a6c1b.png)
- nem üres, azaz
- II. „alternatív nemürességi axiómarendszer”:
- Tartalmazza az üres halmazt, azaz

- 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]](../../../math/5/5/2/552920324e40c93c1eee0b65ce7a6c1b.png)
- Tartalmazza az üres halmazt, azaz
A következőkben a matroidok meghatározására a „nemürességi” a.r.-t használjuk.
[szerkesztés] A bővíthetőségi axiómarendszer
E szerint egy U véges halmaz feletti matroid egy olyan
párból álló struktúra, ahol
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 a matroidok definiálására leginkább használt axiómarendszer.
| B1. | nem-üresség: | ; |
| B2. | leszállóság: | ![]() |
| B3. | kölcsönös bővíthetőség: | ![]() |
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.)
[szerkesztés] Halmaz bővítője és maximális függetlensége
A szóban forgó
elemet egyébként a K halmaz bővítőjének nevezzük. Célszerű ezt általánosabban is megfogalmazni: legyen
az alaphalmaz tetszőleges részhalmaza. Ha van olyan
elem, melyre
, akkor ezt az elemet az X bővítőjének, ha pedig olyan
, melyre
, akkor utóbbit X antibővítőjének nevezzük.
Ha
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 (
) értjük a matroidelméletben (nem pedig a számosságok rendezésére,
-re), hiszen ez pontosan azt jelenti, hogy nincs olyan Y halmaz, melyre
.
A fenti fogalmak általánosítása: Legyen most is
az alaphalmaz két részhalmaza. Ha van olyan
elem, melyre
(s ekkor
, akkor ezt az elemet az A halmaz X-re vonatkozó relatív bővítőjének nevezzük.
Ha
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.
[szerkesztés] 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: | ; |
| 2. | leszállóság: | ![]() |
| 3. | maximalitási tulajdonság: |
![]() |
[szerkesztés] Halmaz rangja
Az
nem bővíthető független halmazok esetén az
jelölést bevezetve a harmadik axióma nyilván teljesen ugyanaz, mint a következő:

![\ \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]](../../../math/1/1/7/11731406366734f217f69c02ed1281e5.png)
Az rX természetes számot, mely a matroidelméletben lényeges szerepet játszik, az
(nem feltétlenül független) halmaz rangjának nevezzük. Az U halmaz rangját a matroid rangjának nevezzük.
[szerkesztés] 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
bővíthetőségi tulajdonsággal rendelkező nem, üres leszálló halmazrendszer. Legyen
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
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
, amelyre
független, de mivel
és M véges (mivel az alaphalmaz is véges), ezért
, 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
esetén. - Legyen
izokardinalitási tulajdonsággal rendelkező halmazrendszer. Legyen ekkor K,N két független halmaz úgy, hogy
. Ekkor K nem lehet maximális független halmaz az
(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
elem, hogy ezzel bővítve K-t független halmazt kapjunk. Egyszóval
-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.
[szerkesztés] 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:
[szerkeszté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.

![\left[ \ \ \left| F \right| +1 = \left| F' \right| \ \Rightarrow \ \left( \ \ \exist x \! \in \! F'-F : F \cup \left\{ x \right\} \in \mathcal{F} \ \ \right) \ \ \right]](../../../math/f/8/a/f8a6166a9a8cacdf437cbe57f6a13da2.png)
- Ennek igazolása:
- ha ez igaz, akkor a bővíthetőségi axióma is teljesül, hiszen ha
független halmaz, akkor amennyiben
, úgy M is független a leszállási axióma szerint, és létezik olyan M is, hogy
legyen, és ekkor a gyengített axióma szerint van egy K-t függetlenné bővítő
-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
független halmazok esetén bővíthető a K, akkor nyilván olyan N-ekre is, melyekre
. 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).
- ha ez igaz, akkor a bővíthetőségi axióma is teljesül, hiszen ha
[szerkesztés] Források
- Cormen – Leiserson – Rivest – Stein: Új algoritmusok . Scolar Kiadó, Bp., 2003. ISBN 9639193909
- Frank András: (jegyzetek) Matroidelmélet jegyzet (Post Script).
![\; \left[ \ \left| K \right| < \left| N \right| \ \Rightarrow \ \exist x \! \in N \! - \! K : \ \left( K \cup \left\{ x \right\} \in \mathcal{F} \right) \ \right]](../../../math/c/1/6/c16dda8d53a386950af97047c582413f.png)
![\left[ \ \left( \ \exist x \! \in \! X: \ F \cup \left\{ x \right\} \not\in \mathcal{F} \ \right) \Rightarrow \left| F \right| = \left| G \right| \ \right]](../../../math/6/a/c/6ace91f244b9d290b181b94c7a480c2c.png)


Based on work by