선 그래프

3. 성질

연결 그래프의 선 그래프는 연결되어 있다. 원래 그래프에 임의의 두 변을 연결하는 경로가 있다면, 선 그래프에서는 이 경로에 해당하는 꼭짓점들이 경로를 형성한다.^[3] 그러나 고립된 꼭짓점을 가진 비연결 그래프도 연결된 선 그래프를 가질 수 있다.^[3]

선 그래프는 원래 그래프에 차수가 1이 아닌 단절선이 있을 때만 절점을 갖는다.^[1]

\(n\)개의 꼭짓점과 \(m\)개의 변을 가진 그래프 \(G\)의 선 그래프 \(L(G)\)는 \(m\)개의 꼭짓점을 가지며, \(L(G)\)의 변의 수는 \(G\)의 각 꼭짓점 차수의 제곱의 합을 2로 나눈 값에서 \(m\)을 뺀 값과 같다.^[4]

\(L(G)\)의 독립 집합은 \(G\)의 매칭과 일대일 대응 관계를 갖는다. 특히, \(L(G)\)의 최대 독립 집합은 \(G\)의 최대 매칭과 같다. 최대 매칭은 다항 시간 안에 찾을 수 있기 때문에, 선 그래프의 최대 독립 집합도 효율적으로 구할 수 있다.^[2]

그래프 \(G\)의 변 색수는 그 선 그래프 \(L(G)\)의 꼭짓점 색수와 같다.^[5]

변-추이 그래프의 선 그래프는 꼭짓점-추이 그래프이다.^[6]

만약 그래프 \(G\)가 오일러 사이클을 갖는다면, 즉 연결되어 있고 모든 꼭짓점의 차수가 짝수라면, \(G\)의 선 그래프는 해밀턴 그래프이다.^[7]

