Motsvarande

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 27 mars 2022; kontroller kräver 2 redigeringar .

I grafteori är en matchande , eller en oberoende uppsättning kanter i en graf, en uppsättning av parvisa icke-angränsande kanter.

Definition

Låt en graf G = ( V , E ) ges, en matchande M i G är en uppsättning av parvisa icke-intilliggande kanter, det vill säga kanter som inte har gemensamma hörn, d.v.s. . $\forall e,f\in M:e\cap f=\emptyset$

Relaterade definitioner

En maximal matchning är en matchande M i en graf G som inte ingår i någon annan matchning av denna graf, det vill säga det är omöjligt att lägga till en enda kant till den som inte ligger intill alla kanter av matchningen. Med andra ord, en matchande M av en graf G är maximal om någon kant i G har en icke-tom skärningspunkt med minst en kant från M . Nedan finns exempel på maximala matchningar (röda kanter) i tre grafer [1] .

Den största matchningen (eller maximal storleksmatchning [2] ) är matchningen som innehåller det maximala antalet kanter. Matchningstalet [3] för en graf är antalet kanter i den största matchningen. En graf kan ha en uppsättning största matchningar. Dessutom är varje största matchning maximal, men inte något maximum kommer att vara störst. De följande tre figurerna visar de största matchningarna i samma tre kolumner [1] . $\nu (G)$ $G$

Vissa författare använder termen "maximal matchning" för den största matchningen [4] [5] [6] [7] .

En perfekt matchning (eller 1-faktor ) är en matchning där alla hörn i grafen deltar. Det vill säga att varje hörn av grafen faller in mot exakt en kant som ingår i matchningen. Figur (b) i figuren ovan är ett exempel på en sådan matchning. Varje perfekt matchning är störst och maximal. En perfekt matchning är också en kantbeläggning av minsta storlek. I det allmänna fallet , var är grafens kantskyddsnummer , med andra ord, storleken på den största matchningen överstiger inte storleken på den minsta kanttäckningen. $\nu (G)\leq \rho (G)$ $\rho (G)$ $G$

En nästan perfekt matchning är en matchning där exakt en vertex inte deltar. Detta kan hända om grafen har ett udda antal hörn. I figuren ovan är matchningen i kolumn (c) nästan perfekt. Om det för någon vertex i grafen finns en nästan perfekt matchning som inte innehåller exakt denna vertex, kallas grafen faktor kritisk .

Låt ett matchande M ges .

en alternerande bana är en bana där kanterna växelvis hör till matchningen och inte tillhör den.
en förstärkningsbana (eller förstärkningsbana) är en alternerande väg som börjar och slutar med fria hörn (d.v.s. deltar inte i matchningen).

Berges lemma säger att en matchning är maximal om och bara om det inte finns någon komplementär väg.

Egenskaper

Antalet perfekta matchningar i en tvådelad graf är lika med permanenten för dess närliggande matris .
I vilken graf som helst utan isolerade hörn, summeras antalet matchningar och antalet kanttäckningar till antalet hörn [8] .
- I synnerhet, om det finns en perfekt matchning, är båda siffrorna | v | / 2.

Om A och B är två maximala matchningar, då | A | ≤ 2| b | och | b | ≤ 2| A |. För att se detta, notera att varje kant från B \ A kan paras ihop med högst två kanter från A \ B eftersom A är en matchning. Varje kant A \ B är dock konjugerad till kanten B \ A eftersom B är maximal. Följaktligen, $|A\setminus B|\leq 2|B\setminus A|$

Nästa har vi

|A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|

Detta innebär i synnerhet att varje maximal matchning är en 2-approximation av den största matchningen, såväl som en 2-approximation av den minsta maximala matchningen. Denna ojämlikhet är exakt. Till exempel, om G är en bana med 3 kanter och 4 hörn, är den minsta storleken på den maximala matchningen 1 och storleken på den största matchningen är 2.

Polynom av matchningar

