Perfekt matchning - Perfect matching

I grafteori är en perfekt matchning i en graf en matchning som täcker varje toppunkt i grafen. Mer formellt, givet en graf G = ( V , E ), en perfekt matchning i G är en delmängd M av E , så att varje hörn i V ligger i anslutning till exakt en kant i M .

En perfekt matchning kallas också en 1-faktor ; se Graffaktorisering för en förklaring av denna term. I en del litteratur används termen komplett matchning .

Varje perfekt matchning är en maximal kardinalitetsmatchning , men motsatsen är inte sant. Tänk till exempel på följande grafer:

I diagram (b) finns en perfekt matchning (av storlek 3) eftersom alla 6 hörn matchas; i graferna (a) och (c) finns en maximal kardinalitetsmatchning (av storlek 2) som inte är perfekt, eftersom vissa hörn är oöverträffade.

En perfekt matchning är också en minimistorlek kant lock . Om det finns en perfekt matchning, så är både matchningsnumret och kantomslaget lika med $| V | / 2$ .

En perfekt matchning kan endast ske när grafen har ett jämnt antal hörn. En nästan perfekt matchning är en där exakt en hörn är oöverträffad. Detta kan bara inträffa när grafen har ett udda antal hörn, och en sådan matchning måste vara maximal. I figuren ovan visar del (c) en nästan perfekt matchning. Om det för varje hörn i en graf finns en nästan perfekt matchning som bara utelämnar den punkten, kallas grafen också för faktorkritisk .

Karakteriseringar

Halls äktenskapsteorem ger en karakterisering av tvåpartsdiagram som har en perfekt matchning.

Den Tutte sats ger en karakterisering för godtyckliga grafer.

En perfekt matchning är en spännande 1-vanlig subgraf, aka en 1-faktor . I allmänhet är en k -regelbunden subgraf en k -faktor .

En spektral karakterisering för att en graf ska få en perfekt matchning ges av Hassani Monfared och Mallik enligt följande: Låt vara en graf på jämna hörn och vara distinkta icke -noll rent imaginära tal . Därefter har en perfekt matchning om och endast om det finns en verklig antisymmetrisk matris med grafen och egenvärden . Observera att den (enkla) grafen för en verklig symmetrisk eller sned-symmetrisk matris av ordning har hörn och kanter som ges av de icke-noll-off-diagonala posterna av . ${\ displaystyle G}$ ${\ displaystyle n}$ ${\ displaystyle \ lambda _ {1}> \ lambda _ {2}> \ ldots> \ lambda _ {\ frac {n} {2}}> 0}$ ${\ displaystyle {\ frac {n} {2}}}$ ${\ displaystyle G}$ ${\ displaystyle A}$ ${\ displaystyle G}$ ${\ displaystyle \ pm \ lambda _ {1}, \ pm \ lambda _ {2}, \ ldots, \ pm \ lambda _ {\ frac {n} {2}}}$ ${\ displaystyle A}$ ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle A}$

Beräkning

Att avgöra om en graf medger en perfekt matchning kan göras på polynomtid , med vilken algoritm som helst för att hitta en maximal kardinalitetsmatchning .

Att räkna antalet perfekta matchningar, även i bipartitdiagram , är dock #P-komplett . Detta beror på att beräkningen av permanenten för en godtycklig 0–1-matris (ett annat #P-komplett problem) är samma sak som att beräkna antalet perfekta matchningar i bipartitgrafen som har den angivna matrisen som dess biadjacensmatris .

En anmärkningsvärd sats av Kasteleyn säger att antalet perfekta matchningar i en plan graf kan beräknas exakt i polynomtid via FKT -algoritmen .

Antalet perfekta matchningar i en komplett graf K _n (med n jämnt) ges av dubbelfaktoralen : ${\ displaystyle (n-1) !!}$

Perfekt matchande polytop

Den perfekta matchande polytopen i en graf är en polytop i R ^{| E |}där varje hörn är en incidensvektor för en perfekt matchning.

Se även

Referenser

^ Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, kapitel 5.
^ Keivan Hassani Monfared och Sudipta Mallik, sats 3.6, spektral karakterisering av matchningar i grafer, linjär algebra och dess tillämpningar 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004
^ Callan, David (2009), En kombinatorisk undersökning av identiteter för dubbelfaktorialen , arXiv : 0906.1317 , Bibcode : 2009arXiv0906.1317C.

[1] Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, kapitel 5.

[2] Keivan Hassani Monfared och Sudipta Mallik, sats 3.6, spektral karakterisering av matchningar i grafer, linjär algebra och dess tillämpningar 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004

[3] Callan, David (2009), En kombinatorisk undersökning av identiteter för dubbelfaktorialen , arXiv : 0906.1317 , Bibcode : 2009arXiv0906.1317C.

Languages

In other projects