선 그래프

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

 정의 
(무향 단순) 그래프 의 선 그래프 는 다음과 같은 그래프이다.
 . 즉, 선 그래프의 꼭짓점은 원래 그래프의 변과 일대일 대응한다.
 . 즉, 선 그래프의 변은 원래 그래프의 서로 인접한 한 쌍의 변과 일대일 대응한다.

 성질 
연결 성분 을 갖는 그래프의 선 그래프는 다음과 같다.

휘트니 정리()에 따르면, 임의의 두 연결 그래프 , 에 대하여, 다음 두 조건이 서로 동치이다.

 이거나, 이거나, . 여기서 은 완전 그래프, 은 완전 이분 그래프이다.
이는 해슬러 휘트니가 증명하였다.

섬네일|오른쪽|선 그래프의 유도 부분 그래프로 존재할 수 없는 9개의 그래프
임의의 그래프 에 대하여, 다음 두 조건이 동치이다.
 인 그래프 이 존재한다.
 는 9개의 특별한 그래프들을 유도 부분 그래프로 포함하지 않는다 (그림 참조).

 선 그래프의 반복 
유한 연결 그래프 에 대하여, 다음 두 조건이 동치이다.

 는 순환 그래프 이다 ().
임의의 유한 연결 그래프 에 대하여, 그래프의 열

은 다음 네 가지 가운데 하나의 현상을 보인다.
 만약 가 순환 그래프라면 이는 항등열이다.
 만약 가 완전 이분 그래프 라면 이다.
 만약 가 경로 그래프 이라면 이므로 결국 공 그래프 이 된다.
 가 순환 그래프나 경로 그래프 또는 가 아니라면, 와 는 무한대로 발산한다.
연결 그래프가 아닌 경우, 각 연결 성분에 위 분류가 적용된다.

 예 
예를 들어 아래 그래프 의 선 그래프 는 아래와 같다.

 각주 

 외부 링크 


분류:그래프족