Graficul trapezoidal

În teoria grafurilor, grafurile trapezoidale sunt grafuri de intersecție trapezoidală , toate ale căror laturi paralele se află pe două drepte. Această clasă de grafice este cuprinsă în clasa graficelor de cocomparabilitate și conține grafice de interval și grafice de permutare ca subclase. Graficul este trapezoidaldacă și numai dacă există o mulțime de trapeze corespunzătoare vârfurilor graficului, iar două vârfuri ale graficului sunt legate printr-o muchie dacă și numai dacă trapezele corespunzătoare vârfurilor se intersectează. Graficele trapezoidale au fost introduse în 1988 de Ido Dagan, Martin Charles Golumbic și Ron Pinter. Pentru aceste grafice, există algoritmi cu timp de rulare pentru colorarea graficului, pentru găsirea de seturi independente ponderate , acoperiri ale clicurilor și clicurilor ponderate maxime. ${O}(n\log n)$

Definiție și caracteristici

Să fie date două drepte paralele. Pe aceste drepte sunt definite trapeze, în care două vârfuri se află pe o linie, iar celelalte două se află pe cealaltă dreaptă. Un grafic este trapezoidal dacă și numai dacă există o mulțime de trapeze corespunzătoare vârfurilor graficului, iar două vârfuri ale graficului sunt conectate printr-o muchie dacă și numai dacă trapezele corespunzătoare vârfurilor se intersectează. Dimensiunea unei mulțimi parțial ordonate este cel mai mic număr d de ordine complete astfel încât . Un grafic de incompatibilitate cu poset este un grafic nedirecționat în care un vârf x este adiacent unui vârf y în G dacă și numai dacă x și y sunt incomparabile în P. Un grafic nedirecționat este un grafic trapez dacă și numai dacă este graficul de incomparabilitate al lui un set parțial ordonat cu dimensiunea de cel mult 2. [1] $P=(X,<)$ $P_{1}...P_{d)$ $P=P_{1}\cap ...\cap P_{d)$ $P=(X,<)$ $G=(X,E)$

Aplicații

Problemele de găsire a clicurilor maxime și colorarea graficelor trapezoidale sunt legate de problema așezării canalelor conductoare în proiectarea circuitelor integrate . Dacă unele puncte etichetate sunt setate pe părțile de sus și de jos ale plăcii, punctele cu aceleași etichete vor fi conectate la o rețea comună. Această rețea poate fi reprezentată printr-un trapez care conține puncte extreme (stânga și dreapta) cu aceeași etichetă. Plasele pot fi așezate fără încrucișare dacă și numai dacă trapezele nu se intersectează. Astfel, numărul de straturi necesare pentru așezarea conductoarelor fără intersecții este egal cu numărul cromatic al graficului.

Reprezentări echivalente

Reprezentare prin trapeze

Trapezele pot fi folosite pentru a reprezenta un grafic, pe baza definiției.

Reprezentare prin dreptunghiuri

Reprezentarea casetei dominante afișează punctele de pe o linie ca puncte de pe axa x și punctele de pe cealaltă linie ca puncte de pe axa y a planului euclidian. Atunci orice trapez corespunde unui dreptunghi în plan. În R K , se spune că x este dominat de y , care se scrie ca x < y dacă x i este mai mic decât y i pentru i = 1, …, k . Spunem că dreptunghiul b domină b' dacă colțul de jos al lui b domină colțul de sus al lui b' . Spunem că două dreptunghiuri sunt comparabile dacă unul îl domină pe celălalt. Astfel, două trapeze nu se intersectează exact atunci când dreptunghiurile lor corespunzătoare sunt comparabile. Reprezentarea casetei este utilă deoarece relația de dominanță permite aplicarea algoritmului de desfășurare [2] Reprezentarea graficului din figura 1 sub formă de dreptunghiuri este prezentată în figura 3.

Grafice bitolerante

Graficele bitolerante sunt grafice de incomparabilitate de ordin bitolerant. Se spune că o ordine este tolerantă la biți dacă și numai dacă există intervale I x și numere reale t 1 ( x ) și t r ( x ) atribuite fiecărui punct x în așa fel încât x < y dacă și numai dacă atunci când suprapunerea lui I x și I y este mai mică decât t r ( x ) și t 1 ( y ) iar mijlocul lui I x este mai mic decât mijlocul lui I y . [3] În 1993, Langley a arătat că grafurile bitolerante mărginite sunt echivalente cu clasa grafurilor trapezoidale. [patru]

Relația cu alte familii de grafice

Clasa de grafice trapezoidale conține grafice de interval și grafice de permutare și este echivalentă cu graficele de incomparabilitate ale unor seturi parțial ordonate de dimensiuni de ordin de cel mult două. Graficele de permutare pot fi privite ca un caz special de grafice trapezoidale dacă trapezele sunt reduse la linii (adică trapeze cu lungimi zero ale laturilor paralele).

Ca toate graficele de incomparabilitate, graficele trapezoidale sunt perfecte .

Grafice trapezoidale circulare

Graficele circulare trapezoidale sunt o clasă de grafice propuse de Felsner și colab., în 1993. Aceste grafice sunt o superclasă de grafice trapezoidale și conțin grafice circulare și grafice cu arc de cerc. Un trapez circular este regiunea unui cerc între două coarde care nu se intersectează, iar un grafic trapez circular este graficul de intersecție al familiei de trapeze circulare. O reprezentare circulară a graficului este prezentată în Figura 4. Există un algoritm cu timp de rulare pentru rezolvarea problemei găsirii unei mulțimi independente de greutate maximă și un algoritm cu timp de rulare pentru problema găsirii unei clici cu greutatea maximă. $O(n^{2})$ ${O}(n^{2}\log n)$

