Yhteensopivuus

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 27. maaliskuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Graafiteoriassa yhteensopiva tai riippumaton joukko graafin reunoja on joukko pareittain ei-vierekkäisiä reunoja.

Määritelmä

Olkoon graafi G = ( V , E ), G : ssä vastaava M on joukko pareittain ei-vierekkäisiä reunoja, eli reunoja, joilla ei ole yhteisiä pisteitä, ts. . $\forall e,f\in M:e\cap f=\emptyset$

Aiheeseen liittyvät määritelmät

Maksimisovitus on graafin G vastaava M , joka ei sisälly mihinkään muuhun tämän graafin sovitukseen, eli siihen on mahdotonta lisätä yhtä reunaa, joka ei ole sovituksen kaikkien reunojen vieressä. Toisin sanoen graafin G vastaava M on maksimaalinen, jos jollakin G :n reunalla on ei-tyhjä leikkauspiste vähintään yhden M :n reunan kanssa . Alla on esimerkkejä enimmäissovituksista (punaiset reunat) kolmessa kaaviossa [1] .

Suurin yhteensopivuus (tai maksimikokosovitus [2] ) on sovitus, joka sisältää enimmäismäärän reunoja. Graafin täsmäytysluku [3] on reunojen lukumäärä suurimmassa sovituksessa. Kaaviolla voi olla joukko suurimpia vastaavuuksia. Lisäksi mikä tahansa suurin vastaavuus on suurin, mutta mikään maksimi ei ole suurin. Seuraavat kolme kuvaa osoittavat suurimmat vastaavuudet samoissa kolmessa sarakkeessa [1] . $\nu (G)$ $G$

Jotkut kirjoittajat käyttävät termiä "maksimi vastaavuus" suurimmasta vastaavuudesta [4] [5] [6] [7] .

Täydellinen sovitus (tai 1-tekijä ) on sovitus, jossa kaikki graafin kärjet osallistuvat. Toisin sanoen mikä tahansa graafin kärkikohta osuu täsmälleen yhteen sovitukseen sisältyvään reunaan. Yllä olevan kuvan kuva (b) on esimerkki tällaisesta sovituksesta. Mikä tahansa täydellinen vastaavuus on suurin ja maksimaalinen. Täydellinen yhteensopivuus on myös minimikokoinen reunapäällyste . Yleisessä tapauksessa missä on graafin reunakannen numero, eli suurimman vastaavuuden koko ei ylitä pienimmän reunapeitteen kokoa. $\nu (G)\leq \rho (G)$ $\rho (G)$ $G$

Lähes täydellinen vastaavuus on sovitus, jossa täsmälleen yksi kärki ei osallistu. Tämä voi tapahtua, jos graafissa on pariton määrä pisteitä. Yllä olevassa kuvassa sarakkeen (c) vastaavuus on lähes täydellinen. Jos jollakin graafin kärjellä on lähes täydellinen vastaavuus, joka ei sisällä täsmälleen tätä kärkeä, kuvaajaa kutsutaan tekijäkriittiseksi .

Olkoon vastaava M .

vuorotteleva polku on polku, jossa reunat vuorotellen kuuluvat sovitukseen ja eivät kuulu siihen.
augmenting polku (tai lisäyspolku) on vuorotteleva polku, joka alkaa ja päättyy vapaisiin pisteisiin (eli ei osallistu sovitukseen).

Bergen lemma sanoo, että yhteensopivuus on maksimaalinen silloin ja vain, jos ei ole täydentävää polkua.

Ominaisuudet

Täydellisten vastaavuuksien lukumäärä kaksiosaisessa graafissa on yhtä suuri kuin sen viereisyysmatriisin pysyvä .
Missä tahansa graafissa, jossa ei ole eristettyjä pisteitä, täsmäysten määrä ja reunapeiton määrä laskevat yhteen pisteiden lukumäärän [8] .
- Erityisesti, jos on täydellinen vastaavuus, niin molemmat numerot ovat | v | / 2.

