Matchende

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. marts 2022; checks kræver 2 redigeringer .

I grafteori er et matchende , eller et uafhængigt sæt kanter i en graf, et sæt af parvise ikke-tilstødende kanter.

Definition

Lad en graf G = ( V , E ) være givet, en matchende M i G er et sæt af parvise ikke-tilstødende kanter, det vil sige kanter, der ikke har fælles hjørner, dvs. . $\forall e,f\in M:e\cap f=\emptyset$

Relaterede definitioner

En maksimal matchning er en matchende M i en graf G , som ikke er indeholdt i nogen anden matchning af denne graf, det vil sige, det er umuligt at tilføje en enkelt kant til den, som ikke støder op til alle kanter af matchningen. Med andre ord, en matchende M af en graf G er maksimal, hvis en kant i G har et ikke-tomt skæringspunkt med mindst én kant fra M . Nedenfor er eksempler på maksimale matchninger (røde kanter) i tre grafer [1] .

Den største matchning (eller maksimal størrelse matching [2] ) er den matchning, der indeholder det maksimale antal kanter. Det matchende nummer [3] af en graf er antallet af kanter i den største matchning. En graf kan have et sæt af største matchninger. Desuden er enhver største matching maksimal, men ikke noget maksimum vil være størst. De næste tre figurer viser de største matchninger i de samme tre kolonner [1] . $\nu (G)$ $G$

Nogle forfattere bruger udtrykket "maksimal matchning" for den største matchning [4] [5] [6] [7] .

En perfekt matchning (eller 1-faktor ) er en matchning, hvor alle hjørnerne af grafen deltager. Det vil sige, at ethvert toppunkt på grafen falder sammen med nøjagtig en kant, der er inkluderet i matchningen. Figur (b) i figuren ovenfor er et eksempel på en sådan matchning. Enhver perfekt matchning er størst og maksimal. Et perfekt match er også en kantbeklædning af minimumsstørrelsen. I det generelle tilfælde , hvor er grafens kantdækselnummer , med andre ord overstiger størrelsen af den største matchning ikke størrelsen af den mindste kantdæksel. $\nu (G)\leq \rho (G)$ $\rho (G)$ $G$

En næsten perfekt matchning er en matchning, hvor præcis et toppunkt ikke deltager. Dette kan ske, hvis grafen har et ulige antal hjørner. I figuren ovenfor er matchningen i kolonne (c) næsten perfekt. Hvis der for et hvilket som helst toppunkt i grafen er en næsten perfekt match, der ikke indeholder præcis dette toppunkt, kaldes grafen faktor kritisk .

Lad et matchende M blive givet .

en vekselbane er en sti, hvor kanterne skiftevis hører til matchningen og ikke hører til den.
en forøgende sti (eller forøgelsessti) er en vekslende sti, der starter og slutter med frie hjørner (dvs. ikke deltager i matchningen).

Berges lemma siger, at en matchning er maksimal, hvis og kun hvis der ikke er nogen komplementær vej.

Egenskaber

Antallet af perfekte matchninger i en todelt graf er lig med permanenten af dens tilstødende matrix .
I enhver graf uden isolerede hjørner summer antallet af matchninger og antallet af kantdækninger op til antallet af hjørner [8] .
- Især hvis der er en perfekt match, så er begge tal | v | / 2.

Hvis A og B er to maksimale matchninger, så | A | ≤ 2| b | og | b | ≤ 2| A |. For at se dette skal du bemærke, at hver kant fra B \ A kan parres med højst to kanter fra A \ B , da A er en matchende. Hver kant A \ B er dog konjugeret med kanten B \ A , da B er maksimal. Følgelig, $|A\setminus B|\leq 2|B\setminus A|$

Næste har vi

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

Dette indebærer især, at enhver maksimal matchning er en 2-tilnærmelse af den største matchning, såvel som en 2-tilnærmelse af den minimale maksimale matchning. Denne ulighed er nøjagtig. For eksempel, hvis G er en sti med 3 kanter og 4 hjørner, er minimumsstørrelsen af den maksimale matchning 1, og størrelsen af den største matchning er 2.

Polynomium af matchninger

