Matroid

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 mars 2021; kontroller kräver 5 redigeringar .

En matroid är en klassificering av delmängder av en viss uppsättning , vilket är en generalisering av idén om elements oberoende, på samma sätt som oberoende av element i ett linjärt utrymme , till en godtycklig uppsättning.

Axiomatisk definition

En matroid är ett par , där är en ändlig mängd , som kallas stöd för matroiden , och är någon uppsättning delmängder , som kallas en familj av oberoende uppsättningar , dvs. I detta fall måste följande villkor vara uppfyllda: $(X,I)$ $X$ $jag$ $X$ $I\subset$ $2^{X}$

Den tomma uppsättningen är en oberoende uppsättning, dvs. . $\varnothing \i I$
Alla delmängder av en oberoende mängd är också oberoende mängder, d.v.s. om och , då . $A\in I$ $B\delmängd A$ $B\in I$
Om kraften av A också är större än makten av B, så finns det sådan att . $A,B\in I$ $x\i A\setminus B$ $B\kopp \{x\}\i I$

Baserna för en matroid kallas inklusionsmaximal oberoende uppsättningar . Delmängdersom inte hör tillkallas beroende mängder . Inklusions-minimal beroende uppsättningar kallas matroidcykler . Detta koncept används i en alternativ definition av en matroid. $X$ $jag$

Definition i termer av cykler

En matroid är ett par , där är stödet för matroiden, och är en familj av icke-tomma delmängder , kallad uppsättningen av cykler av matroiden , för vilka följande villkor är uppfyllda: [1] $(X,C)$ $X$ $C$ $X$

Ingen cykel är en delmängd av en annan
Om , innehåller då en cykel $x\in C_{1}\cap C_{2}$ $C_{1}\kopp C_{2}\setminus \{x\}$

Definition i termer av korrekt stängning

Låt vara ett delvis beställt set . — stängning i if $(P,\leq )$ $H:P\till P$ $(P,\leq )$

För valfritt x från P :. $H(x)\geq x$
För valfritt x , y från P : . $x\leq y\Högerpil H(x)\leq H(y)$
För valfritt x från P :. $H{\big (}H(x){\big )}=H(x)$

Tänk på fallet där den delvis ordnade mängden är en boolesk algebra . Låt vara en avslutning . $(P,\leq )=(2^{S},\leq )$ $A\till H(A)$ $A\delmängd S$

Stängningen är korrekt ( korrekt stängningsaxiom ) om $(p\inte \i A,p\in H(A\cup \{q\}))\Högerpil q\in H(A\cup \{p\})$
för någon det finns sådan att $A\delmängd S$ $B\delmängd A$
1. $|B|<+\infty$
2. $H\vänster(B\höger)=H\vänster(A\höger)$

Ett par , där är en ordentlig stängning till , kallas en matroid . $(S,A\till H(A))$ $A\till H(A)$ $(2^{S},\leq )$

Exempel

Universal matroid U n k . Mängden X har kardinalitet n, oberoende mängder är delmängder med kardinalitet högst k. Baser är delmängder av kardinalitet k.
Matroid av grafcykler. Mängden X är uppsättningen av kanter på grafen , de oberoende uppsättningarna är de acykliska delmängderna av dessa kanter, cyklerna är grafens enkla cykler. Baserna är grafens spänner över skogar . En matroid kallas grafisk om den är en cykelmatroid av någon graf. [2]
En matroid av delmängder av en grafs kantuppsättning så att borttagning av en delmängd lämnar grafen ansluten.
Graf cocycle matroid . Uppsättningen X är en uppsättning kanter, cocycles är minimala uppsättningar, vars borttagning leder till förlust av grafanslutning. En matroid kallas cographic om den är en matroid av cocycles av någon graf. [2]
Matrix matroid. Familjen av alla linjärt oberoende delmängder av varje ändlig uppsättning vektorer i ett godtyckligt icke-tomt vektorrum är en matroid.

