연결 그래프

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

연결 그래프는 그래프의 임의의 두 꼭짓점 사이에 경로가 존재하는 그래프를 의미한다. 그래프가 얼마나 튼튼하게 연결되어 있는지를 나타내는 척도로 점 연결도와 변 연결도가 있으며, 유향 그래프에서는 강연결, 점 강연결도, 유향 변 강결합도 등의 개념이 사용된다. 연결 그래프의 성질과 관련된 다양한 정리와 알고리즘이 존재하며, 단절도, 정점 영역 연결도, 집합 간 연결도 등으로 일반화될 수 있다.

연결 그래프

📚 더 읽어볼만한 페이지

그래프 이론 - 다이어그램
다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다.
그래프 이론 - 쾨니히스베르크의 다리 문제
쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.

1. 개요
2. 정의
- 2.1. 꼭짓점 연결성 (점 연결도)
- 2.2. 변 연결성
3. 유향 그래프와 연결도
4. 성질
5. 관련 알고리즘
6. 일반화
7. 예

2. 정의

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

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

그래프가 얼마나 튼튼하게 연결되어 있는지를 나타내는 불변량으로 연결도가 있으며, 주로 점 연결도와 변 연결도로 분류된다.

2.1. 꼭짓점 연결성 (점 연결도)

그래프 $G$ 에서 제거하면 비연결 그래프가 되는 $k$ 개의 정점 집합을 $k$ -점 절단이라고 한다. $G$ 에서 $k$ -점 절단이 존재하는 최소의 $k$ 를 점 연결도 또는 연결도라고 하며, $\kappa(G)$ 또는 $\chi(G)$ 로 나타낸다. 특히, 1-점 절단을 절단점 또는 관절점이라고 부른다. $k$ -연결 그래프는 점 연결도가 $k$ 이상인 그래프이다.

그래프 $G$ 에서 $S$ 를 제거한 그래프에서 $x$ 와 $y$ 사이에 경로가 존재하지 않는 것을 정점 집합 $S$ 가 $x, y$ 를 분리한다고 한다. 그래프 $G$ 에서 (만약 존재한다면) 변 $xy$ 를 제거한 그래프에서 두 정점 $x, y$ 를 분리하는 데 필요한 정점의 개수를 $s$ 라고 할 때, $x, y$ 가 인접하지 않으면 $s$ 를, $x, y$ 가 인접해 있으면 $s + 1$ 을 $x, y$ 의 국소 연결도라고 하며, 보통 $\kappa(x, y)$ 로 나타낸다. 점 연결도는 국소 연결도의 최솟값과 일치한다.

그래프 $G$ 의 어떤 인자가 $k$ 연결이면, $G$ 자신도 $k$ 연결이 된다. $G$ 가 $k$ 연결이고, $G$ 자신을 제외한 인자가 $k$ 연결이 아닐 때 (즉, $G$ 에서 변을 하나라도 제거하면 $k$ 연결이 아닐 때), $G$ 를 극소 $k$ 연결이라고 한다.

2.2. 변 연결성

그래프에서 제거하면 비연결 그래프가 되는 k개의 변 집합을 k-변 절단 (또는 k-컷)이라고 한다. k-변 절단이 존재하는 최소의 k를 변 연결도라고 하며, $\lambda(G), \chi'(G)$ 로 표기한다. 특히, 1-변 절단을 절단 변 또는 다리(bridge^영어)라고 한다. k-변 연결 그래프는 변 연결도가 k 이상인 그래프를 가리킨다.

두 점을 분리하는 변 집합 크기의 최솟값으로 국소 변 연결도가 정의되며 $\lambda(x, y)$ 로 표기된다.

또한, $\lambda(G) = \min_{x, y \in V(G)} \lambda(x, y)$ 가 됨을 덧붙여 둔다.

3. 유향 그래프와 연결도

유향 그래프에서도 무향 그래프에서처럼 연결도에 해당하는 개념을 정의할 수 있다.

3.1. 강연결

유향 그래프가 강결합이라는 것은, 그래프 상의 임의의 두 점 사이에 유향 경로가 존재하는 것이다. 극대 강결합 부분 그래프는 강결합 성분이라고 한다.

3.2. 점 강연결도

어떤 두 점 를 지정했을 때, 제거함으로써 중 어느 쪽을 시작점으로 하더라도 유향 경로가 존재하지 않게 되는 점 집합의 크기의 최솟값으로, 의 국소 점 강연결도 (local vertex-strong connectivity)가 정의된다. 또한, 국소 점 강연결도의 최솟값을 점 강결합도 (vertex-strong connectivity)라고 부른다. 점 강결합도가 이상인 그래프를 점 강결합 그래프 (-strongly connected graph) 또는 강 그래프 (-strong graph)라고 부른다.

3.3. 유향 변 강연결도

어떤 두 점 를 지정했을 때, 제거함으로써 의 어느 쪽을 시작점으로 해도 유향 경로가 존재하지 않게 되는 변 집합의 크기 최소값을 의 국소 유향 변 강결합도라고 정의한다. 또한, 국소 유향 변 강결합도의 최소값을 유향 변 강결합도라고 부른다. 유향 변 강결합도가 이상인 그래프를 유향 변 강결합 그래프 또는 유향 변 강 그래프라고 부른다.

4. 성질

그래프 $G$ 에 대하여 다음이 성립한다.
: $\kappa(G)\le\lambda(G)\le\min_{v\in V(G)}\deg v$

* 그래프 $G$ 의 최소 차수를 $\delta(G)$ 로 나타내면, $\kappa(G) \leqq \lambda(G) \leqq \delta(G)$ 이다.
* 임의의 $l 에 대해, \kappa(G)=l, \lambda(G)=m, \delta(G)=n 을 만족하는 그래프 G 가 존재한다.$
* 2-연결 그래프의 임의의 정점은 사이클 위에 있다.
* 두 점 $x, y$ 사이의 서로 독립적인 경로 (점소 패스)의 최대 개수는 국소 연결도 $\kappa(x, y)$ 와 일치한다 (멩거 정리).
* 두 점 $x, y$ 사이의 변소 패스의 최대 개수는 국소 변 연결도 $\lambda(x, y)$ 와 일치한다 (멩거 정리).
* 임의의 $k$ 차원 다면체의 그래프의 정점 연결도는 $k$ 이다 (발린스키의 정리).

5. 관련 알고리즘

* k-정점 연결 요소 분해
* k-간선 연결 요소 분해
* 강결합 요소 분해

6. 일반화

* 단절점
* 정점 영역 연결도
* 집합 간 연결도

7. 예

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

👆

좌우로 밀어서 보기

그래프	꼭짓점 연결성	변 연결성
비연결 그래프	0	0
완전 그래프 $K_n$ ( $n\ge1$ )	$n-1$	$n-1$
나무 (꼭짓점 2개 이상)	1	1
순환 그래프 $C_n$ ( $n\ge3$ )	2	2
라도 그래프	$\aleph_0$	$\aleph_0$