교차로 그래프

그래프 이론에서 교차 그래프는 집합 집합의 교차로 패턴을 나타내는 그래프다.어떤 그래프는 교차로 그래프로 나타낼 수 있지만, 그래프의 일부 중요한 등급은 그래프의 교차로표현을 형성하는 데 사용되는 집합의 종류에 의해 정의될 수 있다.

형식 정의

공식적으로 교차 그래프 G는 집합 집합 집합에서 형성된 비방향 그래프다.

S_i, i = 0, 1, 2, ...

각 세트 S에_i 대해 하나의 꼭지점 v를_i 생성하고 해당하는 두 세트에 비어 있지 않은 교차점이 있을 때마다 두 꼭지점 v와_i v를_j 에지로 연결함으로써, 즉,

E_i(G) = {v_i, v_j} i ≠ j, S ∩ S_j ≠ ≠ ∅ ∅ ∅ }.

모든 그래프는 교차로 그래프임

모든 비방향 그래프 G는 교차로 그래프로 나타낼 수 있다. G의 각 정점 v에_i 대해, v에_i 입사하는 가장자리로 구성된 S를_i 형성한다. 그런 다음 해당 정점들이 가장자리를 공유하는 경우에만 그러한 두 집합은 비어 있지 않은 교차점을 가진다.Erdős, Goodman & PoSA(1966)는 설정 요소의 총 수가 최대 n²/4이고, 여기서 n은 그래프의 정점 수가 되는 보다 효율적인 구조를_i 제공한다.그들은 모든 그래프가 Sz필라진-Marczewski(1945년)에 대한 교차 그래프라는 관측을 믿지만, 툴리크(1964)도 보라고 말한다.그래프의 교차로 번호는 그래프의 교차로 표현에 있는 요소의 최소 총 수입니다.

교차로 그래프 클래스

많은 중요한 그래프 패밀리는 어떤 종류의 기하학적 구성에서 파생된 집합 집합 패밀리의 제한된 유형의 교차 그래프로 설명될 수 있다.

• 구간 그래프는 실제 선상의 구간 또는 경로 그래프의 연결된 하위 그래프의 교차 그래프로 정의된다.
• 무관심 그래프는 실제 선에서 단위 구간의 교차 그래프로 정의될 수 있다.
• 원형 호 그래프는 원에 있는 호의 교차 그래프로 정의된다.
• 다각형 원 그래프는 원의 모서리가 있는 다각형의 교차점이라고 정의된다.
• 화음 그래프의 한 가지 문자는 트리의 연결된 하위 그래프의 교차 그래프로 표시된다.
• 사다리꼴 그래프는 두 개의 평행선으로 형성된 사다리꼴의 교차 그래프로 정의된다.그것들은 순열 그래프의 개념을 일반화한 것이고, 다시 그들은 cocomparability graph로 알려진 비교가능성 그래프의 보완을 위한 특별한 사례다.
• 단위 디스크 그래프는 평면에 있는 단위 디스크의 교차 그래프로 정의된다.
• 원 그래프는 원의 화음 집합을 교차 그래프로 나타낸 것이다.
• 원 패킹 정리에서는 평면 그래프가 비크로 경계된 평면에서 닫힌 원반 패밀리의 교차 그래프라고 명시하고 있다.
• 스키너먼의 추측(지금의 정리)은 모든 평면 그래프는 평면에 있는 선 세그먼트의 교차 그래프로도 나타낼 수 있다고 말한다.그러나 선 세그먼트의 교차로 그래프도 평행이 아닐 수 있으며, 선 세그먼트의 교차로 그래프를 인식하는 것은 실재론(Schaefer 2010)에 대해 완성된다.
• 그래프 G의 선 그래프는 G의 가장자리에 대한 교차 그래프로 정의되며, 여기서 우리는 각 가장자리를 두 끝점의 집합으로 나타낸다.
• 문자열 그래프는 평면의 곡선을 교차 그래프로 나타낸 것이다.
• 치수 k의 다차원 상자의 교차 그래프인 경우 그래프에는 상자성 k가 있지만 더 작은 치수는 없다.
• clique graph는 다른 그래프의 최대 clique를 교차 그래프로 나타낸 것이다.
• 클라이크 트리의 블록 그래프는 다른 그래프의 연결된 성분의 교차 그래프다.

스키너먼(1985)은 그래프의 교차 클래스, 주어진 집합 집합 집합에서 추출한 집합의 교차 그래프로 설명할 수 있는 유한 그래프 패밀리를 특징으로 했다.가문은 다음과 같은 속성을 가질 필요가 있고 충분하다.

• 가족 내 그래프의 모든 유도 하위 그래프도 가족 내에 있어야 한다.
• 정점을 패거리에 의해 대체함으로써 패밀리의 그래프에서 형성된 모든 그래프도 패밀리에 속해야 한다.
• 패밀리에는 무한히 많은 그래프가 존재하는데, 각 그래프는 시퀀스 내 다음 그래프의 유도 하위그래프로서 패밀리 내 모든 그래프가 시퀀스 내 그래프의 유도 하위그래프라는 속성이 있다.

교차 그래프 표현에 서로 다른 정점을 다른 집합으로 나타내야 한다는 추가 요건이 있는 경우, clique 확장 특성을 생략할 수 있다.

관련개념

교차로 그래프에 대한 주문-이론적 유사성이 포함 순서다.그래프의 교차점 표현이 모든 꼭지점에 세트로 라벨을 표시하여 정점이 비어 있지 않은 경우에만 인접하도록 하는 것과 같은 방식으로, 포셋의 포함 표시는 모든 원소에 세트와 함께 라벨을 표시하여 포셋의 x와 y에 대해 f(x) ⊆ f(y)인 경우에만 x ≤ y로 라벨을 표시한다.

참고 항목

• 접촉 그래프

참조

• Čulík, K. (1964), "Applications of graph theory to mathematical logic and linguistics", Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Prague: Publ. House Czechoslovak Acad. Sci., pp. 13–20, MR 0176940.
• Erdős, Paul; Goodman, A. W.; Pósa, Louis (1966), "The representation of a graph by set intersections" (PDF), Canadian Journal of Mathematics, 18 (1): 106–112, doi:10.4153/CJM-1966-014-3, MR 0186575.
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7.
• McKee, Terry A.; McMorris, F. R. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, vol. 2, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3, MR 1672910.
• Szpilrajn-Marczewski, E. (1945), "Sur deux propriétés des classes d'ensembles", Fund. Math., 33: 303–307, MR 0015448.
• Schaefer, Marcus (2010), "Complexity of some geometric and topological problems" (PDF), Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers, Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, pp. 334–344, doi:10.1007/978-3-642-11805-0_32, ISBN 978-3-642-11804-3.
• Scheinerman, Edward R. (1985), "Characterizing intersection classes of graphs", Discrete Mathematics, 55 (2): 185–193, doi:10.1016/0012-365X(85)90047-0, MR 0798535.

추가 읽기

• 교차로 그래프 이론과 교차로 그래프의 중요한 특수 클래스에 대한 개요는 McKee & McMorris(1999년)를 참조하십시오.

외부 링크

• 얀 크라토치빌, 교차로 그래프 동영상 강의(2007년 6월)
• E. Prisner, 교차로 그래프 카운티를 통과하는 여정