Matroide

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 24. marts 2021; checks kræver 5 redigeringer .

En matroide er en klassificering af delmængder af et bestemt sæt , som er en generalisering af ideen om uafhængighed af elementer, på samme måde som uafhængigheden af elementer i et lineært rum , til et vilkårligt sæt.

Aksiomatisk definition

En matroide er et par , hvor er en endelig mængde , kaldet støtte for matroiden , og er et sæt af delmængder , kaldet en familie af uafhængige mængder , dvs. I dette tilfælde skal følgende betingelser være opfyldt: $(X,I)$ $x$ $jeg$ $x$ $I\undersæt$ $2^{X}$

Det tomme sæt er et selvstændigt sæt, dvs. . $\varnothing \i I$
Alle delmængder af et uafhængigt sæt er også uafhængige mængder, dvs. hvis og , så . $A\i I$ $B\undersæt A$ $B\in I$
Hvis magten af A også er større end magten af B, så eksisterer der sådan, at . $A,B\in I$ $x\i A\setminus B$ $B\kop \{x\}\i I$

Baserne af en matroide kaldes inklusionsmaksimale uafhængige sæt . Delmængder, der ikke hørertil, kaldes afhængige mængder . Inklusions-minimal afhængige sæt kaldes matroid-cyklusser . Dette koncept bruges i en alternativ definition af en matroid. $x$ $jeg$

Definition i form af cyklusser

En matroide er et par , hvor er understøttelsen af matroiden, og er en familie af ikke-tomme delmængder , kaldet sættet af cyklusser af matroiden , for hvilke følgende betingelser er opfyldt: [1] $(X,C)$ $x$ $C$ $x$

Ingen cyklus er en delmængde af en anden
Hvis , så indeholder en cyklus $x\in C_{1}\cap C_{2}$ $C_{1}\kop C_{2}\setminus \{x\}$

Definition i form af korrekt lukning

Lad være et delvist bestilt sæt . — lukning i if $(P,\leq )$ $H:P\til P$ $(P,\leq )$

For ethvert x fra P :. $H(x)\geq x$
For enhver x , y fra P :. $x\leq y\Højrepil H(x)\leq H(y)$
For ethvert x fra P :. $H{\big (}H(x){\big )}=H(x)$

Overvej det tilfælde, hvor det delvist ordnede sæt er en boolsk algebra . Lad være en lukning . $(P,\leq )=(2^{S},\leq )$ $A\til H(A)$ $A\undersæt S$

Lukningen er korrekt ( korrekt lukkeaksiom ) hvis $(p\ikke \i A,p\i H(A\kop \{q\}))\Højrepil q\i H(A\kop \{p\})$
for nogen der findes sådan at $A\undersæt S$ $B\undersæt A$
1. $|B|<+\infty$
2. $H\venstre(B\højre)=H\venstre(A\højre)$

Et par , hvor der er en ordentlig lukning til , kaldes en matroide . $(S,A\til H(A))$ $A\til H(A)$ $(2^{S},\leq )$

Eksempler

Universal matroide U n k . Mængden X har kardinalitet n, uafhængige mængder er delmængder med højst kardinalitet k. Baser er delmængder af kardinalitet k.
Matroid af grafcyklusser. Mængden X er sættet af kanter af grafen , de uafhængige sæt er de acykliske delmængder af disse kanter, cyklusserne er de simple cyklusser af grafen. Baserne er grafens spænder over skove . En matroide kaldes grafik , hvis det er en cyklusmatroide af en graf. [2]
En matroide af delmængder af en grafs kantsæt, således at fjernelse af en delmængde efterlader grafen forbundet.
Graf cocycle matroid . Sættet X er et sæt kanter, cocycles er minimale sæt, hvis fjernelse fører til tab af grafforbindelse. En matroide kaldes cographic, hvis det er en matroide af cocycles af en graf. [2]
Matrix matroide. Familien af alle lineært uafhængige delmængder af ethvert endeligt sæt af vektorer i et vilkårligt ikke-tomt vektorrum er en matroide.

Vi definerer mængden E som mængden bestående af {1, 2, 3, .., n } — tallene på kolonnerne i en eller anden matrix , og mængden I som mængden bestående af delmængder af E, således at vektorerne defineret af de er lineært uafhængige over feltet reelle tal R. Lad os stille os selv et spørgsmål: hvilke egenskaber har det konstruerede sæt jeg?