k -grafii trapezoidale

k - graficele trapezoidale este o generalizare a graficelor trapezoidale la dimensiuni mai mari ale spațiului. Ele au fost propuse de Felsner și se bazează pe definiția dreptunghiurilor multidimensionale dominante. În aceste grafice, vârful x corespunde vectorului . Folosind arbori de sortare ( k − 1) dimensionali pentru a stoca și a prelua coordonatele, algoritmii lui Felsner rezolvă problemele de găsire a numărului cromatic, clicei maxime și setului independent maxim în timp . $(x_{1},\ldots ,x_{k})$ ${O}(n\log ^{k-1}n)$

Algoritmi

Algoritmii pentru graficele trapezoidale ar trebui comparați cu algoritmii pentru graficele de cocomparabilitate mai generale. Pentru aceasta, o clasă mai largă de grafice, problemele de găsire a mulțimii independente maxime și a acoperirii clicei minime pot fi rezolvate în timp . [5] Dagan și colab. au propus mai întâi un algoritm pentru colorarea graficelor trapezoidale în timp , unde n este numărul de vârfuri și k este numărul cromatic al graficului. Mai târziu, folosind reprezentarea dreptunghiulară a graficelor trapezoidale, Felsner a publicat algoritmi pentru găsirea numărului cromatic, a setului independent ponderat, a acoperirii clicei și a clicului maxim ponderat în timp . Toți acești algoritmi necesită o dimensiune de memorie de . Acești algoritmi se bazează pe dominanța reprezentării prin dreptunghiuri, ceea ce permite utilizarea algoritmilor de despachetare. Algoritmii propuși de Felsner folosesc arbori echilibrați, care permit efectuarea în timp a operațiunilor de inserare, ștergere și interogare , ceea ce dă timpul rezultat . ${O}(n^{2}\log n)$ ${O}(nk)$ ${O}(n\log n)$ ${O}(n)$ ${O}(\log n)$ ${O}(n\log n)$

Recunoaștere

Pentru a determina dacă un grafic este trapezoidal, se caută o orientare tranzitivă pe complementul graficului . Deoarece graficele trapezoidale sunt un subset de grafice cocomparabile, dacă este trapezoidal, complementul său trebuie să fie un grafic de comparabilitate. Dacă nu există o orientare tranzitivă asupra complementului , graficul nu este trapezoidal. Dacă se găsește, se verifică dacă ordinea specificată de ordinea trapezoidală va fi. Cel mai rapid algoritm de recunoaștere keystone a fost propus de McConnell și Spinrad în 1994 cu durata de funcționare . Procesul reduce problema dimensiunii unei ordine parțiale (dacă depășește 2) la problema acoperirii grafului bipartit corespunzător cu lanțuri (grafice fără subgrafe 2K 2 generate ). [6] După cum arată Mertzios și Corneil, dacă se utilizează separarea vârfurilor, problema recunoașterii graficelor trapezoidale poate fi rezolvată în timp , unde denotă numărul de muchii. Acest proces folosește extinderea unui grafic dat și apoi transformarea graficului extins prin înlocuirea tuturor vârfurilor originale din grafic cu o pereche de vârfuri noi. Acest „graf divizat” este un grafic de permutare cu proprietăți speciale dacă și numai dacă este trapezoidal. [7] ${G}$ ${F}$ ${G}$ ${G}$ ${G')$ ${F}$ ${G')$ ${G}$ ${F}$ ${F}$ $O(n^{2})$ $O(n(n+m))$ $m$ ${G}$ ${G}$

Note

↑ Ido Dagan, Martin Charles Golumbic și Ron Yair Pinter. Grafice trapezoide și colorarea lor. Apple discret. Math., 35–46, 1988.
↑ Stefan Felsner, Rudolf Muller și Lorenz Wernisch. Grafice trapezoide și generalizări, geometrie și algoritmi. În Teoria algoritmului—SWAT '94 (Aarhus, 1994), volumul 824 din Note de curs în computer. Sci., paginile 143–154. Springer, Berlin, 1994.
↑ Kenneth P. Bogart, Garth Isaak. Ordine și grafice de bitolență proprie și unitare. Matematică discretă 181(1–3): 37–51 (1998).
↑ Martin Charles Golumbic și Irith B.-A. Hartman, eds., Teoria graficelor, combinatorică și algoritmi: aplicații interdisciplinare, Springer-Verlag, New York, 2005
↑ R. McConnel și J. Spinrad, Linear-time modular decomposition and efficient transitive orientation of undirected graphs, Proc. 5. Ann. Symp. pe Discr. Alg. (1994).
↑ Golumbic, Martin Charles. și Ann N. Trenk. Grafice de toleranță. Cambridge [ua: Cambridge University, 2004.
↑ G. B. Mertzios și D. G. Corneil. Divizarea vârfurilor și recunoașterea graficelor trapezoide. Matematică aplicată discretă, 159(11), paginile 1131-1147, 2011.

Link -uri

Martin Charles Golumbic. Teoria graficelor algoritmice și graficele perfecte. — Academic Press, 1980. Ediția a doua, Annals of Discrete Mathematics 57, Elsevier, 2004.