Monochromatický trojúhelník - Monochromatic triangle

Oddíl okrajů kompletní graf K.5 do dvou podmnožin bez trojúhelníků

v teorie grafů a teoretická informatika, problém monochromatického trojúhelníku je algoritmický problém grafů, jehož cílem je rozdělit okraje daného grafu na dvě části bez trojúhelníků podgrafy. to je NP-kompletní ale fixovatelný parametr na grafech ohraničených šířka stromu.

Problémové prohlášení

Problém monochromatického trojúhelníku bere jako vstup n-uzel neorientovaného grafu G (V, E) s množinou uzlů V a hranou množiny E. Výstupem je logická hodnota, pravdivá, pokud lze hranovou množinu E z G rozdělit na dvě disjunktní množiny E1 a E2, takže oba dva podgrafy G1 (V, E1) a G2 (V, E2) jsou grafy bez trojúhelníků a jinak false. Tento rozhodovací problém je NP-kompletní.[1]

Zobecnění na více barev

Problém lze zobecnit na zbarvení hran bez trojúhelníků, nalezení přiřazení barev k okrajům grafu tak, aby žádný trojúhelník neměl všechny tři okraje dané stejnou barvou. Problém monochromatického trojúhelníku je speciální případ zbarvení okrajů bez trojúhelníků, když jsou k dispozici přesně dvě barvy. Pokud existuje zbarvení okrajů bez dvoubarevného trojúhelníku, pak okraje každé barvy tvoří dvě sady E1 a E2 úlohy monochromatického trojúhelníku. Naopak, pokud má problém s monochromatickým trojúhelníkem řešení, můžeme použít jednu barvu pro E1 a druhou barvu pro E2, abychom získali zbarvení hran bez trojúhelníků.

Spojení s Ramseyho teorémem

Podle Ramseyova věta, pro jakékoli konečné číslo k barev existuje řada n takové, že kompletní grafy n nebo více vrcholů nemá s barvami hran bez trojúhelníků k barvy. Pro k = 2, odpovídající hodnota n je 6. To znamená, že odpověď na problém monochromatického trojúhelníku na celém grafu K.6 není.

Parametrizovaná složitost

Je jednoduché vyjádřit problém monochromatického trojúhelníku v monadický druhého řádu logika grafů (MSO2), logickým vzorcem, který tvrdí existenci oddílu hran do dvou podmnožin tak, že neexistují tři vzájemně sousedící vrcholy, jejichž hrany všechny patří na stejnou stranu oddílu. Vyplývá to z Courcelleova věta že problém monochromatického trojúhelníku je fixovatelný parametr na grafech ohraničených šířka stromu. Přesněji řečeno, existuje algoritmus pro řešení problému, jehož doba běhu je počet vrcholů vstupního grafu vynásobený rychle rostoucí, ale vypočítatelnou funkcí šířky stromu.[2]

Reference

  1. ^ Garey, Michael R.; Johnson, David S. (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W. H. Freeman, ISBN  978-0-7167-1045-5. A1.1: GT6, s. 191.
  2. ^ Arnborg, Stefan; Lagergren, Jens; Seese, Detlef (1988), „Problémy snadné pro grafy rozložitelné na stromech (rozšířený abstrakt)“, Automaty, jazyky a programování (Tampere, 1988), Přednášky v informatice, 317, Berlín: Springer, s. 38–51, doi:10.1007/3-540-19488-6_105, PAN  1023625.