Sættet I er ikke tomt. Selvom det oprindelige sæt E var tomt - E = ∅, så vil jeg bestå af et element - et sæt, der indeholder det tomme. I = {{∅}}.
Enhver delmængde af ethvert element i sættet I vil også være et element i dette sæt. Denne egenskab er klar - hvis et bestemt sæt af vektorer er lineært uafhængigt af et felt, så vil enhver af dets undersæt også være lineært uafhængig.
Hvis A, B ∈ I og |A| = |B| + 1, så er der et element x ∈ A − B, således at B ∪ {x} ∈ I.

Lad os bevise, at i det betragtede eksempel er sættet af lineært uafhængige søjler faktisk en matroide. For at gøre dette er det tilstrækkeligt at bevise den tredje egenskab fra definitionen af en matroid. Lad os udføre beviset ved modsigelse .

Bevis. Lad A, B ∈ I og |A| = |B| + 1. Lad W være rummet af vektorer omspændt af A ∪ B . Det er klart, at dens dimension vil være mindst |A|. Antag, at B ∪ {x} er lineært afhængig for alle x ∈ A − B (det vil sige, at den tredje egenskab ikke vil holde). Så danner B en basis i rummet W. Dette indebærer, at |A| ≤ dæmpet W ≤ |B|. Men da A og B ved antagelse består af lineært uafhængige vektorer og |A| > |B|, får vi en modsigelse. Et sådant sæt af vektorer vil være en matroide.

Yderligere vilkår

Dualen af en given matroide er en matroide, hvis støtte falder sammen med støtten fra den givne matroide, og hvis baser er komplementerne af baserne af den givne matroide til støtten. Det vil sige, X * = X, og mængden af baser i den dobbelte matroide er mængden af B * , således at B * = X \ B, hvor B er basen af den givne matroide.
En cyklus (eller kæde ) i en matroide er en mængde A ⊂ X, således at A ∉ I, og for enhver B ⊂ A, hvis B ≠ A, så B ∈ I
Rangen af en matroide er kardinaliteten af dens baser. Rangen af en triviel matroid er nul.

Fano matroid

Matroider med et lille antal elementer vises ofte som diagrammer. Punkterne er hovedsættets elementer, og kurverne "straktes" gennem hver kæde med tre elementer. Diagrammet viser en 3-rangs matroide kaldet Fano matroid, et eksempel, der dukkede op i et papir fra 1935 af Whitney .

Navnet opstod fra det faktum, at Fano-matroiden er et projektivt plan af anden orden , kendt som Fano-planet , hvis koordinatfelt er et toelementsfelt. Dette betyder, at en Fano-matroide er en vektormatroide, der er forbundet med syv ikke-nul-vektorer i et tredimensionelt vektorrum over et felt af to elementer.

Det er kendt fra projektiv geometri , at Fano-matroiden ikke kan repræsenteres af et vilkårligt sæt af vektorer i et reelt eller komplekst vektorrum (eller i et hvilket som helst vektorrum over et felt, hvis karakteristika afviger fra 2).

Sætninger

Alle baser i en matroide har den samme kardinalitet .
En matroide er unikt defineret af dens støtte og baser.
En cyklus kan ikke være en delmængde af en anden cyklus.
Hvis og er cyklusser, så for enhver indeholder en cyklus. $C_{1}$ $C_{2}$ $x\in C_{1}\cap C_{2}:C_{1}\kop C_{2}\setminus \{x\}$
Hvis er en base og , indeholder så præcis én cyklus. $B$ $x\notin B$ $B\kop \{x\}$

Ansøgning

Matroider beskriver godt klassen af problemer, der indrømmer en "grådig" løsning. Se Greedy Rado-Edmonds Algorithm
Matroider i kombinatorisk optimering

Litteratur

Asanov M. O. et al. Diskret matematik: grafer, matroider, algoritmer. - Izhevsk: NSC "Regular and Chaotic Dynamics", 2001. - S. 288.
F. Harari. Grafteori . - Moskva: URSS , 2003. - S. 300 . ISBN 5-354-00301-6
Novikov F. A. Diskret matematik for programmører. - 3. - Sankt Petersborg. : Peter , 2008. - S. 101-105. — 384 s. - ISBN 978-5-91180-759-7 .

Links og noter

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

↑ F. Harari. Graph Theory , s. 57.
↑ 1 2 F. Harari. Graph Theory , s. 186.