연결 그래프

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

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

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

꼭짓점 연결성 
그래프  및 그 꼭짓점의 집합 에 대하여, 꼭짓점을 제거한 그래프 를 다음과 같이 정의하자.
 
 
만약 가 비연결 그래프이거나 자명 그래프 인 경우, 를 의 꼭짓점 절단()이라고 한다. 꼭짓점 절단들은 포함 관계에 따라서 부분 순서 집합을 이루며, 그 극소 원소를 극소 꼭짓점 절단()이라고 한다. 절단 가운데 크기가 가장 작은 것을 최소 꼭짓점 절단()이라고 한다. 그래프 의 꼭짓점 연결성() 은 그 최소 꼭짓점 절단의 크기다.

그래프  및 기수 에 대하여, 만약 라면 를 -꼭짓점 연결 그래프()라고 한다. 연결 그래프는 1-꼭짓점 연결 그래프와 같다.

변 연결성 
그래프  및 그 변의 집합 에 대하여, 변을 제거한 그래프 를 다음과 같이 정의하자.
 
 
만약 가 비연결 그래프인 경우, 를 의 변 절단()이라고 한다. 변 절단들은 포함 관계에 따라서 부분 순서 집합을 이루며, 그 극소 원소를 극소 변 절단()이라고 한다. 절단 가운데 크기가 가장 작은 것을 최소 변 절단()이라고 한다. 그래프 의 변 연결성() 은 그 최소 변 절단의 크기다. 크기가 1인 최소 변 절단을 다리()라고 한다.

그래프  및 기수 에 대하여, 만약 라면 를 -변 연결 그래프()라고 한다.

성질 
그래프 가 연결 그래프라고 하자. 그렇다면, 다음 그래프들 역시 연결 그래프이다.
 의 그래프 준동형사상에 대한 상 
 의 선 그래프 
그래프 에 대하여, 다음이 성립한다.

차수가 인 꼭짓점 추이적 그래프() 에 대하여, 다음이 성립한다.

특히, 인 경우 이다.

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

참고 문헌

외부 링크 
 
 
 
 
 
 

그래프 이론