Grafikus matroid

A matematika által vizsgált egyik struktúratípus a matroid. A grafikus matroid vagy körmatroid (esetleg gráfmatroid), olyan matroidot jelent, melynek

alaphalmaza/univerzuma egy adott irányítatlan gráf éleinek halmaza;
maga a struktúra pedig ennek olyan részhalmazaiból áll, melyek nem tartalmaznak kört, azaz körmentes részgráfot, erdőt alkotnak (kör az olyan véges, de nem üres élsorozat, melyben minden él mindkét végpontja egy másik élnek is végpontja). A körmentes részgráfokat nevezzük tehát függetlennek.

A matroidaxiómák teljesülése gráfmatroidokra[szerkesztés]

A legkönnyebb azt belátni, hogy egy gráf erdőt alkotó részgráfjainak halmaza teljesíti az ún. „izokardinalitási” axiómarendszert.

Az üres halmaz erdő, mivel nem tartalmaz kört (ahogy általában semmit sem). Ez tehát független.
Erdő minden részhalmaza is erdő, ha lenne egy ilyenben kör, akkor azt persze az eredeti, bővebb erdő is tartalmazná. Tehát független részhalmaz részhalmaza is független.
A harmadik axióma szerint tetszőleges két maximális erdőnek azonos élszámúnak kell lennie a ${\mathcal {G}}$ gráfban. Ez egy gráfelméleti tétel alapján tényleg igaz, nevezetesen a maximális független erdők élszáma a pontok és a gráf komponenseinek (a maximális – azaz egymástól diszjunkt – összefüggő részgráfok) számának különbsége.

Ám a bővíthetőségi axiómarendszer teljesülése egyszerűbben is igazolható.

Egyebek[szerkesztés]

Belátható, hogy a grafikus matroidok mindegyike gyakorlatilag tetszőleges T test felett lineárisan reprezentálható (azaz mátrixmatroid).
A gráf persze egyértelműen meghatározza a hozzá tartozó körmatroidot. Fordítva azonban ez nem igaz. Ugyanazon körmatroidhoz különféle gráfok tartozhatnak. Persze egy gráf sokféleképp „rajzolható meg”, de az az érdekes, hogy még ha az izomorfiát is tekintetbe vesszük, akkor sincs egyértelműség. Két nem izomorf gráf körmatroidja lehet izomorf. A legegyszerűbb példa: bármely két k-élű fa körmatroidja izomorf, mert a fák tetszőleges részgráfja erdő (körmentes), és így független. Azonban maga a két fa nem feltétlenül izomorf (aki tanult szerves kémiát, az tudja, hogy ez mennyire igaz). De meglehetősen könnyű másféle, kis élszámú ellenpélda-párokat is konstruálni.

Egy ${\mathcal {G}}\left(U,E\right)$ gráfban körnek nevezünk egy olyan véges $\left(u_{1},u_{2},\ \dots \ u_{n}\right)\in E^{n}$ élsorozatot, melyre, ha $u_{i}=\left(A_{i},B_{i}\right)$ , akkor $B_{i}=A_{i+1}$ ha $0\leq i<n$ , azaz ha út, és még $B_{n}=A_{1}$ is teljesül (azaz zárt út).