Grafic indiferent

Un graf indiferent este un graf nedirecționat construit prin atribuirea unui număr real fiecărui vârf și conectarea a două vârfuri cu o muchie atunci când numerele lor diferă cu cel mult unu [1] . Graficele indiferente sunt și grafice ale intersecțiilor unor seturi de segmente unitare sau intervale cu o anumită proprietate de încorporare (niciun interval nu conține altele). Pe baza acestor două tipuri de reprezentări pe intervale, aceste grafice sunt numite și grafice cu segmente unitare sau grafice cu intervale proprii . Graficele indiferente formează o subclasă de grafice cu intervale .

Descrieri echivalente

Graficele finite indiferente pot fi descrise în mod echivalent ca

Pentru grafice infinite, unele dintre aceste definiții pot fi date prin grafice diferite.

Proprietăți

Deoarece graficele indiferente sunt un caz special de grafice cu intervale , graficele indiferente au toate proprietățile graficelor cu intervale. În special, acestea sunt un caz special de grafuri de acorduri și grafuri perfecte . Aceste grafice sunt, de asemenea, un caz special de grafice circulare , ceea ce nu este adevărat pentru graficele cu intervale generale.

În modelul Erdős-Rényi al graficelor aleatoare, un grafic dintr-un vârf al cărui număr de muchii este substanțial mai mic va fi un grafic indiferent cu o probabilitate mare, în timp ce graficele cu un număr de muchii substanțial mai mare decât nu vor fi un grafic indiferent cu o probabilitate mare [9] .

Lățimea panglicii a unui graf arbitrareste cu o mai mică decât dimensiunea celei mai mari clicuri din graful indiferent care conțineca subgraf și este aleasă pentru a minimiza dimensiunea celei mai mari clicuri [10] . Această proprietate formează paralele, similare conexiunii dintre graficele de lățime de cale și interval și dintre graficele de lățime de arbore și de acord . O noțiune mai slabă de lățime, lățimea clicei , poate fi arbitrar mare pe grafice indiferente [11] . Totuși, orice subclasă adecvată de grafuri indiferente care nu este închisă în raport cu subgrafele generate are o lățime de clică mărginită [12] .

Orice graf indiferent conectat conține o cale hamiltoniană [13] . Un graf indiferent are un graf hamiltonian dacă și numai dacă este dublu conex [14] .

Graficele indiferente satisfac conjectura de reconstrucție — sunt definite în mod unic de subgrafele lor șterse de vârfuri [15] .

Algoritmi

Ca și în cazul graficelor cu disc unități multidimensionale , este posibil să se transforme un set de puncte în graficul lor indiferent sau un set de segmente unitare în graficul segmentului lor unitar în timp liniar , măsurat în funcție de dimensiunea graficului de ieșire. Algoritmul rotunjește punctele (sau centrele de intervale) la cel mai apropiat număr întreg mai mic, folosește un tabel hash pentru a găsi toate perechile de puncte ale căror valori rotunjite diferă cu cel mult unu ( problema cu rază fixă ​​cel mai apropiat vecin ) și selectează perechile în lista rezultată, ale cărei valori nerotunjite nu sunt mai mult de una [16] .

Se poate testa dacă un graf dat este indiferent în timp liniar folosind arbori PQ pentru a construi reprezentări pe intervale ale grafului și apoi se poate testa dacă ordonarea vârfurilor derivată din această reprezentare satisface proprietățile unui graf indiferent [4] . De asemenea, se poate baza algoritmul de recunoaștere pentru grafurile indiferente pe algoritmi de recunoaștere pentru graful cordal [14] . Unii algoritmi alternativi de recunoaștere liniară a timpului se bazează pe căutarea pe lățimea întâi sau pe căutarea lexicografică pe lățimea întâi , mai degrabă decât pe relația dintre graficele indiferente și graficele cu intervale [17] [18] [19] [20] .

Odată ce vârfurile sunt sortate după valorile lor numerice care descriu un grafic indiferent (sau după o succesiune de segmente unitare într-o reprezentare de interval), aceeași ordine poate fi folosită pentru a găsi colorarea optimă a acestor grafice pentru a rezolva problema drumului cel mai scurt. , construind căi hamiltoniene și cele mai mari potriviri în timp liniar [4] . Un ciclu hamiltonian poate fi găsit dintr-un grafic de reprezentare a intervalului adecvat în timp [13] , dar dacă graficul este o intrare la o problemă, aceeași problemă poate fi rezolvată în timp liniar, care poate fi generalizat la grafice cu intervale [21] [ 22] .

Colorarea prescrisă rămâne NP-completă chiar și atunci când este restrânsă la grafice indiferente [23] . Cu toate acestea, este fix-parametric rezolvabil dacă este parametrizat de numărul total de culori de intrare [12] .

Aplicații

În psihologia matematică , graficele indiferente apar din funcțiile de utilitate prin scalarea funcției astfel încât o unitate să reprezinte o diferență de utilitate suficient de mică încât unitatea să poată fi considerată nesemnificativă pentru individ. În această aplicație, perechile de elemente ale căror utilități sunt suficient de mari pot fi ordonate parțial după ordinea relativă a utilității, rezultând semi-ordinea [1] [24] .

În bioinformatică , sarcina de a adăuga un grafic colorat la un grafic colorat corect al segmentelor de unitate poate fi utilizată pentru a modela detectarea ansamblurilor de genom ADN fals negative din fragmente [25] .

Vezi și

Note

  1. ↑ 1 2 3 4 5 6 Roberts, 1969 , p. 139–146.
  2. ↑ 1 2 Bogart, Vest, 1999 , p. 21–23.
  3. ↑ Wegner, 1967 .
  4. ↑ 1 2 3 Looges, Olariu, 1993 , p. 15–25.
  5. ↑ Jackowski, 1992 , p. 103–109.
  6. ↑ 1 2 Gutierrez, Oubina, 1996 , p. 199–205.
  7. ↑ Mertzios, 2008 , p. 332–337.
  8. ↑ 1 2 Brandstädt, Hundt, Mancini, Wagner, 2010 , p. 897–910.
  9. ↑ Cohen, 1982 , p. 21–24.
  10. ↑ Kaplan, Shamir, 1996 , p. 540–561.
  11. ↑ Golumbic, Rotics, 1999 , p. 5–17.
  12. ↑ 1 2 Lozin, 2008 , p. 871–882.
  13. ↑ 1 2 Bertossi, 1983 , p. 97–101.
  14. ↑ 1 2 Panda, Das, 2003 , p. 153–161.
  15. ↑ von Rimscha, 1983 , p. 283–291.
  16. ↑ Bentley, Stanat, Williams, 1977 , p. 209–212.
  17. ↑ Corneil, Kim, Natarajan, Olariu, Sprague, 1995 , p. 99–104.
  18. ↑ Herrera de Figueiredo, Meidanis, Picinin de Mello, 1995 , p. 179–184.
  19. ↑ Cornel, 2004 , p. 371–379.
  20. ↑ Hell, Huang, 2004 , p. 554–570.
  21. ↑ Keil, 1985 , p. 201–206.
  22. ↑ Ibarra, 2009 , p. 1105–1108.
  23. ↑ Marx, 2006 , p. 995–1002.
  24. ↑ Roberts, 1970 , p. 243–258.
  25. ↑ Goldberg, Golumbic, Kaplan, Shamir, 2009 .

Literatură

Link -uri