Perfektní shoda - Perfect matching

v teorie grafů, a perfektní shoda v grafu je a vhodný který pokrývá každý vrchol grafu. Více formálně, vzhledem k grafu G = (PROTI, E), perfektní shoda G je podmnožina M z E, takže každý vrchol v PROTI sousedí přesně s jednou hranou v M.

Dokonalé přizpůsobení se také nazývá a 1-faktor; vidět Faktorizace grafu pro vysvětlení tohoto pojmu. V některé literatuře tento termín kompletní shoda se používá.

Každá dokonalá shoda je a shoda maximální mohutnosti, ale opak není pravdou. Zvažte například následující grafy:^[1]

V grafu (b) je perfektní shoda (o velikosti 3), protože všech 6 vrcholů je spárováno; v grafech (a) a (c) existuje shoda maximální mohutnosti (velikosti 2), která není dokonalá, protože některé vrcholy jsou nesrovnatelné.

Dokonalá shoda je také minimální velikost okrajový kryt. Pokud existuje perfektní shoda, pak se shoduje jak číslo shody, tak číslo krytu hrany $| PROTI | / 2$ .

K dokonalé shodě může dojít pouze tehdy, když má graf sudý počet vrcholů. A téměř dokonalé shody je ten, ve kterém je přesně jeden vrchol neporovnatelný. K tomu může dojít, pouze pokud má graf liché číslo vrcholů a taková shoda musí být maximální. Na výše uvedeném obrázku ukazuje část (c) téměř dokonalé přizpůsobení. Pokud pro každý vrchol v grafu existuje téměř dokonalá shoda, která vynechá pouze tento vrchol, graf se také nazývá faktorově kritický.

Charakterizace

Hallova věta o manželství poskytuje charakteristiku bipartitních grafů, které se dokonale shodují.

The Tutteova věta poskytuje charakteristiku pro libovolné grafy.

Perfektní shoda je překlenutí 1-pravidelný podgraf, a.k.a. 1-faktor. Obecně platí, že překlenutí k-pravidelný podgraf je a k-faktor.

Výpočet

Rozhodnutí, zda graf připouští perfektní shodu, lze provést v polynomiální čas pomocí libovolného algoritmu pro nalezení a maximální shoda mohutnosti.

Počítám však počet perfektních shody, dokonce i v bipartitní grafy, je # P-kompletní. Je to proto, že výpočet trvalý libovolné matice 0–1 (další problém # P-kompletní) je stejný jako výpočet počtu dokonalých shody v bipartitním grafu, který má danou matici jako svoji biadjacency matice.

Pozoruhodná věta o Kasteleyn uvádí, že počet perfektních shody v a rovinný graf lze vypočítat přesně v polynomiálním čase pomocí Algoritmus FKT.

Počet perfektních shody v a kompletní graf K._n (s n sudý) je dán dvojitý faktoriál: ${ displaystyle (n-1) !!}$ ^[2]

Dokonale vyhovující mnohostěn

The dokonale sladěný polytop grafu je mnohostěn v R^{| E |} ve kterém je každý roh vektorem dopadu perfektní shody.

Viz také

Reference

^ Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, kapitola 5.
^ Callan, David (2009), Kombinatorický průzkum identit pro dvojitý faktoriál, arXiv:0906.1317, Bibcode:2009arXiv0906.1317C.

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

[2] Callan, David (2009), Kombinatorický průzkum identit pro dvojitý faktoriál, arXiv:0906.1317, Bibcode:2009arXiv0906.1317C.

[1]

[2]