Matroid

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 24. maaliskuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Matroidi on tietyn joukon osajoukkojen luokittelu , joka on yleistys elementtien riippumattomuuden ideasta, samoin kuin lineaarisen avaruuden elementtien riippumattomuus , mielivaltaiseen joukkoon.

Aksiomaattinen määritelmä

Matroidi on pari , jossa on äärellinen joukko , jota kutsutaan matroidin tueksi , ja se on jokin osajoukkojen joukko , jota kutsutaan itsenäisten joukkojen perheeksi , ts . Tässä tapauksessa seuraavat ehdot on täytettävä: $(X, I)$ $X$ $minä$ $X$ $I\alajoukko$ $2^{X}$

Tyhjä joukko on itsenäinen joukko, ts. . $\varnothing \in$
Kaikki itsenäisen joukon osajoukot ovat myös itsenäisiä joukkoja, ts. jos ja niin sitten . $A\in I$ $B\alajoukko A$ $B\in I$
Jos A: n teho on myös suurempi kuin B: n teho , niin on olemassa sellainen, että . $A,B\in I$ $x\in A\setmiinus B$ $B\cup \{x\}\in I$

Matroidin kantoja kutsutaan inkluusio-maksimiriippumattomiksi joukoiksi . Osajoukkoja, jotka eivät kuulukutsutaan riippuviksi joukoiksi . Inkluusiominimiriippuvaisia joukkoja kutsutaan matroidisykleiksi . Tätä käsitettä käytetään vaihtoehtoisessa matroidin määritelmässä. $X$ $minä$

Määritelmä jaksoina

Matroidi on pari , jossa on matroidin tuki, ja se on ei-tyhjien osajoukkojen perhe , jota kutsutaan matroidin syklien joukoksi , jolle seuraavat ehdot täyttyvät: [1] $(X, C)$ $X$ $C$ $X$

Mikään sykli ei ole toisen osajoukko
Jos , sisältää jakson $x\in C_{1}\cap C_{2}$ $C_{1}\cup C_{2}\setminus \{x\}$

Määritelmä asianmukaisen sulkemisen kannalta

Olkoon osittain tilattu sarja . — sulkeminen jos $(P,\leq )$ $H:P\to P$ $(P,\leq )$

Mille tahansa x : lle P :stä : . $H(x)\geq x$
Mille tahansa x :lle , y : lle P : stä :. $x\leq y\oikea nuoli H(x)\leq H(y)$
Mille tahansa x : lle P :stä : . $H{\big (}H(x){\big )}=H(x)$

Tarkastellaan tapausta, jossa osittain järjestetty joukko on Boolen algebra . Olkoon sulkeminen . $(P,\leq )=(2^{S},\leq )$ $A\–H(A)$ $A\alajoukko S$

Sulkeminen on oikea ( oikea sulkemisaksiooma ), jos $(p\not \in A,p\in H(A\cup \{q\}))\Oikeanuoli q\in H(A\kuppi \{p\})$
sillä sellaista on olemassa $A\alajoukko S$ $B\alajoukko A$
1. $|B|<+\infty$
2. $H\vasen(B\oikea)=H\vasen(A\oikea)$

Paria , jossa on oikea sulkeminen , kutsutaan matroidiksi . $(S,A\–H(A))$ $A\–H(A)$ $(2^{S},\leq )$

Esimerkkejä

Yleismatroidi U n k . Joukon X kardinaliteetti on n, itsenäiset joukot ovat osajoukkoja , joiden kardinaliteetti on enintään k. Kantaukset ovat kardinaalisuuden k osajoukkoja.
Graafisten syklien matroidi. Joukko X on graafin reunojen joukko , itsenäiset joukot ovat näiden reunojen asyklisiä osajoukkoja, syklit ovat graafin yksinkertaisia syklejä. Perusteet ovat kaavion kattavia metsiä . Matroidia kutsutaan graafiseksi , jos se on jonkin graafin syklimatroidi. [2]
Graafin reunajoukon osajoukkojen matroidi siten, että osajoukon poistaminen jättää graafin yhteen.
Kaavio cocycle matroid . Joukko X on joukko reunoja, kosyklit ovat minimaalisia joukkoja, joiden poistaminen johtaa graafisen yhteyden katoamiseen. Matroidia kutsutaan kografiseksi , jos se on jonkin graafin kosyklisten matroidi. [2]
Matriisi matroid. Satunnaisen ei-tyhjän vektoriavaruuden minkä tahansa äärellisen vektorijoukon kaikkien lineaarisesti riippumattomien osajoukkojen perhe on matroidi.

Määrittelemme joukon E joukoksi, joka koostuu joukosta {1, 2, 3, .., n } — jonkin matriisin sarakkeiden numerot , ja joukon I joukoksi, joka koostuu E:n osajoukoista siten, että vektorit , jotka määritellään ne ovat lineaarisesti riippumattomia kentän reaalilukujen R suhteen. Esitetään itsellemme kysymys: mitä ominaisuuksia konstruoidulla joukolla I on?

