Grafic de intervale

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Șapte intervale pe linia reală și graficul corespunzător al intervalului de șapte vârfuri.

În teoria graficelor , un grafic de interval este graficul de intersecție al unui multiset de intervale pe linia reală. Are un singur vârf pentru fiecare interval din set și o margine între fiecare pereche de vârfuri corespunzătoare intervalelor pe care le intersectează.

Definiție

Fie { I 1 , I 2 , ..., I n } ⊂ P ( R ) un set de intervale.

Graficul de interval corespunzător este G = ( V , E ), unde

  • V = { I 1 , I 2 , ..., I n }, e
  • { I α , I β } ∈ Și dacă și numai dacă I α ∩ I β ≠ ∅.

Din această construcție putem verifica o proprietate comună posedată de toate graficele de intervale. Adică, graficul G este un grafic de interval dacă și numai dacă fisurile maxime ale lui G pot fi plasate în ordinea M 1 , M 2 , ..., M k astfel încât pentru orice v ∈ M i ∩ M k , unde i < k , se mai întâmplă ca v ∈ M j pentru orice M j , i ≤ j ≤ k . [1]

Algoritmi de recunoaștere eficienți

Determinarea dacă un grafic dat G = (V, E) este un grafic de intervale se poate face în timp O (| V | + | E |) prin căutarea unei ordonări a fisurilor lui G care este consecutivă cu privire la includerea vârfurile.

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

Familii de grafice conexe

Graficele de intervale sunt grafice acorde și, prin urmare, grafice perfecte . [1] [2] Complementele lor aparțin clasei de grafice de comparabilitate , [3] iar relațiile de comparabilitate sunt tocmai ordinele de interval . [1]

Graficele de intervale care au o reprezentare a intervalului în care orice două intervale sunt fie disjuncte, fie imbricate sunt grafice trivial perfecte .

Graficele de interval adecvate sunt grafice de interval care au o reprezentare a intervalelor în care niciun interval nu conține în mod corespunzător alte intervale; graficele de intervale unitare sunt grafice de interval care au o reprezentare a intervalelor în care fiecare interval are lungimea unității. Fiecare grafic de interval adecvat este un grafic fără stele . Cu toate acestea, inversul nu este adevărat. Fiecare grafic fără stele nu este neapărat un grafic propriu. [4] Dacă colecția de segmente în cauză este un set , adică nu este permisă repetarea segmentelor, atunci graficul este un grafic de intervale unitare dacă și numai dacă este un grafic de interval adecvat. [5]

Graficele intersecției arcurilor unui cerc formând grafice cu arcuri circulare , o clasă de grafic care conține intervalul de grafice. Grafele trapezoidale , intersecțiile trapezoidelor ale căror laturi paralele se află pe aceleași două linii paralele, sunt, de asemenea, o generalizare a graficelor de interval.

Lățimea căilor unui grafic de intervale este dimensiunea fisurii sale maxime minus una (sau echivalent, numărul său cromatic minus unu), iar lățimea căilor oricărui grafic G este egală cu cea mai mică lățime a căilor unui grafic de interval care conține G ca subgraf. [6]

Graficele de interval conectate fără triunghiuri sunt exact copacii de milipede sau copacii "omizi". [7]

Aplicații

Teoria matematică a graficelor de intervale a fost dezvoltată cu o privire asupra aplicațiilor de către cercetătorii din departamentul de matematică al RAND Corporation , care a inclus tineri cercetători precum Peter C. Fishburn și studenți precum Alan C. Tucker și Joel E. Cohen , de asemenea. ca șefi de școală precum Delbert Fulkerson și (adesea în vizită) Victor Klee . [8] Cohen a aplicat grafice de intervale la modelele matematice ale biologiei populației , în special la rețelele alimentare . [9]

Alte aplicații includ genetică, bioinformatică și informatică. Găsirea unui set de intervale reprezentând un grafic de intervale poate fi, de asemenea, utilizat ca o modalitate de asamblare a subsecvențelor adiacente în maparea ADN-ului . [10] Graficele de intervale sunt utilizate pentru a reprezenta probleme de alocare a resurselor în cercetarea operațiunilor și teoria planificării . Fiecare interval reprezintă solicitarea unei resurse pentru o anumită perioadă de timp; problema setului independent cu cea mai mare pondere pentru grafic reprezintă problema găsirii celui mai bun subset de cereri care pot fi satisfăcute fără conflicte. [11] Graficele de intervale joacă, de asemenea, un rol important în raționamentul temporal. [12]

Notă

  1. ^ a b c d Fishburn (1985)
  2. ^ a b Golumbic (1980) .
  3. ^ Gilmore și Hoffman (1964)
  4. ^ Faudree, Flandrin și Ryjáček (1997) , p. 89.
  5. ^ Roberts (1969)
  6. ^ Bodlaender (1998) .
  7. ^ Eckhoff (1993) .
  8. ^ Cohen1978 , Cohen (1978)
  9. ^ Cohen1978 , Cohen (1978)
  10. ^ Zhang , Zhang, Schon, Fischer și Cayanis (1994) .
  11. ^ Bar-Noy , Bar-Noy, Bar-Yehuda, Freund & Naor (2001) .
  12. ^ Golumbic și Shamir (1993) .

Bibliografie

linkuri externe

Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă cu matematica
Adus de la „ https://it.wikipedia.org/w/index.php?title=Grafo_d%27intervallo&oldid=104516747 ”