Matroidaxiómák

A matroid egy axiómákkal definiált matematikai struktúra. A matroidok speciális halmazrendszerek (pontosabban egy  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  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.

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  halmaz feletti  halmazrendszerre:

 I. „nemürességi axiómarendszer”:
 nem üres, azaz 
 leszálló, azaz 

 II. „alternatív nemürességi axiómarendszer”:
 Tartalmazza az üres halmazt, azaz 
 leszálló, azaz 

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  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:
 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) 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.

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ó  elemet egyébként a  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  bővítőjének, ha pedig olyan , melyre , akkor utóbbit  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  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  halmaz -re vonatkozó relatív bővítőjének nevezzük.

Ha  független, és nincs -re vonatkozó relatív bővítője, akkor nevezzük -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.

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ő:

  

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

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ét független halmaz úgy, hogy . Ekkor  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 (). Tehát van olyan  elem, hogy ezzel bővítve -t független halmazt kapjunk. Egyszóval -beli, mert könnyen láthatóan e két halmaz egyenlő, így tehát  bővíthető egy -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.

  
 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  is független a leszállási axióma szerint, és létezik olyan  is, hogy  legyen, és ekkor a gyengített axióma szerint van egy -t függetlenné bővítő -beli elem, tehát ez a bővítő elem -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 , akkor nyilván olyan -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).

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

Hipergráfok