원형 아크 그래프

그래프 이론에서 원-아크 그래프는 원의 호 집합을 교차 그래프로 나타낸 것이다.집합의 각 호에 대해 하나의 꼭지점이 있고, 교차하는 호에 해당하는 모든 정점 쌍 사이의 가장자리가 있다.

형식적으로, let's let.

${\displaystyle I_{1},I_{2},\ldots,I_{n}\subset C_{1}:{1}$

호의 집합이다그러면 해당하는 원형 아크 그래프는 G = (V, E)이고, 여기서

$V=\{ 표시기 스타일I_{1},I_{2},\ldots,I_{n}\}}}$

그리고

${\displaystyle \{I_{\alpha }},I_{\beta }\in E\iff I_{\alpha }\cap I_{\beta }\neq \varnothy.}$

G에 해당하는 호를 호모형이라고 한다.

인식

터커(1980)는 $O{\displaystyle \mathcal{}}$(${\displaystyle {n\mathrm{}}^{}}$ 3${\displaystyle {}^{}}$) ${\displaystyle {\mathcal{O}(n^{3})$ 시간에$$ 실행되는 원형 아크 그래프의 첫 번째 다항식 인식 알고리즘을 시연했다.McConnell(2003)은 첫 번째 선형$({\displaystyle O}$(${\displaystyle n}$+ m${\displaystyle }$)${\displaystyle({\mathcal{O}(n+m)}}$ 시간$$ 인식 알고리즘을 제공했으며 여기서 $m{\displaystyle }$ ${\displaystyle m}$은 가장자리 수입니다.더 최근에 카플란과 누스바움은^[1] 더 간단한 선형 시간 인식 알고리즘을 개발했다.

다른 그래프 클래스와의 관계

원형 아크 그래프는 구간 그래프를 자연스럽게 일반화한 것이다.원형 아크 그래프 G에 원의 어느 지점을 노출시키지 않는 호 모델이 있는 경우, 그 지점에서 원을 잘라 한 줄로 늘어뜨려 구간표현이 가능하다.그러나 구간 그래프와 달리 원-아크 그래프는 코드 없는 홀수 사이클₅ C, C₇ 등이 원형-아크 그래프이기 때문에 항상 완벽한 것은 아니다.

일부 하위 클래스

다음에서 $G{\displaystyle }$=${\displaystyle }$( V${\displaystyle }$, ${\displaystyle E}$) ${\displaystyle G=(V,E)}$을(를) 임의 그래프로$$ 한다.

단위 원형 아크 그래프

${\displaystyle G}$ ${\displaystyle G}$은 각 호가 길이가 같은 해당 호 모델이 있는 경우 단위 원형 아크 그래프입니다.

n 정점에 라벨로 표시된 단위 원형 아크 그래프 수는${\displaystyle }$(n +${\displaystyle 2}$ ${\displaystyle )(\genfrac{}{}{0ex}{}{\mathrm{2n}}{}}$- ${\displaystyle \genfrac{}{}{0ex}{}{}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{n}}{}}$- 1${\displaystyle \genfrac{}{}{0ex}{}{}{}}$)${\displaystyle -}$ ${\displaystyle {2\mathrm{}}^{}}$ n${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\$ {$2n-1}{n-1-2}}-^{2n-1}$에 의해 주어진다$.$

적절한 원형 아크 그래프

${\displaystyle G}$ ${\displaystyle G}$은(는) 적절한 원형 아크 그래프(원형 간격 그래프라고도 함)^[3]로$$, 호가 제대로 다른 호를 포함하지 않는 해당 호 모델이 있는 경우.이러한 그래프를 인식하고 적절한 호 모델을 구성하는 것은 둘 다 선형$({\displaystyle O}$(${\displaystyle n}$+ m$){\displaystyle ({\mathcal{O}}(n+m)}$시간$$ 내에 수행할 수 있다.^[4]그것들은 발톱이 없는 그래프의 기본적인 하위 분류들 중 하나를 형성한다.^[3]

헬리콥터 원형 아크 그래프

${\displaystyle G}$ ${\displaystyle G}$은 호가 헬리 패밀리를 구성하는 등 해당 호 모델이 존재하는 경우 헬리 원형 아크 그래프다.가브릴(1974)은 $O{\displaystyle \mathcal{}}$(${\displaystyle {}^{}{3\mathrm{}}^{}}$ $){\$ 인식 알고리즘을$$ 암시하는 이 클래스의 특성을 부여한다.

조에리스 외 (2009) 이 클래스의 다른 특성을 부여하며, 이는 입력이 그래프일 때 O(n+m) 시간에 실행되는 인식 알고리즘을 의미한다.입력 그래프가 헬리 원형 아크 그래프가 아닌 경우 알고리즘은 금지 유도 서브그래프의 형태로 이 사실의 인증서를 반환한다.그들은 또한 주어진 원형 아크 모델이 헬리 특성을 가지고 있는지 여부를 결정하기 위한 O(n) 시간 알고리즘을 제공했다.

적용들

원형 아크 그래프는 운영 연구의 정기적인 자원 할당 문제를 모델링하는 데 유용하다.각 간격은 특정 기간 동안 시간에 따라 반복되는 자원에 대한 요청을 나타낸다.

메모들

참조

• Chudnovsky, Maria; Seymour, Paul (2008), "Claw-free graphs. III. Circular interval graphs" (PDF), Journal of Combinatorial Theory, Series B, 98 (4): 812–834, doi:10.1016/j.jctb.2008.03.001, MR 2418774.
• Deng, Xiaotie; Hell, Pavol; Huang, Jing (1996), "Linear-Time representation algorithms for proper circular-arc graphs and proper interval graphs", SIAM Journal on Computing, 25 (2): 390–403, doi:10.1137/S0097539792269095.
• Gavril, Fanica (1974), "Algorithms on circular-arc graphs", 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, archived from the original on 2010-05-22, retrieved 2008-05-21. 제2판 이산 수학 연보 57, 엘시비에, 2004.
• Joeris, Benson L.; Lin, Min Chih; McConnell, Ross M.; Spinrad, Jeremy P.; Szwarcfiter, Jayme L. (2009), "Linear-Time Recognition of Helly Circular-Arc Models and Graphs", Algorithmica, 59 (2): 215–239, CiteSeerX 10.1.1.298.3038, doi:10.1007/s00453-009-9304-5.
• McConnell, Ross (2003), "Linear-time recognition of circular-arc graphs", Algorithmica, 37 (2): 93–147, CiteSeerX 10.1.1.22.4725, doi:10.1007/s00453-003-1032-7.
• Tucker, Alan (1980), "An efficient test for circular-arc graphs", SIAM Journal on Computing, 9 (1): 1–24, doi:10.1137/0209001.

외부 링크

• 원형 호 그래프, 그래프 클래스 포함 정보 시스템