Intervalový graf - Interval graph

Nesmí být zaměňována s Hypergraf D-intervalu.
Sedm intervalů na reálné přímce a odpovídající graf intervalu sedmi vrcholů.

v teorie grafů, an intervalový graf je neorientovaný graf vytvořený ze souboru intervaly na skutečná linie, s vrcholem pro každý interval a hranou mezi vrcholy, jejichž intervaly se protínají. To je průsečíkový graf intervalů.

Intervalové grafy jsou chordální grafy a perfektní grafy. Mohou být rozpoznáni v lineární čas a optimální zbarvení grafu nebo maximální klika v těchto grafech lze nalézt v lineárním čase. Intervalové grafy zahrnují všechny správné intervalové grafy, grafy definované stejným způsobem ze sady jednotkové intervaly.

Tyto grafy byly použity k modelování potravinářské weby a studovat plánování problémy, ve kterých je třeba vybrat podmnožinu úkolů, které mají být provedeny v nepřekrývajících se časech. Mezi další aplikace patří sestavování souvislých podsekcí v DNA mapování a časové uvažování.

Definice

Intervalový graf je neorientovaný graf G vytvořené z rodiny intervalů

Si, i = 0, 1, 2, ...

vytvořením jednoho vrcholu protii pro každý interval Sia spojením dvou vrcholů protii a protij o hranu, kdykoli mají odpovídající dvě sady neprázdnou křižovatku, tj. hranovou sadu G je

E(G) = {{protii, protij} | Si ∩ Sj ≠ ∅}.

Charakterizace

Tři vrcholy tvoří asteroid trojitý (AT) v grafu, pokud pro každé dva existuje cesta obsahující tyto dva, ale žádný soused třetího. Graf neobsahuje AT, pokud nemá asteroidní trojnásobek. Nejstarší charakterizace intervalových grafů se zdá být následující:

  • Graf je intervalový graf právě tehdy, když je akordický a bez AT.[1]

Další charakterizace:

  • Graf je intervalový graf právě tehdy, je-li maximální kliky lze objednat M1, M2, ..., Mk takový, že pro každého proti ∈ Mi ∩ Mk, kde i < k, je tomu také tak proti ∈ Mj pro všechny Mj, i ≤ j ≤ k.[2]
  • Graf je intervalový graf tehdy a jen tehdy, když lze okrajový klikový kryt všech jeho maximálních kliků uspořádat do reprezentace cesty kliky.[3]

Byly popsány různé další charakterizace intervalových grafů a variant.[5][6]

Efektivní algoritmus rozpoznávání

Určení, zda daný graf G = (V, E) je intervalový graf, ve kterém lze provádět Ó(|PROTI|+|E|) čas hledáním objednávky maxima kliky z G to je postupné s ohledem na začlenění vrcholů. Mnoho známých algoritmů pro tento problém funguje tímto způsobem, i když je také možné rozpoznat intervalové grafy v lineárním čase bez použití jejich klik (Hsu 1992 ).

Původní lineární algoritmus rozpoznávání času z Booth & Lueker (1976) je založen na jejich komplexu PQ strom datová struktura, ale Habib a kol. (2000) ukázal, jak vyřešit problém jednodušeji pomocí lexikografické vyhledávání na šířku, na základě skutečnosti, že graf je intervalový graf právě tehdy, když je akordický a jeho doplněk je srovnávací graf.[2][7]Podobný přístup využívající algoritmus LexBFS se šesti zatáčkami je popsán v Corneil, Olariu & Stewart (2009).

Související rodiny grafů

Charakterizací intervalových grafů jako akordické grafy bez AT,[1] intervalové grafy jsou silně chordální grafy a tudíž perfektní grafy.Jejich doplňuje patří do třídy srovnatelné grafy,[4] a srovnatelné vztahy jsou přesně ty intervalové objednávky.[2]

Na základě skutečnosti, že graf je intervalovým grafem, právě když je akordický a jeho doplněk je srovnávací graf, máme: Graf a jeho doplněk jsou intervalové grafy právě tehdy, je-li obojí a dělený graf a a permutační graf.

Intervalové grafy, které mají intervalovou reprezentaci, ve které jsou každé dva intervaly disjunktní nebo vnořené, jsou triviálně dokonalé grafy.

Graf má boxicita maximálně jeden právě tehdy, pokud se jedná o intervalový graf; boxicita libovolného grafu G je minimální počet intervalových grafů na stejné sadě vrcholů tak, že průsečík sad okrajů intervalových grafů je G.

Průnikové grafy oblouky a kruh formulář kruhové obloukové grafy, třída grafů, která obsahuje intervalové grafy. The lichoběžníkové grafy, průsečíky lichoběžníků, jejichž paralelní strany leží na stejných dvou paralelních liniích, jsou rovněž zobecněním intervalových grafů.

Připojený bez trojúhelníků intervalové grafy jsou přesně housenky.[8]

Správné intervalové grafy

Správné intervalové grafy jsou intervalové grafy, které mají intervalovou reprezentaci, ve které není žádný interval správně obsahuje jakýkoli jiný interval; grafy jednotkových intervalů jsou intervalové grafy, které mají intervalové vyjádření, ve kterém má každý interval jednotkovou délku. Reprezentace jednotkových intervalů bez opakovaných intervalů je nutně správná reprezentace intervalů. Ne každá správná reprezentace intervalů je reprezentací jednotkových intervalů, ale každý správný intervalový graf je grafem jednotkových intervalů a naopak.[9] Každý správný intervalový graf je a graf bez drápů; naopak, správné intervalové grafy jsou přesně intervalové grafy bez drápů. Existují však grafy bez drápů, které nejsou intervalovými grafy.[10]