Jos A ja B ovat kaksi maksimaalista vastaavuutta, niin | A | ≤ 2| b | ja | b | ≤ 2| A |. Nähdäksesi tämän huomaa, että jokainen B \ A reuna voidaan yhdistää enintään kahden A \ B :n reunaan, koska A on täsmäys. Jokainen reuna A \ B on kuitenkin konjugoitu reunaan B \ A , koska B on maksimi. Näin ollen $|A\setminus B|\leq 2|B\setminus A|$

Seuraavaksi meillä on

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

Erityisesti tämä tarkoittaa, että mikä tahansa maksimisovitus on 2-likimäärä suurimmasta vastaavuudesta sekä 2-likimäärä suurimmasta vähimmäissovituksesta. Tämä eriarvoisuus on tarkkaa. Jos G on esimerkiksi polku, jossa on 3 reunaa ja 4 kärkeä, enimmäissovituksen vähimmäiskoko on 1 ja suurimman vastaavuuden koko on 2.

Vastaavuuksien polynomi

Graafissa k -reunasovitusten määrän generoivaa funktiota kutsutaan sovituspolynomiksi . Olkoon G graafi ja m k k -reunasovitusten lukumäärä . Kuvaajan G sovituspolynomi on

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

Vastaavalle polynomille on toinenkin määritelmä

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

missä n on graafin kärkien lukumäärä. Molemmilla määritelmillä on omat käyttöalueet.

Algoritmit ja laskennallinen monimutkaisuus

Suurin vastaavuus kaksiosaisessa kaaviossa

Vastaavuusongelmia syntyy usein työskenneltäessä kaksiosaisten graafien kanssa . Suurimman vastaavuuden löytäminen kaksiosaisesta graafista [9] on ehkä yksinkertaisin ongelma. Täytepolun algoritmi saa sen etsimällä täytepolun jokaisesta kärjestä ja lisäämällä sen vastaavuuteen, jos polku löytyy. Vaihtoehtoinen ratkaisu on, että yhteensovitusta täydennetään niin kauan kuin on olemassa laajenevia täydentäviä polkuja: $G=(V=(X,Y),E)$ $x\in X$ $Y$

Asenna . $M=\emptyset$
Vaikka täydennyspolut laajenevat : $P$
1. $M=M\oplus E(P)$

Lisäävä polku on polku, jonka muoto on totta . Kasvavaa polkua kutsutaan laajenevaksi poluksi, jos . $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: Jokaiselle kuvaajalle , sovitus- ja täydennyspolulle vastaavuus ja on voimassa . Todistus: Antaa , Ja olla alkupiste , Niin ja , Ja olla viimeinen kärkipiste , Niin että ja , Ja olla välipiste , Niin . Tästä seuraa, että graafiin lisätään yksi reuna enemmän kuin siitä poistetaan. $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: Kaikille kuvaajan ja vastaavuuksia siten , että seuraava on totta: kaavio sisältää vähintään loppuun polkuja, jotka eivät leikkaa pisteissä suhteessa . Todiste: Antaa ja , kun taas todella ja ja näin seuraa . Olkoon kaavion yhdistetyille komponenteille . Seuraavilta _ $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\))$ ${\näyttötyyli \delta (H)\alajoukko \{0,1,2\))$ $G_{i}=(V,E_{i})$ $1\leqslant i\leqslant g$ $H$ ${\näyttötyyli \delta (H)\alajoukko \{0,1,2\))$

${\displaystyle G_{i))$ on eristetty kärkipiste tai
${\displaystyle G_{i))$ on tasapituinen sykli, tai
${\displaystyle G_{i))$ on parillisen pituinen polku tai
${\displaystyle G_{i))$ on parittoman pituinen polku

Vertices in tulevat vuorotellen ja . Päästää ${\displaystyle G_{i))$ $M$ $N$ ${\displaystyle d(G_{i})=|E_{i}\cap N|-|E_{i}\cap M|\subset \{-1,0,1\))$

, mutta vain jos se on lisäävä polku. ja tämä tarkoittaa, että komponentteja on oltava minimissään ja sen seurauksena täydentäviä polkuja. Yhdistettyjen komponenttien määritelmän mukaan tällaiset komplementaariset polut eivät leikkaa pisteissä. $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$

