연결 그래프

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

정의

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

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

꼭짓점 연결성

그래프 $G$ 및 그 꼭짓점의 집합 $S\subset V(G)$에 대하여, 꼭짓점을 제거한 그래프 $G\setminus S$를 다음과 같이 정의하자.

• $V(G\setminus S)=V(G)\setminus S$
• $uv\in E(G\setminus S)\iff uv\in E(G)\quad \forall u,v\in V(G\setminus S)$

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

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

변 연결성

그래프 $G$ 및 그 변의 집합 $T\subset E(G)$에 대하여, 변을 제거한 그래프 $G\setminus T$를 다음과 같이 정의하자.

• $V(G\setminus T)=V(G)$
• $uv\in E(G\setminus T)\iff uv\in E(G)\setminus T\quad \forall u,v\in V(G\setminus T)$

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

그래프 $G$ 및 기수 $k$에 대하여, 만약 $k\leq \lambda (G)$라면 $G$를 $k$-변 연결 그래프(영어: $k$-edge-connected graph)라고 한다.

성질

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

• $G$의 그래프 준동형사상에 대한 상 $\phi (G)$
• $G$의 선 그래프 $L(G)$

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

$\kappa (G)\leq \lambda (G)\leq \min _{v\in V(G)}\deg v$

차수가 $d\geq 2$인 꼭짓점 추이적 그래프(영어: vertex-transitive graph) $G$에 대하여, 다음이 성립한다.

$\lceil 2(d+1)/3\rceil \leq \kappa (G)\leq \lambda (G)=d$

특히, $d=2,3,4$인 경우 $\kappa (G)=\lambda (G)=d$이다.

예

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

그래프	꼭짓점 연결성	변 연결성
비연결 그래프	0	0
완전 그래프 $K_{n}$ ($n\geq 1$)	$n-1$	$n-1$
나무 (꼭짓점 2개 이상)	1	1
순환 그래프 $C_{n}$ ($n\geq 3$)	2	2
라도 그래프	$\aleph _{0}$	$\aleph _{0}$

각주

• Diestel, Reinhard (2010). 《Graph theory》. Graduate Texts in Mathematics (영어) 173 4판. ISBN 978-3-642-14278-9. Zbl 1204.05001.  CS1 관리 - 추가 문구 (링크)

외부 링크

• “Graph, connectivity of a”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Connected graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Disconnected graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Biconnected graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “k-connected graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Edge connectivity”. 《Wolfram MathWorld》 (영어). Wolfram Research.