연결 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''연결 그래프'''(連結graph, {{llang|en|connected graph}})는 모든 두 꼭짓점 사이에 [[경로 (그래프 이론)|경로]]가 존재하는 [[그래프]]이다.

== 정의 ==
[[그래프]] <math>G</math>의 서로 다른 두 꼭짓점 <math>u,v\in V(G)</math>에 대하여, <math>u</math>와 <math>v</math> 사이의 [[경로 (그래프 이론)|경로]]가 존재한다면 두 꼭짓점이 '''연결되었다'''({{llang|en|connected}})고 한다.

[[파일:Sample-graph.jpg|thumb]]
'''연결 그래프'''({{llang|en|connected graph}})는 임의의 서로 다른 두 꼭짓점이 연결된 그래프이다. 그래프의 '''연결 성분'''({{llang|en|connected component}})은 (포함 관계에 대한) 극대 연결 [[부분 그래프]]이다.

=== 꼭짓점 연결성 ===
그래프 <math>G</math> 및 그 꼭짓점의 집합 <math>S\subset V(G)</math>에 대하여, 꼭짓점을 제거한 그래프 <math>G\setminus S</math>를 다음과 같이 정의하자.
* <math>V(G\setminus S)=V(G)\setminus S</math>
* <math>uv\in E(G\setminus S)\iff uv\in E(G)\quad\forall u,v\in V(G\setminus S)</math>
만약 <math>G\setminus S</math>가 비연결 그래프이거나 자명 그래프 <math>K_1</math>인 경우, <math>S</math>를 <math>G</math>의 '''꼭짓점 절단'''({{llang|en|vertex cut}})이라고 한다. 꼭짓점 절단들은 포함 관계에 따라서 [[부분 순서 집합]]을 이루며, 그 극소 원소를 '''극소 꼭짓점 절단'''({{llang|en|minimal vertex cut}})이라고 한다. 절단 가운데 크기가 가장 작은 것을 '''최소 꼭짓점 절단'''({{llang|en|minimum vertex cut}})이라고 한다. 그래프 <math>G</math>의 '''꼭짓점 연결성'''({{llang|en|vertex connectivity}}) <math>\kappa(G)</math>은 그 최소 꼭짓점 절단의 크기다.

그래프 <math>G</math> 및 [[기수 (수학)|기수]] <math>k</math>에 대하여, 만약 <math>k\le\kappa(G)</math>라면 <math>G</math>를 <math>k</math>-'''꼭짓점 연결 그래프'''({{llang|en|<math>k</math>-vertex-connected graph}})라고 한다. 연결 그래프는 1-꼭짓점 연결 그래프와 같다.

=== 변 연결성 ===
그래프 <math>G</math> 및 그 변의 집합 <math>T\subset E(G)</math>에 대하여, 변을 제거한 그래프 <math>G\setminus T</math>를 다음과 같이 정의하자.
* <math>V(G\setminus T)=V(G)</math>
* <math>uv\in E(G\setminus T)\iff uv\in E(G)\setminus T\quad\forall u,v\in V(G\setminus T)</math>
만약 <math>G\setminus T</math>가 비연결 그래프인 경우, <math>T</math>를 <math>G</math>의 '''변 절단'''({{llang|en|edge cut}})이라고 한다. 변 절단들은 포함 관계에 따라서 [[부분 순서 집합]]을 이루며, 그 극소 원소를 '''극소 변 절단'''({{llang|en|minimal edge cut}})이라고 한다. 절단 가운데 크기가 가장 작은 것을 '''최소 변 절단'''({{llang|en|minimum edge cut}})이라고 한다. 그래프 <math>G</math>의 '''변 연결성'''({{llang|en|edge connectivity}}) <math>\lambda(G)</math>은 그 최소 변 절단의 크기다. 크기가 1인 최소 변 절단을 '''다리'''({{llang|en|bridge}})라고 한다.

그래프 <math>G</math> 및 [[기수 (수학)|기수]] <math>k</math>에 대하여, 만약 <math>k\le\lambda(G)</math>라면 <math>G</math>를 <math>k</math>-'''변 연결 그래프'''({{llang|en|<math>k</math>-edge-connected graph}})라고 한다.

== 성질 ==
그래프 <math>G</math>가 연결 그래프라고 하자. 그렇다면, 다음 그래프들 역시 연결 그래프이다.
* <math>G</math>의 그래프 준동형사상에 대한 [[상 (수학)|상]] <math>\phi(G)</math>
* <math>G</math>의 [[선 그래프]] <math>L(G)</math>
그래프 <math>G</math>에 대하여, 다음이 성립한다.
:<math>\kappa(G)\le\lambda(G)\le\min_{v\in V(G)}\deg v</math>
차수가 <math>d\ge2</math>인 꼭짓점 추이적 그래프({{llang|en|vertex-transitive graph}}) <math>G</math>에 대하여, 다음이 성립한다.<ref>{{서적 인용|제목=Algebraic graph theory|총서=Graduate Texts in Mathematics|권=207|성=Godsil|이름=Chris|공저자=Gordon F. Royle|출판사=Springer|doi=10.1007/978-1-4613-0163-9|날짜=2001|isbn=978-0-387-95241-3|zbl=0968.05002|언어=en}}</ref>
:<math>\lceil 2(d+1)/3\rceil\le\kappa(G)\le\lambda(G)=d</math>
특히, <math>d=2,3,4</math>인 경우 <math>\kappa(G)=\lambda(G)=d</math>이다.

== 예 ==
간단한 그래프의 꼭짓점·변 연결성은 다음과 같다.
{| class="wikitable"
|-
! 그래프 !! 꼭짓점 연결성 !! 변 연결성
|-
| 비연결 그래프 || 0 || 0
|-
| [[완전 그래프]] <math>K_n</math> (<math>n\ge1</math>) || <math>n-1</math> || <math>n-1</math>
|-
| [[나무 (그래프 이론)|나무]] (꼭짓점 2개 이상) || 1 || 1
|-
| [[순환 그래프]] <math>C_n</math> (<math>n\ge3</math>) || 2 || 2
|-
| [[라도 그래프]] || <math>\aleph_0</math> || <math>\aleph_0</math>
|}

== 각주 ==
{{각주}}
* {{서적 인용|제목=Graph theory|총서=Graduate Texts in Mathematics|권=173|성=Diestel|이름=Reinhard|판=4판|날짜=2010|isbn= 978-3-642-14278-9|url=http://diestel-graph-theory.com/|zbl=1204.05001|언어=en}}

== 외부 링크 ==
* {{eom|title=Graph, connectivity of a}}
* {{매스월드|id=ConnectedGraph|title=Connected graph}}
* {{매스월드|id=DisconnectedGraph|title=Disconnected graph}}
* {{매스월드|id=BiconnectedGraph|title=Biconnected graph}}
* {{매스월드|id=k-ConnectedGraph|title=''k''-connected graph}}
* {{매스월드|id=EdgeConnectivity|title=Edge connectivity}}

{{전거 통제}}

[[분류:그래프 이론]]