Grafic cerc

În teoria grafurilor, un graf cerc este un grafic al intersecțiilor setului de coarde ale unui cerc . Adică este un graf nedirecționat ale cărui vârfuri pot fi identificate cu acordurile cercului, iar aceste vârfuri sunt adiacente dacă și numai dacă acordurile corespunzătoare se intersectează.

Complexitate algoritmică

Spinrad [1] a prezentat un algoritm care rulează în timp O( n 2 ) care testează dacă un graf nedirecționat n -vertex dat este circular și, dacă este circular, construiește un set de acorduri care produc un graf circular.

Multe alte probleme care sunt NP-complete pe graficele generale au algoritmi de timp polinomial, dacă sunt limitate la graficele circulare. De exemplu, Klox [2] a arătat că lățimea arborelui unui grafic circular poate fi determinată și arborele de descompunere optim construit în timp O( n 3 ). În plus, cea mai mică înlocuire (adică un graf cordal cu cât mai puține muchii care conține ca subgraf graficul cerc dat) poate fi găsită în timpul O( n 3 ) [3] . Tiskin [4] a arătat că cea mai mare clică a unui grafic circular poate fi găsită în timpul O( n log 2 n ), iar Nash și Gregg [5] au arătat că cea mai mare mulțime independentă a unui grafic circular neponderat poate fi găsită în O( n min{ d , α }), unde d este un parametru de grafic cunoscut sub numele de densitate și α este numărul de independență al graficului circular .

Totuși, există probleme care rămân NP-complete , chiar și atunci când sunt limitate la grafice circulare. Aceste sarcini includ căutarea multimii dominante , a celui mai mic set dominant conectat și a celui mai mic set dominant total [6] .

Număr cromatic

Numărul cromatic al unui grafic circular este cel mai mic număr de culori care poate fi folosit pentru a colora acordurile astfel încât să nu aibă două acorduri care se intersectează să aibă aceeași culoare. Deoarece este posibil să se formeze un grafic circular în care un număr mare arbitrar de coarde se intersectează între ele, numărul cromatic al unui grafic circular poate fi arbitrar mare, iar determinarea numărului cromatic al unui grafic circular este o problemă NP-completă [8] ] . O problemă NP-completă este, de asemenea, verificarea dacă este posibil să colorați un grafic circular cu patru culori [9] . Unger [10] a susținut că căutarea unei colorări cu trei culori se poate face în timp polinomial , dar lipsesc multe detalii din descrierea rezultatelor sale [10] .

Unii autori au studiat problemele de colorare a subclaselor limitate de grafice circulare cu un număr mic de culori. În special, graficele circulare, în care nu există seturi de k sau mai multe acorduri, în care toate acordurile se intersectează, pot fi colorate fără a depăși culorile [11] . În special, pentru k  = 3 (adică pentru graficele cu cerc fără triunghi ), numărul cromatic nu depășește cinci, iar această limită este clară - toate graficele cu cerc fără triunghi pot fi colorate cu cinci culori și există triunghiuri -grafice circulare libere care necesită cinci culori pentru a colora [12] . Dacă un grafic circular are cel puțin cinci circumferințe (adică nu conține triunghiuri și cicluri cu patru vârfuri), acesta poate fi colorat folosind trei culori [ 13] . Problema colorării graficelor cu casete fără triunghiuri este echivalentă cu problema reprezentării graficelor cu casete ca un grafic izometric la un produs direct al copacilor . În această corespondență de probleme, numărul de culori din colorare corespunde numărului de arbori din produs [14] .

Aplicații

Graficele circulare apar în designul VLSI ca o abstractizare a unui caz special de rutare PCB cunoscut sub numele de „rutare de trecere a canalului bipolar”. În acest caz, zona de urmărire este un dreptunghi, toate rețelele sunt bipolare, iar cablurile sunt situate de-a lungul perimetrului dreptunghiului. Este ușor de observat că graficul de intersecție al acestei rețele este un grafic circular [15] . Unul dintre obiectivele rutării este de a se asigura că nu există contact electric între diferite rețele și că posibilele părți suprapuse ar trebui să se afle pe straturi diferite. Astfel, graficele circulare captează o parte din sarcinile de urmărire.

Colorarea graficelor circulare poate fi folosită și pentru a găsi o carte înglobare a graficelor arbitrare - dacă vârfurile unui grafic dat G sunt situate pe un cerc, iar marginile graficului G formează acordurile cercului, atunci graficul lui intersecțiile acestor acorduri este un grafic cerc, iar colorarea acestui grafic cerc este echivalent cu o încorporare de carte care păstrează aranjamentul cercului . În această echivalență, numărul de culori corespunde numărului de pagini din insertul de carte [16] .

Clase de grafice înrudite

Graficul de intersecție a unui set de intervale pe o dreaptă se numește grafic de intervale .

Un grafic este circular dacă și numai dacă este un grafic cu intervale regulate . Acestea sunt grafice ale căror vârfuri corespund unor segmente de linie (deschise), iar două vârfuri sunt conectate printr-o muchie dacă două intervale au o intersecție nevide. Cu toate acestea, niciun interval nu este complet cuprins într-un alt interval.

Graficele cu șiruri, graficele de intersecție ale curbelor în plan, includ grafice cu cerc ca caz special.

Orice grafic moștenit de distanță este un grafic circular, la fel ca orice permutare sau grafic indiferent . Orice graf exterior planar este de asemenea circular [17] [16] .

Note

  1. ↑ Spinrad, 1994 .
  2. ↑ Kloks, 1996 .
  3. ↑ Kloks, Kratsch, Wong, 1998 .
  4. ↑ Tiskin, 2010 .
  5. ↑ Nash, Gregg, 2010 .
  6. ↑ Keil, 1993 .
  7. ↑ Ageev, 1996 .
  8. ↑ Garey, Johnson, Miller, Papadimitriou, 1980 .
  9. ↑ Unger (1988) .
  10. ↑ 12 Unger , 1992 .
  11. ↑ Černý, 2007 . Pentru limitele anterioare, vezi Gyárfás, 1985 , Kostochka, 1988 și Kostochka, Kratochvíl, 1997 .
  12. ↑ Vezi Kostochka, 1988 pentru limita superioară și Ageev, 1996 pentru graficele care ating limita inferioară. Karapetyan ( Karapetyan 1984 ) și ( Gyárfás, Lehel 1985 ) au indicat anterior limite mai slabe pentru aceeași problemă.
  13. ↑ Ageev, 1999 .
  14. ↑ Bandelt, Chepoi, Eppstein, 2010 .
  15. ↑ Sherwani, 2000 .
  16. ↑ 12 Unger , 1988 .
  17. ↑ Wessel, Poschel, 1985 .

Literatură

Link -uri