선 그래프

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

정의

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

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

성질

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

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

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

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

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

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

임의의 그래프 ${\displaystyle \Gamma }$에 대하여, 다음 두 조건이 동치이다.^[1][2]

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

선 그래프의 반복

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

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

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

${\displaystyle \Gamma ,L(\Gamma ),L(L(\Gamma )),\dots }$

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

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

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

예

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

• 
  그래프 ${\displaystyle \Gamma }$
• 
  선 그래프 ${\displaystyle L(\Gamma )}$