선 그래프

위키백과, 우리 모두의 백과사전.
(라인 그래프에서 넘어옴)
이동: 둘러보기, 검색

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

정의[편집]

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

  • V(L(\Gamma))=E(\Gamma). 즉, 선 그래프의 꼭짓점은 원래 그래프의 변과 일대일 대응한다.
  • E(L(\Gamma))=\{(v_1v_2)(v_2v_3)\colon v_1v_2,v_2v_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에 대하여, 다음 두 조건이 서로 동치이다.

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

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

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

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

선 그래프의 반복[편집]

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

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

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

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

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

[편집]

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

참고 문헌[편집]

  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. MR0262097.
  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.

바깥 고리[편집]