Volá se intervalový graf q-vlastní, pokud existuje reprezentace, ve které žádný interval není obsažen více než q ostatní. Tato představa rozšiřuje myšlenku správných intervalových grafů tak, že 0-správný intervalový graf je správný intervalový graf.[11]

Nesprávné intervalové grafy

Volá se intervalový graf p- nesprávné, pokud existuje reprezentace, ve které žádný interval neobsahuje více než p ostatní. Tato představa rozšiřuje myšlenku správných intervalových grafů tak, že 0-nesprávný intervalový graf je správný intervalový graf.[12]

k-Vnořené intervalové grafy

Intervalový graf je k-hnízděno, pokud není řetězec délky k + 1 intervalů vnořených do sebe. Toto je zobecnění správných intervalových grafů, protože 1-vnořené intervalové grafy jsou přesně správné intervalové grafy.[13]

Aplikace

Matematická teorie intervalových grafů byla vyvinuta s ohledem na aplikace výzkumníků na RAND Corporation oddělení matematiky, které zahrnovalo mladé vědce - jako např Peter C. Fishburn a studenti mají rádi Alan C. Tucker a Joel E. Cohen — Kromě vůdců - jako např Delbert Fulkerson a (opakující se návštěvník) Victor Klee.[14] Cohen aplikoval intervalové grafy na matematické modely z populační biologie konkrétně potravinářské weby.[15]

Pro znázornění se používají intervalové grafy přidělení zdrojů problémy v operační výzkum a teorie plánování. V těchto aplikacích každý interval představuje požadavek na prostředek (například procesorovou jednotku distribuovaného výpočetního systému nebo místnost pro třídu) na určité časové období. Maximální hmotnost problém nezávislé množiny protože graf představuje problém nalezení nejlepší podmnožiny požadavků, které lze uspokojit bez konfliktů.[16]Optimální zbarvení grafu intervalového grafu představuje přiřazení zdrojů, které pokrývá všechny požadavky s co nejmenším počtem zdrojů; lze jej najít v polynomiální čas podle a chamtivé zbarvení algoritmus, který obarví intervaly v seřazeném pořadí podle jejich levých koncových bodů.[17]

Mezi další aplikace patří genetika, bioinformatika a informatika. Nalezení sady intervalů, které představují intervalový graf, lze také použít jako způsob sestavení souvislých subsekvencí v DNA mapování.[18] Intervalové grafy také hrají důležitou roli v časovém uvažování.[19]

Dokončení intervalu a šířka cesty

Li G je libovolný graf, dokončení intervalu z G je intervalový graf na stejné množině vrcholů, která obsahuje G jako podgraf. Parametrizovaná verze dokončení intervalu (vyhledejte intervalový supergraf s k další hrany) je pevně nastavitelný parametr, a navíc je řešitelný v parametrizovaném subexponenciálním čase.[20][21]

The šířka cesty intervalového grafu je o jednu menší než velikost jeho maximální kliky (nebo ekvivalentně o jednu menší než jeho chromatické číslo) a šířka každého grafu G je stejná jako nejmenší šířka cesty intervalového grafu, který obsahuje G jako podgraf.[22]

Poznámky

  1. ^ A b Lekkerkerker & Boland (1962)
  2. ^ A b C (Fishburn 1985 )
  3. ^ Fulkerson & Gross (1965)
  4. ^ A b Gilmore & Hoffman (1964)
  5. ^ McKee & McMorris (1999)
  6. ^ Brandstädt, Le & Spinrad (1999)
  7. ^ Golumbic (1980).
  8. ^ Eckhoff (1993).
  9. ^ Roberts (1969); Gardi (2007)
  10. ^ Faudree, Flandrin & Ryjáček (1997), str. 89.
  11. ^ Proskurowski, Andrzej; Telle, Jan Arne (1999). "Třídy grafů s modely s omezeným intervalem". Diskrétní matematika a teoretická informatika. 3 (4): 167–176. CiteSeerX  10.1.1.39.9532.
  12. ^ Beyerl, Jeffrey; Jamison, Robert (2008). Msgstr "Intervalové grafy s omezením omezení". Congressus Numerantium. 191 (2008): 117–128. arXiv:1109.6675. Bibcode:2011arXiv1109,6675B.
  13. ^ Klavík, Pavel; Otachi, Yota; Šejnoha, Jiří (14.10.2015). "O třídách intervalových grafů omezeného vnoření a počtu délek". arXiv:1510.03998 [cs.DM ].
  14. ^ Cohen (1978, str.ix – 10 )
  15. ^ Cohen (1978, str.12–33 )
  16. ^ Bar-Noy a kol. (2001).
  17. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Úvod do algoritmů (2. vyd.). MIT Press a McGraw-Hill. ISBN  0-262-03293-7.
  18. ^ Zhang a kol. (1994).
  19. ^ Golumbic & Shamir (1993).
  20. ^ Villanger a kol. (2009).
  21. ^ Bliznets et al. (2014).
  22. ^ Bodlaender (1998).

Reference

externí odkazy