Wykres trapezu

W teorii grafów wykresy trapezowe to wykresy przecięcia trapezów między dwiema poziomymi liniami. Są klasą grafów współporównywalności, które zawierają grafy interwałowe i grafy permutacji jako podklasy. Graf jest grafem trapezowym, jeśli istnieje zbiór trapezów odpowiadających wierzchołkom grafu, w którym dwa wierzchołki są połączone krawędzią wtedy i tylko wtedy, gdy odpowiednie trapezy się przecinają. Wykresy trapezowe zostały wprowadzone przez Dagana, Golumbica i Pintera w 1988. Istnieją $pokrycia$ dla liczby chromatycznej, niezależnego zestawu ważonego kliki o

Rysunek 1: Trapezowa reprezentacja wykresu G.

Definicje i charakterystyki

Biorąc pod uwagę kanał, parę dwóch linii poziomych, trapez między tymi liniami jest określony przez dwa punkty na górnej i dwa punkty na dolnej linii. Graf jest grafem trapezowym, jeśli istnieje zbiór trapezów odpowiadających wierzchołkom grafu, w którym dwa wierzchołki są połączone krawędzią wtedy i tylko wtedy, gdy odpowiednie trapezy się przecinają. Wymiar rzędu przedziałów częściowo uporządkowanego zbioru _, $P$ _minimalna liczba d rzędów przedziałów P d = P. ₁ ∩…∩P _re . Wykres nieporównywalności częściowo uporządkowanego zestawu $X$$( X , mi )$ gdzie = , sąsiaduje z y w G wtedy i tylko wtedy, gdy x i y są nieporównywalne w P. Graf nieskierowany jest grafem trapezowym wtedy i tylko wtedy, gdy jest wykresem nieporównywalności rzędu częściowego o wymiarze rzędu co najwyżej 2.

Aplikacje

Problemy znajdowania maksymalnych klik i kolorowania wykresów trapezów są związane z problemami trasowania kanałów w projekcie VLSI . Mając kilka oznaczonych zacisków na górnej i dolnej stronie dwustronnego kanału, zaciski z tą samą etykietą zostaną połączone we wspólną sieć. Ta sieć może być reprezentowana przez trapez zawierający skrajne prawe i lewe końcówki z tą samą etykietą. Sieci można poprowadzić bez przecięcia wtedy i tylko wtedy, gdy odpowiadające im trapezy się nie przecinają. Dlatego liczba warstw potrzebnych do poprowadzenia sieci bez przecinania się jest równa liczbie chromatycznej grafu.

Reprezentacje równoważne

Reprezentacja trapezu

Trapezów można użyć do przedstawienia wykresu trapezowego, używając definicji wykresu trapezowego. Reprezentację trapezu wykresu trapezu można zobaczyć na rysunku 1.

Reprezentacja pudełkowa

Dominujące prostokąty lub reprezentacja pudełkowa odwzorowuje punkty na dolnej z dwóch linii reprezentacji trapezu jako leżące na osi x , a punkty górnej linii jako leżące na osi y płaszczyzny euklidesowej. Każdy trapez odpowiada zatem prostopadłemu do osi prostopadłościanowi na płaszczyźnie. Posługując się pojęciem porządku dominacji (w R ^K , x mówi się, że jest zdominowane przez y , oznaczane x < y , jeśli x _i jest mniejsze niż y _i dla i = 1, …, k ), mówimy, że pudełko b dominuje nad pudełkiem b', jeśli dolny róg b dominuje nad górnym narożnikiem b' . Ponadto, jeśli jedno z dwóch pudełek dominuje nad drugim, mówimy, że są one porównywalne. W przeciwnym razie są nieporównywalne. Zatem dwa trapezy są rozłączne dokładnie wtedy, gdy odpowiadające im pudełka są porównywalne. Reprezentacja pudełkowa jest użyteczna, ponieważ powiązana kolejność dominacji umożliwia użycie algorytmów linii przemiatania.

Wykresy bitolerancji

Wykresy bitolerancji to wykresy nieporównywalności rzędu bitolerancji. Rząd jest porządkiem bitolerancji wtedy i tylko wtedy, gdy istnieją przedziały I _x i liczby rzeczywiste t ₁ ( x ) i t _r ( x ) przypisane do każdego wierzchołka x w taki sposób, że x < y wtedy i tylko wtedy, gdy nakładanie się I _x i I _y są mniejsze niż zarówno t _r ( x ), jak i t ₁ ( y ) a środek I _x jest mniejszy niż środek I _y . W 1993 Langley wykazał, że ograniczone wykresy bitolerancji są równoważne klasie wykresów trapezowych.

Stosunek do innych rodzin grafów