Den genererande funktionen av antalet k -kantsmatchningar i en graf kallas matchande polynom . Låt G vara en graf och m k vara antalet k -kantmatchningar. Det matchande polynomet i grafen G är

\sum _{{k\geq 0}}m_{k}x^{k}

Det finns en annan definition av det matchande polynomet

\summa _{{k\geq 0}}(-1)^{k}m_{k}x^{{n-2k}}

där n är antalet hörn i grafen. Båda definitionerna har sina egna tillämpningsområden.

Algoritmer och beräkningskomplexitet

Den största matchningen i en tvådelad graf

Matchningsproblem uppstår ofta när man arbetar med tvådelade grafer . Att hitta den största matchningen i en tvådelad graf [9] är kanske det enklaste problemet. Algoritmen för utfyllnadsväg får det genom att hitta utfyllnadsvägen från varje vertex in och lägga till den i matchningen om en väg hittas. En alternativ lösning är att matchningen kommer att kompletteras så länge det finns expanderande kompletterande vägar: $G=(V=(X,Y),E)$ $x\i X$ $Y$

Installera . $M=\emptyset$
Medan det finns växande påfyllningsvägar : $P$
1. $M=M\oplus E(P)$

En förstärkande sökväg är en sökväg av formuläret som är sant för . En utökad bana kallas en expanderande bana om . $v_{0},\{v_{0},v_{1}\},v_{1},\{v_{1},v_{2}\},v_{2},\dots ,v_ {l-1},\{v_{l-1},v_{l}\},v_{l}$ $\{v_{i-1},v_{i}\}\in M\Leftrightarrow \{v_{i},v_{i+1}\}\notin M$ $0\leqslant i\leqslant l$ $v_{0},v_{l}\notin M$

Lemma: För varje graf , matchande och kompletteringsväg gäller matchningen och . Bevis: Låt , och vara den initiala hörn av , så och , och vara den sista vertex av , så att och , och vara en mellanliggande vertex av , så . Det följer av detta att ytterligare en kant kommer att läggas till i grafen än att den tas bort från den. $G=(V,E)$ $M$ $P$ $M\oplus E(P)$ $|M\oplus E(P)|=|M|+1$ $G'=(V,M)$ $G''=(V,M\oplus E(P))$ $v$ $P$ $\delta _{G'}(v)=0$ $\delta _{G''}(v)=1$ $w$ $P$ $\delta _{G'}(w)=0$ $\delta _{G''}(w)=1$ $u$ $P$ $\delta _{G'}(u)=\delta _{G''}(u)=1$

Lemma: För alla grafer och matchningar så att följande är sant: grafen innehåller ett minimum av kompletteringsvägar som inte skär varandra vid hörn med avseende på . Bevis: Låt och , medan verkligen och och sålunda följer . Låt för de sammankopplade komponenterna i grafen . Från följer $G=(V,E)$ $M$ $N$ $|M|<|N|$ $H=(V,M\oplus N)$ $|N|-|M|$ $M$ $G$ $G_{M}=(V,M)$ $G_{N}=(V,N)$ ${\displaystyle \delta (G_{M})\subset \{0,1\))$ ${\displaystyle \delta (G_{N})\subset \{0,1\))$ ${\displaystyle \delta (H)\subset \{0,1,2\))$ $G_{i}=(V,E_{i})$ $1\leqslant i\leqslant g$ $H$ ${\displaystyle \delta (H)\subset \{0,1,2\))$

${\displaystyle G_{i))$ är en isolerad vertex eller
${\displaystyle G_{i))$ är en cykel av jämn längd, eller
${\displaystyle G_{i))$ är en bana av jämn längd, eller
${\displaystyle G_{i))$ är en väg med udda längd

Topparna i kommer växelvis från och . Låta ${\displaystyle G_{i))$ $M$ $N$ ${\displaystyle d(G_{i})=|E_{i}\cap N|-|E_{i}\cap M|\subset \{-1,0,1\))$