• \(L(\Gamma')\cong\Gamma\)인 그래프 \(\Gamma'\)이 존재한다.
• \(\Gamma\)는 그림에 제시된 9개의 특정 그래프들을 유도 부분 그래프로 포함하지 않는다.

3. 1. 휘트니 동형 정리

3. 2. 선 그래프의 반복

• 만약 \(\Gamma\)가 순환 그래프라면 이는 항등열이다.
• 만약 \(\Gamma\)가 완전 이분 그래프 \(K_{1,3}\)라면 \(C_3\cong L(G)\cong L(L(G))=\cdots\)이다.
• 만약 \(\Gamma\)가 경로 그래프 \(P_n\)이라면 \(L(P_n)=P_{n-1}\)이므로 결국 공 그래프 \(P_0\)이 된다.
• \(\Gamma\)가 순환 그래프, 경로 그래프, \(K_{1,3}\)이 아니라면, \(|V(L^n(\Gamma))|\)와 \(|E(L^n(\Gamma))|\)는 무한대로 발산한다.

• 만약 \(G\)가 사이클 그래프이면, \(L(G)\)와 이 수열의 각 후속 그래프는 \(G\) 자체와 동형이다. 이것들은 \(L(G)\)가 \(G\)와 동형인 유일한 연결 그래프이다.^[20]
• 만약 \(G\)가 갈고리 \(K_{1,3}\)이면, \(L(G)\)와 수열의 모든 후속 그래프는 삼각형이다.
• 만약 \(G\)가 경로 그래프이면, 수열의 각 후속 그래프는 결국 빈 그래프로 수열이 종료될 때까지 더 짧은 경로이다.
• 나머지 모든 경우에, 이 수열의 그래프 크기는 결국 무한대로 증가한다.

3. 3. 다른 그래프와의 관계

• 연결 그래프의 선 그래프는 연결되어 있다. 만약 그래프 G가 연결되어 있다면, 임의의 두 변을 연결하는 경로가 존재하고, 이는 L(G)의 임의의 두 꼭짓점을 포함하는 경로로 변환된다. 그러나 고립된 꼭짓점을 가지고 있어서 연결되지 않은 그래프 G는 그럼에도 불구하고 연결된 선 그래프를 가질 수 있다.^[3]
• 선 그래프는 기본 그래프에 차수가 1이 아닌 단절선이 있는 경우에만 절점을 갖는다.^[1]
• n개의 꼭짓점과 m개의 변을 가진 그래프 G의 경우, 선 그래프 L(G)의 꼭짓점 수는 m이고, L(G)의 변의 수는 G의 꼭짓점 차수의 제곱의 합의 절반에서 m을 뺀 값이다.^[4]
• L(G)의 독립 집합은 G의 매칭에 해당한다. 특히 L(G)의 최대 독립 집합은 G의 최대 매칭에 해당한다.^[2]
• 그래프 G의 변 색수는 선 그래프 L(G)의 꼭짓점 색수와 같다.^[5]
• 변-추이 그래프의 선 그래프는 꼭짓점-추이 그래프이다.^[6]
• 만약 그래프 G가 오일러 사이클을 가지고 있다면, 즉, G가 연결되어 있고 각 꼭짓점에 짝수 개의 변이 있다면, G의 선 그래프는 해밀턴 그래프이다.^[7]
• 두 개의 단순 그래프가 그래프 동형이면, 그들의 선 그래프도 동형이다. 휘트니 그래프 동형 정리는 연결된 그래프의 모든 쌍에 대해 이러한 관계의 역을 제공한다.
• 모든 선 그래프는 클로가 없는 그래프이며, 세 잎 트리 형태의 유도된 부분 그래프가 없는 그래프이다.^[18]
• 트리의 선 그래프는 정확히 클로가 없는 블록 그래프이다.^[16]

4. 예

다음은 그래프(왼쪽)와 그 선 그래프(오른쪽)를 보여주는 예시이다. 선 그래프의 각 꼭짓점은 원래 그래프에서 해당 모서리의 양 끝점 쌍으로 표시된다. 예를 들어, 오른쪽의 녹색 꼭짓점 1,3은 왼쪽의 파란색 꼭짓점 1과 3 사이의 모서리에 해당한다. 녹색 꼭짓점 1,3은 다른 세 개의 녹색 꼭짓점과 인접하는데, 이는 1,4 및 1,2 (파란색 그래프에서 꼭짓점 1을 공유하는 모서리에 해당)와 4,3 (파란색 그래프에서 꼭짓점 3을 공유하는 모서리에 해당)이다.

완전 그래프 $K\_n$의 선 그래프는 삼각 그래프, 존슨 그래프 $J(n,\; 2)$, 또는 크네저 그래프 $KG\_\{n,2\}$의 여그래프라고도 불린다.

5. 특징화

선 그래프는 다른 그래프의 간선 연결 구조를 나타내는 그래프로, 다음과 같은 특징을 갖는다.

• 클리크 분할: 선 그래프 L(G)는 클리크(모든 정점이 서로 연결된 부분 그래프)들로 분할할 수 있다. 이때, L(G)의 각 정점은 정확히 두 개의 클리크에 속해야 한다.^[18] 이러한 클리크 분할이 존재하고, L(G)의 두 정점이 동일한 두 개의 클리크에 모두 속하지 않는다면, L(G)는 어떤 그래프의 선 그래프가 된다.

• 휘트니 정리: 두 연결 그래프의 선 그래프가 동일하면, 원래 두 그래프도 동일하거나 특정한 예외 경우(완전 그래프 K₃, 완전 이분 그래프 K_1,3 또는 정점이 없거나 1개인 그래프)에 해당한다.
• 베이네케 정리: 선 그래프는 9개의 특정한 그래프를 유도 부분 그래프로 포함하지 않는다. 이 9개의 그래프는 와 같다. 즉, 어떤 그래프가 이 9개 그래프 중 하나라도 유도 부분 그래프로 가지면, 그 그래프는 선 그래프가 아니다.^[19]

6. 알고리즘

Roussopoulos, 1973와 Lehot, 1974는 선 그래프를 인식하고 원래 그래프를 재구성하는 선형 시간 알고리즘을 설명했다.^[1] Sysło, 1982는 이러한 방법을 방향 그래프로 일반화했다.^[2] Degiorgi, Simon, 1995는 정점 삽입 및 삭제에 따라 동적 그래프를 유지하고 각 단계에서 변경된 에지 수에 비례하는 시간 내에 입력의 선 그래프 표현(존재하는 경우)을 유지하기 위한 효율적인 데이터 구조를 설명했다.^[3]

Roussopoulos, 1973와 Lehot, 1974의 알고리즘은 홀수 삼각형(선 그래프에서 삼각형 꼭짓점의 홀수 개수에 인접한 다른 정점이 있는 속성이 있는 삼각형)과 관련된 선 그래프의 특징을 기반으로 한다.^[1] 그러나 Degiorgi, Simon, 1995의 알고리즘은 휘트니의 동형 정리만 사용한다.^[3] 나머지 그래프가 선 그래프가 되도록 하는 삭제를 인식해야 한다는 점이 복잡하지만, 정적 인식 문제에 특화되면 삽입만 수행하면 되며 알고리즘은 다음 단계를 수행한다.

• 입력 그래프 ''L''을 한 번에 하나의 정점을 추가하여 구성하고, 각 단계에서 이전에 추가된 정점과 인접한 정점을 추가할 정점을 선택한다. ''L''에 정점을 추가하는 동안, 그래프 ''G''를 유지한다. 알고리즘이 적절한 그래프 ''G''를 찾지 못하면 입력은 선 그래프가 아니며 알고리즘이 종료된다.
• ''G''에 네 개 이하의 정점이 있는 그래프에 정점 ''v''를 추가할 때, 선 그래프 표현이 고유하지 않을 수 있다. 그러나 이 경우, 증가된 그래프는 선 그래프로 표현할 수 있을 정도로 작으므로 무차별 대입 검색을 통해 상수 시간 내에 찾을 수 있다.
• 다른 그래프 ''G''의 선 그래프와 같은 더 큰 그래프 ''L''에 정점 ''v''를 추가할 때, ''S''를 ''L''에서 ''v''의 이웃에 해당하는 에지로 형성된 ''G''의 부분 그래프로 한다. ''S''가 하나의 정점 또는 두 개의 인접하지 않은 정점으로 구성된 정점 덮개를 갖는지 확인한다. 덮개에 두 개의 정점이 있는 경우, 이 두 정점을 연결하는 에지(''v''에 해당)를 추가하여 ''G''를 증가시킨다. 덮개에 정점이 하나만 있는 경우, 이 정점에 인접한 새로운 정점을 ''G''에 추가한다.

7. 일반화

중간 그래프는 평면 그래프의 선 그래프와 관련되며, 다면체 절단 연산과 관련이 있다. 최대 정점 차수가 3인 평면 그래프의 선 그래프는 평면 그래프이며, 모든 평면 임베딩은 임베딩으로 확장될 수 있다. 그러나 차수가 더 높은 평면 그래프의 선 그래프는 비평면 그래프가 될 수 있다. 중간 그래프는 최대 차수가 3인 평면 그래프의 선 그래프와 일치하지만, 항상 평면 그래프이다. 중간 그래프는 라인 그래프와 동일한 정점을 가지지만, 엣지는 잠재적으로 더 적다. 정다면체 또는 단순 다면체의 경우, 중간 그래프 연산은 다면체의 각 정점을 그에 인접한 모든 엣지의 중점을 통과하는 평면으로 잘라내는 연산으로 기하학적으로 표현될 수 있으며, 이는 두 번째 절단, 퇴화 절단, 또는 정류로 다양하게 알려져 있다.^{[22][23][24][25][26][27]}

그래프의 전체 그래프는 정점 또는 변을 정점으로 가지며, 두 요소가 인접하거나 인접할 때마다 두 요소 사이에 변을 갖는다. 전체 그래프는 각 변을 세분화한 다음 세분화된 그래프의 제곱을 취하여 얻을 수도 있다.^[28]

선 그래프의 개념은 멀티그래프인 경우로 확장될 수 있다. 멀티그래프의 경우, 동일한 선 그래프를 갖는 비동형 그래프 쌍의 수가 더 많다. 예를 들어 완전 이분 그래프는 동일한 수의 간선을 가진 쌍극자 그래프 및 섀넌 멀티그래프와 동일한 선 그래프를 갖는다. 그럼에도 불구하고, Whitney의 동형 정리와 유사한 내용들이 이 경우에도 여전히 파생될 수 있다.^[29]

참조

_[1] 학술 p. 71
_[2] 서적 Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives https://books.google[...] John Wiley & Sons
_[3] 학술 p. 32 https://books.google[...]
_[4] 학술 Theorem 8.1, p. 72
_[5] 서적 Graph Theory https://books.google[...] Springer
_[6] 서적 Topics in graph automorphisms and reconstruction https://books.google[...] Cambridge University Press
_[7] 학술 Theorem 8.8, p. 80
_[8] 학술 Theorem 8.3, p. 72
_[9] 학술
_[10] 저널 Which graphs are determined by their spectrum? https://research.til[...]
_[11] 학술 Theorem 8.6, p. 79
_[12] 저널 The strong perfect graph theorem http://annals.prince[...]
_[13] 학술 Theorem 8.7, p. 79
_[14] 학술
_[15] 저널 Graphs with 1-factors American Mathematical Society
_[16] 학술 Theorem 8.5, p. 78
_[17] 저널 Maximum induced trees in graphs
_[18] 학술 Theorem 8.4, p. 74
_[19] 학술
_[20] 학술
_[21] 학술 Theorem 8.11, p. 81
_[22] 학술
_[23] 저널 The medial graph and voltage-current duality
_[24] 서적 Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985) New York Acad. Sci.
_[25] 서적 Polyhedra: A Visual Approach University of California Press
_[26] 서적 Space Structures—their Harmony and Counterpoint Birkhäuser
_[27] 웹사이트 Rectification
_[28] 학술 p. 82
_[29] 학술
_[30] 저널 The Clique Complex and Hypergraph Matching 2001-01-01
_[31] 서적 Beiträge zur Graphentheorie Teubner 1968
_[32] 저널 Characterizations of derived graphs 1970
_[33] 저널 The interchange graph of a finite graph