Faktorově kritický graf - Factor-critical graph

Faktorově kritický graf společně s perfektní párování subgrafů vytvořených odstraněním jednoho z jeho vrcholů.

v teorie grafů, matematická disciplína, a faktorově kritický graf (nebo hypomatchable graf[1][2]) je graf s n vrcholy, ve kterých každý podgraf z n − 1 vrcholy má a perfektní shoda. (Perfektní shoda v grafu je podmnožinou jeho okrajů s vlastností, že každý z jeho vrcholů je koncovým bodem přesně jedné z hran v podmnožině.)

Shoda, která pokrývá všechny vrcholy grafu kromě jednoho, se nazývá a téměř dokonalé shody. Ekvivalentně je faktorově kritický graf graf, ve kterém jsou téměř dokonalé shody, které se vyhýbají všem možným vrcholům.

Příklady

Tři grafy přátelství, příklady nehamiltonovských faktorově kritických grafů
The gyroelongated pentagonal pyramid, a bez drápů faktorově kritický graf

Jakákoli lichá délka graf cyklu je faktorově kritický,[1] jako každý jiný kompletní graf s lichým počtem vrcholů.[3] Obecněji, každý Hamiltonian graf s lichým počtem vrcholů je faktorově kritický. The grafy přátelství (grafy vytvořené spojením kolekce trojúhelníků v jediném společném vrcholu) poskytují příklady grafů, které jsou kritické z hlediska faktorů, ale nikoli Hamiltonovců.

Pokud graf G je faktorově kritický, pak také Mycielskian z G. Například Grötzschův graf, Mycielskian z pěti-vertex cyklu grafu, je faktorově kritický.[4]

Každý 2-vrchol připojený graf bez drápů s lichým počtem vrcholů je faktorově kritický. Například 11-vertexový graf vytvořený odstraněním vrcholu z pravidelný dvacetistěn (graf gyroelongated pentagonal pyramid ) je 2-propojený a bez drápů, takže je faktorově kritický. Tento výsledek vyplývá přímo ze zásadnější věty, že každý připojený graf bez drápů se sudým počtem vrcholů má perfektní shodu.[5]

Charakterizace

Faktorově kritické grafy lze charakterizovat několika různými způsoby, kromě jejich definice jako grafů, ve kterých každé odstranění vrcholů umožňuje perfektní shodu:

  • Tibor Gallai dokázal, že graf je faktorově kritický právě tehdy, když je připojeno a pro každý uzel proti grafu existuje a maximální shoda to nezahrnuje proti. Z těchto vlastností vyplývá, že graf musí mít lichý počet vrcholů a že každá maximální shoda musí odpovídat všem vrcholům kromě jednoho.[6]
  • László Lovász dokázal, že graf je faktorově kritický právě tehdy, má-li lichý rozklad ucha, rozdělení jeho okrajů do sekvence podgrafů, z nichž každý má lichou délku cesta nebo cyklus, přičemž první v sekvenci je cyklus, přičemž každá cesta v sekvenci má oba koncové body, ale žádné vnitřní body na vrcholech v předchozích podgrafech, a každý cyklus jiný než první v sekvenci má přesně jeden vrchol v předchozích podgrafech. Například graf na obrázku může být takto rozdělen na cyklus pěti hran a cestu tří hran. V případě, že je také uvedena téměř dokonalá shoda faktorově kritického grafu, lze zvolit rozklad ucha takovým způsobem, že každé ucho střídá spárované a nepřizpůsobené hrany.[7][8]
  • Graf je také faktorově kritický právě tehdy, pokud jej lze posloupností snížit na jediný vrchol kontrakce lichých cyklů. Kromě toho je v této charakterizaci možné zvolit každý cyklus v pořadí tak, aby obsahoval vrchol vytvořený kontrakcí předchozího cyklu.[1] Například, jestliže jeden stahuje uši rozkladu ucha, v pořadí daném rozkladem, pak v době, kdy je každé ucho kontrahováno, tvoří lichý cyklus, takže k nalezení posloupnosti lichých cyklů lze použít charakterizaci rozkladu ucha uzavřít smlouvu. Naopak ze sekvence lichých kontrakcí cyklu, z nichž každá obsahuje vrchol vytvořený z předchozí kontrakce, lze vytvořit rozklad ucha, ve kterém uši jsou sady okrajů smrštěných v každém kroku.
  • Předpokládejme, že graf G je dána spolu s výběrem vrcholu proti a odpovídající M který pokrývá všechny vrcholy jiné než proti. Pak G je faktorově kritický právě tehdy, pokud je v něm sada cest G, střídající se mezi shodnými a nepřizpůsobenými hranami, které se spojují proti ke každému z ostatních vrcholů v G. Na základě této vlastnosti je možné určit v lineární čas zda graf G s daným téměř dokonalým spojením je rozhodující faktor.[9]