Sarja I ei ole tyhjä. Vaikka alkuperäinen joukko E olisi tyhjä - E = ∅, niin minä koostun yhdestä alkiosta - joukosta, joka sisältää tyhjän. I = {{∅}}.
Mikä tahansa joukon I elementin osajoukko on myös tämän joukon elementti. Tämä ominaisuus on selvä - jos tietty joukko vektoreita on lineaarisesti riippumaton kentästä, niin mikä tahansa sen osajoukko on myös lineaarisesti riippumaton.
Jos A, B ∈ I ja |A| = |B| + 1, silloin on sellainen alkio x ∈ A − B, että B ∪ {x} ∈ I.

Osoittakaamme, että tarkasteltavassa esimerkissä lineaarisesti riippumattomien sarakkeiden joukko on todellakin matroidi. Tätä varten riittää todistaa matroidin määritelmän kolmas ominaisuus. Suoritetaan todistus ristiriitamenetelmällä .

Todiste. Olkoon A, B ∈ I ja |A| = |B| + 1. Olkoon W vektoreiden A ∪ B ulottuma avaruus. On selvää, että sen mitta on vähintään |A|. Oletetaan, että B ∪ {x} on lineaarisesti riippuvainen kaikille x ∈ A − B (eli kolmas ominaisuus ei päde). Tällöin B muodostaa kantan avaruudessa W. Tämä tarkoittaa, että |A | ≤ himmeä W ≤ |B|. Mutta koska oletuksella A ja B koostuvat lineaarisesti riippumattomista vektoreista ja |A| > |B|, saadaan ristiriita. Tällainen vektoreiden joukko on matroidi.

Lisäehdot

Tietyn matroidin duaali on matroidi, jonka tuki osuu yhteen tietyn matroidin tuen kanssa ja jonka kantat ovat tietyn matroidin kantajen komplementteja tukeen. Eli X * = X ja kaksoismatroidin kantajoukko on B * :n joukko siten, että B * = X \ B, missä B on annetun matroidin kanta.
Matroidin sykli (tai ketju ) on joukko A ⊂ X siten, että A ∉ I, ja mille tahansa B ⊂ A:lle, jos B ≠ A, niin B ∈ I
Matroidin arvo on sen kantajen kardinaalisuus. Triviaalin matroidin arvo on nolla.

Fano matroid

Matroidit, joissa on pieni määrä elementtejä, esitetään usein kaavioina. Pisteet ovat pääjoukon elementtejä, ja käyrät "venytetään" jokaisen kolmen elementin ketjun läpi. Kaavio esittää 3-luokan matroidia nimeltä Fano-matroid, esimerkki, joka esiintyi Whitneyn vuoden 1935 artikkelissa .

Nimi syntyi siitä, että Fano-matroidi on toisen asteen projektiivinen taso , joka tunnetaan nimellä Fano-taso , jonka koordinaattikenttä on kaksielementtikenttä. Tämä tarkoittaa, että Fano-matroidi on vektorimatroidi, joka liittyy seitsemään nollasta poikkeavaan vektoriin kolmiulotteisessa vektoriavaruudessa kahden elementin kentän yli.

Projektiivisesta geometriasta tiedetään, että Fano-matroidia ei voida esittää mielivaltaisella vektoreiden joukolla todellisessa tai kompleksisessa vektoriavaruudessa (tai missä tahansa vektoriavaruudessa kentän päällä, jonka ominaisuudet poikkeavat 2:sta).

Lauseet

Kaikilla matroidin kannaksilla on sama kardinaliteetti .
Matroid on yksilöllisesti määritelty sen tuen ja tukien perusteella.
Jakso ei voi olla toisen syklin osajoukko.
Jos ja ovat syklejä, niin mikä tahansa sisältää syklin. $C_{1}$ $C_{2}$ $x\in C_{1}\cap C_{2}:C_{1}\cup C_{2}\setminus \{x\}$
Jos on perusta ja , Sitten sisältää täsmälleen yhden syklin. $B$ $x\ei B$ $B\cup \{x\}$

Sovellus

Matroidit kuvaavat hyvin ongelmien luokkaa, jotka myöntävät "ahneen" ratkaisun. Katso Greedy Rado-Edmonds -algoritmi
Matroidit kombinatorisessa optimoinnissa

Kirjallisuus

Asanov M. O. et ai. Diskreetti matematiikka: Graafit, Matroidit, Algoritmit. - Izhevsk: NSC "säännöllinen ja kaoottinen dynamiikka", 2001. - s. 288.
F. Harari. Graafiteoria . - Moskova: URSS , 2003. - S. 300 . ISBN 5-354-00301-6
Novikov F. A. Diskreetti matematiikka ohjelmoijille. - 3. - Pietari. : Peter , 2008. - S. 101-105. — 384 s. - ISBN 978-5-91180-759-7 .

Linkkejä ja muistiinpanoja

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

↑ F. Harari. Graafiteoria , s. 57.
↑ 1 2 F. Harari. Graafiteoria , s. 186.