그래프 이론에서 연결 그래프(連結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. doi:10.1007/978-1-4613-0163-9. ISBN 978-0-387-95241-3. Zbl 0968.05002. 

외부 링크

편집