선 그래프

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

정의

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

• $V(L(\mathrm{\Gamma }))=E(\mathrm{\Gamma })$. 즉, 선 그래프의 꼭짓점은 원래 그래프의 변과 일대일 대응한다.
• $E(L(\mathrm{\Gamma }))=\{(v_1{v}_2)(v_2{v}_3):v_1{v}_2,v_2{v}_3\in E(\mathrm{\Gamma })\}$. 즉, 선 그래프의 변은 원래 그래프의 서로 인접한 한 쌍의 변과 일대일 대응한다.

성질

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

$L({\mathrm{\Gamma }}_1\bigsqcup \cdots \bigsqcup {\mathrm{\Gamma }}_c)=L({\mathrm{\Gamma }}_1)\bigsqcup \cdots \bigsqcup L({\mathrm{\Gamma }}_c)$

휘트니 정리(틀:Llang)에 따르면, 임의의 두 연결 그래프 ${\mathrm{\Gamma }}_1$, ${\mathrm{\Gamma }}_2$에 대하여, 다음 두 조건이 서로 동치이다.

• $L({\mathrm{\Gamma }}_1)\cong L({\mathrm{\Gamma }}_2)$
• ${\mathrm{\Gamma }}_1\cong {\mathrm{\Gamma }}_2$이거나, $\{{\mathrm{\Gamma }}_1,{\mathrm{\Gamma }}_2\}=\{K_3,K_{1,3}\}$이거나, $\{{\mathrm{\Gamma }}_1,{\mathrm{\Gamma }}_2\}=\{K_0,K_1\}$. 여기서 $K_n$은 완전 그래프, $K_{m,n}$은 완전 이분 그래프이다.

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

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

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

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

선 그래프의 반복

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

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

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

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

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

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

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

예

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

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

외부 링크

• 틀:매스월드