Trapéz grafikon

A gráfelméletben a trapézgráfok trapézmetszetgráfok , amelyeknek mindegyik párhuzamos oldala két egyenesen fekszik. A gráfoknak ezt az osztályát az összehasonlíthatósági gráfok osztálya tartalmazza, és alosztályként intervallumgráfokat és permutációs gráfokat tartalmaz . A grafikon trapéz alakú akkor és csak akkor, ha létezik a gráf csúcsainak megfelelő trapézhalmaz, és a gráf két csúcsa akkor és csak akkor van összekötve éllel, ha a csúcsoknak megfelelő trapézek metszik egymást. A trapéz gráfokat 1988-ban vezette be Ido Dagan, Martin Charles Golumbic és Ron Pinter. Ezekhez a grafikonokhoz léteznek futási idővel rendelkező algoritmusok a grafikon színezésére, súlyozott független halmazok , klikklefedettségek és maximális súlyozott klikkek keresésére. ${O}(n\log n)$

Definíció és jellemzők

Legyen két párhuzamos egyenes. Ezeken az egyeneseken trapézokat határozunk meg, amelyekben két csúcs van az egyik egyenesen, a másik kettő pedig a másik egyenesen. Egy gráf akkor és csak akkor trapéz alakú , ha van a gráf csúcsainak megfelelő trapézhalmaz, és a gráf két csúcsa akkor és csak akkor van összekötve éllel, ha a csúcsoknak megfelelő trapézek metszik egymást. Egy részlegesen rendezett halmaz dimenziója a legkisebb számú d teljes rendelés úgy, hogy . A poszet inkompatibilitási gráf olyan irányítatlan gráf , amelyben egy x csúcs akkor és csak akkor szomszédos egy y csúcsgal G-ben, ha x és y össze nem hasonlítható P-ben. Az irányítatlan gráf akkor és csak akkor trapéz gráf, ha ez az összehasonlíthatatlansági gráf egy részben megrendelt készlet legfeljebb 2-es mérettel. [1] $P=(X,<)$ ${\displaystyle P_{1}...P_{d))$ ${\displaystyle P=P_{1}\cap ...\cap P_{d))$ $P=(X,<)$ $G=(X,E)$

Alkalmazások

A maximális klikkek megtalálásának és a trapézgráfok színezésének problémái az integrált áramkörök tervezésénél a vezető csatornák lefektetésének problémájához kapcsolódnak . Ha néhány címkézett pont van beállítva a tábla felső és alsó oldalán, akkor az azonos címkével ellátott pontok egy közös hálózathoz kapcsolódnak. Ez a hálózat egy trapézzel ábrázolható, amely szélső (bal és jobb) pontokat tartalmaz azonos címkével. A hálókat akkor és csak akkor lehet keresztezés nélkül lefektetni, ha a trapézok nem metszik egymást. Így a metszéspontok nélküli vezetékek lefektetéséhez szükséges rétegek száma megegyezik a gráf kromatikus számával.

Egyenértékű ábrázolások

Ábrázolás trapézokkal

A definíció alapján a trapézok használhatók egy gráf ábrázolására.

Téglalapokkal való ábrázolás

A domináns dobozábrázolás az euklideszi sík egyik vonalának pontjait az x tengely pontjaiként, a másik egyenes pontjait pedig az euklideszi sík y tengelyének pontjaként jeleníti meg . Ekkor bármely trapéz megfelel egy téglalapnak a síkban. R K -ban az x - et y uralja , amelyet x < y -ként írunk fel, ha x i kisebb, mint y i i = 1, …, k esetén . Azt mondjuk, hogy a b téglalap uralja b'-t, ha b alsó sarka uralja b ' felső sarkát . Azt mondjuk, hogy két téglalap összehasonlítható, ha az egyik uralja a másikat. Így két trapéz nem metszi egymást pontosan, ha a hozzájuk tartozó téglalapok összehasonlíthatók. A dobozábrázolás azért hasznos, mert a dominancia-reláció lehetővé teszi a kicsomagolási algoritmus alkalmazását [2] Az 1. ábra grafikonjának téglalap alakú ábrázolása a 3. ábrán látható.

Bitoleráns gráfok

A bittoleráns gráfok bittoleráns sorrendű összehasonlíthatatlansági gráfok. Egy sorrendet akkor és csak akkor mondunk bittűrőnek, ha minden x ponthoz I x intervallum és t 1 ( x ) és t r ( x ) valós számok vannak hozzárendelve úgy, hogy x < y akkor és csak akkor I x és I y átfedése kisebb, mint t r ( x ) és t 1 ( y ), I x közepe pedig kisebb, mint I y közepe . [3] 1993-ban Langley kimutatta, hogy a korlátos bitleráns gráfok egyenértékűek a trapézgráfok osztályával. [négy]

Kapcsolat más gráfcsaládokkal

A trapézgráfok osztálya intervallumgráfokat és permutációs gráfokat tartalmaz, és egyenértékű a legfeljebb kettő sorrendű, részben rendezett halmazok összehasonlíthatatlansági gráfjaival. A permutációs gráfok a trapézgráfok speciális esetének tekinthetők, ha a trapézokat egyenesekre redukáljuk (vagyis nulla párhuzamos oldalhosszúságú trapézokra).

Mint minden összehasonlíthatatlansági grafikon, a trapéz gráfok is tökéletesek .

Körkörös trapézgrafikonok