Löydät täydentävän polun seuraavasti:

Annettu kaksiosainen graafi ja vastaavuus . $G=(V,W,E)$ $M$
Luo missä $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\))$
Täydentävän polun haku rajoittuu etsimiseen vapaasta kärjestä vapaaseen kärkeen . $G'$ $v\in V$ $w\in W$

Koska lisäyspolku löytyy DFS-ajasta, algoritmin ajoaika on . Tämä ratkaisu vastaa superlähteen , jossa on reunat, lisäämistä kaikkiin kärkipisteisiin ja supervaraston , jossa on reunat kaikista pisteistä (kuvaajan muunnos kestää , ja maksimivirtauksen löytäminen kohteesta kohteeseen . Kaikki reunat, jotka virtaavat osoitteesta muodostavat maksimivastaavuuden, ja koko suurimmasta vastaavuudesta on yhtä suuri kuin aikapohjainenHopcroft-Karp nopeampi. Toinen lähestymistapa perustuu nopeaan matriisikerto -algoritmiin ja antaa monimutkaisuuden [10] , joka on teoriassa parempi riittävän tiheille kaavioille , mutta käytännössä algoritmi on hitaampi [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}})$

Painotetussa kaksiosaisessa graafissa

Painotetussa kaksiosaisessa graafissa jokaiselle reunalle on määritetty paino. Maksimipainosovitus kaksiosaisessa graafissa [9] määritellään vastaavuudeksi, jolle vastaavuuden reunojen painojen summalla on maksimiarvo. Jos graafi ei ole täydellinen kaksiosainen , puuttuvat reunat lisätään nollapainolla. Tällaisen vastaavuuden löytämisen ongelma tunnetaan määritysongelmana . Merkittävä unkarilainen algoritmi ratkaisee määritysongelman ja oli yksi ensimmäisistä kombinatorisista optimointialgoritmeista . Ongelma voidaan ratkaista käyttämällä modifioitua lyhimmän polun hakua lisäyspolun algoritmissa. Jos käytetään Bellman-Ford-algoritmia , ajoaika on , tai reunan hintaa voidaan siirtää sellaiseen aikaan, kun Dijkstran algoritmia käytetään Fibonacci-kasalla [12] . [13] $O(V^{2}E)$ $O(V^{2}\log {V}+VE)$

Parhaat vastaavuudet

On olemassa polynominen aika-algoritmi suurimman vastaavuuden tai maksimipainosovituksen löytämiseksi ei-kaksiosaisesta graafista. Jack Edmondsin mukaan sitä kutsutaan polku-, puu- ja värimenetelmäksi tai yksinkertaisesti Edmonds-sovitusalgoritmiksi . Algoritmi käyttää kaksisuuntaisia kaaria . Saman tekniikan yleistystä voidaan käyttää suurimman riippumattoman joukon löytämiseen kaavioissa ilman kynsiä . Edmodsin algoritmia parannettiin myöhemmin ajoajaksi , joka vastaa kaksiosaisten graafien algoritmeja [14] . Toinen Muchan ja Sankovsimin (Mucha, Sankowski) [10] kehittämä (satunnaistettu) algoritmi , joka perustuu matriisien nopeaan tuloon , antaa kompleksisuuden . $O(\sqrt{V}E)$ $O(V^{{2.376}})$

Vastaavia enimmäismääriä

Suurin vastaavuus löytyy yksinkertaisella ahneella algoritmilla . Suurin maksimisovitus on suurin polynomiajassa löydettävissä oleva vastaavuus. Toteutus pseudokoodilla:

Annettu määrä . $G=(V,E)$
Asenna . $M=\emptyset$
Niin kauan kuin sarja ei ole tyhjä: $E$
1. Valitse . $e\in E$
2. Asenna . ${\displaystyle M=M\cup \{e\))$
3. Asenna . ${\displaystyle E=\{e'\in E\mid e'\cap e=\emptyset \))$
Tuo esiin . $M$

Mitään polynomiaikaista algoritmia ei kuitenkaan tunneta, joka löytäisi pienimmän maksimisovituksen , eli maksimisovituksen, joka sisältää mahdollisimman pienen määrän reunoja.

