Matchande polytop

I grafteorin är den matchande polytopen för en given graf ett geometriskt objekt som representerar de möjliga matchningarna i grafen . Det är en konvex polytop vars hörn motsvarar en matchning. Det har stor teoretisk betydelse i teorin om matchning.

Förberedelser

Incidensvektorer och matriser

Låt G = ( V , E ) vara en graf med n = | V | noder och m = | E | kanter.

För varje delmängd U av hörn är dess incidensvektor 1 U en vektor med storleken n , där elementet v är 1 om noden v är i U och 0 annars. På liknande sätt, för varje delmängd F av kanter, är dess incidensvektor 1F en vektor med storleken m , där elementet e är 1 om kanten e är i F, och 0 annars.

För varje nod v i V betecknas uppsättningen av kanter i E intill v med E ( v ). Därför är varje vektor 1 E(v) en 1 gånger m vektor i vilken element e är 1 om kanten e är intill v, och 0 annars. Grafens incidensmatris, betecknad med A G , är en n -by- m matris där varje rad v är incidensvektorn 1 E(V) . Med andra ord är varje element v , e i matrisen 1 om nod v är intill kanten e , och 0 annars.

Nedan finns tre exempel på incidensmatriser: triangelgrafen (en cykel med längd 3), en kvadratisk graf (en cykel med längd 4) och hela grafen på 4 hörn.

Linjära program

För varje delmängd F av kanter representerar punktprodukten 1 E(v) · 1 F antalet kanter i F som ligger intill v . Därför är följande påståenden likvärdiga:

  • En delmängd F av kanter representerar en matchning i G;
  • För varje nod v i V : 1 E(v) · 1 F ≤ 1.
  • A G · 1 F ≤ 1 V. _

Kardinaliteten för en uppsättning F av kanter är punktprodukten 1 E · 1 F . Därför ges en maximal kardinalitetsmatchning i G av följande linjära heltalsprogram :

Maximera 1 E · x

Med förbehåll för: x i {0,1} m

__________ A G · x ≤ 1 V .

Bråkmatchande polytop

Den bråkmatchande polytopen i en graf G , betecknad FMP( G ), är polytopen som definieras av relaxationen av ovanstående linjära program, där varje x kan vara en bråkdel och inte bara ett heltal:

Maximera 1 E · x

0 Med förbehåll för: x ≥ E

__________ A G · x ≤ 1 V .

Detta är ett linjärt program . Den har m "minst-0"-begränsningar och n "mindre-än-ett"-begränsningar. Uppsättningen av dess möjliga lösningar är en konvex polytop . Varje punkt i denna polytop är en bråkdelsmatchning . Till exempel, i triangelgrafen finns det 3 kanter, och motsvarande linjära program har följande 6 begränsningar:

Maximera x 1 + x 2 + x 3

Med förbehåll för: x 1 ≥0, x 2 ≥0, x 3 ≥0 .

__________ x 1 + x 2 ≤ 1 , x 2 + x 3 ≤ 1, x 3 + x 1 ≤ 1.

Denna uppsättning ojämlikheter representerar en polytop i R 3 - det 3-dimensionella euklidiska rummet.

Polytopen har fem hörn ( extrempunkter ). Dessa är de punkter som uppnår jämlikhet i 3 av de 6 definierande ojämlikheterna. Hörnen är (0,0,0), (1,0,0), (0,1,0), (0,0,1) och (1/2,1/2,1/2). Det första hörnet (0,0,0) representerar den triviala (tomma) matchningen. De nästa tre hörnen (1,0,0), (0,1,0), (0,0,1) representerar de tre matchningarna av storlek 1. Det femte hörnet (1/2,1/2,1/2) ) representerar inte en matchning - den representerar en bråkmatchning där varje kant är "halvt in, halvt ut". Observera att detta är den största bråkmatchningen i denna graf - dess vikt är 3/2, i motsats till de tre integralmatchningarna vars storlek bara är 1.

Som ett annat exempel, i 4-cykeln finns det 4 kanter. Motsvarande LP har 4+4=8 begränsningar. FMP är en konvex polytop i R 4 . Hörnen på denna polytop är (0,0,0,0), (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0) ,0,1), (1,0,1,0), (0,1,0,1). Vart och ett av de två sista hörnen representerar matchning av storlek 2, vilket är en maximal matchning. Observera att i det här fallet har alla hörn heltalskoordinater.

Integrerad matchande polytop

