Lichoběžníkový graf

V teorii grafů jsou lichoběžníkové grafy lichoběžníkové průnikové grafy , jejichž všechny rovnoběžné strany leží na dvou úsecích. Tato třída grafů je obsažena ve třídě grafů kosrovnatelnosti a obsahuje intervalové grafy a permutační grafy jako podtřídy. Graf je lichoběžníkový tehdy a jen tehdy, když existuje množina lichoběžníků odpovídajících vrcholům grafu a dva vrcholy grafu jsou spojeny hranou právě tehdy, když se lichoběžníky odpovídající vrcholům protínají. Lichoběžníkové grafy zavedly v roce 1988 Ido Dagan, Martin Charles Golumbic a Ron Pinter. Pro tyto grafy existují algoritmy s dobou běhu pro obarvení grafu, pro nalezení vážených nezávislých množin , pokrytí klik a maximální vážené kliky. ${O}(n\log n)$

Definice a charakteristika

Nechť jsou dány dvě rovnoběžné čáry. Na těchto přímkách jsou definovány lichoběžníky, ve kterých dva vrcholy leží na jedné přímce a další dva leží na druhé přímce. Graf je lichoběžníkový právě tehdy, když existuje množina lichoběžníků odpovídajících vrcholům grafu a dva vrcholy grafu jsou spojeny hranou právě tehdy, když se lichoběžníky odpovídající vrcholům protínají. Rozměr částečně objednané sady je nejmenší počet d kompletních zakázek takový, že . Posetový graf nekompatibility je neorientovaný graf , ve kterém vrchol x sousedí s vrcholem y v G právě tehdy, když x a y jsou nesrovnatelné v P. Neorientovaný graf je lichoběžníkový graf tehdy a jen tehdy, když je to graf nesrovnatelnosti částečně objednaná sada o rozměru nejvýše 2. [1] $P=(X,<)$ ${\displaystyle P_{1}...P_{d))$ ${\displaystyle P=P_{1}\cap ...\cap P_{d))$ $P=(X,<)$ $G=(X,E)$

Aplikace

Problémy hledání maximálních klik a vybarvování lichoběžníkových grafů souvisí s problémem pokládání vodivých kanálů při návrhu integrovaných obvodů . Pokud jsou některé označené body nastaveny na horní a spodní straně desky, body se stejnými štítky budou připojeny ke společné síti. Tato síť může být reprezentována lichoběžníkem, který obsahuje krajní (levý a pravý) body se stejným označením. Sítě lze pokládat bez křížení tehdy a pouze tehdy, pokud se lichoběžníky neprotínají. Počet potřebných vrstev pro pokládku vodičů bez průsečíků se tedy rovná chromatickému číslu grafu.

Ekvivalentní reprezentace

Znázornění pomocí lichoběžníků

Lichoběžníky lze použít k zobrazení grafu na základě definice.

Znázornění pomocí obdélníků

Dominantní obdélníková reprezentace zobrazuje body na jedné čáře jako body na ose x a body na druhé čáře jako body na ose y euklidovské roviny. Potom libovolný lichoběžník odpovídá obdélníku v rovině. V RK se říká , že x dominuje y , které se zapisuje jako x < y , pokud x i je menší než y i pro i = 1, …, k . Řekneme, že obdélník b dominuje b' , jestliže spodní roh b dominuje hornímu rohu b' . Říkáme, že dva obdélníky jsou srovnatelné, pokud jeden dominuje druhému. Dva lichoběžníky se tedy neprotínají přesně, když jsou jejich odpovídající obdélníky srovnatelné. Krabicová reprezentace je užitečná, protože vztah dominance umožňuje použít rozbalovací algoritmus [2] Znázornění grafu z obrázku 1 ve formě obdélníků je na obrázku 3.

Bitolerantní grafy

Bitolerantní grafy jsou nesrovnatelné grafy bitolerantního řádu. O řádu se říká, že je bitově tolerantní tehdy a jen tehdy, když každému bodu x jsou přiřazeny intervaly I x a reálná čísla t 1 ( x ) a t r ( x ) tak, že x < y právě tehdy, když překrytí I x a I y je menší než t r ( x ) a ti ( y ) a střed I x je menší než střed I y . [3] V roce 1993 Langley ukázal, že ohraničené bitolerantní grafy jsou ekvivalentní třídě lichoběžníkových grafů. [čtyři]

Vztah k jiným skupinám grafů

Třída lichoběžníkových grafů obsahuje intervalové grafy a permutační grafy a je ekvivalentní grafům nesrovnatelnosti částečně uspořádaných množin řádové dimenze nejvýše dvou. Na permutační grafy lze pohlížet jako na speciální případ lichoběžníkových grafů, pokud jsou lichoběžníky redukovány na úsečky (tj. lichoběžníky s nulovou délkou rovnoběžných stran).

Jako všechny grafy nesrovnatelnosti jsou i lichoběžníkové grafy dokonalé .

Kruhové lichoběžníkové grafy

