Graficul arcului circular

În teoria grafurilor, un grafic al arcelor unui cerc este un grafic al intersecțiilor unui set de arce ale unui cerc . Graficul are un vârf pentru fiecare arc de cerc și o muchie între două vârfuri dacă arcurile corespunzătoare se intersectează.

Formal, să

- multe arcuri. Atunci graficul arcului de cerc corespunzător este G = ( V ,  E ), unde

și

Familia de arce corespunzătoare graficului G se numește modelul arcului .

Recunoaștere

Tooker [1] a găsit primul algoritm de recunoaștere a polinomilor pentru graficele cu arc circular care rulează în timp . Mai târziu, McConnell [2] a găsit primul algoritm de recunoaștere liniară în timp .

Relația cu alte clase de grafice

Graficele cu arc circular sunt o generalizare naturală a graficelor cu intervale . Dacă graficul arcului circular G are un model de arc care nu acoperă unele puncte de pe cerc, cercul poate fi rupt în acel punct și îndreptat într-un segment de linie, dând o reprezentare a intervalului. Totuși, spre deosebire de graficele cu intervale, graficele cu arc de cerc nu sunt întotdeauna perfecte , deoarece ciclurile impare fără coarde C 5 , C 7 etc. sunt grafice cu arc de cerc.

Unele subclase

Fie  mai jos un grafic arbitrar.

Grafice ale arcelor unitare ale unui cerc

este un grafic de arc de cerc unitar dacă există un model de arc în care toate arcele au aceeași lungime.

Grafice cu arc regulat

este un grafic cu arc de cerc obișnuit (sau un grafic cu interval de ciclu [3] ) dacă există un model de arc corespunzător în care niciun arc nu conține complet altul. Recunoașterea unor astfel de grafice și construirea unui model corect de arc se poate face în timp liniar . [patru]

Grafice cu arc circular Helly

este un grafic cu arc Helly circular dacă există un model de arc corespunzător astfel încât arcele să formeze o familie Helly . Gavril [5] oferă o descriere a acestei clase, din care urmează algoritmul de recunoaștere în timp .

Joris et al .[6] dau alte caracteristici (inclusiv enumerarea subgrafelor interzise generate) ale acestei clase, din care urmează un algoritm de recunoaștere care rulează în timp O(n+m) . Dacă graficul de intrare nu este un grafic cu arc Helly circular, atunci algoritmul returnează o confirmare a acestui fapt sub forma unui subgraf generat interzis. De asemenea, au oferit un algoritm pentru a determina dacă un model de arc circular dat formează o familie Helly în timp O(n) .

Aplicații

Graficele cu arc circular sunt utile în modelarea problemelor periodice de alocare a resurselor în cercetarea operațională . Fiecare interval reprezintă o solicitare pentru o anumită perioadă, care se repetă în timp.

Note

  1. ↑ Tucker, 1980 .
  2. ↑ McConnell, 2003 .
  3. ↑ Chudnovsky, Seymour, 2008 .
  4. ↑ Deng et al, 1996 .
  5. ↑ Gavril, 1974 .
  6. ↑ Joeris et al, 2009 .

Link -uri