선 그래프

그래프 이론에서 선 그래프(線graph, 영어: line graph)는 어떤 그래프의 변들을 꼭짓점으로 삼고, 원래 그래프의 변의 인접 여부를 변으로 삼는 그래프이다. 끝을 선으로 연결한 그래프는 꺾은선 그래프라고 한다.

정의

(무향 단순) 그래프 $\Gamma$의 선 그래프 $L(\Gamma )$는 다음과 같은 그래프이다.

• $V(L(\Gamma ))=E(\Gamma )$. 즉, 선 그래프의 꼭짓점은 원래 그래프의 변과 일대일 대응한다.
• $E(L(\Gamma ))=\{(v_{1}v_{2})(v_{2}v_{3})\colon v_{1}v_{2},v_{2}v_{3}\in E(\Gamma )\}$. 즉, 선 그래프의 변은 원래 그래프의 서로 인접한 한 쌍의 변과 일대일 대응한다.

성질

연결 성분 $\Gamma _{1},\dots ,\Gamma _{c}$을 갖는 그래프의 선 그래프는 다음과 같다.

$L(\Gamma _{1}\sqcup \cdots \sqcup \Gamma _{c})=L(\Gamma _{1})\sqcup \cdots \sqcup L(\Gamma _{c})$

휘트니 정리(영어: Whitney theorem)에 따르면, 임의의 두 연결 그래프 $\Gamma _{1}$, $\Gamma _{2}$에 대하여, 다음 두 조건이 서로 동치이다.

• $L(\Gamma _{1})\cong L(\Gamma _{2})$
• $\Gamma _{1}\cong \Gamma _{2}$이거나, $\{\Gamma _{1},\Gamma _{2}\}=\{K_{3},K_{1,3}\}$이거나, $\{\Gamma _{1},\Gamma _{2}\}=\{K_{0},K_{1}\}$. 여기서 $K_{n}$은 완전 그래프, $K_{m,n}$은 완전 이분 그래프이다.

이는 해슬러 휘트니가 증명하였다.

선 그래프의 유도 부분 그래프로 존재할 수 없는 9개의 그래프

임의의 그래프 $\Gamma$에 대하여, 다음 두 조건이 동치이다.

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

선 그래프의 반복

유한 연결 그래프 $\Gamma$에 대하여, 다음 두 조건이 동치이다.

• $\Gamma \cong L(\Gamma )$
• $\Gamma$는 순환 그래프 $C_{n}$이다 ($n\geq 3$).

임의의 유한 연결 그래프 $\Gamma$에 대하여, 그래프의 열

$\Gamma ,L(\Gamma ),L(L(\Gamma )),\dots$

은 다음 네 가지 가운데 하나의 현상을 보인다.

• 만약 $\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 ))|$는 무한대로 발산한다.

연결 그래프가 아닌 경우, 각 연결 성분에 위 분류가 적용된다.

예

예를 들어 아래 그래프 $\Gamma$의 선 그래프 $L(\Gamma )$는 아래와 같다.

• 
  그래프 $\Gamma$
• 
  선 그래프 $L(\Gamma )$

외부 링크

• Weisstein, Eric Wolfgang. “Line graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.