Matroid

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. március 24-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A matroid egy bizonyos halmaz részhalmazainak osztályozása , amely az elemek függetlenségének gondolatának általánosítása, hasonlóan a lineáris tér elemeinek függetlenségéhez, tetszőleges halmazra.

Axiomatikus definíció

A matroid egy olyan pár , ahol egy véges halmaz , amelyet a matroid támaszának nevezünk , és néhány részhalmaz , amelyet független halmazok családjának nevezünk , azaz . Ebben az esetben a következő feltételeknek kell teljesülniük: $(X, I)$ $x$ $én$ $x$ $I\alhalmaz$ $2^{X}$

Az üres halmaz független halmaz, azaz. . $\varnothing \in I$
Egy független halmaz minden részhalmaza is független halmaz, azaz. ha és , akkor . $A\in I$ $B\A részhalmaz$ $B\in I$
Ha A hatványa is nagyobb, mint B hatványa , akkor létezik olyan, hogy . $A, B\ az I-ben$ $x\in A\setminus B$ $B\kupa \{x\}\ az I-ben$

A matroid alapjait zárvány-maximális független halmazoknak nevezzük. A nem tartozórészhalmazokat függő halmazoknak nevezzük. A befogadás-minimális függő halmazokat matroid ciklusoknak nevezzük. Ezt a fogalmat a matroid egy alternatív definíciójában használják. $x$ $én$

Definíció ciklusokban

A matroid egy olyan pár , ahol a matroid támasza, és nem üres részhalmazok családja , amelyet a matroid ciklusainak halmazának neveznek , és amelyre a következő feltételek teljesülnek: [1] $(X,C)$ $x$ $C$ $x$

Egyetlen ciklus sem egy másik részhalmaza
Ha , akkor ciklust tartalmaz $x\in C_{1}\cap C_{2}$ $C_{1}\cup C_{2}\setminus \{x\}$

Meghatározás a megfelelő zárás szempontjából

Legyen egy részben rendezett halmaz . — bezárás, ha $(P,\leq )$ $H:P\to P$ $(P,\leq )$

Bármely x -re P : . $H(x)\geq x$
Bármely x , y esetén P : . $x\leq y\jobbra H(x)\leq H(y)$
Bármely x -re P : . $H{\big (}H(x){\big )}=H(x)$

Tekintsük azt az esetet, amikor a részben rendezett halmaz egy Boole-algebra . Legyen lezárás . $(P,\leq )=(2^{S},\leq )$ $A\–H(A)$ $S részhalmaz$

A lezárás helyes ( megfelelő zárási axióma ), ha $(p\not \in A,p\in H(A\cup \{q\}))\Jobbra q\in H(A\cup \{p\})$
mert létezik ilyen $S részhalmaz$ $B\A részhalmaz$
1. $|B|<+\infty$
2. $H\bal(B\jobb)=H\bal(A\jobb)$

Az a pár , ahol a megfelelő lezárás , matroidnak nevezzük . $(S,A\–H(A))$ $A\–H(A)$ $(2^{S},\leq )$

Példák

Univerzális matroid U n k . Az X halmaz n számú, a független halmazok legfeljebb k számú részhalmazok . A bázisok a k számosság részhalmazai.
Gráfciklusok matroidja. Az X halmaz a gráf éleinek halmaza , a független halmazok ezen élek aciklikus részhalmazai, a ciklusok a gráf egyszerű ciklusai. Az alapok a gráf átívelő erdői . Egy matroidot grafikusnak nevezünk, ha valamilyen gráf ciklus-matroidja. [2]
Egy gráf élhalmazának részhalmazainak matroidja úgy, hogy egy részhalmaz eltávolításával a gráf összekapcsolva marad.
Graph cocycle matroid . Az X halmaz élek halmaza, a kociklusok minimális halmazok, amelyek eltávolítása a gráfkapcsolat elvesztéséhez vezet. Egy matroidot kografikusnak nevezünk, ha valamilyen gráf kociklusainak matroidja. [2]
Mátrix matroid. Egy tetszőleges nem üres vektortér bármely véges vektorhalmazának lineárisan független részhalmazainak családja egy matroid.

Az E halmazt úgy definiáljuk, mint az {1, 2, 3, .., n } — valamely mátrix oszlopainak számát — álló halmazt, az I halmazt pedig E részhalmazokból álló halmazként úgy definiáljuk, hogy az által meghatározott vektorok lineárisan függetlenek az R mezei valós számok felett . Tegyük fel magunknak a kérdést: milyen tulajdonságokkal rendelkezik az I konstruált halmaz?

