Cesta zbarvení - Path coloring
v teorie grafů, cesta zbarvení obvykle odkazuje na jeden ze dvou problémů:
- Problém barvení a (multi) sada z cesty v grafu , takovým způsobem, že jakékoli dvě cesty které sdílejí výhodu v přijímat různé barvy. Soubor a graf jsou k dispozici na vstupu. Tato formulace je ekvivalentní s vrchol zbarvení the konfliktní graf sady , tj. graf se sadou vrcholů a hrany spojující všechny páry cest které nejsou vůči sobě disjunktní .
- Problém zbarvení (v souladu s výše uvedenou definicí) jakýkoli zvolený (multi) sada cest v , takže sada párů koncových vrcholů cest z se rovná nějaké sadě nebo multisetu , nazvaný a soubor požadavků. Soubor a graf jsou k dispozici na vstupu. Tento problém je zvláštním případem obecnější třídy problémů se směrováním grafů, známé jako plánování hovorů.
U obou výše uvedených problémů je obvykle cílem minimalizovat počet barev použitých při barvení. V různých variantách zbarvení cesty, může být a jednoduchý graf, digraf nebo multigraf.
Reference
- [1] Složitost zbarvení cesty a plánování hovorů Thomas Erlebach a Klaus Jansen
- [2] Kompendium problémů s optimalizací NP autor: Viggo Kann (problém: Minimum Path Coloring)
![]() | Tento kombinatorika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |