Matchning i hypergrafer

I grafteorin är en matchning i en hypergraf en uppsättning hyperkanter , där varannan hyperkant är osammanhängande . Det är en förlängning av begreppet matchning i en graf .

Definition

Kom ihåg att en hypergraf $H$ är ett par $(V, E)$ , där $V$ är en uppsättning av hörn och $E$ är en uppsättning delmängder av $V$ som kallas hyperkanter . Varje hyperedge kan innehålla en eller flera hörn.

En matchning i $H$ är en delmängd $M$ av $E$ , så att varannan hyperkant $e 1$ och $e 2$ i $M$ har en tom skärningspunkt (har ingen vertex gemensam).

Matchningstalet för en hypergraf $H$ är den största storleken på en matchning i $H$ . Det betecknas ofta med $ν(H)$ .

Som ett exempel, låt $V$ vara mängden ${1,2,3,4,5,6,7}.$ Betrakta en 3-uniform hypergraf på $V$ (en hypergraf där varje hyperedge innehåller exakt 3 hörn). Låt $H$ vara en 3-enhetlig hypergraf med 4 hyperkanter:

{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }

Sedan tillåter $H$ flera matchningar av storlek 2, till exempel:

{ {1,2,3}, {4,5,6} }

{ {1,4,5}, {2,3,6} }

Men i någon delmängd av 3 hyperkanter skär åtminstone två av dem varandra, så det finns ingen matchning av storlek 3. Därför är det matchande antalet $H$ 2.

Skärande hypergraf

En hypergraf $H = (V, E)$ kallas skärande om varannan hyperkant i $E$ har en vertex gemensam. En hypergraf $H$ är skärande om och endast om den inte har någon matchning med två eller flera hyperkanter, om och endast om $ν(H) = 1$ .

Matchning i en graf som ett specialfall

En graf utan självslingor är bara en 2-uniform hypergraf: varje kant kan betraktas som en uppsättning av de två hörn som den förbinder. Till exempel representerar denna 2-enhetliga hypergraf en graf med 4 hörn ${1,2,3,4}$ och 3 kanter:

{ {1,3}, {1,4}, {2,4} }

Enligt definitionen ovan är en matchning i en graf en uppsättning $M$ av kanter, så att varje två kanter i $M$ har en tom skärningspunkt. Detta motsvarar att säga att inga två kanter i $M$ ligger intill samma vertex; detta är exakt definitionen av en matchning i en graf .

Bråkmatchning

En bråkmatchning i en hypergraf är en funktion som tilldelar en bråkdel i $[0,1]$ till varje hyperkant, så att för varje vertex $v$ i $V är$ summan av bråkdelar av hyperkanter som innehåller $v$ högst 1. En matchning är en speciell fallet med en bråkmatchning där alla bråk är antingen 0 eller 1. Storleken på en bråkmatchning är summan av bråkdelar av alla hyperkanter.

Bråkmatchningstalet för en hypergraf H $är$ den största storleken på en bråkmatchning i $H$ . Det betecknas ofta med $ν *(H)$ .

Eftersom en matchning är ett specialfall av en bråkmatchning, för varje hypergraf $H$ :

Matchande-tal( $H$ ) ≤ bråk-matchande-tal( $H$ )

Symboliskt är denna princip skriven:

\nu (H)\leq \nu ^{*}(H)

I allmänhet kan bråkmatchningstalet vara större än matchningstalet. En sats av Zoltán Füredi ger övre gränser för förhållandet bråkmatchande tal( $H$ ) / matchande tal( $H$ ):