Den integralmatchande polytopen (vanligtvis bara kallad den matchande polytopen ) i en graf G , betecknad MP( G ), är en polytop vars hörn är infallsvektorerna för integralmatchningarna i G.

MP( G ) finns alltid i FMP( G ). I exemplen ovan:

  • MP för triangelgrafen är strikt inkluderad i dess FMP, eftersom MP inte innehåller det icke-integrerade hörnet (1/2, 1/2, 1/2).
  • MP för 4-cykeldiagrammet är identisk med dess FMP, eftersom alla hörn av FMP är integrerade.

De matchande polytoperna i en tvådelad graf

Ovanstående exempel är ett specialfall av följande allmänna sats:

G är en tvådelad graf om-och-bara-om MP( G ) = FMP( G ) om-och-bara-om alla hörn av FMP( G ) endast har heltalskoordinater.

Denna sats kan bevisas på flera sätt.

Bevis med matriser

När G är tvådelad är dess incidensmatris A G helt unimodulär - varje kvadratisk submatris av den har determinant 0, +1 eller −1. Beviset är genom induktion på k - storleken på submatrisen (som vi betecknar med K ). Basen k = 1 följer av definitionen av A G - varje element i den är antingen 0 eller 1. För k >1 finns det flera fall:

  • Om K har en kolumn som bara består av nollor, då är det K = 0.
  • Om K har en kolumn med en enda 1, så kan det K expanderas kring denna kolumn och den är lika med antingen +1 eller -1 gånger en determinant av en ( k − 1) med ( k − 1) matris, som genom induktionen antagandet är 0 eller +1 eller −1.
  • Annars har varje kolumn i K två 1:or. Eftersom grafen är tvådelad kan raderna delas upp i två delmängder, så att i varje kolumn är en 1 i den översta delmängden och den andra 1 i den nedre delmängden. Detta betyder att summan av den översta delmängden och summan av den nedre delmängden båda är lika med 1 E minus en vektor av | E | ettor. Detta betyder att raderna av K är linjärt beroende, så det K = 0.

Som ett exempel, i 4-cykeln (som är tvådelad), det A G = 1. Däremot i 3-cykeln (som inte är tvådelad) är det A G = 2.

Varje hörn av FMP( G ) uppfyller en uppsättning m linjärt oberoende olikheter med likhet. För att beräkna hörnkoordinaterna måste vi därför lösa ett ekvationssystem som definieras av en kvadratisk submatris av A G . Enligt Cramers regel är lösningen ett rationellt tal där nämnaren är determinanten för denna submatris. Denna determinant måste vara +1 eller −1; därför är lösningen en heltalsvektor. Därför är alla hörnkoordinater heltal.

Med de n "mindre-än-ett"-begränsningarna är hörnkoordinaterna antingen 0 eller 1; därför är varje hörn incidensvektorn för en integralmatchning i G . Därför FMP( G ) = MP( G ).

Fasetterna av den matchande polytopen

En aspekt av en polytop är uppsättningen av dess punkter som uppfyller en väsentlig definierande olikhet mellan polytopen och likheten. Om polytopen är d -dimensionell, är dess fasetter ( d − 1)-dimensionella. För alla grafer G ges fasetterna av MP( G ) av följande olikheter:

  • 0 x ≥ E
  • 1 E ( v ) · x ≤ 1 (där v är en oisolerad vertex så att om v bara har en granne u , så är { u , v } en sammankopplad komponent av G, och om v har exakt två grannar, då ligger de inte intill).
  • 1 E ( S ) · x ≤ (| S | − 1)/2 (där S spänner över en 2-kopplad faktorkritisk subgraf.)

Perfekt matchande polytop

Den perfekt matchande polytopen i en graf G , betecknad PMP( G ), är en polytop vars hörn är incidensvektorerna för de perfekta integralmatchningarna i G. Uppenbarligen ingår PMP( G ) i MP( G ); Faktum är att PMP(G) är ansiktet på MP( G ) som bestäms av jämlikheten:

1 E · x = n /2.

Se även

  1. ^ a b c d    Lovász, László ; Plummer, MD (1986), Matchande teori , Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1 , MR 0859549
  2. ^ "1 tvådelad matchande polytop, stabil matchande polytop x1 x2 x3 föreläsning 10: feb ppt nedladdning" . slideplayer.com . Hämtad 2020-07-17 .

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Matching_polytope&oldid=1078697756 "