Den genererende funktion af antallet af k -kantmatchninger i en graf kaldes matchende polynomium . Lad G være en graf og m k være antallet af k -kantmatchninger. Det matchende polynomium i grafen G er

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

Der er en anden definition af det matchende polynomium

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

hvor n er antallet af hjørner i grafen. Begge definitioner har deres egne anvendelsesområder.

Algoritmer og beregningsmæssig kompleksitet

Den største match i en todelt graf

Matchningsproblemer opstår ofte, når man arbejder med todelte grafer . At finde den største overensstemmelse i en todelt graf [9] er måske det enkleste problem. Udfyldningsstialgoritmen får det ved at finde udfyldningsstien fra hvert vertex ind og tilføje den til matchningen, hvis en sti er fundet. En alternativ løsning er, at matchningen vil blive suppleret, så længe der er udvidede komplementære stier: $G=(V=(X,Y),E)$ $x\i X$ $Y$

Installer . $M=\emptyset$
Mens der er udvidede genopfyldningsstier : $P$
1. $M=M\oplus E(P)$

En forstærkende sti er en sti i formen , som er sand for . En forøgelsessti kaldes en ekspanderende sti, hvis . $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: For enhver graf , matchende og færdiggørelsessti er matchende og gyldig . Bevis: Lad , og være den indledende toppunkt af , så og , og være den sidste toppunkt af , så at og , og være en mellemliggende toppunkt af , så . Det følger heraf, at der vil blive tilføjet en kant mere til grafen end fjernet fra 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: For enhver graf og matchninger , således at følgende er sandt: Grafen indeholder et minimum af færdiggørelsesstier, der ikke skærer hinanden ved hjørner i forhold til . Bevis: Lad og , mens virkelig og og dermed følger . Lad for de forbundne komponenter i grafen . Fra følger $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)\delsæt \{0,1,2\))$ $G_{i}=(V,E_{i})$ $1\leqslant i\leqslant g$ $H$ ${\displaystyle \delta (H)\delsæt \{0,1,2\))$

${\displaystyle G_{i))$ er et isoleret toppunkt eller
${\displaystyle G_{i))$ er en cyklus af lige længde, eller
${\displaystyle G_{i))$ er en sti af lige længde, eller
${\displaystyle G_{i))$ er en sti af ulige længde

Toppunkterne i kommer skiftevis fra og . Lade ${\displaystyle G_{i))$ $M$ $N$ ${\displaystyle d(G_{i})=|E_{i}\cap N|-|E_{i}\cap M|\subset \{-1,0,1\))$

, men kun hvis er en forstærkende sti. og det betyder, at der skal være et minimum af komponenter med og som følge heraf komplementære veje. Ifølge definitionen af forbundne komponenter vil sådanne komplementære stier ikke skære hinanden ved toppunkter. $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 finde den komplementære vej som denne:

