Kryt cesty - Path cover

Vzhledem k řízený graf G = (PROTI, E), a kryt cesty je sada směrované cesty tak, že každý vrchol proti ∈ PROTI patří alespoň k jedné cestě. Všimněte si, že kryt cesty může zahrnovat cesty délky 0 (jeden vrchol).[1]

A kryt cesty může také odkazovat na a vrcholový disjunktní kryt cesty, tj. soubor cest tak, že každý vrchol proti ∈ PROTI patří přesně jedna cesta.[2]

Vlastnosti

Věta Gallai a Milgram ukazuje, že počet cest v nejmenším krytu cesty nemůže být větší než počet vrcholů v největším nezávislá sada.[3] Zejména pro jakýkoli graf G, je kryt cesty P a nezávislý soubor Já takhle Já obsahuje přesně jeden vrchol z každé cesty v P. Dilworthova věta následkem tohoto výsledku.

Výpočetní složitost

Vzhledem k orientovanému grafu G, minimální krytí cesty problém spočívá v nalezení krytí cesty pro G mít nejméně cest.

Minimální kryt cesty sestává z jedné cesty právě tehdy, když existuje Hamiltonova cesta v G. The Problém hamiltonovské cesty je NP-kompletní, a proto je problém s minimálním pokrytím cesty NP-tvrdé. Pokud je však graf acyklický, problém je ve třídě složitosti P a lze jej tedy vyřešit v polynomiálním čase transformací do a vhodný problém.

Aplikace

Mezi aplikace krytů minimální cesty patří testování softwaru.[4] Například pokud graf G představuje všechny možné spouštěcí sekvence počítačového programu, pak je kryt cesty sada testovacích běhů, která pokrývá každý programový příkaz alespoň jednou.

Viz také

Poznámky

  1. ^ Diestel (2005), Oddíl 2.5.
  2. ^ Franzblau & Raychaudhuri (2002).
  3. ^ Diestel (2005), Věta 2.5.1.
  4. ^ Ntafos & Hakimi (1979)

Reference

  • Bang-Jensen, Jørgen; Gutin, Gregory (2006), Digrafy: Teorie, algoritmy a aplikace (1. vyd.), Springer.
  • Diestel, Reinhard (2005), Teorie grafů (3. vyd.), Springer.
  • Franzblau, D. S .; Raychaudhuri, A. (2002), „Optimální hamiltoniánské dokončení a kryty cest pro stromy a redukce na maximální průtok“, ANZIAM Journal, 44 (2): 193–204, doi:10.1017 / S1446181100013894.
  • Ntafos, S. C .; Hakimi, S. Louis. (1979), „On path cover problems in digraphs and applications to program testing“, Transakce IEEE v softwarovém inženýrství, 5 (5): 520–529, doi:10.1109 / TSE.1979.234213.