Vlastnosti

Faktorově kritické grafy musí mít vždy lichý počet vrcholů a musí být 2-hrana připojena (to znamená, že nemohou mít žádné mosty ).[10] Nejsou však nutně 2-vrchol připojený; grafy přátelství poskytují protiklad. Není možné, aby faktorově kritický graf byl bipartitní, protože v bipartitním grafu s téměř dokonalým spojením jsou jedinými vrcholy, které lze odstranit, aby se vytvořil dokonale shodný graf, ty na větší straně bipartice.

Každý graf s kritickým faktorem spojeným se dvěma vrcholy m hran má alespoň m různé téměř dokonalé shody a obecněji každý kritický faktorový graf m hrany a C bloky (komponenty připojené ke 2 vrcholům) má alespoň m − C + 1 různé téměř dokonalé shody. Grafy, u nichž jsou tyto hranice těsné, lze charakterizovat tím, že mají liché ušní dekompozice určité formy.[3]

Libovolný připojený graf lze transformovat na faktorově kritický graf pomocí uzavírání smluv dostatečně mnoho z jeho okrajů. The minimální sady hran, které je třeba zkrátit, aby se vytvořil daný graf G faktorově kritické tvoří základy a matroid, skutečnost, z níž vyplývá, že a chamtivý algoritmus lze použít k nalezení sady minimální hmotnosti hran ke smrštění, aby byl graf faktorově kritický, v polynomiální čas.[11]

Aplikace

A květ je faktorově kritický podgraf většího grafu. Blossoms hrají klíčovou roli v Jack Edmonds ' algoritmy pro maximální shoda a perfektní shoda minimální hmotnosti v nebipartitních grafech.[12]

v polyedrická kombinatorika, faktorově důležité grafy hrají důležitou roli při popisu aspektů odpovídající mnohostěn daného grafu.[1][2]

Zobecnění a související pojmy

Říká se, že je graf k-faktor kritický, pokud každá podmnožina n − k vrcholy má perfektní shodu. Podle této definice je hypomatchovatelný graf kritický z 1 faktoru.[13] Ještě obecněji, graf je (A,b)-faktor kritický, pokud každá podmnožina n − k vrcholy má r-faktor, to znamená, že je to vrcholová množina r-pravidelný podgraf daného grafu.

A kritický graf (bez kvalifikace) se obvykle předpokládá, že znamená graf, u kterého odstranění každého z jeho vrcholů snižuje počet barev, které potřebuje v a zbarvení grafu. Koncept kritičnosti se v teorii grafů používá mnohem obecněji k označení grafů, u nichž odstranění všech možných vrcholů změní nebo nezmění některé relevantní vlastnosti grafu. A odpovídající kritický graf je graf, u kterého odstranění jakéhokoli vrcholu nemění velikost a maximální shoda; podle Gallaiho charakterizace jsou grafy kritické shody přesně grafy, ve kterých je každá připojená komponenta kritická.[14] The doplňkový graf kritického grafu je nutně shoda-kritická, což byla skutečnost, kterou Gallai použil k prokázání nižších mezí počtu vrcholů v kritickém grafu.[15]

Kromě teorie grafů byl koncept faktorové kritičnosti rozšířen na matroidy definováním typu rozkladu uší na matroidech a definováním matroidu jako kritického faktoru, pokud má rozklad ucha, ve kterém jsou všechny uši liché.[16]

