연결 그래프

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

그래프 이론에서, 연결 그래프(連結graph, 영어: connected graph)는 모든 두 꼭짓점 사이에 경로가 존재하는 그래프이다.

정의[편집]

그래프 의 서로 다른 두 꼭짓점 에 대하여, 사이의 경로가 존재한다면 두 꼭짓점이 연결되었다(영어: connected)고 한다.

연결 그래프(영어: connected graph)는 임의의 서로 다른 두 꼭짓점이 연결된 그래프이다. 그래프의 연결 성분(영어: connected component)은 (포함 관계에 대한) 극대 연결 부분 그래프이다.

꼭짓점 연결성[편집]

그래프 및 그 꼭짓점의 집합 에 대하여, 꼭짓점을 제거한 그래프 를 다음과 같이 정의하자.

만약 가 비연결 그래프이거나 자명 그래프 인 경우, 꼭짓점 절단(영어: vertex cut)이라고 한다. 꼭짓점 절단들은 포함 관계에 따라서 부분 순서 집합을 이루며, 그 극소 원소를 극소 꼭짓점 절단(영어: minimal vertex cut)이라고 한다. 절단 가운데 크기가 가장 작은 것을 최소 꼭짓점 절단(영어: minimum vertex cut)이라고 한다. 그래프 꼭짓점 연결성(영어: vertex connectivity) 은 그 최소 꼭짓점 절단의 크기다.

그래프 기수 에 대하여, 만약 라면 -꼭짓점 연결 그래프(영어: -vertex-connected graph)라고 한다. 연결 그래프는 1-꼭짓점 연결 그래프와 같다.

변 연결성[편집]

그래프 및 그 변의 집합 에 대하여, 변을 제거한 그래프 를 다음과 같이 정의하자.

만약 가 비연결 그래프인 경우, 변 절단(영어: edge cut)이라고 한다. 변 절단들은 포함 관계에 따라서 부분 순서 집합을 이루며, 그 극소 원소를 극소 변 절단(영어: minimal edge cut)이라고 한다. 절단 가운데 크기가 가장 작은 것을 최소 변 절단(영어: minimum edge cut)이라고 한다. 그래프 변 연결성(영어: edge connectivity) 은 그 최소 변 절단의 크기다. 크기가 1인 최소 변 절단을 다리(영어: bridge)라고 한다.

그래프 기수 에 대하여, 만약 라면 -변 연결 그래프(영어: -edge-connected graph)라고 한다.

성질[편집]

그래프 가 연결 그래프라고 하자. 그렇다면, 다음 그래프들 역시 연결 그래프이다.

  • 의 그래프 준동형사상에 대한
  • 선 그래프

그래프 에 대하여, 다음이 성립한다.

차수가 인 꼭짓점 추이적 그래프(영어: vertex-transitive graph) 에 대하여, 다음이 성립한다.[1]

특히, 인 경우 이다.

[편집]

간단한 그래프의 꼭짓점·변 연결성은 다음과 같다.

그래프 꼭짓점 연결성 변 연결성
비연결 그래프 0 0
완전 그래프 ()
나무 (꼭짓점 2개 이상) 1 1
순환 그래프 () 2 2
라도 그래프

참고 문헌[편집]

  1. Godsil, Chris; Gordon F. Royle (2001). 《Algebraic graph theory》. Graduate Texts in Mathematics (영어) 207. Springer. ISBN 978-0-387-95241-3. Zbl 0968.05002. doi:10.1007/978-1-4613-0163-9. 

외부 링크[편집]