Bråkmatchning

I grafteorin är en bråkmatchning en generalisering av en matchning där varje hörn intuitivt kan brytas upp i bråkdelar som matchas till olika grannhörn.

Definition

Givet en graf G = ( V , E ), är en bråkmatchning i G en funktion som tilldelar varje kant e i E en bråkdel f ( e ) i [0, 1], så att för varje vertex v i V , summan av bråkdelar av kanter som gränsar till v är som mest 1:

\forall v\in V:\sum _{e\ni v}f(e)\leq 1

En matchning i traditionell mening är ett specialfall av en bråkmatchning, där bråkdelen av varje kant är antingen 0 eller 1: f ( e ) = 1 om e är i matchningen, och f ( e ) = 0 om det är inte. Av denna anledning, i samband med bråkmatchningar, kallas vanliga matchningar ibland för integralmatchningar .

Storleken på en integralmatchning är antalet kanter i matchningen, och matchningstalet $\nu (G)$ i en graf G är den största storleken på en matchning i G . Analogt storleken på en bråkmatchning summan av bråkdelar av alla kanter. Bråkmatchningstalet för en graf G är den största storleken på en bråkmatchning i G . Det betecknas ofta med $\nu ^{*}(G)$ . Eftersom en matchning är ett specialfall av en bråkmatchning, har man för varje graf G att det integrala matchningstalet för G är mindre än eller lika med bråkmatchningstalet för G ; i symboler:

\nu (G)\leq \nu ^{*}(G).

En graf där

\nu (G)=\nu ^{*}(G)

kallas en stabil graf . Varje tvådelad graf är stabil; detta betyder att i varje tvådelad graf är bråkmatchningstalet ett heltal och det är lika med det integrerade matchningstalet.

I en allmän graf, $\nu (G)>{\frac {2}{3}}\nu ^{*}(G).$ Bråkens matchande tal är antingen ett heltal eller ett halvt heltal.

Presentation av matris

För en tvådelad graf G = ( X + Y , E ) kan en bråkmatchning presenteras som en matris med | X | rader och | Y | kolumner. Värdet på posten i rad x och kolumn y är bråkdelen av kanten ( x , y ).

Perfekt bråkmatchning

En bråkmatchning kallas perfekt om summan av vikter intill varje vertex är exakt 1. Storleken på en perfekt matchning är exakt | V |/2.

I en tvådelad graf G = ( X + Y , E ), kallas en bråkmatchning för X-perfekt om summan av vikter intill varje vertex av X är exakt 1. Storleken på en X -perfekt bråkmatchning är exakt | X |.

För en tvådelad graf G = ( X + Y , E ), är följande ekvivalenta:

G medger en X -perfekt integralmatchning,
G medger en X -perfekt bråkmatchning, och
G uppfyller villkoret för Halls äktenskapsteorem .

Det första villkoret innebär det andra eftersom en integralmatchning är en bråkmatchning. Den andra innebär den tredje eftersom, för varje delmängd W av X , summan av vikter nära hörn av W är | W |, så att kanterna intill dem nödvändigtvis gränsar till åtminstone | W | hörn av Y. Enligt Halls äktenskapsteorem innebär det sista villkoret det första. ^{[ bättre källa behövs ]}

I en allmän graf är ovanstående villkor inte ekvivalenta - den största bråkmatchningen kan vara större än den största integralmatchningen. Till exempel medger en 3-cykel en perfekt bråkmatchning av storlek 3/2 (bråkdelen av varje kant är 1/2), men tillåter inte perfekt integralmatchning - den största integralmatchningen är av storlek 1.

Algoritmiska aspekter

En största bråkmatchning i en graf kan lätt hittas genom linjär programmering , eller alternativt genom en maximal flödesalgoritm . I en tvådelad graf är det möjligt att konvertera en maximal bråkmatchning till en maximal integralmatchning av samma storlek. Detta leder till en enkel polynom-tidsalgoritm för att hitta en maximal matchning i en tvådelad graf.

Om G är en tvådelad graf med | X | = | Y | = n , och M är en perfekt bråkmatchning, då är matrisrepresentationen av M en dubbelstokastisk matris - summan av element i varje rad och varje kolumn är 1. Birkhoffs algoritm kan användas för att dekomponera matrisen till en konvex summa av som mest n2-2n + 2 permutationsmatriser ^. Detta motsvarar att sönderdela M till en konvex summa av högst n ² -2 n +2 perfekta matchningar.

Maximal kardinalitet bråkmatchning

En bråkmatchning av maximal kardinalitet (dvs. maximal summa av bråk) kan hittas genom linjär programmering . Det finns också en starkt polynomisk tidsalgoritm, som använder förstärkningsvägar , som körs i tiden $O(|V||E|)$ .

Bråkmatchning med maximal vikt

Anta att varje kant på grafen har en vikt. En bråkdelsmatchning av maximal vikt i en graf kan hittas genom linjär programmering . I en tvådelad graf är det möjligt att konvertera en maximal vikt-bråkmatchning till en maximal-vikt-integralmatchning av samma storlek, på följande sätt:

Låt f vara bråkmatchningen.
Låt H vara en subgraf av G som endast innehåller kanterna e med icke-integral bråkdel, 0< f ( e )<1.
Om H är tomt så är vi klara.
om H har en cykel måste den vara jämn (eftersom grafen är tvådelad), så vi kan konstruera en ny bråkmatchning f ₁ genom att överföra en liten bråkdel ε från jämna kanter till udda kanter, och en ny bråkmatchning f ₂ genom att överföra ε från udda kanter till jämna kanter. Eftersom f är medelvärdet av f ₁ och f ₂ , är vikten av f medelvärdet mellan vikten av f ₁ och f ₂ . Eftersom f har maxvikt måste alla tre matchningarna ha samma vikt. Det finns ett val av e för vilka åtminstone en av f ₁ eller f ₂ har färre icke-integralfraktioner. Att fortsätta på samma sätt leder till en integrerad matchning av samma vikt.
Antag att H inte har någon cykel, och låt P vara en längsta väg i H . Bråkdelen av varje kant som gränsar till den första eller sista vertexen i P måste vara 0 (om den är 1 - den första/sista kanten i P bryter mot villkoret för bråkmatchning; om den är i (0,1) - är P inte den längsta). Därför kan vi konstruera nya bråkmatchningar f ₁ och f ₂ genom att överföra ε från udda kanter till jämna kanter eller vice versa. Återigen f ₁ och f ₂ ha maximal vikt, och minst en av dem har färre icke-integralfraktioner.

Bråkmatchande polytop

Givet en graf G = ( V , E ), är den bråkmatchande polytopen för G en konvex polytop som representerar alla möjliga bråkmatchningar av G . Det är en polytop i R ^{| E |} - den | E |-dimensionell euklidisk rymd. Varje punkt ( x ₁ ,..., x _|E| ) i polytopen representerar en matchning där bråkdelen av varje kant e är x _e . Polytopen definieras av | E | icke-negativitetsbegränsningar ( xe _| ≥ 0 för alla e i E ) och V | vertex-begränsningar (summan av x _e , för alla kanter e som ligger intill en vertex v , är högst 1). I en tvådelad graf är hörnen på den bråkmatchande polytopen alla integrala.

Se även

Fraktionerad färgning