Az I készlet nem üres. Még ha az eredeti E halmaz üres is volt - E = ∅, akkor egy elemből fogok állni - egy halmazból, amely az üreset tartalmazza. I = {{∅}}.
Az I halmaz bármely elemének bármely részhalmaza ennek a halmaznak is eleme lesz. Ez a tulajdonság egyértelmű - ha egy bizonyos vektorhalmaz lineárisan független egy mező felett, akkor bármelyik részhalmaza is lineárisan független lesz.
Ha A, B ∈ I és |A| = |B| + 1, akkor van olyan x ∈ A − B elem, amelyre B ∪ {x} ∈ I.

Bizonyítsuk be, hogy a vizsgált példában a lineárisan független oszlopok halmaza valóban matroid. Ehhez elegendő a harmadik tulajdonságot bizonyítani a matroid definíciójából. Végezzük el a bizonyítást ellentmondásos módszerrel .

Bizonyíték. Legyen A, B ∈ I és |A| = |B| + 1. Legyen W az A ∪ B által átfogott vektorok tere . Nyilvánvaló, hogy mérete legalább |A| lesz. Tegyük fel, hogy B ∪ {x} lineárisan függő minden x ∈ A − B esetén (vagyis a harmadik tulajdonság nem érvényesül). Ekkor B bázist képez a W térben . Ez azt jelenti, hogy |A| ≤ dim W ≤ |B|. De mivel feltételezés szerint A és B lineárisan független vektorokból és |A| -ból áll > |B|, akkor ellentmondást kapunk. Egy ilyen vektorhalmaz matroid lesz.

További feltételek

Egy adott matroid duálisa olyan matroid, amelynek támasztéka egybeesik az adott matroid támasztékával, és amelynek bázisai az adott matroid bázisainak a támaszhoz való komplementerei . Azaz X * = X, és a kettős matroid bázisainak halmaza a B * halmaza úgy, hogy B * = X \ B, ahol B az adott matroid bázisa.
Egy ciklus (vagy lánc ) egy matroidban egy A ⊂ X halmaz, ahol A ∉ I, és bármely B ⊂ A esetén, ha B ≠ A, akkor B ∈ I
A matroid rangja az alapjainak kardinalitása. Egy triviális matroid rangja nulla.

Fano matroid

A kis számú elemet tartalmazó matroidokat gyakran diagramként ábrázolják. A pontok a főhalmaz elemei, a görbék pedig minden három elemből álló láncon keresztül „feszülnek”. A diagram egy 3-rangú matroidot mutat, amelyet Fano matroidnak hívnak, egy példa, amely Whitney 1935-ös cikkében jelent meg .

Az elnevezés onnan ered, hogy a Fano-matroid egy másodrendű projektív sík , más néven Fano-sík , melynek koordinátamezője egy kételemű mező. Ez azt jelenti, hogy a Fano-matroid egy vektor-matroid, amely hét nullától eltérő vektorral van társítva egy háromdimenziós vektortérben egy két elemből álló mező felett.

A projektív geometriából ismert, hogy a Fano-matroid nem ábrázolható tetszőleges vektorkészlettel valós vagy összetett vektortérben (vagy bármely olyan vektortérben , amelynek jellemzői eltérnek a 2-től).

Tételek

A matroid minden bázisa azonos kardinalitású .
A matroidot a támasztéka és az alapjai egyedileg határozzák meg.
Egy ciklus nem lehet egy másik ciklus részhalmaza.
Ha a és ciklusok, akkor bármelyik ciklust tartalmaz. $C_{1}$ $C_{2}$ $x\in C_{1}\cap C_{2}:C_{1}\cup C_{2}\setminus \{x\}$
Ha egy bázis és , akkor pontosan egy ciklust tartalmaz. $B$ $x\nem B$ $B\kupa \{x\}$

Alkalmazás

A matroidok jól leírják a „kapzsi” megoldást engedő problémák osztályát. Lásd Greedy Rado-Edmonds algoritmus
Matroidok a kombinatorikus optimalizálásban

Irodalom

Asanov M. O. és munkatársai : Diszkrét matematika: gráfok, matroidok, algoritmusok. - Izhevsk: NSC "Szabályos és kaotikus dinamika", 2001. - 288. o.
F. Harari. Gráfelmélet . - Moszkva: URSS , 2003. - S. 300 . ISBN 5-354-00301-6
Novikov F. A. Diszkrét matematika programozóknak. - 3. - Szentpétervár. : Péter , 2008. - S. 101-105. — 384 p. - ISBN 978-5-91180-759-7 .

Linkek és megjegyzések

https://web.archive.org/web/20080619011117/http://rain.ifmo.ru/cat/view.php/theory/unsorted/matroids-2004

↑ F. Harari. Gráfelmélet , p. 57.
↑ 1 2 F. Harari. Gráfelmélet , p. 186.