Kruhové lichoběžníkové grafy jsou třídou grafů navržených Felsnerem et al. v roce 1993. Tyto grafy jsou nadtřídou lichoběžníkových grafů a obsahují kruhové grafy a kruhové obloukové grafy. Kruhový lichoběžník je oblast kruhu mezi dvěma neprotínajícími se tětivami a graf kruhového lichoběžníku je graf průsečíku rodiny kruhových lichoběžníků. Kruhové znázornění grafu je na obrázku 4. Existuje algoritmus s dobou běhu pro řešení problému nalezení nezávislé množiny maximální hmotnosti a algoritmus s dobou běhu pro problém nalezení kliky s maximální váhou. $O(n^{2})$ ${O}(n^{2}\log n)$

k -lichoběžníkové grafy

k - lichoběžníkové grafy je zobecnění lichoběžníkových grafů do vyšších dimenzí prostoru. Byly navrženy Felsnerem a jsou založeny na definici dominantních vícerozměrných obdélníků. V těchto grafech vrchol x odpovídá vektoru . Pomocí ( k − 1)-rozměrných třídicích stromů k ukládání a získávání souřadnic řeší Felsnerovy algoritmy problémy hledání chromatického čísla, maximální kliky a maximální nezávislé množiny v čase . $(x_{1},\ldots ,x_{k})$ ${O}(n\log ^{k-1}n)$

Algoritmy

Algoritmy pro lichoběžníkové grafy by měly být porovnány s algoritmy pro obecnější grafy kosrovnatelnosti. K tomu lze včas vyřešit širší třídu grafů, problémy s nalezením maximální nezávislé množiny a minimálního pokrytí kliky . [5] Dagan a kol . Později Felsner pomocí obdélníkové reprezentace lichoběžníkových grafů publikoval algoritmy pro nalezení chromatického čísla, vážené nezávislé množiny, pokrytí kliky a maximální vážené kliky v čase . Všechny tyto algoritmy vyžadují velikost paměti . Tyto algoritmy jsou založeny na dominanci reprezentace pomocí obdélníků, což umožňuje použití rozbalovacích algoritmů. Algoritmy navržené Felsnerem používají vyvážené stromy, které umožňují operace vkládání, mazání a dotazování provádět v čase , což dává výsledný čas . ${O}(n^{2}\log n)$ ${O}(nk)$ ${O}(n\log n)$ ${O}(n)$ ${O}(\log n)$ ${O}(n\log n)$

Rozpoznávání

Chcete-li určit, zda je graf lichoběžníkový, hledáme tranzitivní orientaci na doplňku grafu . Protože lichoběžníkové grafy jsou podmnožinou kosrovnatelných grafů, je-li lichoběžníkový, jeho doplněk musí být graf srovnatelnosti. Pokud tranzitivní orientace na doplňku neexistuje, graf není lichoběžníkový. Pokud se najde, zkontroluje se, zda bude pořadí určené lichoběžníkovým řádem. Nejrychlejší algoritmus rozpoznávání lichoběžníkového kamene byl navržen McConnellem a Spinradem v roce 1994 s provozní dobou . Proces redukuje otázku dimenze dílčího řádu (zda přesahuje 2) na problém pokrytí odpovídajícího bipartitního grafu řetězci (grafy bez generovaných 2K 2 podgrafů). [6] Jak ukázali Mertzios a Corneil, pokud se použije separace vrcholů, problém rozpoznávání lichoběžníkových grafů může být vyřešen v čase , kde značí počet hran. Tento proces využívá rozšíření daného grafu a poté transformaci rozšířeného grafu nahrazením všech původních vrcholů v grafu dvojicí nových vrcholů. Tento „rozdělený graf“ je permutační graf se speciálními vlastnostmi právě tehdy, je-li lichoběžníkový. [7] ${G}$ ${F}$ ${G}$ ${G}$ ${G'}$ ${F}$ ${G'}$ ${G}$ ${F}$ ${F}$ $O(n^{2})$ $O(n(n+m))$ $m$ ${G}$ ${G}$

Poznámky

↑ Ido Dagan, Martin Charles Golumbic a Ron Yair Pinter. Lichoběžníkové grafy a jejich barvení. Diskrétní Apple. Math., 35–46, 1988.
↑ Stefan Felsner, Rudolf Muller a Lorenz Wernisch. Lichoběžníkové grafy a zobecnění, geometrie a algoritmy. In Algorithm theory — SWAT '94 (Aarhus, 1994), svazek 824 Lecture Notes in Comput. Sci., strany 143–154. Springer, Berlín, 1994.
↑ Kenneth P. Bogart, Garth Isaak. Správné a jednotkové řády a grafy bittolerance. Diskrétní matematika 181 (1–3): 37–51 (1998).
↑ Martin Charles Golumbic a Irith B.-A. Hartman, eds., Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications, Springer-Verlag, New York, 2005
↑ R. McConnel a J. Spinrad, Lineární modulární rozklad a efektivní tranzitivní orientace neorientovaných grafů, Proc. 5. Ann. Symp. na Discr. Alg. (1994).
↑ Golumbic, Martin Charles. a Ann N. Trenk. Toleranční grafy. Cambridge [ua: Cambridge Univ., 2004.
↑ G. B. Mertzios a D. G. Corneil. Rozdělení vrcholů a rozpoznávání lichoběžníkových grafů. Discrete Applied Mathematics, 159(11), strany 1131-1147, 2011.

Odkazy

Martin Charles Golumbic. Algoritmická teorie grafů a dokonalé grafy. — Academic Press, 1980. Druhé vydání, Annals of Discrete Mathematics 57, Elsevier, 2004.