Gallai–Edmonds nedbrytning

En illustration av de tre uppsättningarna i Gallai–Edmonds uppdelning av en exempelgraf.

I grafteorin är Gallai -Edmonds-nedbrytningen en uppdelning av en grafs hörn i tre delmängder som ger information om strukturen för maximala matchningar i grafen. Tibor Gallai och Jack Edmonds upptäckte det oberoende av varandra och bevisade dess nyckelegenskaper.

Gallai–Edmonds sönderdelning av en graf kan hittas med hjälp av blossom-algoritmen .

Egenskaper

Givet en graf $G$ , består dess Gallai–Edmonds-sönderdelning av tre disjunkta uppsättningar av hörn, ${\displaystyle A(G)} ,$ C $\displaystyle C(G)}$ , och $D(G)$ , vars förening är $V(G)$ : mängden av alla hörn av $G$ . Först delas hörnen av ${\displaystyle G} in i$ väsentliga hörn (hörn som täcks av varje maximal matchning i $G$ ) och oväsentliga hörn (hörn som lämnas utan täckning av minst en maximal matchning i $G$ ). Mängden $D(G)$ är definierad för att innehålla alla oväsentliga hörn. Viktiga hörn är uppdelade i $A(G)$ och $C(G)$ : uppsättningen $A(G)$ är definierad att innehålla alla väsentliga hörn som gränsar till minst en vertex av $D(G)$ och $C(G)$ definieras för att innehålla alla väsentliga hörn som inte gränsar till några hörn av $D(G)$ .

Det är vanligt att identifiera uppsättningarna $A(G)$ , $C(G)$ och $D(G)$ med subgraferna inducerade av dessa uppsättningar. Till exempel säger vi "komponenterna i $D(G)$ " för att betyda de anslutna komponenterna i subgrafen inducerade av $D(G)$ .

Nedbrytningen av Gallai–Edmonds har följande egenskaper:

1. Komponenterna i $D(G)$ är faktorkritiska grafer : varje komponent har ett udda antal hörn, och när någon av dessa hörn utelämnas, finns det en perfekt matchning av de återstående hörnen . I synnerhet har varje komponent en nästan perfekt matchning: en matchning som täcker alla utom en av hörnen.
2. Subgrafen inducerad av $C(G)$ har en perfekt matchning.
3. Varje delmängd $X\subseteq A(G)$ har grannar i minst $|X|+1$ komponenter av $D(G)$ .
4. Varje maximal matchning i $G$ har följande struktur: den består av en nästan perfekt matchning av varje komponent i $D(G)$ , en perfekt matchning av ${\ displaystyle C(G)}$ , och kanter från alla hörn i $A(G)$ till distinkta komponenter i $D(G)$ .
5. Om $D(G)$ har ${\displaystyle k} komponenter, då$ är antalet kanter i varje maximal matchning i $G$${\frac {1}{2}}(|V(G)|-k+|A(G)|)$ .

Generaliseringar

Gallai-Edmonds-nedbrytningen är en generalisering av Dulmage-Mendelsohns nedbrytning från tvådelade grafer till allmänna grafer.

En utvidgning av Gallai–Edmonds nedbrytningssats till flerkantsmatchningar ges i Katarzyna Paluchs "Capacitated Rank-Maximal Matchings".