Wykres łuku kołowego

Wykres łuku kołowego (po lewej) i odpowiadający mu model łuku (po prawej).

W teorii grafów wykres kołowo-łukowy jest wykresem przecięcia zestawu łuków na okręgu. Ma jeden wierzchołek dla każdego łuku w zestawie i krawędź między każdą parą wierzchołków odpowiadającą przecinającym się łukom.

Formalnie niech

{\ Displaystyle I_ {1}, ja_ {2}, \ ldots, ja_ {n} \ podzbiór C_ {1}}

być zbiorem łuków. Wtedy odpowiedni wykres kołowy to G = ( V , E ) gdzie

{\ Displaystyle V = \ {I_ {1}, ja_ {2}, \ ldots, ja_ {n} \}}

I

{\ Displaystyle \ {I _ {\ alfa}, I _ {\ beta} \} \ w E \ iff I _ {\ alfa} \ czapka I_ {\ beta} \ neq \ varnothing.}

Rodzina łuków odpowiadająca G jest nazywana modelem łuku .

Uznanie

Tucker (1980) zademonstrował $rozpoznawania$ dla wykresów łukowych, który działa . McConnell ( $pierwszy$ $)$ podał liniowy , . Niedawno Kaplan i Nussbaum opracowali prostszy algorytm liniowego rozpoznawania czasu.

Związek z innymi klasami grafów

Wykresy łukowe są naturalnym uogólnieniem wykresów interwałowych . Jeśli wykres łuku kołowego G ma model łuku, który pozostawia pewien punkt koła odkryty, okrąg można wyciąć w tym punkcie i rozciągnąć do linii, co daje reprezentację interwałową. Jednak w przeciwieństwie do grafów interwałowych, grafy kołowo-łukowe nie zawsze są doskonałe , ponieważ nieparzyste cykle bez akordów C ₅ , C ₇ itd. są grafami kołowo-łukowymi.

Niektóre podklasy

Poniżej $_$ _

Jednostkowe wykresy kołowo-łukowe

${\ displaystyle G}$ jest jednostkowym wykresem łuku kołowego, jeśli istnieje odpowiedni model łuku, taki że każdy łuk ma równą długość.

Liczba oznaczonych jednostkowych wykresów kołowo-łukowych na n wierzchołkach jest dana wzorem ${\ Displaystyle (n + 2) {\ binom {2n-1 }{n-1}}-2^{2n-1}}$ .

Właściwe wykresy łukowe

$Jest$ to właściwy wykres łuku kołowego (znany również jako wykres przedziału kołowego ), jeśli istnieje odpowiedni model łuku, taki że żaden łuk nie zawiera właściwie innego $zbudowanie$ odpowiedniego modelu łuku można czasie Tworzą one jedną z podstawowych podklas grafów bez pazurów .

Diabelskie wykresy łukowe

Jest $wykresem$ łuku kołowego Helly'ego, jeśli istnieje odpowiedni model łuku, taki że łuki tworzą Helly . Gavril (1974) $podaje$ klasy, która algorytm

Joeris i in. (2009) podają inne charakterystyki tej klasy, które implikują algorytm rozpoznawania, który działa w czasie O(n+m), gdy dane wejściowe są wykresami. Jeżeli graf wejściowy nie jest grafem Helly'ego o łuku kołowym, to algorytm zwraca poświadczenie tego faktu w postaci podgrafu zabronionego indukowanego. Podali również O(n) do określania, czy dany model łuku kołowego ma właściwość Helly.

Aplikacje

Wykresy łukowe są przydatne w modelowaniu okresowych problemów alokacji zasobów w badaniach operacyjnych . Każdy interwał reprezentuje żądanie zasobu dla określonego okresu, powtarzane w czasie.

Notatki

Czudnowski, Maria ; Seymour, Paul (2008), „Wykresy bez pazurów. III. Wykresy przedziałów kołowych” (PDF) , Journal of Combinatorial Theory , Seria B, 98 (4): 812–834, doi : 10.1016/j.jctb.2008.03. 001 , MR 2418774 .
Deng, Xiaotie; Piekło, Paweł ; Huang, Jing (1996), „Algorytmy reprezentacji w czasie liniowym dla odpowiednich wykresów łuków kołowych i odpowiednich wykresów interwałowych”, SIAM Journal on Computing , 25 (2): 390–403, doi : 10.1137 / S0097539792269095 .
Gavril, Fanica (1974), „Algorytmy na wykresach kołowych”, Networks , 4 (4): 357–369, doi : 10.1002/net.3230040407 .
Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs , Academic Press, ISBN 978-0-444-51530-8 , zarchiwizowane z oryginału w dniu 22.05.2010 , pobrane 21.05.2008 . Wydanie drugie, Annals of Discrete Mathematics 57, Elsevier, 2004.
Joeris, Benson L.; Lin, Min Chih; McConnell, Ross M.; Spinrad, Jeremy P.; Szwarcfiter, Jayme L. (2009), „Rozpoznawanie w czasie liniowym modeli i wykresów Helly Circular-Arc”, Algorithmica , 59 (2): 215–239, CiteSeerX 10.1.1.298.3038 , doi : 10.1007/s00453-009- 9304-5 .
McConnell, Ross (2003), „Rozpoznawanie wykresów kołowych w czasie liniowym”, Algorithmica , 37 (2): 93–147, CiteSeerX 10.1.1.22.4725 , doi : 10.1007/s00453-003-1032-7 .
Tucker, Alan (1980), „Wydajny test wykresów łukowych”, SIAM Journal on Computing , 9 (1): 1–24, doi : 10.1137/0209001 .

Linki zewnętrzne

Wykres łuku kołowego , system informacji o inkluzjach klas wykresów