다중 그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
다중 그래프. 회색의 원은 꼭짓점을, 푸른 선은 고리를, 붉은 선은 중복되는 변을, 검은 선은 중복되지 않는 변을 나타낸다.

그래프 이론에서, 다중 그래프(多重graph, 영어: multigraph 멀티그래프[*])는 두 꼭짓점 사이에 여러 변이 허용되는, 그래프의 일반화이다.

정의[편집]

다중 그래프 는 다음과 같은 순서쌍이다.

  • 집합이다. 이를 꼭짓점의 집합이라고 하며, 그 원소를 꼭짓점(영어: vertex)이라고 한다.
  • 집합이다. 이를 변의 집합이라고 하며, 그 원소를 (영어: edge)이라고 한다.
  • 함수이다. 여기서 이다. 만약 라면, 끝점(영어: endpoint)이라고 한다. 양 끝점이 같은 변을 고리(영어: loop 루프[*])라고 한다. 다중 그래프 의 꼭짓점의 집합은 , 변의 집합은 로 쓴다.

꼭짓점 차수(영어: degree) 는 다음과 같다.

즉, 고리들은 차수에서 두 배로 센다.

다중 그래프의 경우 그래프에 대한 대부분의 용어들이 적용되지만, 다른 경우도 있다. 예를 들어, 다중 그래프에서 변을 축약(영어: contraction)시키면, 중복되는 변들을 하나로 합치지 않으며, 고리 또한 남겨둔다.

관련 개념[편집]

(단순) 그래프는 고리가 없고, 두 꼭짓점 사이에 최대 하나의 변이 존재하는 다중 그래프이다. 반대로, 주어진 다중 그래프에서 변의 중복수를 잊고, 고리를 삭제한다면 그래프를 얻는다.

화살집(영어: quiver 퀴버[*])은 변이 방향을 갖춘 다중 그래프이다. 즉, 유향 그래프와 다중 그래프의 공통적인 일반화이다.

참고 문헌[편집]

외부 링크[편집]