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

정의

편집

(무향 단순) 그래프  선 그래프  는 다음과 같은 그래프이다.

  •  . 즉, 선 그래프의 꼭짓점은 원래 그래프의 변과 일대일 대응한다.
  •  . 즉, 선 그래프의 변은 원래 그래프의 서로 인접한 한 쌍의 변과 일대일 대응한다.

성질

편집

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

 

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

  •  
  •  이거나,  이거나,  . 여기서  완전 그래프,  완전 이분 그래프이다.

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

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

임의의 그래프  에 대하여, 다음 두 조건이 동치이다.[1][2]

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

선 그래프의 반복

편집

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

  •  
  •  순환 그래프  이다 ( ).

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

 

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

  • 만약  가 순환 그래프라면 이는 항등열이다.
  • 만약  완전 이분 그래프  라면  이다.
  • 만약  경로 그래프  이라면  이므로 결국 공 그래프  이 된다.
  •  순환 그래프경로 그래프 또는  가 아니라면,   는 무한대로 발산한다.

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

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

각주

편집
  1. Beineke, L. W. (1968). 〈Derived graphs of digraphs〉. H. Sachs, H.-J. Voss, H.-J. Walter. 《Beiträge zur Graphentheorie》 (영어). Leipzig: Teubner. 17–33쪽. 
  2. Beineke, L. W. (1970). “Characterizations of derived graphs”. 《Journal of Combinatorial Theory》 (영어) 9 (2): 129–135. doi:10.1016/S0021-9800(70)80019-9. MR 0262097. 
  3. van Rooij, A. C. M.; Herbert Wilf (1965). “The interchange graph of a finite graph”. 《Acta Mathematica Hungarica》 (영어) 16 (3–4): 263–269. doi:10.1007/BF01904834. 

외부 링크

편집