Givet en todelt graf og en matchende . $G=(V,W,E)$ $M$
Opret hvor $G'=(V\kop W,E'\kop E'')$
1. ${\displaystyle E'=\{(v,w)\midt \{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øgningen efter en komplementær vej reduceres til at søge fra et frit toppunkt til et frit toppunkt . $G'$ $v\in V$ $w\in W$

Da forstærkningsstien kan findes i DFS-tid, er køretiden for algoritmen . Denne løsning svarer til at tilføje en superkilde med kanter til alle toppunkter og en superstock med kanter fra alle toppunkter (graftransformation vil tage , og finde det maksimale flow fra til . Alle kanter der flyder fra for at danne en maksimal matchning, og størrelsen af den største matching vil være lig med Den tidsbaseredeHopcroft-Karp hurtigere. En anden tilgang er baseret på den hurtige matrix multiplikationsalgoritme og giver kompleksitet [10] , hvilket er bedre i teorien for tilstrækkelig tætte grafer , men i praksis algoritmen er langsommere. [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 vægtet todelt graf

I en vægtet todelt graf tildeles hver kant en vægt. En maksimal vægtmatchning i en todelt graf [9] er defineret som en matchning, for hvilken summen af vægtene af matchningens kanter har en maksimal værdi. Hvis grafen ikke er en komplet todelt , tilføjes de manglende kanter med nul vægt. Problemet med at finde en sådan matching er kendt som opgaveproblemet . Den bemærkelsesværdige ungarske algoritme løser opgaveproblemet og var en af de første kombinatoriske optimeringsalgoritmer . Problemet kan løses ved hjælp af en modificeret søgning på den korteste vej i algoritmen for forøgelse af sti. Hvis Bellman-Ford-algoritmen bruges , vil køretiden være , eller prisen på kanten kan flyttes for at nå tidspunktet, når Dijkstras algoritme anvendes med en Fibonacci-heap [12] . [13] $O(V^{2}E)$ $O(V^{2}\log {V}+VE)$

Største matchninger

Der er en polynomiel tidsalgoritme til at finde den største matchende eller maksimale vægtmatchning i en ikke-todelt graf. Efter Jack Edmonds kaldes det sti-, træ- og farvemetoden eller blot Edmonds matchende algoritme . Algoritmen bruger tovejsbuer . En generalisering af den samme teknik kan bruges til at finde det maksimale uafhængige sæt i grafer uden kløer . Edmods' algoritme blev efterfølgende forbedret til køretid , hvilket svarer til algoritmer for todelte grafer [14] . En anden (randomiseret) algoritme udviklet af Mucha og Sankovsim (Mucha, Sankowski) [10] , baseret på det hurtige produkt af matricer , giver kompleksitet . $O(\sqrt{V}E)$ $O(V^{{2,376}})$

Maksimalt antal matchninger

Den maksimale matchning kan findes med en simpel grådig algoritme . Den største maksimale matchning er den største matchning, der kan findes i polynomisk tid. Implementering ved hjælp af pseudokode:

Givet tælle . $G=(V,E)$
Installer . $M=\emptyset$
Så længe sættet ikke er tomt: $E$
1. Vælg . $e\in E$
2. Installer . $M=M\cup \{e\}$
3. Installer . ${\displaystyle E=\{e'\in E\mid e'\cap e=\emptyset \))$
Tag ud . $M$

Imidlertid er der ingen polynomiel-tidsalgoritme kendt til at finde den mindste maksimale matchning , dvs. den maksimale matchning, der indeholder det mindst mulige antal kanter.

Bemærk, at den største matchning af k kanter er et kantdominerende sæt med k kanter. Omvendt, givet et minimalt kantdominerende sæt med k kanter, kan vi bygge den største matchning med k kanter i polynomisk tid. Problemet med at finde minimumsstørrelsen af den maksimale matchning svarer således til problemet med at finde det minimumskantdominerende sæt [15] . Begge disse optimeringsproblemer er kendt som NP-hard , og deres genkendelsesversioner er klassiske eksempler på NP-komplette problemer [16] . Begge problemer kan tilnærmes med en faktor 2 med polynomiel tid - find blot en vilkårlig maksimal matchende M [17] .

Optællingsopgaver

Antallet af matchninger i en graf er kendt som Hosoyya-indekset . Beregning af dette tal er #P-komplet . Problemet forbliver #P-komplet i det specielle tilfælde med at angive perfekte matchninger i en todelt graf , da beregning af permanenten af en tilfældig 0-1 matrix (et andet #P-komplet problem) er det samme som at beregne antallet af perfekte matchninger i en todelt graf med en given matrix som en tilstødende matrix . Der er dog et randomiseret polynomisk-tidstilnærmelsesskema til beregning af antallet af matchninger i en todelt graf [18] . En vidunderlig sætning fra Casteleyn om, at antallet af perfekte matchninger i en plan graf kan beregnes nøjagtigt i polynomisk tid ved hjælp af FKT-algoritmen .

Antallet af perfekte matchninger i en komplet graf K n (med lige n ) er givet ved dobbeltfaktoren ( n − 1)!! [19] . Antallet af matchninger i en komplet graf uden begrænsning, så matchningen er perfekt, er givet ved telefonnumre [20] .

Find alle kanter, matchende kanter

Et af hovedproblemerne i teorien om matchninger er at finde alle kanter, der kan udvides til den største matchning. Den bedste deterministiske algoritme til at løse dette problem kører i tid [21] . Der findes en randomiseret algoritme, der løser problemet i tide [22] . I tilfælde af en todelt graf kan du finde den største matchning og bruge den til at finde alle de maksimalt matchende kanter i lineær tid [23] ; hvilket vil resultere for generelle todelte grafer og for tætte todelte grafer med . Hvis en af de største matchninger er kendt på forhånd [24] , vil den samlede køretid for algoritmen være . $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)$

Karakteristika og bemærkninger

Königs sætning siger, at i todelte grafer er størrelsen af den største matchning lig med størrelsen af den mindste toppunktsdæksel . Heraf følger det, at for todelte grafer kan problemerne med at finde det mindste toppunktsdæksel , det største uafhængige sæt og det maksimale toppunkt biclique løses i polynomisk tid .

Halls teorem (eller bryllupssætning) giver en karakterisering af todelte grafer, der har perfekte matchninger, mens Tutts teorem giver en karakterisering af vilkårlige grafer.

En perfekt matchning genererer en spændende 1-regulær subgraf, det vil sige en 1-faktor . Generelt er en spændende k - regulær subgraf en k -faktor .

Ansøgninger

Kekules strukturformel for aromatiske forbindelser består af perfekte matchninger af deres kulstofskelet , der viser placeringen af dobbeltbindingerne i den kemiske struktur . Disse strukturer er opkaldt efter Friedrich August Kekule , som viste, at benzen (i form af grafteori er det en cyklus på 6 hjørner) kan repræsenteres som en sådan struktur [25] .

Hosoyya-indekset er antallet af ikke-tomme matchninger plus én. Det bruges i beregningsmæssig og matematisk kemi til at studere organiske forbindelser.

Se også

Noter

↑ 1 2 Stanislav Okulov. Diskret matematik. Teori og praksis for problemløsning i informatik. Studievejledning . — Liter, 2014-02-07. - S. 186. - 428 s. — ISBN 9785457534674 .
↑ Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, kapitel 5.
↑ Evstigneev V.A., Kasyanov V.N. Serie-parallel pose // Ordbog over grafer i datalogi / Redigeret af prof. Viktor Nikolaevich Kasyanov. - Novosibirsk: LLC "Siberian Scientific Publishing House", 2009. - V. 17. - (Design og optimering af programmer). - ISBN 978-591124-036-3 .
↑ Fuad Aleskerov, Ella Khabina, Dmitry Schwartz. Binære relationer, grafer og kollektive beslutninger . - Liter, 2016-01-28. - S. 22. - 343 s. — ISBN 9785457966925 .
↑ Rubchinsky A. A. Diskrete matematiske modeller. Indledende koncepter og standardproblemer . — Directmedia, 2014-08-06. - S. 136. - 269 s. — ISBN 9785445838029 .
↑ Leonid Gladkov, Vladimir Kureichik, Viktor Kureichik. Genetiske algoritmer . - Liter, 2016-01-28. - S. 276. - 367 s. — ISBN 9785457965997 .
↑ Leonid Gladkov, Vladimir Kureichik, Viktor Kureichik, Pavel Sorokoletov. Bioinspirerede metoder i optimering . - Liter, 2016-01-28. - S. 330. - 381 s. — ISBN 9785457967472 .
↑ Tibor Gallai. Über extreme Punkt- und Kantenmengen // Ann. Univ. sci. Budapest. Eötvös sekt. Math.. - 1959. - Vol . 2 . — s. 133–138 .
↑ 1 2 Douglas Brent West. Introduktion til grafteori. — 2. - Prentice Hall, 1999. - ISBN 0-13-014400-2 .
↑ 1 2 M. Mucha, P. Sankowski. Maksimale matchninger via Gaussisk eliminering // Proc. 45. IEEE Symp. Grundlaget for datalogi . - 2004. - S. 248-255 .
↑ Bala G. Chandran, Dorit S. Hochbaum. Praktiske og teoretiske forbedringer til bipartite-matchning ved hjælp af pseudoflow-algoritmen . - 2011. - arXiv : 1105.1569 . .
↑ M. Fredman, R. Tarjan. Fibonacci-dynger og deres anvendelser i forbedrede netværksoptimeringsalgoritmer // Journal of the ACM . - 1987. - T. 34 , no. 3 . — S. 596–615 .
↑ Rainer Burkard, Mauro Dell'Amico, Silvano Martello. Opgaveproblemer . - Philadelphia: SIAM, Society for Industrial and Applied Mathematics, 2009. - s . 77-79 , 98. kapitel 4.1.3 Historiske noter, bøger og undersøgelser, kapitel 4.4.3 Effektive implementeringer
↑ Silvio Micali, Vijay Vazirani. En algoritme til at finde maksimal matchning i generelle grafer // Proc. 21. IEEE Symp. Grundlaget for datalogi . - 1980. - S. 17-27 . - doi : 10.1109/SFCS.1980.12 . $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$
↑ Yannakakis Mihalis, Gavril Fanica. Kantdominerende sæt i grafer // SIAM Journal on Applied Mathematics. - 1980. - T. 38 , no. 3 . — S. 364–372 . - doi : 10.1137/0138030 .
↑ Michael R. Garey, David S. Johnson. Computere og intraktabilitet: En guide til teorien om NP-fuldstændighed . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 . . Det kantdominerende sæt er diskuteret i tilfælde af dominerende sæt problemer, opgave GT2 i bilag A1.1. Den mindste størrelse maksimale matchning er GT10-problemet i appendiks A1.1.
↑ Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi. Kompleksitet og tilnærmelse: kombinatoriske optimeringsproblemer og deres tilnærmelsesegenskaber. — Springer, 2003. Det mindste dominerende kantsæt er et GT3-problem i appendiks B (side 370). Minimum størrelse maksimal matchning er opgave GT10 i appendiks B (side 374). Se også Minimum Edge Dominating Set Arkiveret 5. september 2013 på Wayback Machine og Minimum Maximal Matching Arkiveret 6. marts 2014 på Wayback Machine på webkompendiet Arkiveret 2. oktober 2013 på Wayback Machine .
↑ Ivona Bezáková, Daniel Štefankovič, Vijay V. Vazirani, Eric Vigoda. Accelerering af simuleret annealing for de permanente og kombinatoriske tælleproblemer // SIAM Journal on Computing . - 2008. - T. 37 , no. 5 . - S. 1429-1454 . - doi : 10.1137/050644033 .
↑ David Callan. En kombinatorisk undersøgelse af identiteter for dobbeltfaktorialet . - 2009. - arXiv : 0906.1317 .
↑ Ekstreme problemer for topologiske indekser i kombinatorisk kemi // Journal of Computational Biology . - 2005. - T. 12 , no. 7 . — S. 1004–1013 . - doi : 10.1089/cmb.2005.12.1004 .
↑ Marcelo H. de Carvalho, Joseph Cheriyan. En algoritme til ørenedbrydning af matchende dækkede grafer // Proc. ACM/SIAM-symposium om diskrete algoritmer (SODA). - 2005. - S. 415-423 . $O(VE)$
↑ Michael O. Rabin, Vijay V. Vazirani. Maksimale matchninger i generelle grafer gennem randomisering // J. of Algorithms. - 1989. - T. 10 . — S. 557–567 .
↑ Tamir Tassa. Find alle maksimalt matchbare kanter i en todelt graf // Teoretisk datalogi . - 2012. - T. 423 . — S. 50–58 . - doi : 10.1016/j.tcs.2011.12.071 .
↑ Aris Gionis, Arnon Mazza, Tamir Tassa. k -Anonymisering genbesøgt // International Conference on Data Engineering (ICDE) . - 2008. - S. 744-753 .
↑ Se for eksempel Nenad Trinajstić, Douglas J. Klein, Milan Randić. På nogle løste og uløste problemer i kemisk grafteori . - 1986. - T. 30 , no. S20 . — S. 699–742 . - doi : 10.1002/qua.560300762 .

Læsning for yderligere læsning

László Lovász, Michael D. Plummer. Matchende teori. - Nord-Holland, 1986. - ISBN 0-444-87916-1 .
Introduktion til algoritmer. - sekund. - MIT Press og McGraw-Hill, 2001. - ISBN 0-262-53196-8 .

SJ Cyvin, Ivan Gutman. Kekule-strukturer i benzenoide kulbrinter. — Springer-Verlag, 1988.
Marek Karpinski, Wojciech Rytter. Hurtige parallelle algoritmer til problemer med grafmatchning . - Oxford University Press, 1998. - ISBN 978-0-19-850162-6 .