Toleranční graf - Tolerance graph

v teorie grafů, a toleranční graf je neorientovaný graf ve kterém každý vrchol může být reprezentován a uzavřený interval a reálné číslo se nazývá jeho tolerance, a to takovým způsobem, že v grafu sousedí dva vrcholy, kdykoli se jejich intervaly překrývají v délce, která je alespoň minimální z jejich dvou tolerancí.[1]Tuto třídu grafů představil v roce 1982 Martin Charles Golumbic a Clyde Monma, která je použila k modelování plánování problémy, při kterých mohou úkoly, které mají být modelovány, sdílet zdroje po omezenou dobu.[2]

Každý intervalový graf je graf tolerance.[3] The doplňkový graf každého grafu tolerance je a dokonale uspořádatelný graf, z čehož vyplývá, že samotné grafy tolerance jsou perfektní grafy.[4]

to je NP-kompletní k určení, zda je daný graf tolerančním grafem.[5]Protože jsou však toleranční grafy dokonalými grafy, mnoho algoritmických problémů, které jsou obtížné pro jiné třídy grafů, včetně zbarvení grafu a klika problém, lze vyřešit v polynomiální čas na grafech tolerance.[3]

Reference

  1. ^ Golumbic, Martin Charles; Trenk, Ann N. (2004), Toleranční grafy, Cambridge studia pokročilé matematiky, 89, Cambridge University Press, Cambridge, str. xii + 265, doi:10.1017 / CBO9780511542985, ISBN  0-521-82758-2, PAN  2051713
  2. ^ Golumbic, Martin C.; Monma, Clyde L. (1982), „Zobecnění intervalových grafů s tolerancemi“, Sborník ze třinácté jihovýchodní konference o kombinatorice, teorii grafů a výpočtech (Boca Raton, Fla., 1982), Congressus Numerantium, 35: 321–331, PAN  0725892
  3. ^ A b "Graphclass: tolerance", Informační systém o třídách grafů a jejich začlenění, vyvoláno 2019-09-30
  4. ^ Golumbic, Martin Charles; Monma, Clyde L .; Trotter, William T. Jr. (1984), "Toleranční grafy", Diskrétní aplikovaná matematika, 9 (2): 157–170, doi:10.1016 / 0166-218X (84) 90016-7, PAN  0761599
  5. ^ Mertzios, George B .; Sau, Ignasi; Zaks, Shmuel (2011), "Rozpoznání tolerančních a omezených tolerančních grafů" (PDF), SIAM Journal on Computing, 40 (5): 1234–1257, doi:10.1137/090780328, PAN  2854571