PROFILPELAJAR.COM

그래프 이론에서 연결 그래프(連結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$ 에 대하여, 다음이 성립한다.^[1]

\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}$

각주

↑ 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.

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.