Huomaa, että k reunan suurin vastaavuus on reunadominoiva joukko , jossa on k reunaa. Päinvastoin, kun otetaan huomioon minimaalinen reunadominoiva joukko, jossa on k reunaa, voimme rakentaa suurimman vastaavuuden k reunalla polynomiajassa. Siten ongelma suurimman sovituksen minimikoon löytämisessä vastaa ongelmaa minimireunadominoivan joukon löytämisessä [15] . Molemmat optimointiongelmat tunnetaan nimellä NP-hard , ja niiden tunnistusversiot ovat klassisia esimerkkejä NP-täydellisistä ongelmista [16] . Molemmat tehtävät voidaan approksimoida kertoimella 2 polynomisella ajalla - etsi vain mielivaltainen maksimi, joka vastaa M [17] .

Luettelotehtävät

Kaavion osumien lukumäärä tunnetaan Hosoyya-indeksinä . Tämän luvun laskeminen on #P-täydellinen . Ongelma pysyy #P-täydellisessä erikoistapauksessa täydellisten vastaavuuksien listaamisessa kaksiosaisessa graafissa , koska satunnaisen 0-1 matriisin pysyvän laskeminen (toinen #P-täydellinen tehtävä) on sama kuin täydellisten vastaavuuksien lukumäärän laskeminen kaksiosainen graafi, jossa on annettu matriisi vierekkäisyysmatriisina . On kuitenkin olemassa satunnaistettu polynomi-ajan approksimaatiomalli vastaavuuksien määrän laskemiseksi kaksiosaisessa graafissa [18] . Casteleynin upea lause , jonka mukaan täydellisten täsmäysten lukumäärä tasograafissa voidaan laskea tarkasti polynomiajassa FKT-algoritmin avulla .

Täydellisten vastaavuuksien lukumäärä täydellisessä graafissa K n (parillisella n ) saadaan kaksoistekijällä ( n − 1)!! [19] . Täydellisen kaavion täsmäysten määrä ilman rajoituksia, jotta täsmäys olisi täydellinen, annetaan puhelinnumeroilla [20] .

Kaikkien reunojen etsiminen, vastaavat reunat

Yksi sovitusteorian tärkeimmistä ongelmista on löytää kaikki reunat, jotka voidaan laajentaa suurimpaan yhteensovitukseen. Paras deterministinen algoritmi tämän ongelman ratkaisemiseksi toimii ajassa [21] . On olemassa satunnaistettu algoritmi, joka ratkaisee ongelman ajoissa [22] . Kaksiosaisen graafin tapauksessa voit löytää suurimman yhteensopivuuden ja käyttää sitä kaikkien maksimaalisten yhteensopivien reunojen etsimiseen lineaarisessa ajassa [23] ; mikä johtaa yleisille kaksiosaisille graafiille ja tiheille kaksiosaisille graafiille, joissa on . Jos yksi suurimmista vastaavuuksista tiedetään etukäteen [24] , algoritmin kokonaisajoaika on . $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)$

Ominaisuudet ja huomautukset

Königin lause sanoo, että kaksiosaisissa graafissa suurimman sovituksen koko on yhtä suuri kuin pienimmän kärjen peitteen koko . Tästä seuraa, että kaksiosaisten graafien osalta ongelmat pienimmän kärjen peitteen , suurimman itsenäisen joukon ja maksimipisteen kaksiklikkien löytämisessä voidaan ratkaista polynomiajassa .

Hallin teoreema (tai häälause) tarjoaa karakterisoinnin kaksiosaisille kaavioille, joilla on täydellinen yhteensopivuus, kun taas Tuttin lause tarjoaa mielivaltaisten graafien karakterisoinnin.

Täydellinen vastaavuus luo kattavan 1-säännöllisen aligraafin, eli 1-kertoimen . Yleensä kattava k -säännöllinen osagraafi on k - tekijä .

Sovellukset

