Intervalový graf

Intervalový graf  je graf průsečíků více množin intervalů na přímce. Má jeden vrchol pro každý interval v množině a hranu mezi každou dvojicí vrcholů, pokud se odpovídající intervaly protínají.

Definice

Nechť  je množina intervalů.

Odpovídající intervalový graf je , kde

Z této konstrukce lze získat obecné vlastnosti intervalových grafů. Graf G je tedy intervalový právě tehdy, když největší kliky grafu G lze uspořádat tak, že pro any , kde , platí i pro libovolné [1] .

Efektivní rozpoznávací algoritmy

Je možné určit, zda je graf intervalovým grafem v čase seřazením největších klik grafu G .

Původní algoritmus lineárního rozpoznávání času Bootha a Luekera ( Booth, Lueker 1976 ) je založen na složité struktuře PQ stromů , ale Habib, McConnell, Paul a Viennot ( Habib, McConnell, Paul, Viennot 2000 ) ukázali, jak tento problém vyřešit. problém jednodušeji pomocí lexikografického vyhledávání do šířky a na základě skutečnosti, že graf je intervalový právě tehdy, je-li akordický a jeho doplňkem  je graf srovnatelnosti [1] [2] .

Související rodiny grafů

Intervalové grafy jsou chordální a tudíž dokonalé [1] [2] . Jejich doplňky patří do třídy grafů srovnatelnosti [3] a srovnávací relace je právě intervalového řádu [1] .

Intervalový graf, který má reprezentaci intervalu, ve které jsou libovolné dva intervaly buď disjunktní nebo vnořené, jsou triviální dokonalé grafy .

Pravidelný intervalový graf  je intervalový graf, který má intervalovou reprezentaci, ve které žádný interval není vlastní podmnožinou jakéhokoli jiného intervalu. Jednotkové intervalové grafy  jsou intervalové grafy, které mají intervalovou reprezentaci, ve které má každý interval jednotkovou délku. Žádný pravidelný intervalový graf nemá žádné drápy . Opak však není pravdou – graf bez drápů nemusí být nutně graf s pravidelným intervalem [4] . Pokud je množina segmentů množina , tj. opakování segmentů není povoleno, pak je graf jednotkovým intervalovým grafem právě tehdy, když se jedná o pravidelný intervalový graf [5] .

Kruhové obloukové průsečíkové grafy tvoří kruhové obloukové grafy, třídu grafů obsahující intervalové grafy. Lichoběžníkové grafy , průsečík lichoběžníků, jejichž všechny rovnoběžné strany leží na dvou rovnoběžných čarách, jsou zobecněním intervalových grafů.

Šířka dráhy intervalového grafu je o jednu menší než velikost maximální kliky (nebo ekvivalentně o jednu menší než její chromatické číslo) a šířka dráhy jakéhokoli grafu G je rovna nejmenší šířce dráhy intervalového grafu obsahujícího G jako a podbod [6] .

Související intervalové grafy bez trojúhelníků  jsou přesně housenkové stromy [7] .

Náhodný intervalový graf - intervalový graf vybudovaný na náhodné rodině segmentů, např. segmenty vrcholů segmentů lze volit např. přirozeným rozložením na jednotkovém segmentu.

Aplikace

Matematická teorie intervalových grafů byla vyvinuta s ohledem na aplikace výzkumníků v matematické divizi společnosti RAND Corporation , která zahrnovala mladé výzkumníky jako Peter Fishburne a studenty jako Alan Tucker a Joel Coen , nikoli počítací vůdci jako Delbert Ray Fulkerson a (častý host) Victor Klee [8] . Cohen aplikoval intervalové grafy na matematické modely populací , zejména potravních řetězců [9] .

Mezi další aplikace patří genetika, bioinformatika a informatika . Hledání sady segmentů reprezentujících intervalový graf může být použito jako technika pro sestavení spojitých sekvencí v DNA [10] . Intervalové grafy se používají při nastavování problémů s alokací zdrojů v operačním výzkumu a plánování úkolů . Každá mezera představuje požadavek na zdroj na určité časové období. Problém najít nezávislou množinu maximální váhy grafu je problém najít nejlepší podmnožinu dotazů, které lze provést bez konfliktů [11] .

Poznámky

  1. ↑ 1 2 3 4 Fishburn, 1985 .
  2. ↑ 12 Golumbic , 1980 .
  3. ↑ Gilmore, Hoffman, 1964 .
  4. ↑ Faudree, Flandrin, Ryjáček, 1997 , str. 89
  5. ↑ Roberts, 1969 .
  6. ↑ Bodlaender, 1998 .
  7. ↑ Eckhoff, 1993 .
  8. ↑ Cohen, 1978 ix-10
  9. ↑ Cohen, 1978 12-33
  10. ↑ Zhang a kol., 1994 .
  11. ↑ Bar-Noy, Bar-Yehuda, Freund, Naor, 2001 .

Literatura

Odkazy