임계값 그래프

그래프 이론에서 임계값 그래프는 다음과 같은 두 가지 연산을 반복적으로 적용하여 1Vertex 그래프에서 구성할 수 있는 그래프다.

1. 그래프에 단일 절연 정점 추가.
2. 그래프에 지배적인 단일 꼭지점 추가, 즉 다른 모든 꼭지점에 연결된 단일 꼭지점 추가.

예를 들어, 그림의 그래프는 분계점 그래프 입니다.단일 버텍스 그래프(버텍스 1)로 시작한 다음, 번호가 매겨지는 순서대로 검은색 정점을 분리된 정점으로, 빨간색 정점을 지배 정점으로 추가하여 구성할 수 있다.

임계값 그래프는 Chvatal & Hammer(1977년)에 의해 처음 도입되었다.문턱 그래프에 관한 한 장이 골룸빅(1980년)에 등장하고, 마하데브&펠레드(1995)라는 책이 그것들에 바쳐져 있다.

대체 정의

등가 정의는 다음과 같다: 그래프는 실제 $숫자{\displaystyle }$ S ${\displaystyle S}$이(가) 있는 경우 임계값$$ 그래프이고, 각 $꼭지점{\displaystyle }$ v ${\displaystyle v}$에 대해$$ 실제 정점 $중량{\displaystyle }$ w${\displaystyle }$(${\displaystyle v}$ ${\displaystyle )}$ ${\$$displaystyle w$$(v)},$ $,$$u$}, ${\displaystyle u}$ v ${\displaystylease u}$에 대해 에지가 된다. if w ()+ )> ${\displaystyle w(u)+w(v)}$인 경우$S}$

다른 동등한 정의는 다음과 같다: 실제 숫자 $T{\displaystyle }$ {\$displaystyle T}$이(가$)$ 있는 경우 그래프는 임계값 그래프이며, 각 꼭지점 $v{\displaystyle }$ ${\displaystyle$ $v$$}$에 대해 $실제{\displaystyle }$ 꼭지점 무게 $a{\displaystyle }$ $v$ ${\displaystyle )}$ ${\$$displaystyle x\subseteq$ V$},$ X$}$이(가$$$)$가 독립된 경우$$.$\sum {\displaystyle \underset{}{}}$ ${\displaystyle \underset{}{v}}$ ${\displaystyle \underset{}{\in }}$ ${\displaystyle \underset{}{X}}$ a${\displaystyle }$(${\displaystyle v}$ ${\displaystyle )}$ ${\displaystyle \le }$ T${\displaystyle }$. ${\displaystyle \sum _{v\in X}a(v)\leq$ T$.}$인 경우에만 해당됨

"임계 그래프"라는 이름은 이러한 정의에서 유래한다: S는 가장자리가 되는 속성에 대한 "임계" 또는 동등하게 T는 독립성을 위한 임계값이다.

임계값 그래프에도 금지된 그래프 특성이 있다. 그래프는 3 에지 경로 그래프, 4 에지 주기 그래프 또는 2 에지 일치인 유도 하위 그래프를 구성하는 4개의 꼭지점이 없는 경우에만 임계값 그래프다.

분해

정점의 반복적인 추가를 사용하는 정의에서, 일련의 기호를 사용하여 분계점 그래프를 고유하게 설명하는 대체 방법을 도출할 수 있다.${\displaystyle ϵ}$ ${\displaystyle \epsilon }$은(는) 항상 문자열의 첫 번째 문자로 그래프의 첫 번째 꼭지점을 나타낸다.이후의 모든 문자는 분리된 꼭지점(또는 결합 꼭지점)의 추가를 $나타내는{\displaystyle }$u {\$displaystyle$u} 또는 지배적인 꼭지점(또는 결합 꼭지점)의$$추가를 나타내는 j {\$displaystyle j}$ 중 하나이다$.$예를 들어 문자열 string ${\displaystyle u}$ ${\displaystyle j}$ ${\displaystyle \epsilon uj}$은 잎이 세 개인 별 그래프를 나타내고$$, $while{\displaystyle }$ ${\displaystyle u}$ ${\displaystyle j}$ ${\displaystyle \epsilon uj}$은 세 개의 꼭지점에 있는 경로를 나타낸다$$.그림의 그래프는 ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle u}$ j ${\displaystyle \epsilon uujuj}$로 나타낼 수 있다.

그래프 및 인식의 관련 클래스

분계점 그래프는 cographs, 분할 그래프, 그리고 아주 완벽한 그래프의 특별한 경우다.그래프는 cograph와 split graph인 경우에만 분계점 그래프다.사소한 완벽 그래프와 사소한 완벽 그래프의 보완적 그래프가 모두 임계값 그래프다.분계점 그래프도 구간 그래프의 특별한 경우다.이러한 모든 관계는 금지된 유도 하위 그래프에 의해 특성화 측면에서 설명될 수 있다.cograph는 4개의 꼭지점 P에₄ 유도 경로가 없는 그래프를 말하며, 분계점 그래프는₄ 유도 P₄, C, 2K가₂ 없는 그래프다.C는₄ 4개의 꼭지점의 주기이고 2K는₂ 그것의 보완, 즉 두 개의 분리 에지다.이는 또한 P가₄ 자체 보완적이므로, P-₄, C-₄, 2K가₂ 없는 그래프의 보완도 마찬가지라는 점을 보완해야 하는 이유를 설명한다.

헤거네스 & 크래치(2007)는 임계값 그래프를 선형 시간 내에 인식할 수 있다는 것을 보여주었다. 그래프가 임계값이 아닐 경우 장애물(P₄, C₄ 또는 2K₂ 중 하나)이 출력된다.

참고 항목

• 무관심 그래프
• 시계열-병렬 그래프
• 임계값 하이퍼그래프^[1]

참조

• Chvátal, Václav; Hammer, Peter L. (1977), "Aggregation of inequalities in integer programming", in Hammer, P. L.; Johnson, E. L.; Korte, B. H.; et al. (eds.), Studies in Integer Programming (Proc. Worksh. Bonn 1975), Annals of Discrete Mathematics, vol. 1, Amsterdam: North-Holland, pp. 145–162.
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, New York: Academic Press. 제2판 이산수학 연보, 57, 엘스비에, 2004.
• Heggernes, Pinar; Kratsch, Dieter (2007), "Linear-time certifying recognition algorithms and forbidden induced subgraphs" (PDF), Nordic Journal of Computing, 14 (1–2): 87–108 (2008), MR 2460558.
• Mahadev, N. V. R.; Peled, Uri N. (1995), Threshold Graphs and Related Topics, Elsevier.

외부 링크

• 임계값 그래프, 그래프 클래스의 정보 시스템 및 포함.