A kör alakú trapézgráfok a gráfok egy osztálya, amelyet Felsner és munkatársai javasoltak 1993-ban. Ezek a gráfok a trapézgráfok szuperosztályát képezik, és körgráfokat és körív gráfokat tartalmaznak. A kör alakú trapéz a kör tartománya két nem metsző húr között, a körtrapéz gráf pedig a körtrapézcsalád metszésgráfja. A grafikon körkörös ábrázolása a 4. ábrán látható. Létezik egy futási idővel rendelkező algoritmus a maximális súly független halmazának megoldására, és egy futási idővel rendelkező algoritmus a maximális súlyú klikk megtalálásának problémájára. $O(n^{2})$ ${O}(n^{2}\log n)$

k -trapéz gráfok

A k - trapézgráfok a trapézgráfok általánosítása a tér magasabb dimenzióira. Felsner javasolta, és a domináns többdimenziós téglalapok meghatározásán alapulnak. Ezekben a gráfokban az x csúcs a vektornak felel meg . A ( k − 1)-dimenziós rendezési fák segítségével a koordináták tárolására és lekérésére a Felsner-algoritmusok megoldják a kromatikus szám, a maximális klikk és a maximális független halmaz időben történő megtalálásának problémáját . $(x_{1},\ldots ,x_{k})$ ${O}(n\log ^{k-1}n)$

Algoritmusok

A trapéz gráfok algoritmusait össze kell hasonlítani az általánosabb összehasonlíthatósági gráfok algoritmusaival. Ehhez a gráfok szélesebb osztálya, a maximális független halmaz és a minimális klikkfedés megtalálásának problémája időben megoldható . [5] Dagan és munkatársai először javasoltak egy algoritmust a trapéz gráfok időben történő színezésére , ahol n a csúcsok száma, k pedig a gráf kromatikus száma. Később Felsner trapézgráfok téglalapábrázolásával algoritmusokat adott ki a kromatikus szám, a súlyozott független halmaz, a klikk lefedettség és a maximális súlyozott klikk időben történő megtalálására . Mindezek az algoritmusok memóriaméretet igényelnek . Ezek az algoritmusok a téglalapok általi ábrázolás dominanciáján alapulnak, ami lehetővé teszi a kicsomagoló algoritmusok használatát. A Felsner által javasolt algoritmusok kiegyensúlyozott fákat használnak, amelyek lehetővé teszik a beillesztési, törlési és lekérdezési műveletek időben történő végrehajtását , ami megadja az eredményül kapott időt . ${O}(n^{2}\log n)$ ${O}(nk)$ ${O}(n\log n)$ ${O}(n)$ ${O}(\log n)$ ${O}(n\log n)$

Elismerés

Annak meghatározásához, hogy egy gráf trapéz alakú-e, tranzitív orientációt kell keresni a gráf komplementerén . Mivel a trapéz gráfok az összehasonlítható gráfok egy részhalmaza, ha trapéz alakú, akkor komplementerének összehasonlíthatósági gráfnak kell lennie. Ha a komplementen nem létezik tranzitív orientáció , akkor a gráf nem trapéz alakú. Ha megtalálta, akkor ellenőrzi, hogy a trapézsorrend által megadott sorrend lesz-e. A leggyorsabb trapézkő felismerési algoritmust McConnell és Spinrad javasolták 1994-ben futási idővel . A folyamat a részleges sorrend dimenziójának kérdését (hogy meghaladja-e a 2-t) arra a problémára redukálja, hogy a megfelelő bipartit gráfot láncokkal lefedjük (2K 2 részgráfok nélküli gráfok). [6] Ahogy Mertzios és Corneil kimutatta, csúcsszétválasztás esetén a trapézgráfok felismerésének problémája időben megoldható , ahol az élek számát jelöli. Ez a folyamat egy adott gráf kibontását , majd a kiterjesztett gráf átalakítását használja úgy, hogy a gráf összes eredeti csúcsát egy pár új csúcsra cseréli. Ez a „felosztott gráf” akkor és csak akkor, ha trapéz alakú, speciális tulajdonságokkal rendelkező permutációs gráf. [7] ${G}$ ${F}$ ${G}$ ${G}$ ${\displaystyle {G'))$ ${F}$ ${\displaystyle {G'))$ ${G}$ ${F}$ ${F}$ $O(n^{2})$ $O(n(n+m))$ $m$ ${G}$ ${G}$

Jegyzetek

↑ Ido Dagan, Martin Charles Golumbic és Ron Yair Pinter. Trapéz grafikonok és színezésük. Diszkrét Apple. Math., 35–46, 1988.
↑ Stefan Felsner, Rudolf Muller és Lorenz Wernisch. Trapézgráfok és általánosítások, geometria és algoritmusok. Az Algoritmuselméletben – SWAT '94 (Aarhus, 1994), a Lecture Notes in Comput 824. kötete. Sci., 143–154. Springer, Berlin, 1994.
↑ Kenneth P. Bogart, Garth Isaak. Helyes és egységnyi bittolerancia-sorrendek és grafikonok. Discrete Mathematics 181 (1–3): 37–51 (1998).
↑ Martin Charles Golumbic és Irith B.-A. Hartman, szerk., Graph Theory, Combinatorics and Algorithms: Interdiszciplináris alkalmazások, Springer-Verlag, New York, 2005
↑ R. McConnel és J. Spinrad, Lineáris idejű moduláris dekompozíció és irányítatlan gráfok hatékony tranzitív orientációja, Proc. 5. Ann. Symp. a Discr. Alg. (1994).
↑ Golumbic, Martin Charles. és Ann N. Trenk. Tűrési grafikonok. Cambridge [ua: Cambridge Univ., 2004.
↑ G. B. Mertzios és D. G. Corneil. Csúcsfelosztás és trapézgráfok felismerése. Discrete Applied Mathematics, 159(11), 1131-1147 oldal, 2011.

Linkek

Martin Charles Golumbic. Algoritmikus gráfelmélet és tökéletes gráfok. – Academic Press, 1980. Második kiadás, Annals of Discrete Mathematics 57, Elsevier, 2004.