다중 그래프

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

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

정의[편집]

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

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

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

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

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

관련 개념[편집]

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

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

참고 문헌[편집]

외부 링크[편집]