Om varje hyperedge i H innehåller högst r hörn, då
${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1+{\frac {1}{r}}.$

I synnerhet i en enkel graf:

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq {\frac {3}{2}}.$
- Olikheten är skarp: Låt $H r$ vara det $r$ -uniforma ändliga projektiva planet . Då är $ν (H r) = 1$ eftersom varannan hyperkant skär varandra, och $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} ν *( H r ) = r – 1 + 1 / r$ av bråkmatchningen som tilldelar en vikt på $1 / r$ till varje hyperkant (det är en matchning eftersom varje vertex finns i $r$ hyperkanter, och dess storlek är $r - 1 + 1 / r$ eftersom det finns $r 2 - r + 1$ hyperkanter). Därför är förhållandet exakt $r - 1 + 1 / r$ .
Om $r$ är sådan att det $r$ -uniforma ändliga projektiva planet inte existerar (till exempel $r = 7$ ), så gäller en starkare olikhet:
${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.$
Om H är r -partit (hörnen är uppdelade i r delar och varje hyperedge innehåller en vertex från varje del), då:
${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.$

I synnerhet i en tvådelad graf, $ν *(H) = ν (H)$ . Detta bevisades av András Gyárfás .
- Olikheten är skarp: Låt $H r-$ vara det trunkerade projektiva planet av ordningen $r - 1$ . Då är $ν (H r -) = 1$ eftersom varannan hyperkant skär varandra, och $ν *(H r -) = r - 1$ genom bråkmatchningen som tilldelar en vikt på $1 / r$ till varje hyperkant (det finns $r 2 - r$ hyperkanter ).

Perfekt matchning

En matchande $M$ kallas perfekt om varje vertex $v$ i $V$ finns i exakt en hyperedge av $M$ . Detta är den naturliga förlängningen av begreppet perfekt matchning i en graf.

En bråkmatchande $M$ kallas perfekt om för varje vertex $v$ i $V$ summan av bråkdelar av hyperkanter i $M$ som innehåller $v$ är exakt 1.

Betrakta en hypergraf $H$ där varje hyperkant innehåller högst $n$ hörn. Om $H$ medger en perfekt bråkmatchning, är dess bråkmatchningsnummer minst $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} | V | ⁄ n$ . Om varje hyperedge i $H$ innehåller exakt $n$ hörn, är dess bråkmatchningsnummer exakt $| V | ⁄ n$ . Detta är en generalisering av det faktum att storleken på en perfekt matchning i en graf är $| V | ⁄ 2$ .

Givet en uppsättning $V av hörn,$ kallas en samling $E$ av delmängder av $V$ balanserad om hypergrafen $(V, E)$ medger en perfekt bråkmatchning.

Till exempel, om $V = {1,2,3,a,b,c}$ och $E = { {1,a}, {2,a}, {1,b}, {2,b}, {3, c} },$ då är $E$ balanserad, med perfekt bråkmatchning ${ 1/2, 1/2, 1/2, 1/2, 1 }.$

Det finns olika tillräckliga förutsättningar för att det ska finnas en perfekt matchning i en hypergraf:

Hall-typ satser för hypergrafer - presenterar tillräckliga villkor analogt med Halls äktenskapssats, baserat på uppsättningar av grannar.
Perfekt matchning i höggradiga hypergrafer - presenterar tillräckliga förhållanden analogt med Diracs teorem om Hamiltons cykler, baserat på graden av hörn.
Keevash och Mycroft utvecklade en geometrisk teori för hypergrafmatchning.

Balanserad set-familj

En mängd-familj $E$ $över H = (V , E)$ en markmängd $V$ kallas balanserad (med avseende på $V$ ) om hypergrafen medger en perfekt bråkmatchning.

Betrakta till exempel vertexmängden $V = {1,2,3,a,b,c}$ och kantmängden $E = {1-a, 2-a, 1-b, 2-b, 3-c}.$ $E$ är balanserad, eftersom det finns en perfekt bråkmatchning med vikterna ${1/2, 1/2, 1/2, 1/2, 1}.$

Beräknar en maximal matchning

Problemet med att hitta en maximal kardinalitetsmatchning i en hypergraf, och därmed beräkna $\nu (H)$ , är NP-svårt även för 3-enhetliga hypergrafer (se 3-dimensionell matchning ). Detta i motsats till fallet med enkla (2-uniforma) grafer där beräkning av en maximal kardinalitetsmatchning kan göras i polynomtid.

Matchande och täckande

En vertex-cover i en hypergraf $H = (V, E)$ är en delmängd $T$ av $V$ , så att varje hyperedge i $E$ innehåller minst en vertex av $T$ (det kallas också en transversal eller en träffande set , och är ekvivalent med ett fast lock ). Det är en generalisering av begreppet ett vertextäcke i en graf.

Hönts -täckningsnumret för en hypergraf $H$ är den minsta storleken på ett vertextäcke i $H$ . Det betecknas ofta med $τ (H)$ , för transversal.

En bråkdel av vertextäcke är en funktion som tilldelar en vikt till varje vertex i $V$ , så att för varje hyperkant $e$ i $E är$ summan av bråkdelar av hörn i $e$ minst 1. Ett vertextäcke är ett specialfall av en bråkdel av vertex omslag där alla vikter är antingen 0 eller 1. Storleken på ett bråkdelstäcke är summan av bråkdelar av alla hörn.

Bråkdelen av vertex-täckningsnumret för en hypergraf $H$ är den minsta storleken på en bråkdel av vertextäcket i $H$ . Det betecknas ofta med $τ *(H)$ .

Eftersom en vertex-cover är ett specialfall av en fraktionell vertex-cover, för varje hypergraf $H$ :

bråk-vertex-täcktal ( $H$ ) ≤ vertex-täck-nummer ( $H$ ).

Linjär programmeringsdualitet innebär att för varje hypergraf $H$ :

bråk-matchande-tal ( $H$ ) = bråk-vertex-täcktal ( $H$ ).

Därför, för varje hypergraf $H$ :

\nu (H)\leq \nu ^{*}(H)=\tau ^{*}(H) \leq \tau (H)

Om storleken på varje hyperkant i $H$ är högst $r$ så är föreningen av alla hyperkanter i en maximal matchning en vertex-cover (om det fanns en otäckt hyperedge, kunde vi ha lagt till den i matchningen). Därför:

\tau (H)\leq r\cdot \nu (H).

Denna olikhet är snäv: likhet gäller till exempel när $V$ innehåller $r \cdot ν (H) + r - 1$ hörn och $E$ innehåller alla delmängder av $r$ hörn.

Men i allmänhet $τ *(H) < r \cdot ν (H)$ , eftersom $ν *(H) < r \cdot ν (H)$ ; se Bråkmatchning ovan.

Rysers gissning säger att i varje $r$ -partit $r$ -uniform hypergraf:

\tau (H)\leq (r-1)\nu (H).

Några speciella fall av gissningen har bevisats; se Rysers gissning .

Kőnigs egendom

En hypergraf har egenskapen Kőnig om dess maximala matchningsnummer är lika med dess minsta vertex-täcktal, nämligen om $ν (H) = τ (H)$ . Kőnig -Egerváry-satsen visar att varje tvådelad graf har Kőnig-egenskapen. För att utvidga denna sats till hypergrafer måste vi utvidga begreppet bipartiteness till hypergrafer.

En naturlig generalisering är följande. En hypergraf kallas 2-colorable om dess hörn kan vara 2-färgade så att varje hyperedge (med storleken minst 2) innehåller minst en vertex av varje färg. En alternativ term är Fastighet B . En enkel graf är tvådelad om den är 2-färgbar. Det finns dock 2-färgbara hypergrafer utan Kőnigs egendom. Betrakta till exempel hypergrafen med $V = {1,2,3,4}$ med alla tripletter $E = { {1,2,3} , {1,2,4} , {1,3,4} , {2 ,3,4} }.$ Den är 2-färgbar, till exempel kan vi färga ${1,2}$ blå och ${3,4}$ vit. Men dess matchande nummer är 1 och dess vertex-täcknummer är 2.

En starkare generalisering är följande. Givet en hypergraf $H = (V, E)$ och en delmängd $V'$ av $V$ , är begränsningen av $H$ till $V'$ hypergrafen vars hörn är $V$ , och för varje hyperedge $e$ i $E$ som skär $V'$ , har den en hyperedge $e '$ det är skärningspunkten mellan $e$ och $V'$ . En hypergraf kallas balanserad om alla dess begränsningar är 2-färgbara. En enkel graf är tvådelad om den är balanserad.

En enkel graf är tvådelad om den inte har några cykler med udda längd. På samma sätt är en hypergraf balanserad om den inte har några kretsar med udda längd . En krets med längden $k$ i en hypergraf är en alternerande sekvens $(v 1, e 1, v 2, e 2, \dots, v k, e k, v k +1 = v 1)$ , där $v i$ är distinkta hörn och e $. i$ är distinkta hyperkanter, och varje hyperedge innehåller vertex till vänster och vertex till höger Kretsen kallas obalanserad om varje hyperedge inte innehåller några andra hörn i kretsen. Claude Berge bevisade att en hypergraf är balanserad om och bara om den inte innehåller en obalanserad krets med udda längd. Varje balanserad hypergraf har Kőnigs egenskaper.

Följande är likvärdiga:

Varje partiell hypergraf av $H$ (dvs en hypergraf härledd från $H$ genom att radera några hyperkanter) har egenskapen Kőnig.
Varje partiell hypergraf av $H$ har egenskapen att dess maximala grad är lika med dess minsta kantfärgningsnummer .
$H$ har egenskapen Helly , och skärningsgrafen för $H$ (den enkla grafen där hörnen är $E$ och två element i $E$ är länkade om och endast om de skär varandra) är en perfekt graf .

Matchning och packning

Problemet med uppsättningspackning motsvarar hypergrafmatchning.

En vertexpackning i en (enkel) graf är en delmängd $P$ av dess hörn, så att inga två hörn i $P$ är intill varandra.

Problemet med att hitta en maximal vertexpackning i en graf är likvärdig med problemet med att hitta en maximal matchning i en hypergraf:

Givet en hypergraf $H = (V, E)$ , definiera dess skärningsgraf $Int(H)$ som den enkla grafen vars hörn är $E$ och vars kanter är par $(e 1, e 2)$ så att $e 1$ , $e 2$ har en vertex i allmänning. Då är varje matchning i $H$ en vertex-packning i $Int(H)$ och vice versa.
Givet en graf $G = (V', E')$ , definierar dess stjärnhypergraf $St(G)$ som hypergrafen vars hörn är $E'$ och vars hyperkanter är stjärnorna i $G: s hörn$ (dvs. för varje vertex $v'$ i $V '$ , det finns en hyperedge i $St(G)$ som innehåller alla kanter i $E'$ som gränsar till $v'$ ). Då är varje vertexpackning i $G$ en matchning i $St(G)$ och vice versa.
Alternativt, givet en graf $G = (V', E')$ , definiera dess klickhypergraf $Cl(G)$ som hypergrafen vars hörn är klickarna av $G$ , och för varje vertex $v'$ i $V'$ finns det en hyperedge i $Cl (G)$ som innehåller alla klick i $G$ som innehåller $v'$ . Återigen, varje vertexpackning i $G$ är en matchning i $Cl(G)$ och vice versa. Observera att $Cl(G)$ inte kan konstrueras från $G$ i polynomtid , så det kan inte användas som en reduktion för att bevisa NP-hårdhet. Men det har några teoretiska användningsområden.

Se även

3-dimensionell matchning – ett specialfall av hypergrafmatchning till 3-uniforma hypergrafer.
Vertextäcke i hypergrafer
Tvådelad hypergraf
Regnbågsmatchning i hypergrafer
D-intervallhypergraf - en oändlig hypergraf där det finns en viss relation mellan matchningen och det täckande numret.
Erdős–Ko–Rado-sats om parvisa icke-disjunkta kanter i hypergrafer

^ ^a ^b ^c ^d ^e ^f ^g Lovász, László ; Plummer, MD (1986), Matchande teori , Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1 , MR 0859549
^ Berge, Claude (1973). Grafer och hypergrafer . Amsterdam: Nord-Holland.
^ ^a ^b Aharoni, Ron; Kessler, Ofra (1990-10-15). "Om en möjlig utvidgning av Halls teorem till tvådelade hypergrafer" . Diskret matematik . 84 (3): 309–313. doi : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .
^ ^a ^b ^c ^d Füredi, Zoltán (1981-06-01). "Maximal grad och bråkmatchningar i enhetliga hypergrafer". Combinatorica . 1 (2): 155–162. doi : 10.1007/BF02579271 . ISSN 1439-6912 . S2CID 10530732 .
^ Lovász, L. (1974). Berge, Claude; Ray-Chaudhuri, Dijen (red.). "Minimaxsatser för hypergrafer". Hypergrafseminarium . Föreläsningsanteckningar i matematik. Berlin, Heidelberg: Springer. 411 : 111–126. doi : 10.1007/BFb0066186 . ISBN 978-3-540-37803-7 .
^ ^a ^b Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira (2020-01-02). "Rättvis division med flera bitar" . Diskret tillämpad matematik . 283 : 115–122. arXiv : 1710.09477 . doi : 10.1016/j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .
^ Keevash, Peter; Mycroft, Richard (2015-01-01). En geometrisk teori för hypergrafmatchning . Memoirs of the American Mathematical Society. Vol. 233. American Mathematical Society. ISBN 978-1-4704-0965-4 .
^ Berge, CLAUDE (1973-01-01), Srivastava, JAGDISH N. (red.), " KAPITEL 2 – Balanserade hypergrafer och några tillämpningar på grafteori", A Survey of Combinatorial Theory , North-Holland, s. 15– 23, ISBN 978-0-7204-2262-7 , hämtad 2020-06-19
^ Berge, Claude; Vergnas, Michel LAS (1970). "Sur Un Theorems Du Type König Pour Hypergraphes". Annals of the New York Academy of Sciences . 175 (1): 32–40. doi : 10.1111/j.1749-6632.1970.tb56451.x . ISSN 1749-6632 . S2CID 84670737 .

[lp-1] ^ ^a ^b ^c ^d ^e ^f ^g Lovász, László ; Plummer, MD (1986), Matchande teori , Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1 , MR 0859549

[2] Berge, Claude (1973). Grafer och hypergrafer . Amsterdam: Nord-Holland.

[:1-3] Aharoni, Ron; Kessler, Ofra (1990-10-15). "Om en möjlig utvidgning av Halls teorem till tvådelade hypergrafer" . Diskret matematik . 84 (3): 309–313. doi : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .

[:2-4] Füredi, Zoltán (1981-06-01). "Maximal grad och bråkmatchningar i enhetliga hypergrafer". Combinatorica . 1 (2): 155–162. doi : 10.1007/BF02579271 . ISSN 1439-6912 . S2CID 10530732 .

[5] Lovász, L. (1974). Berge, Claude; Ray-Chaudhuri, Dijen (red.). "Minimaxsatser för hypergrafer". Hypergrafseminarium . Föreläsningsanteckningar i matematik. Berlin, Heidelberg: Springer. 411 : 111–126. doi : 10.1007/BFb0066186 . ISBN 978-3-540-37803-7 .

[:0-6] Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira (2020-01-02). "Rättvis division med flera bitar" . Diskret tillämpad matematik . 283 : 115–122. arXiv : 1710.09477 . doi : 10.1016/j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .

[7] Keevash, Peter; Mycroft, Richard (2015-01-01). En geometrisk teori för hypergrafmatchning . Memoirs of the American Mathematical Society. Vol. 233. American Mathematical Society. ISBN 978-1-4704-0965-4 .

[8] Berge, CLAUDE (1973-01-01), Srivastava, JAGDISH N. (red.), " KAPITEL 2 – Balanserade hypergrafer och några tillämpningar på grafteori", A Survey of Combinatorial Theory , North-Holland, s. 15– 23, ISBN 978-0-7204-2262-7 , hämtad 2020-06-19

[9] Berge, Claude; Vergnas, Michel LAS (1970). "Sur Un Theorems Du Type König Pour Hypergraphes". Annals of the New York Academy of Sciences . 175 (1): 32–40. doi : 10.1111/j.1749-6632.1970.tb56451.x . ISSN 1749-6632 . S2CID 84670737 .