Intervallum grafikon

Az intervallumgráf  egy vonalon lévő intervallumok több halmazának metszéspontjainak grafikonja . Van egy csúcsa a halmaz minden intervallumához, és egy éle az egyes csúcspárok között, ha a megfelelő intervallumok metszik egymást.

Definíció

Legyen  intervallumok halmaza.

A megfelelő intervallumgráf , ahol

Ebből a konstrukcióból az intervallumgráfok általános tulajdonságait kaphatjuk meg. Így a G gráf akkor és csak akkor intervallum, ha a G gráf legnagyobb klikkjei úgy rendezhetők , hogy bármely , ahol , bármely [1] -re is teljesüljön .

Hatékony felismerési algoritmusok

Meghatározható, hogy egy gráf időben intervallumgráf- e, ha a G gráf legnagyobb klikkjeit rendezzük .

Booth és Lueker eredeti lineáris időfelismerő algoritmusa ( Booth, Lueker 1976 ) PQ-fák összetett struktúráján alapul , de Habib, McConnell, Paul és Viennot ( Habib, McConnell, Paul, Viennot 2000 ) megmutatta, hogyan kell megoldani a probléma egyszerűbben, széleskörű lexikográfiai keresést használva és azon a tényen alapul, hogy egy gráf akkor és csak akkor intervallum, ha akkordális , és komplementere  egy összehasonlítási gráf [1] [2] .

Kapcsolódó grafikoncsaládok

Az intervallumgráfok akkordálisak , ezért tökéletesek [1] [2] . Komplementereik az összehasonlíthatósági gráfok osztályába tartoznak [3] , és az összehasonlítási reláció pontosan az intervallumsorrend [1] .

Az olyan intervallumgráf, amelynek intervallumábrázolása, amelyben bármely két intervallum diszjunkt vagy egymásba ágyazott, triviális tökéletes gráfok .

A szabályos intervallumgráf  olyan intervallumgráf, amelynek olyan intervallumábrázolása van, amelyben nincs intervallum megfelelő részhalmaza bármely más intervallumnak. Az egységintervallumgrafikonok  olyan intervallumgráfok, amelyeknek van egy intervallumábrázolása, amelyben minden intervallum egységnyi hosszúságú. Minden szabályos intervallumú gráfnak nincsenek karmai . Ennek az ellenkezője azonban nem igaz – a karmok nélküli gráf nem feltétlenül szabályos intervallumgráf [4] . Ha a szegmensek halmaza halmaz , azaz a szegmensek ismétlése nem megengedett, akkor a grafikon akkor és csak akkor egységintervallumgráf, ha szabályos intervallumgráf [5] .

A körív metszéspontú gráfok körív gráfokat alkotnak , az intervallumgráfokat tartalmazó gráfok osztályát. A trapézgráfok , amelyeknek mindegyik párhuzamos oldala két párhuzamos egyenesen van, az intervallumgráfok általánosítása.

Az intervallumgráf útvonala eggyel kisebb, mint a maximális klikk mérete (vagy ennek megfelelően eggyel kisebb, mint a kromatikus száma), és bármely G gráf útvonala egyenlő a G -t tartalmazó intervallumgráf legkisebb útvonalával. alpont [6] .

A háromszög nélküli kapcsolódó intervallumgráfok  pontosan hernyófák [7] .

Véletlenszerű intervallumgráf - szegmensek véletlenszerű családjára épülő intervallumgráf, például a szegmensek csúcsainak szegmensei kiválaszthatók például természetes eloszlás alapján egy egységszegmensen.

Alkalmazások

Az intervallumgráfok matematikai elméletét a RAND Corporation matematikai részlegének kutatóinak alkalmazásaira szem előtt tartva fejlesztették ki , amelybe olyan fiatal kutatók is beletartoztak, mint Peter Fishburne és olyan hallgatók, mint Alan Tucker és Joel Coen . számláló vezetők, mint Delbert Ray Fulkerson és (gyakori vendég) Victor Klee [8] . Cohen intervallumgráfokat alkalmazott populációk , különösen táplálékláncok matematikai modelljére [9] .

Egyéb alkalmazások közé tartozik a genetika, a bioinformatika és a számítástechnika . Az intervallumgráfot reprezentáló szegmenskészlet keresése a DNS -ben folytonos szekvenciák összeállításának módszereként használható [10] . Az intervallumgrafikonokat az erőforrás-allokációs problémák beállítására használják a műveletek kutatásában és a feladatütemezésben . Minden hiányosság egy adott időszakra vonatkozó erőforrás iránti kérelmet jelent. A gráf maximális súlyának független halmazának megtalálásának problémája az, hogy megtaláljuk a lekérdezések legjobb részhalmazát, amely ütközések nélkül végrehajtható [11] .

Jegyzetek

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

Irodalom

Linkek