Vi definierar mängden E som mängden bestående av {1, 2, 3, .., n } — numren på kolumnerna i någon matris , och mängden I som mängden bestående av delmängder av E så att vektorerna definierade av de är linjärt oberoende över fältet reella tal R. Låt oss ställa oss en fråga: vilka egenskaper har den konstruerade mängden jag?

Uppsättningen I är inte tom. Även om den ursprungliga mängden E var tom - E = ∅, så kommer jag att bestå av ett element - en mängd som innehåller den tomma. I = {{∅}}.
Varje delmängd av något element i uppsättningen I kommer också att vara ett element i denna uppsättning. Den här egenskapen är tydlig - om en viss uppsättning vektorer är linjärt oberoende över ett fält, kommer vilken som helst av dess delmängder också att vara linjärt oberoende.
Om A, B ∈ I och |A| = |B| + 1, då finns det ett element x ∈ A − B så att B ∪ {x} ∈ I.

Låt oss bevisa att i det betraktade exemplet är uppsättningen linjärt oberoende kolumner verkligen en matroid. För att göra detta räcker det att bevisa den tredje egenskapen från definitionen av en matroid. Låt oss utföra bevismetoden med motsägelse .

Bevis. Låt A, B ∈ I och |A| = |B| + 1. Låt W vara rymden av vektorer som sträcks av A ∪ B . Det är tydligt att dess dimension kommer att vara minst |A|. Antag att B ∪ {x} är linjärt beroende för alla x ∈ A − B (det vill säga den tredje egenskapen kommer inte att gälla). Då bildar B en bas i rymden W. Detta innebär att |A| ≤ dim W ≤ |B|. Men eftersom A och B enligt antagandet består av linjärt oberoende vektorer och |A| > |B|, får vi en motsägelse. En sådan uppsättning vektorer kommer att vara en matroid.

Ytterligare villkor

Dualen av en given matroid är en matroid vars stöd sammanfaller med stödet för den givna matroiden, och vars baser är komplementen av baserna för den givna matroiden till stödet. Det vill säga X * = X, och mängden baser för den dubbla matroiden är mängden B * så att B * = X \ B, där B är basen för den givna matroiden.
En cykel (eller kedja ) i en matroid är en mängd A ⊂ X så att A ∉ I, och för vilken B ⊂ A som helst, om B ≠ A, då B ∈ I
Rangen på en matroid är kardinaliteten av dess baser. Rangen för en trivial matroid är noll.

Fano matroid

Matroider med ett litet antal element visas ofta som diagram. Punkterna är elementen i huvuduppsättningen, och kurvorna "sträcks" genom varje treelementskedja. Diagrammet visar en 3-ranks matroid som kallas Fano matroid, ett exempel som dök upp i en tidning från 1935 av Whitney .

Namnet uppstod från det faktum att Fano-matroiden är ett andra ordningens projektivt plan , känt som Fano-planet , vars koordinatfält är ett tvåelementsfält. Detta betyder att en Fano-matroid är en vektormatroid som är associerad med sju icke-nollvektorer i ett tredimensionellt vektorrum över ett fält med två element.

Det är känt från projektiv geometri att Fano-matroiden inte kan representeras av en godtycklig uppsättning vektorer i ett verkligt eller komplext vektorrum (eller i något vektorrum över ett fält vars egenskaper skiljer sig från 2).

Satser

Alla baser i en matroid har samma kardinalitet .
En matroid är unikt definierad av dess stöd och baser.
En cykel kan inte vara en delmängd av en annan cykel.
Om och är cykler, så innehåller alla en cykel. $C_{1}$ $C_{2}$ $x\in C_{1}\cap C_{2}:C_{1}\cup C_{2}\setminus \{x\}$
If är en bas och innehåller då exakt en cykel. $B$ $x\notin B$ $B\kopp \{x\}$

Applikation

Matroider beskriver väl klassen av problem som erkänner en "girig" 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 för programmerare. - 3:a. - St Petersburg. : Peter , 2008. - S. 101-105. — 384 sid. - ISBN 978-5-91180-759-7 .

Länkar och anteckningar

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

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