Vrcholový kryt cyklu - Vertex cycle cover

V matematice, a vrcholový cyklus (běžně se nazývá jednoduše kryt cyklu) a graf G je sada cykly což jsou podgrafy z G a obsahují všechny vrcholy G.

Pokud cykly krytu nemají společné žádné vrcholy, je kryt vyvolán vrchol-disjunkt nebo někdy jednoduše disjunktní obal cyklu. Toto je někdy známé jako přesný vrcholový cyklus. V tomto případě sada cyklů představuje a překlenující podgraf z G. Disjunktní obal cyklu neorientovaného grafu (pokud existuje) lze najít v polynomiální čas transformací problému na problém hledání a perfektní shoda ve větším grafu.[1][2]

Pokud cykly krytu nemají společné hrany, je kryt vyvolán hrana disjunktní nebo jednoduše disjunktní obal cyklu.

Podobné definice existují pro digrafy, pokud jde o řízené cykly. Nalezení vrcholového-disjunktního cyklu pokrytí směrovaného grafu lze také provést v polynomiální čas podobným snížením na perfektní shoda[3]. Přidání podmínky, že každý cyklus by měl mít délku alespoň 3, však dělá problém NP-tvrdé[4].

Vlastnosti a aplikace

Trvalý

The trvalý a (0,1) -matice se rovná počtu vrcholů cyklů disjunktních cyklů a řízený graf s tím matice sousedství. Tato skutečnost se používá ve zjednodušeném důkazu, který ukazuje, že výpočet permanentní je # P-kompletní.[5]

Minimální disjunktní kryty cyklu

Problémy s nalezením vrcholů disjunktních a hranových disjunktních cyklů s minimálním počtem cyklů jsou NP-kompletní. Problémy nejsou třída složitosti APX. Varianty pro digrafy nejsou ani v APX.[6]

Viz také

Reference

  1. ^ David Eppstein. "Rozdělte graf na cykly uzel-disjunkt".
  2. ^ Tutte, W. T. (1954), „Krátký důkaz věty o faktorech pro konečné grafy“ (PDF), Kanadský žurnál matematiky, 6: 347–352, doi:10.4153 / CJM-1954-033-3, PAN  0063008.
  3. ^ https://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt (problém 1)
  4. ^ Garey a Johnson, Počítače a neřešitelnost, GT13
  5. ^ Ben-Dor, Amir a Halevi, Shai. (1993). "Nula jedna permanentní je #P-kompletní, jednodušší důkaz ". Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems, 108-117.
  6. ^ Složitost a aproximace: Problémy kombinatorické optimalizace a vlastnosti jejich přibližnosti (1999) ISBN  3-540-65431-3 378, 379, citovat Sahni, Sartaj; Gonzalez, Teofilo (1976), "P-úplné problémy s aproximací " (PDF), Deník ACM, 23 (3): 555–565, doi:10.1145/321958.321975, PAN  0408313..