Reference

  1. ^ A b C d Pulleyblank, W. R.; Edmonds, J. (1974), "Facets of 1-matching polyhedra", in Berge, C.; Ray-Chaudhuri, D. K. (eds.), Seminář o hypergrafiiPřednášky z matematiky, 411, Springer-Verlag, str. 214–242, doi:10.1007 / BFb0066196, ISBN  978-3-540-06846-4.
  2. ^ A b Cornuéjols, G.; Pulleyblank, W. R. (1983), „Kritické grafy, párování a prohlídky nebo hierarchie relaxací pro problém obchodního cestujícího“, Combinatorica, 3 (1): 35–52, doi:10.1007 / BF02579340, PAN  0716420.
  3. ^ A b Liu, Yan; Hao, Jianxiu (2002), „Výčet téměř dokonalých shody faktorově kritických grafů“, Diskrétní matematika, 243 (1–3): 259–266, doi:10.1016 / S0012-365X (01) 00204-7, PAN  1874747.
  4. ^ Došlić, Tomislav (2005), „Mycielskians and matchings“, Diskuse Mathematicae Graph Theory, 25 (3): 261–266, doi:10,7151 / dmgt.1279, PAN  2232992.
  5. ^ Favaron, Odile; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Rozšíření faktorové kritičnosti a shody v DCT grafech", Diskuse Mathematicae Graph Theory, 17 (2): 271–278, CiteSeerX  10.1.1.25.6314, doi:10,7151 / dmgt.1054, PAN  1627955.
  6. ^ Gallai, T. (1963), „Neuer Beweis eines Tutte'schen Satzes“, Magyar Tud. Akad. Rohož. Kutató Int. Közl., 8: 135–139, PAN  0166777. Jak uvádí Frank, András; Szegő, László (2002), „Poznámka k vzorci shody cesty“ (PDF), Journal of Graph Theory, 41 (2): 110–119, CiteSeerX  10.1.1.20.7918, doi:10,1002 / jgt.10055, PAN  1926313.
  7. ^ Lovász, L. (1972), „Poznámka o faktorově kritických grafech“, Studia Sci. Matematika. Hungar., 7: 279–280, PAN  0335371.
  8. ^ Korte, Bernhard H.; Vygen, Jens (2008), „10.4 Ear-Decompositions of Factor-Critical Graphs“, Kombinatorická optimalizace: Teorie a algoritmy Algoritmy a kombinatorika, 21 (4. vydání), Springer-Verlag, str. 235–241, ISBN  978-3-540-71843-7.
  9. ^ Lou, Dingjun; Rao, Dongning (2004), "Charakteristické faktory kritické grafy a algoritmus" (PDF), Australasian Journal of Combinatorics, 30: 51–56, PAN  2080453.
  10. ^ Seyffarth, Karen (1993), „Obaly a dvojité obaly dokonalých cest maximálních rovinných grafů“, Diskrétní matematika, 117 (1–3): 183–195, doi:10.1016 / 0012-365X (93) 90334-P, PAN  1226141.
  11. ^ Szigeti, Zoltán (1996), „Na matroidu definovaném ušními rozklady grafů“, Combinatorica, 16 (2): 233–241, doi:10.1007 / BF01844849, PAN  1401896. Dřívější algoritmus pro kontrakci minimálního počtu (nevážených) hran pro dosažení grafu kritického pro faktor viz Frank, András (1993), „Konzervativní vážení a ušní rozklady grafů“, Combinatorica, 13 (1): 65–81, doi:10.1007 / BF01202790, PAN  1221177.
  12. ^ Edmonds, Jacku (1965), „Cesty, stromy a květiny“, Kanadský žurnál matematiky, 17: 449–467, doi:10.4153 / CJM-1965-045-4, PAN  0177907.
  13. ^ Favaron, Odile (1996), "Na k-faktorově kritické grafy ", Diskuse Mathematicae Graph Theory, 16 (1): 41–51, doi:10,7151 / dmgt. 1022, PAN  1429805.
  14. ^ Erdős, P.; Füredi, Z.; Gould, R. J.; Gunderson, D. S. (1995), "Extrémní grafy pro protínající se trojúhelníky", Journal of Combinatorial Theory, Řada B, 64 (1): 89–100, doi:10.1006 / jctb.1995.1026, PAN  1328293.
  15. ^ Gallai, T. (1963b), „Kritische Graphen II“, Publ. Matematika. Inst. Hungar. Acad. Sci., 8: 373–395. Jak uvádí Stehlík, Matěj (2003), „Kritické grafy s připojenými doplňky“, Journal of Combinatorial Theory, Řada B, 89 (2): 189–194, doi:10.1016 / S0095-8956 (03) 00069-8, PAN  2017723.
  16. ^ Szegedy, Balázs; Szegedy, Christian (2006), „Symplectic spaces and ear-decomposition of matroids“, Combinatorica, 26 (3): 353–377, doi:10.1007 / s00493-006-0020-3, PAN  2246153.