Hallöverträdare
I grafteorin är en Hall-överträdare en uppsättning hörn i en graf som bryter mot villkoret för Halls äktenskapsteorem .
Formellt, givet en tvådelad graf G = ( X + Y , E ) , är en Hall-överträdare i X en delmängd W av X , för vilken | N G ( W )| < | W | , där N G ( W ) är uppsättningen av grannar till W i G .
Om W är en Hallöverträdare, så finns det ingen matchning som mättar alla hörn av W . Därför finns det heller ingen matchning som mättar X . Halls äktenskapsteorem säger att motsatsen också är sant: om det inte finns någon Hallöverträdare, så finns det en matchning som mättar X .
Algoritmer
Att hitta en Hallöverträdare
En Hall-överträdare kan hittas med en effektiv algoritm. Algoritmen nedan använder följande termer:
- En M -alternerande bana , för vissa matchande M , är en bana där den första kanten inte är en kant av M , den andra kanten är av M , den tredje inte är av M , etc.
- En vertex z är M -nåbar från någon vertex x , om det finns en M - alternerande väg från x till z .
Som ett exempel, betrakta figuren till höger, där de vertikala (blå) kanterna anger det matchande M . Spetsuppsättningarna Y 1 , X 1 , Y 2 , X 2 , är M -nåbara från x 0 (eller någon annan vertex av X 0 ), men Y 3 och X 3 är inte M -nåbara från x 0 .
Algoritmen för att hitta en Hall-överträdare fortsätter enligt följande.
- Hitta en maximal matchande M (den kan hittas med Hopcroft–Karp-algoritmen) .
- Om alla hörn av X är matchade, returnera "Det finns ingen Hallöverträdare".
- I annat fall, låt x 0 vara en omatchad vertex.
- Låt W vara mängden av alla hörn av X som är M -nåbara från x 0 (den kan hittas med Breadth-first search ; i figuren innehåller W x 0 och X 1 och X 2 ).
- Återgå W .
Detta W är verkligen en Hall-kränkare på grund av följande fakta:
- Alla hörn av N G ( W ) matchas av M . Antag motsägelsefullt att någon vertex y i N G ( W ) är omatchad av M . Låt x vara dess granne i W . Vägen från x 0 till x till y är en M -förstärkande väg - den är M -alternerande och den börjar och slutar med oöverträffade hörn, så genom att "invertera" den kan vi öka M , vilket motsäger dess maximalitet.
- W innehåller alla matchningar av N G ( W ) av M . Detta beror på att alla dessa matchningar är M -nåbara från x 0 .
- W innehåller en annan vertex - x 0 - som är omatchad av M per definition.
- Därför | W | = | N G ( W )| + 1 > | N G ( W )| , så W uppfyller verkligen definitionen av en Hallöverträdare.
Hitta minimala och minimala Hallöverträdare
En inklusionsminimal Hallöverträdare är en Hallöverträdare så att var och en av dess delmängder inte är en Hallöverträdare.
Ovanstående algoritm hittar faktiskt en inklusionsminimal Hallöverträdare. Detta beror på att om någon vertex tas bort från W , så kan de återstående hörnen matchas perfekt till hörnen på N G ( W ) (antingen genom kanterna på M eller genom kanterna på den M-alternerande banan från x 0 ).
Algoritmen ovan hittar inte nödvändigtvis en Hall-överträdare med minsta kardinalitet . Till exempel, i figuren ovan, returnerar den en Hallöverträdare av storlek 5, medan X 0 är en Hallöverträdare av storlek 3.
Faktum är att hitta en Hall-överträdare med minsta kardinalitet är NP-svårt. Detta kan bevisas genom reduktion från klickproblemet .
Att hitta en Hallöverträdare eller en utökad väg
Följande algoritm tar som indata en godtycklig matchande M i en graf och en vertex x 0 i X som inte är mättad av M .
Den returnerar som utdata, antingen en Hall violator som innehåller x 0 eller en sökväg som kan användas för att utöka M .
- Ställ in k = 0 , W k := { x 0 }, Z k := {} .
- Hävda:
- 0 W k = { x ,..., x k } där x i är distinkta hörn av X ;
- Z k = { y 1 ,..., y k } där y i är distinkta hörn av Y ;
- För alla i 1 ≥ matchas y . i till x i av M
- För alla i ≥ 1 är y i ansluten till några x j < i med en kant som inte är i M .
- Om N G ( W k ) ⊆ Z k , så är W k en Hallöverträdare, eftersom | W k | = k +1 > k = | Z k | ≥ | N G ( W k )| . Returnera Hall-kränkaren W k .
- Låt annars y k +1 vara ett hörn i N G ( W k ) \ Z k . Tänk på följande två fall:
- Fall 1: y k +1 matchas av M .
- Eftersom x är 0 Wk omatchad , Zk , och varje xi i Wk i matchas till yi i måste partnern till denna yk . +1 vara någon vertex av X som inte är Beteckna det med x k +1 .
- Låt Wk + +1 1 WkU { xk + . 1 och 1 : = + 1 : = ZkU { yk } } Zk och k := k +
- Gå tillbaka till steg 2 .
- Fall 2: y k +1 är omatchad av M .
- Eftersom y k +1 är i N G ( W k ) , är den ansluten till något x i (för i < k + 1 ) med en kant som inte är i M . x i är ansluten till y i med en kant i M . y i är ansluten till något x j (för j < i ) med en kant som inte är i M , och så vidare. Att följa dessa anslutningar måste så småningom leda till x 0 , vilket är oöverträffat. Därför har vi en M-förstärkande väg. Återgå M-augmenting-banan .
Vid varje iteration växer W k och Z k med en vertex. Därför måste algoritmen avslutas efter högst | X | iterationer.
Proceduren kan användas iterativt: börja med att M är en tom matchning, anropa proceduren om och om igen, tills antingen en Hallöverträdare hittas, eller så mättar den matchande M alla hörn av X . Detta ger ett konstruktivt bevis för Halls teorem.
externa länkar
- En tillämpning av Hallöverträdare i begränsningsprogrammering .
-
"Hitta en delmängd i tvådelad graf som bryter mot Halls tillstånd" . Datavetenskap stack utbyte . 2014-09-15 . Hämtad 2019-09-08 .
{{ citera webben }}: CS1 underhåll: url-status ( länk )