Klasa grafów trapezowych właściwie zawiera sumę grafów interwałowych i permutacyjnych i jest równoważna grafom nieporównywalności zbiorów częściowo uporządkowanych o wymiarze rzędu interwałowego co najwyżej dwa. Wykresy permutacyjne można postrzegać jako szczególny przypadek wykresów trapezowych, w których każdy trapez ma pole zerowe. Dzieje się tak, gdy oba punkty trapezu na górnym kanale są w tej samej pozycji i oba punkty na dolnym kanale są w tej samej pozycji.

Podobnie jak wszystkie wykresy nieporównywalności, wykresy trapezowe są doskonałe .

Wykresy trapezów kołowych

Wykresy trapezów kołowych to klasa wykresów zaproponowana przez Felsnera i in. w 1993 r. Są nadklasą klasy wykresów trapezowych i zawierają również wykresy kołowe i wykresy łukowe. Trapez kołowy to obszar w okręgu, który leży między dwoma nie przecinającymi się cięciwami, a wykres trapezu kołowego to wykres przecięcia rodzin trapezów kołowych na wspólnym okręgu. Istnieje $algorytm$ problemu z maksymalnym ${\ displaystyle {O} (n ^ {2} \ log n)}$ algorytm dla problemu kliki o maksymalnej wadze.

k - Wykresy trapezowe

k - Wykresy trapezowe są rozszerzeniem wykresów trapezowych do rzędów wyższych wymiarów. Zostały one po raz pierwszy zaproponowane przez Felsnera i opierają się na definicji dominujących pudełek przenoszonych do wyższych wymiarów, w których punkt x jest reprezentowany przez wektor ${\ Displaystyle (x_ {1}, \ ldots ,x_{k})}$ . Wykorzystując ( k - 1)-wymiarowe drzewa zakresu do przechowywania i wyszukiwania współrzędnych, algorytmy Felsnera dla liczby chromatycznej, maksymalnej kliki i maksymalnego niezależnego zestawu można zastosować do k -wykresy trapezowe w czasie ${\ Displaystyle {O} (n \ log ^ {k-1} n)} .$

Algorytmy

Algorytmy dla wykresów trapezowych należy porównać z algorytmami dla ogólnych wykresów współporównywalności. $tej$ i minimalnego pokrycia kliki można rozwiązać . Dagan i in. pierwszy zaproponował ${\ Displaystyle {O} (nk)}$ algorytm kolorowania grafów trapezowych, gdzie n to liczba węzłów, a k to liczba chromatyczna grafu. Później, używając reprezentacji pudełkowej wykresów trapezowych, Felsner opublikował $dla$ kliki i kliki o maksymalnej Wszystkie te algorytmy wymagają ${\ Displaystyle {O} (n)}$ przestrzeń. Algorytmy te opierają się na powiązanej dominacji w reprezentacji pudełkowej, która umożliwia stosowanie algorytmów linii wymiatających. $} O}(n\log n)}$ wstawiania, usuwania i zapytań w czasie, co daje $} ($ algorytmy.

Uznanie

Aby ustalić, czy wykres $}$${$ \ displaystyle $}$ . Ponieważ wykresy trapezowe $musi$ podzbiorem wykresów współporównywalności, jeśli jest wykresem trapezowym, jego dopełnienie $być$ wykresem Jeśli orientacja przechodnia dopełnienia ${\ displaystyle {F}}$${\ displaystyle {G'}}$ nie istnieje, $jest$ wykresem trapezowym. Jeśli $istnieje$ , sprawdź, czy kolejność podana przez $porządkiem$ . Najszybszy $wynosił$ kolejności trapezów został ., A jego czas działania Proces redukuje pytanie o wymiar interwałowy 2 do problemu pokrycia powiązanego wykresu dwudzielnego za pomocą wykresów łańcuchowych (wykresy bez indukcji 2K ₂ ). Używając podziału wierzchołków, problem rozpoznawania grafów trapezowych został pokazany przez Mertziosa i Corneila, $}$$m$ m oznacza liczbę krawędzi. Ten proces obejmuje powiększanie danego wykresu ${\ displaystyle {G}}$ , a następnie przekształcając graf rozszerzony, zastępując każdy wierzchołek oryginalnego grafu parą nowych wierzchołków. Ten $jest$ wykres podzielony” jest wykresem permutacyjnym o specjalnych właściwościach tylko wtedy, gdy wykresem trapezowym.

Notatki

•   Golumbic, Martin Charles (1980). Teoria grafów algorytmicznych i grafy doskonałe . Prasa akademicka. ISBN 0-444-51530-5 . Wydanie drugie, Annals of Discrete Mathematics 57, Elsevier, 2004.