선 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''선 그래프'''(線graph, {{llang|en|line graph}})는 어떤 그래프의 변들을 [[꼭짓점]]으로 삼고, 원래 그래프의 변의 인접 여부를 변으로 삼는 그래프이다. 끝을 선으로 연결한 그래프는 '''꺾은선 그래프'''라고 한다.

== 정의 ==
(무향 단순) 그래프 <math>\Gamma</math>의 '''선 그래프''' <math>L(\Gamma)</math>는 다음과 같은 [[그래프]]이다.
* <math>V(L(\Gamma))=E(\Gamma)</math>. 즉, 선 그래프의 꼭짓점은 원래 그래프의 변과 [[일대일 대응]]한다.
* <math>E(L(\Gamma))=\{(v_1v_2)(v_2v_3)\colon v_1v_2,v_2v_3\in E(\Gamma)\}</math>. 즉, 선 그래프의 변은 원래 그래프의 서로 인접한 한 쌍의 변과 [[일대일 대응]]한다.

== 성질 ==
연결 성분 <math>\Gamma_1,\dots,\Gamma_c</math>을 갖는 그래프의 선 그래프는 다음과 같다.
:<math>L(\Gamma_1\sqcup\cdots\sqcup\Gamma_c)=L(\Gamma_1)\sqcup\cdots\sqcup L(\Gamma_c)</math>

'''휘트니 정리'''({{llang|en|Whitney theorem}})에 따르면, 임의의 두 [[연결 그래프]] <math>\Gamma_1</math>, <math>\Gamma_2</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* <math>L(\Gamma_1)\cong L(\Gamma_2)</math>
* <math>\Gamma_1\cong\Gamma_2</math>이거나, <math>\{\Gamma_1,\Gamma_2\}=\{K_3,K_{1,3}\}</math>이거나, <math>\{\Gamma_1,\Gamma_2\}=\{K_0,K_1\}</math>. 여기서 <math>K_n</math>은 [[완전 그래프]], <math>K_{m,n}</math>은 [[완전 이분 그래프]]이다.
이는 [[해슬러 휘트니]]가 증명하였다.

[[파일:Forbidden line subgraphs.svg|섬네일|오른쪽|선 그래프의 [[유도 부분 그래프]]로 존재할 수 없는 9개의 그래프]]
임의의 [[그래프]] <math>\Gamma</math>에 대하여, 다음 두 조건이 동치이다.<ref>{{서적 인용
 | last = Beineke | first = L. W.
 | 장 = Derived graphs of digraphs
 | editor = H. Sachs, H.-J. Voss, H.-J. Walter
 | location = Leipzig
 | pages = 17–33
 | publisher = Teubner
 | title = Beiträge zur Graphentheorie
 | 날짜 = 1968 | 언어=en}}</ref><ref>{{저널 인용
 | last = Beineke | first = L. W.
 | doi = 10.1016/S0021-9800(70)80019-9
 | journal = Journal of Combinatorial Theory
 | pages = 129–135
 | title = Characterizations of derived graphs
 | volume = 9
 | 날짜 = 1970
 | mr = 0262097
 | issue = 2  | 언어=en}}</ref>
* <math>L(\Gamma')\cong\Gamma</math>인 그래프 <math>\Gamma'</math>이 존재한다.
* <math>\Gamma</math>는 9개의 특별한 그래프들을 [[유도 부분 그래프]]로 포함하지 않는다 (그림 참조).

=== 선 그래프의 반복 ===
유한 [[연결 그래프]] <math>\Gamma</math>에 대하여, 다음 두 조건이 동치이다.
* <math>\Gamma\cong L(\Gamma)</math>
* <math>\Gamma</math>는 [[순환 그래프]] <math>C_n</math>이다 (<math>n\ge3</math>).
임의의 유한 [[연결 그래프]] <math>\Gamma</math>에 대하여, 그래프의 열
:<math>\Gamma,L(\Gamma),L(L(\Gamma)),\dots</math>
은 다음 네 가지 가운데 하나의 현상을 보인다.<ref>{{저널 인용
 | last = van Rooij | first = A. C. M.
 | 공저자 = Herbert Wilf
 | doi = 10.1007/BF01904834
 | issue = 3–4
 | journal = Acta Mathematica Hungarica
 | pages = 263–269
 | title = The interchange graph of a finite graph
 | volume = 16
 | year = 1965 | 언어=en}}</ref>
* 만약 <math>\Gamma</math>가 순환 그래프라면 이는 항등열이다.
* 만약 <math>\Gamma</math>가 [[완전 이분 그래프]] <math>K_{1,3}</math>라면 <math>C_3\cong L(G)\cong L(L(G))=\cdots</math>이다.
* 만약 <math>\Gamma</math>가 [[경로 그래프]] <math>P_n</math>이라면 <math>L(P_n)=P_{n-1}</math>이므로 결국 공 그래프 <math>P_0</math>이 된다.
* <math>\Gamma</math>가 [[순환 그래프]]나 [[경로 그래프]] 또는 <math>K_{1,3}</math>가 아니라면, <math>|V(L^n(\Gamma))|</math>와 <math>|E(L^n(\Gamma))|</math>는 무한대로 발산한다.
[[연결 그래프]]가 아닌 경우, 각 연결 성분에 위 분류가 적용된다.

== 예 ==
예를 들어 아래 그래프 <math>\Gamma</math>의 선 그래프 <math>L(\Gamma)</math>는 아래와 같다.
<gallery>
파일:Line graph construction (original).png|그래프 <math>\Gamma</math>
파일:Line graph construction (result).png|선 그래프 <math>L(\Gamma)</math>
</gallery>

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|id=LineGraph|title=Line graph}}

[[분류:그래프족]]