Grafic de intervale

Un grafic de intervale  este un grafic al intersecțiilor unui set multiplu de intervale pe o dreaptă. Are câte un vârf pentru fiecare interval din mulțime și o muchie între fiecare pereche de vârfuri dacă intervalele corespunzătoare se intersectează.

Definiție

Fie  un set de intervale.

Graficul intervalului corespunzător este , unde

Din această construcție se pot obține proprietăți generale ale graficelor de intervale. Astfel, graficul G este interval dacă și numai dacă cele mai mari clicuri ale graficului G pot fi ordonate în așa fel încât pentru orice , unde , este valabil și pentru orice [1] .

Algoritmi eficienți de recunoaștere

Este posibil să se determine dacă un grafic este grafic de interval în timp ordonând cele mai mari clicuri ale graficului G .

Algoritmul original de recunoaștere a timpului liniar al lui Booth și Lueker ( Booth, Lueker 1976 ) se bazează pe o structură complexă de arbori PQ , dar Habib, McConnell, Paul și Viennot ( Habib, McConnell, Paul, Viennot 2000 ) au arătat cum să rezolve problema. problema mai simplu folosind căutarea lexicografică în lățime și bazată pe faptul că un grafic este un interval dacă și numai dacă este cordal și complementul său  este un grafic de comparabilitate [1] [2] .

Familii înrudite de grafice

Graficele de intervale sunt cordale și deci perfecte [1] [2] . Complementele lor aparțin clasei de grafice de comparabilitate [3] , iar relația de comparație este exact ordinul intervalului [1] .

Un grafic de intervale care are o reprezentare a intervalului în care oricare două intervale sunt fie disjunse, fie imbricate sunt grafice perfecte triviale .

Un grafic cu intervale regulate  este un grafic cu intervale care are o reprezentare a intervalului în care niciun interval nu este un subset propriu al oricărui alt interval. Graficele cu intervale unitare  sunt grafice cu intervale care au o reprezentare a intervalului în care fiecare interval are lungimea unitară. Orice grafic cu intervale regulate nu are gheare . Cu toate acestea, inversul nu este adevărat - un grafic fără gheare nu este neapărat un grafic cu intervale regulate [4] . Dacă mulțimea de segmente este o mulțime , adică repetarea segmentelor nu este permisă, atunci graficul este un grafic cu intervale unitare dacă și numai dacă este un grafic cu intervale regulate [5] .

Graficele de intersecție cu arc de cerc formează grafice cu arc de cerc , o clasă de grafice care conțin grafice cu intervale. Graficele trapezoidale , intersecția trapezelor, toate ale căror laturi paralele se află pe două drepte paralele, sunt o generalizare a graficelor de intervale.

Lățimea de cale a unui grafic cu intervale este cu o dimensiune mai mică decât dimensiunea clicei maxime (sau, echivalent, cu una mai mică decât numărul său cromatic), iar lățimea de cale a oricărui grafic G este egală cu cea mai mică lățime de cale a unui grafic de intervale care conține G ca subgraful [6] .

Graficele de intervale înrudite fără triunghiuri  sunt exact arbori de omizi [7] .

Grafic cu interval aleatoriu - un grafic cu intervale construit pe o familie aleatorie de segmente, de exemplu, segmentele vârfurilor segmentelor pot fi alese, de exemplu, prin distribuție naturală pe un segment unitar.

Aplicații

Teoria matematică a graficelor de intervale a fost dezvoltată cu ochii pe aplicațiile cercetătorilor din divizia de matematică a RAND Corporation , care includea tineri cercetători precum Peter Fishburne și studenți precum Alan Tucker și Joel Coen , nu numărând lideri precum Delbert Ray Fulkerson și (oaspete frecvent) Victor Klee [8] . Cohen a aplicat grafice de interval modelelor matematice ale populațiilor , în special lanțurilor trofice [9] .

Alte aplicații includ genetica, bioinformatica și informatica . Căutarea unui set de segmente reprezentând un grafic de interval poate fi folosită ca tehnică de asamblare a secvențelor continue în ADN [10] . Graficele cu intervale sunt utilizate în stabilirea problemelor de alocare a resurselor în cercetarea operațională și planificarea sarcinilor . Fiecare decalaj reprezintă o solicitare pentru o resursă pentru o anumită perioadă de timp. Problema găsirii unei mulțimi independente a greutății maxime a unui graf este problema găsirii celui mai bun subset de interogări care pot fi executate fără conflicte [11] .

Note

  1. ↑ 1 2 3 4 Fishburn, 1985 .
  2. ↑ 12 Golumbic , 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 și colab., 1994 .
  11. ↑ Bar-Noy, Bar-Yehuda, Freund, Naor, 2001 .

Literatură

Link -uri