라인 그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

그래프 이론에서 그래프 G=(V,E)의 라인 그래프(line graph) L(G)란,

  • G의 변을 꼭지점으로 하고,
  • G의 두 변이 어느 꼭지점에서 만날 경우 그 두 변이 서로 인접한 것으로

정의한 그래프를 뜻한다.

예를 들어 아래 그래프 G의 라인 그래프 L(G)는 아래와 같다.