, men bara om är en utökad väg. och detta innebär att det måste finnas ett minimum av komponenter med och som en konsekvens kompletterande vägar. Enligt definitionen av anslutna komponenter kommer sådana komplementära vägar inte att skära varandra vid hörn. $d(G_{i})=1$ ${\displaystyle G_{i))$ $\sum _{i=1}^{g}d(G_{i})=|N\setminus M|-|M\setminus N|=|N|-|M|$ $|N|-|M|$ ${\displaystyle G_{i))$ $d(G_{i})=1$

Du kan hitta den kompletterande vägen så här:

Givet en tvådelad graf och en matchning . $G=(V,W,E)$ $M$
Skapa var $G'=(V\cup W,E'\cup E'')$
1. ${\displaystyle E'=\{(v,w)\mid \{v,w\}\in E\setminus M\land v\in V\land w\in W\))$
2. ${\displaystyle E''=\{(w,v)\mid \{v,w\}\in M\land v\in V\land w\in W\))$
Sökandet efter en komplementär väg reduceras till att söka från en fri vertex till en fri vertex . $G'$ $v\in V$ $w\in W$

Eftersom den utökade sökvägen kan hittas i DFS-tid är algoritmens körtid . Denna lösning är likvärdig med att lägga till en superkälla med kanter till alla hörn och en superstock med kanter från alla hörn (grafomvandlingen tar , och hitta det maximala flödet från till . Alla kanter som flyter från för att bilda en maximal matchning, och storleken av den största matchningen kommer att vara lika med Den tidsbaseradeHopcroft-Karps snabbare. Ett annat tillvägagångssätt är baserat på den snabba matrismultiplikationsalgoritmen och ger komplexitet [10] , vilket är bättre i teorin för tillräckligt täta grafer , men i praktiken Algoritmen är långsammare [11] $O(|E|)$ $O(|V||E|)$ $s$ $X$ $t$ $Y$ $O(n+m)$ $s$ $t$ $X$ $Y$ $O({\sqrt {V}}E)$ $O(V^{{2,376}})$

I en viktad tvådelad graf

I en viktad tvådelad graf tilldelas varje kant en vikt. En maximal viktmatchning i en tvådelad graf [9] definieras som en matchning för vilken summan av vikterna av matchningens kanter har ett maximalt värde. Om grafen inte är en fullständig tvådelad , läggs de saknade kanterna till med noll vikt. Problemet med att hitta en sådan matchning kallas uppdragsproblemet . Den anmärkningsvärda ungerska algoritmen löser tilldelningsproblemet och var en av de första kombinatoriska optimeringsalgoritmerna . Problemet kan lösas med en modifierad sökning av kortaste vägen i algoritmen för utökad väg. Om Bellman-Ford-algoritmen används kommer körtiden att vara , eller så kan priset på kanten flyttas för att nå tiden när Dijkstras algoritm tillämpas med en Fibonacci-hög [12] . [13] $O(V^{2}E)$ $O(V^{2}\log {V}+VE)$

Bästa matchningarna

Det finns en polynomtidsalgoritm för att hitta den största matchningen eller maximal viktmatchning i en icke-tvådelad graf. Efter Jack Edmonds kallas det för väg-, träd- och färgmetoden eller helt enkelt Edmonds matchningsalgoritm . Algoritmen använder dubbelriktade bågar . En generalisering av samma teknik kan användas för att hitta den maximala oberoende uppsättningen i grafer utan klor . Edmods algoritm förbättrades därefter till körtid , vilket motsvarar algoritmer för tvådelade grafer [14] . En annan (randomiserad) algoritm utvecklad av Mucha och Sankovsim (Mucha, Sankowski) [10] , baserad på den snabba produkten av matriser , ger komplexitet . $O(\sqrt{V}E)$ $O(V^{{2,376}})$

Maximalt antal matchningar

Den maximala matchningen kan hittas med en enkel girig algoritm . Den största maximala matchningen är den största matchningen som kan hittas i polynomtid. Implementering med pseudokod:

Givet räkning . $G=(V,E)$
Installera . $M=\emptyset$
Så länge setet inte är tomt: $E$
1. Välj . $e\in E$
2. Installera . ${\displaystyle M=M\cup \{e\))$
3. Installera . ${\displaystyle E=\{e'\in E\mid e'\cap e=\emptyset \))$
Ta fram . $M$

Emellertid är ingen polynom-tidsalgoritm känd för att hitta den minsta maximala matchningen , d.v.s. den maximala matchningen som innehåller minsta möjliga antal kanter.

Observera att den största matchningen av k kanter är en kantdominerande uppsättning med k kanter. Omvänt, givet en minimal kantdominerande mängd med k kanter, kan vi bygga den största matchningen med k kanter i polynomtid. Således är problemet med att hitta den minsta storleken för den maximala matchningen ekvivalent med problemet med att hitta den minsta kantdominerande uppsättningen [15] . Båda dessa optimeringsproblem är kända som NP-hard , och deras igenkänningsversioner är klassiska exempel på NP-kompletta problem [16] . Båda problemen kan approximeras med en faktor 2 med polynomtid - hitta bara ett godtyckligt maximalt matchande M [17] .

Uppräkningsuppgifter

Antalet matchningar i en graf kallas Hosoyya-index . Att beräkna detta nummer är #P-komplett . Problemet förblir #P-komplett i det speciella fallet att lista perfekta matchningar i en tvådelad graf , eftersom att beräkna permanenten för en slumpmässig 0-1-matris (ett annat #P-komplett problem) är detsamma som att beräkna antalet perfekta matchningar i en tvådelad graf med en given matris som en närliggande matris . Det finns emellertid ett randomiserat polynom-tidsapproximationsschema för att beräkna antalet matchningar i en tvådelad graf [18] . Ett underbart teorem från Casteleyn som säger att antalet perfekta matchningar i en plan graf kan beräknas exakt i polynomtid med FKT-algoritmen .

Antalet perfekta matchningar i en komplett graf K n (med jämnt n ) ges av dubbelfaktorialen ( n − 1)!! [19] . Antalet matchningar i en komplett graf utan begränsning, så att matchningen blir perfekt, ges av telefonnummer [20] .

Hitta alla kanter, matchande kanter

Ett av huvudproblemen i teorin om matchningar är att hitta alla kanter som kan utökas till den största matchningen. Den bästa deterministiska algoritmen för att lösa detta problem går i tid [21] . Det finns en randomiserad algoritm som löser problemet i tid [22] . I fallet med en tvådelad graf kan du hitta den största matchningen och använda den för att hitta alla maximalt matchande kanter i linjär tid [23] ; vilket kommer att resultera för allmänna tvådelade grafer och för täta tvådelade grafer med . Om en av de största matchningarna är känd i förväg [24] kommer den totala körtiden för algoritmen att vara . $O(VE)$ ${\tilde {O}}(V^{{2.376}})$ $O(V^{{1/2}}E)$ $O((V/\log V)^{{1/2}}E)$ $E=\Theta (V^{2})$ $O(V+E)$

Egenskaper och anmärkningar

Königs teorem säger att i tvådelade grafer är storleken på den största matchningen lika med storleken på det minsta vertextäcket . Av detta följer att för tvådelade grafer kan problemen med att hitta det minsta vertextäcket , den största oberoende uppsättningen och den maximala vertex biclique lösas i polynomtid .

Halls teorem (eller bröllopssatsen) ger en karakterisering av tvådelade grafer som har perfekt matchning, medan Tutts teorem ger en karakterisering av godtyckliga grafer.

En perfekt matchning genererar en sträckande 1-regelbunden subgraf, det vill säga en 1-faktor . I allmänhet är en spännande k -reguljär subgraf en k -faktor .

Applikationer

Kekules strukturformel för aromatiska föreningar består av perfekta matchningar av deras kolskelett , vilket visar placeringen av dubbelbindningarna i den kemiska strukturen . Dessa strukturer är uppkallade efter Friedrich August Kekule , som visade att bensen (i termer av grafteorin är det en cykel med 6 hörn) kan representeras som en sådan struktur [25] .

Hosoyya-indexet är antalet icke-tomma matchningar plus en. Det används i beräknings- och matematisk kemi för att studera organiska föreningar.

Se även

Anteckningar

↑ 1 2 Stanislav Okulov. Diskret matematik. Teori och praktik för problemlösning inom informatik. Studiehandledning . — Liter, 2014-02-07. - S. 186. - 428 sid. — ISBN 9785457534674 .
↑ Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, kapitel 5.
↑ Evstigneev V.A., Kasyanov V.N. Serieparallell poset // Dictionary of graphs in data science / Redigerad av prof. Viktor Nikolaevich Kasyanov. - Novosibirsk: LLC "Siberian Scientific Publishing House", 2009. - V. 17. - (Design och optimering av program). - ISBN 978-591124-036-3 .
↑ Fuad Aleskerov, Ella Khabina, Dmitry Schwartz. Binära relationer, grafer och kollektiva beslut . — Liter, 2016-01-28. - S. 22. - 343 sid. — ISBN 9785457966925 .
↑ Rubchinsky A. A. Diskreta matematiska modeller. Inledande koncept och standardproblem . — Directmedia, 2014-08-06. - S. 136. - 269 sid. — ISBN 9785445838029 .
↑ Leonid Gladkov, Vladimir Kureichik, Viktor Kureichik. Genetiska algoritmer . — Liter, 2016-01-28. - S. 276. - 367 sid. — ISBN 9785457965997 .
↑ Leonid Gladkov, Vladimir Kureichik, Viktor Kureichik, Pavel Sorokoletov. Bioinspirerade metoder inom optimering . — Liter, 2016-01-28. - S. 330. - 381 sid. — ISBN 9785457967472 .
↑ Tibor Gallai. Über extreme Punkt- und Kantenmengen // Ann. Univ. sci. Budapest. Eötvös Sect. Math.. - 1959. - Vol 2 . — s. 133–138 .
↑ 1 2 Douglas Brent West. Introduktion till grafteori. — 2:a. - Prentice Hall, 1999. - ISBN 0-13-014400-2 .
↑ 1 2 M. Mucha, P. Sankowski. Maximala matchningar via Gaussisk eliminering // Proc. 45:e IEEE Symp. Grunderna för datavetenskap . - 2004. - S. 248-255 .
↑ Bala G. Chandran, Dorit S. Hochbaum. Praktiska och teoretiska förbättringar för tvådelad matchning med hjälp av pseudoflödesalgoritmen . - 2011. - arXiv : 1105.1569 . .
↑ M. Fredman, R. Tarjan. Fibonacci-högar och deras användning i förbättrade nätverksoptimeringsalgoritmer // Journal of the ACM . - 1987. - T. 34 , nr. 3 . — S. 596–615 .
↑ Rainer Burkard, Mauro Dell'Amico, Silvano Martello. Uppdragsproblem . - Philadelphia: SIAM, Society for Industrial and Applied Mathematics, 2009. - s . 77-79 , 98. kapitel 4.1.3 Historiska anteckningar, böcker och undersökningar, kapitel 4.4.3 Effektiva implementeringar
↑ Silvio Micali, Vijay Vazirani. En algoritm för att hitta maximal matchning i allmänna grafer // Proc. 21:a IEEE Symp. Grunderna för datavetenskap . - 1980. - S. 17-27 . - doi : 10.1109/SFCS.1980.12 . $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$
↑ Yannakakis Mihalis, Gavril Fanica. Kantdominerande uppsättningar i grafer // SIAM Journal on Applied Mathematics. - 1980. - T. 38 , nr. 3 . — S. 364–372 . - doi : 10.1137/0138030 .
↑ Michael R. Garey, David S. Johnson. Datorer och svårhanterlighet: En guide till teorin om NP-fullständighet . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 . . Den kantdominerande mängden diskuteras i fallet med dominerande mängdproblem, Problem GT2 i bilaga A1.1. Minsta storlek maximal matchning är GT10-problemet i Bilaga A1.1.
↑ Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi. Komplexitet och approximation: kombinatoriska optimeringsproblem och deras approximationsegenskaper. — Springer, 2003. Den minsta dominerande kantuppsättningen är ett GT3-problem i Appendix B (sidan 370). Minsta storlek maximal matchning är uppgift GT10 i bilaga B (sidan 374). Se även Minimum Edge Dominating Set Arkiverad 5 september 2013 på Wayback Machine och Minimum Maximal Matching Arkiverad 6 mars 2014 på Wayback Machine på webbkompendiet Arkiverad 2 oktober 2013 på Wayback Machine .
↑ Ivona Bezáková, Daniel Štefankovič, Vijay V. Vazirani, Eric Vigoda. Accelerera simulerad glödgning för de permanenta och kombinatoriska räkneproblemen // SIAM Journal on Computing . - 2008. - T. 37 , nr. 5 . - S. 1429-1454 . - doi : 10.1137/050644033 .
↑ David Callan. En kombinatorisk undersökning av identiteter för dubbelfaktorial . - 2009. - arXiv : 0906.1317 .
↑ Extrema problem för topologiska index i kombinatorisk kemi // Journal of Computational Biology . - 2005. - T. 12 , nr. 7 . — S. 1004–1013 . - doi : 10.1089/cmb.2005.12.1004 .
↑ Marcelo H. de Carvalho, Joseph Cheriyan. En algoritm för öronupplösningar av matchande täckta grafer // Proc. ACM/SIAM Symposium on Discrete Algorithms (SODA). - 2005. - S. 415-423 . $O(VE)$
↑ Michael O. Rabin, Vijay V. Vazirani. Maximala matchningar i allmänna grafer genom randomisering // J. of Algorithms. - 1989. - T. 10 . — S. 557–567 .
↑ Tamir Tassa. Hitta alla maximalt matchbara kanter i en tvådelad graf // Teoretisk datavetenskap . - 2012. - T. 423 . — S. 50–58 . - doi : 10.1016/j.tcs.2011.12.071 .
↑ Aris Gionis, Arnon Mazza, Tamir Tassa. k -Anonymisering återbesökt // International Conference on Data Engineering (ICDE) . - 2008. - S. 744-753 .
↑ Se till exempel Nenad Trinajstić, Douglas J. Klein, Milan Randić. Om några lösta och olösta problem inom kemisk grafteori . - 1986. - T. 30 , nr. S20 . — S. 699–742 . - doi : 10.1002/qua.560300762 .

Läsning för vidare läsning

László Lovász, Michael D. Plummer. Matchande teori. - North-Holland, 1986. - ISBN 0-444-87916-1 .
Introduktion till algoritmer. — andra. - MIT Press och McGraw-Hill, 2001. - ISBN 0-262-53196-8 .

SJ Cyvin, Ivan Gutman. Kekule-strukturer i bensenoidkolväten. — Springer-Verlag, 1988.
Marek Karpinski, Wojciech Rytter. Snabba parallella algoritmer för grafmatchningsproblem . - Oxford University Press, 1998. - ISBN 978-0-19-850162-6 .

Länkar

Ett exempel på att lösa ett problem på YouTube Arkiverad 22 mars 2016 på Wayback Machine
En algoritm för att hitta den största matchningen i en tvådelad graf Arkiverad 7 januari 2012 på Wayback Machine
Ett grafbibliotek med Hopcroft-Karp och Push-Relabel-baserad implementering av maximal kardinalitetsmatchning Arkiverad 25 oktober 2005 på Wayback Machine