다중 그래프

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

다중 그래프. 회색의 원은 꼭짓점을, 푸른 선은 고리를, 붉은 선은 중복되는 변을, 검은 선은 중복되지 않는 변을 나타낸다.

정의편집

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

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

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

 

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

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

관련 개념편집

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

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

참고 문헌편집

외부 링크편집