Kekulen aromaattisten yhdisteiden rakennekaava koostuu niiden hiilirungon täydellisestä yhteensovittamisesta , mikä osoittaa kaksoissidosten sijainnin kemiallisessa rakenteessa . Nämä rakenteet on nimetty Friedrich August Kekulen mukaan, joka osoitti, että bentseeni (graafiteoriassa se on 6 kärjen sykli) voidaan esittää sellaisena rakenteena [25] .

Hosoyya-indeksi on ei-tyhjien osumien lukumäärä plus yksi. Sitä käytetään laskennallisessa ja matemaattisessa kemiassa orgaanisten yhdisteiden tutkimiseen.

Katso myös

Muistiinpanot

↑ 1 2 Stanislav Okulov. Diskreetti matematiikka. Informatiikan ongelmanratkaisun teoria ja käytäntö. Opinto-opas . - Litraa, 2014-02-07. - S. 186. - 428 s. — ISBN 9785457534674 .
↑ Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, luku 5.
↑ Evstigneev V.A., Kasyanov V.N. Sarja-rinnakkaisposetti // Tietojenkäsittelytieteen graafien sanakirja / Toimittanut prof. Viktor Nikolajevitš Kasjanov. - Novosibirsk: LLC "Siberian Scientific Publishing House", 2009. - V. 17. - (Ohjelmien suunnittelu ja optimointi). - ISBN 978-591124-036-3 .
↑ Fuad Aleskerov, Ella Khabina, Dmitry Schwartz. Binäärirelaatiot, kaaviot ja kollektiiviset päätökset . - Litraa, 28.1.2016. - S. 22. - 343 s. — ISBN 9785457966925 .
↑ Rubchinsky A. A. Diskreetit matemaattiset mallit. Alkukäsitteet ja standardiongelmat . — Directmedia, 2014-08-06. - S. 136. - 269 s. — ISBN 9785445838029 .
↑ Leonid Gladkov, Vladimir Kureichik, Viktor Kureichik. Geneettiset algoritmit . - Litraa, 28.1.2016. - S. 276. - 367 s. — ISBN 9785457965997 .
↑ Leonid Gladkov, Vladimir Kureichik, Viktor Kureichik, Pavel Sorokoletov. Bioinspiroidut menetelmät optimoinnissa . - Litraa, 28.1.2016. - S. 330. - 381 s. — 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. Johdatus graafiteoriaan. – 2. - Prentice Hall, 1999. - ISBN 0-13-014400-2 .
↑ 1 2 M. Mucha, P. Sankowski. Suurin mahdollinen vastaavuus Gaussin eliminoinnin kautta // Proc. 45. IEEE Symp. Tietojenkäsittelytieteen perusteet . - 2004. - S. 248-255 .
↑ Bala G. Chandran, Dorit S. Hochbaum. Käytännön ja teoreettisia parannuksia kaksiosaiseen sovitukseen käyttämällä pseudoflow-algoritmia . - 2011. - arXiv : 1105.1569 . .
↑ M. Fredman, R. Tarjan. Fibonacci-kasat ja niiden käyttö parannetuissa verkon optimointialgoritmeissa // Journal of the ACM . - 1987. - T. 34 , no. 3 . — S. 596–615 .
↑ Rainer Burkard, Mauro Dell'Amico, Silvano Martello. Tehtäväongelmat . - Philadelphia: SIAM, Society for Industrial and Applied Mathematics, 2009. - s . 77-79 , 98. luku 4.1.3 Historialliset muistiinpanot, kirjat ja tutkimukset, luku 4.4.3 Tehokkaat toteutukset
↑ Silvio Micali, Vijay Vazirani. Algoritmi maksimivastaavuuden löytämiseksi yleisistä kaavioista // Proc. 21. IEEE Symp. Tietojenkäsittelytieteen perusteet . - 1980. - S. 17-27 . - doi : 10.1109/SFCS.1980.12 . $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$
↑ Yannakakis Mihalis, Gavril Fanica. Reunaa hallitsevat joukot kaavioissa // SIAM Journal on Applied Mathematics. - 1980. - T. 38 , no. 3 . — S. 364–372 . - doi : 10.1137/0138030 .
↑ Michael R. Garey, David S. Johnson. Tietokoneet ja hallitsemattomuus: opas NP-täydellisyyden teoriaan . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 . . Reunadominoivaa joukkoa käsitellään hallitsevien joukkoongelmien tapauksessa, tehtävä GT2 liitteessä A1.1. Vähimmäiskoon maksimivastaavuus on GT10-ongelma liitteessä A1.1.
↑ Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi. Monimutkaisuus ja approksimaatio: kombinatorisen optimoinnin ongelmat ja niiden lähentävyysominaisuudet. — Springer, 2003. Vallitsevan reunan vähimmäisjoukko on GT3-ongelma liitteessä B (sivu 370). Vähimmäiskoon maksimivastaavuus on tehtävä GT10 liitteessä B (sivu 374). Katso myös Minimum Edge Dominating Set arkistoitu 5. syyskuuta 2013 Wayback Machinessa ja Minimum Maximal Matching Arkistoitu 6. maaliskuuta 2014 Wayback Machinessa verkkokokoelmassa Arkistoitu 2. lokakuuta 2013 Wayback Machinessa .
↑ Ivona Bezáková, Daniel Štefankovič, Vijay V. Vazirani, Eric Vigoda. Simuloidun hehkutuksen nopeuttaminen pysyviin ja kombinatorisiin laskentaongelmiin // SIAM Journal on Computing . - 2008. - T. 37 , no. 5 . - S. 1429-1454 . - doi : 10.1137/050644033 .
↑ David Callan. Kombinatorinen kartoitus kaksoisfaktoraalin identiteeteistä . - 2009. - arXiv : 0906.1317 .
↑ Äärimmäiset ongelmat topologisille indekseille kombinatorisessa kemiassa // 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. Algoritmi sovituspeitettyjen kaavioiden korvahajotuksiin // Proc . ACM/SIAM-symposium diskreetistä algoritmista (SODA). - 2005. - S. 415-423 . $O(VE)$
↑ Michael O. Rabin, Vijay V. Vazirani. Maksimivastaavuudet yleisissä kaavioissa satunnaistuksen kautta // J. of Algorithms. - 1989. - T. 10 . — S. 557–567 .
↑ Tamir Tassa. Kaikkien maksimaalisesti yhteensopivien reunojen etsiminen kaksiosaisesta graafista // Tietojenkäsittelyteoria . - 2012. - T. 423 . - S. 50-58 . - doi : 10.1016/j.tcs.2011.12.071 .
↑ Aris Gionis, Arnon Mazza, Tamir Tassa. k -Anonymisointi uudelleen // International Conference on Data Engineering (ICDE) . - 2008. - S. 744-753 .
↑ Katso esimerkiksi Nenad Trinajstić, Douglas J. Klein, Milan Randić. Joistakin kemiallisen graafiteorian ratkaistuista ja ratkaisemattomista ongelmista . - 1986. - T. 30 , no. S20 . — S. 699–742 . - doi : 10.1002/qua.560300762 .

Lue lisää lukemista varten

László Lovász, Michael D. Plummer. Vastaamisen teoria. - Pohjois-Hollanti, 1986. - ISBN 0-444-87916-1 .
Johdatus algoritmeihin. - toinen. - MIT Press ja McGraw-Hill, 2001. - ISBN 0-262-53196-8 .

SJ Cyvin, Ivan Gutman. Kekule-rakenteet bentseenoidihiilivedyissä. - Springer-Verlag, 1988.
Marek Karpinski, Wojciech Rytter. Nopeat rinnakkaisalgoritmit kaavioiden täsmäysongelmiin . - Oxford University Press, 1998. - ISBN 978-0-19-850162-6 .

Linkit

Esimerkki ongelman ratkaisemisesta YouTubessa , arkistoitu 22. maaliskuuta 2016 Wayback Machinella
Algoritmi suurimman vastaavuuden löytämiseksi kaksiosaisesta kaaviosta Arkistoitu 7. tammikuuta 2012 Wayback Machinessa
Kaaviokirjasto, jossa on Hopcroft-Karp- ja Push-Relabel-pohjainen maksimikardinaliteettisovitustoteutus Arkistoitu 25. lokakuuta 2005 Wayback Machinessa