Dulmage – Mendelsohn sönderdelning - Dulmage–Mendelsohn decomposition
I grafteorin är sönderdelningen av Dulmage – Mendelsohn en uppdelning av en bipartitgrafs hörn i delmängder, med egenskapen att två intilliggande hörn hör till samma delmängd om och bara om de är parade med varandra i en perfekt matchning av Graf. Det är uppkallat efter AL Dulmage och Nathan Mendelsohn , som publicerade det 1958. En generalisering till vilken graf som helst är Edmonds – Gallai -sönderdelningen med hjälp av Blossom -algoritmen .
Den grova sönderdelningen
Låt G = ( X + Y , E ) vara en tvådelad graf, och låt D vara mängden av hörn i G som inte motsvaras i åtminstone en maximal matchning av G . Då är D nödvändigtvis en oberoende uppsättning , så G kan delas upp i tre delar:
- Hörnen i D ∩ X och deras grannar;
- Hörnen i D ∩ Y och deras grannar;
- De återstående hörnen.
Varje maximal matchning i G består av matchningar i den första och andra delen som matchar alla grannar till D , tillsammans med en perfekt matchning av de återstående hörnen.
Alternativ grov sönderdelning
En alternativ definition av den grova sönderdelningen presenteras i (den tillskrivs vem som i sin tur tillskriver den).
Låt G vara en tvåpartig graf, M en maximal matchning i G och V 0 uppsättningen hörn för G utan motstycke med M ("fria hörn"). Sedan kan G delas upp i tre delar:
- E - de jämna hörnena - hörnen som kan nås från V 0 via en M -alternerande bana med jämn längd.
- O - udda hörn - hörnen som kan nås från V 0 med en M -alternerande väg med udda längd.
- U - de oåtkomliga hörnena - hörnen som inte kan nås från V 0 med en M -alternerande väg.
En illustration visas till vänster. De tjocka linjerna är kanterna på M . De svaga linjerna är andra kanter av G . De röda prickarna är hörnen överträffas av M .
Baserat på denna sönderdelning kan kanterna i G delas upp i sex delar enligt deras slutpunkter: EU, EE, OO, OU, EO, UU . Denna sönderdelning har följande egenskaper:
- Uppsättningarna E , O , U är parvis åtskilda.
- Uppsättningarna E , O , U beror inte på den maximalt matchande M (dvs varje maximal matchning definierar exakt samma sönderdelning).
- G innehåller endast OO, OU, EO och UU kanter.
- Varje maximal matchning i G innehåller endast EO- och UU- kanter.
- Någon maximal-matchning i G mättas alla hörn i O och alla hörn i U .
- Storleken på en maximal matchning i G är | O | + | U | / 2.
Den fina sönderdelningen
Den tredje uppsättningen hörn i den grova sönderdelningen (eller alla hörn i en graf med perfekt matchning) kan dessutom delas upp i delmängder med följande steg:
- Hitta en perfekt matchning av G .
- Bilda en riktad graf H vars hörn är de matchade kanter i G . För varje oöverträffad kant ( x, y ) i G , lägg till en riktad kant i H från den matchade kanten av x till den matchade kanten på y .
- Hitta de starkt anslutna komponenterna i den resulterande grafen.
- För varje komponent i H , bilda en delmängd av Dulmage – Mendelsohn -sönderdelningen som består av hörnen i G som är slutpunkter för kanterna i komponenten.
För att se att denna indelning i delmängder kännetecknar kanterna som hör till perfekta matchningar, anta att två hörn x och y i G tillhör samma delmängd av sönderdelningen, men inte redan matchas av den första perfekta matchningen. Då finns det en starkt ansluten komponent i H som innehåller kant x, y . Denna kant måste tillhöra en enkel cykel i H (enligt definitionen av stark anslutning) som nödvändigtvis motsvarar en alternerande cykel i G (en cykel vars kanter växlar mellan matchade och oöverträffade kanter). Denna alternerande cykel kan användas för att modifiera den initiala perfekta matchningen för att producera en ny matchning som innehåller kant x, y .
En kant x, y i grafen G tillhör alla perfekta matchningar av G , om och bara om x och y är de enda medlemmarna i deras uppsättning i sönderdelningen. En sådan kant existerar om och endast om det matchande förhindringsnumret för grafen är en.
Kärna
Som en annan komponent i Dulmage – Mendelsohn -sönderdelningen definierade Dulmage och Mendelsohn kärnan i en graf som föreningen av dess maximala matchningar. Detta koncept bör dock särskiljas från kärnan i betydelsen grafhomomorfismer och från k -kärnan som bildas genom avlägsnande av låggradiga hörn.
Ansökningar
Denna sönderdelning har använts för att dela upp maskor i finit elementanalys och för att bestämma specificerade, underspecificerade och överspecificerade ekvationer i system med olinjära ekvationer.
Referenser
- Dulmage, AL & Mendelsohn, NS (1958). "Täckning av tvåpartsgrafer". Burk. J. Math . 10 : 517–534. doi : 10.4153/cjm-1958-052-0 . Det ursprungliga Dulmage – Mendelsohn -papperet