(덕성여대 수학과)

Sec5. 연결성

이산수학 <Ch3> Path and cycles (10.4~10.6)

이상준 교수

(덕성여대 수학과)

교재 : Robin J. Wilson

Introduction to Graph Theory, 4^th ed 강의 슬라이드 : 이상준, 오연주(15)

길(walk)

„ 정의:

„① 길(walk)이란 그래프의 한 정점에서 시작하여 인접한 정점들로 지나가는 일련의 모서리들이다.

„ 𝑣_" → 𝑣_$ → 𝑣_% → ⋯ → 𝑣_'

„② 𝑣_"를 시작 정점이라 하고, 𝑣_'을 끝 정점이라 한다.

„③ 길(walk)의 길이는 모서리의 수이다.

„ 예제:

„① v→w→x→y→z→z→y→w 는 길이 7의 길(walk)이다.

„② v : 시작 정점, w : 끝 정점

Trail, path, cycle

„ 정의:

„ 추적(trail)은 모서리를 한번씩만 이용하는 길이다. (중복 모서리가 없슴)

„ 경로(path)는 정점을 한번씩만 이용하는 길가다. (중복 정점이 없슴)

„예외: 시작정점과 끝정점은 같을 수 있다.

„ 시작 정점과 끝 정점이 같을 때, 추적(trail) 또는 경로(path)가 폐쇄되었다(closed)고 한다.

„ 사이클(cycle)은 폐쇄된 경로(closed path)이다.

„ 예제:

„ 길이 4의 경로(path)

„ 길이 6의 사이클(cycle)

연결그래프 (connected graph)

„ 정의: 비방향성 그래프에서 모든 정점들의 쌍 사이에 경로가 존재한다면, 그래프는 연결되었다(connected)라고 한다.

„ 예제:

„ 질문: 그래프가 얼마나 강하게 연결되어 있나?

„그래프가 연결되지 않기 위해 얼마나 많은 모서리와 정점들이 제거해야 할까?

Separating set

„ 정의:

„ 연결된 그래프에서 separating (vertex) set는

정점을 지우면 G가 연결되지 않게 되는 정점의 집합이다.

„ cut-vertex는 하나의 정점을 가진 separating set이다.

„ 예제:

k-connected

„ 정의:

„연결된 그래프 G의 연결성 k(G)는

정점을 지우면 G가 연결되지 않게 되는 정점들의 최소한의 수이다.

„k(G)≥k 이면, G가 k-connected 라 한다.

„ 예제:

Disconnecting set

„ 정의:

„연결된 그래프 G에서 disconnecting (edge) set은

모서리를 제거하면 G가 연결되지 않게 되는 모서리의 집합이다.

„cutset은

minimal

„브릿지(bridge)는 하나의 모서리를 가진 cutset이다.

„ 예제:

„{ab,ac,bd,dc}는 disconnecting set이고 cutset이다.

„{ab,ac,ad,ed}는 disconnecting set이고 cutset이다.

„bc는 브릿지이다.

k-edge connected

„ 정의:

„ 그래프 G의 모서리 연결성 𝝀(𝐆)은

모서리를 제거했을 때 G가 연결되지 않게 되는 모서리의 최소한의 수이다.

„ 𝜆(G) ≥ 𝑘 이면, G가 k-edge connected 라고 한다.

„ 예제:

연습

Sec6. Eulerian 그래프

이산수학 <Ch3> Path and cycles (10.4~10.6)

이상준 교수

(덕성여대 수학과)

강의 슬라이드 : 이상준, 오연주(15) 교재 : Robin J. Wilson

Introduction to Graph Theory, 4^th ed

„ 정의:

„ ① G의 모든 모서리를 포함하는 폐쇄된 추적(trail)이 있다면, 연결 그래프는 Eulerian이다.

„ ② 이러한 추적(trail)이 Eulerian trail이다.

„ ③ G의 모든 모서리를 포함하는 추적(trail)이 있다면, non-Eulerian graph G는 semi-Eulerian이다.

„ 예제:

„ ①

„ ②

„ ③

„ 역사: Königsberg의 다리 문제

„질문: 그림 6.4와 같이 각각 7개의 다리를 정확히 한 번 건너서 시작점으로 되돌 아 올 수 있을까?

„ 관찰: 만일 G가 Eulerian이면, G의 각 정점의 차수(degree)는 짝수이다.

„증명:

„ 정리: 연결 그래프 G가 Eulerian일 필요충분조건은 G의 각 정점의 차수(degree)가 짝수인 것이다.

„증명:

„ 따름정리6.4: 연결 그래프가 semi-Eulerian일 필요충분조건은 홀수 차수(degree)의 정점을 정확히 두 개 가지는 것이다.

„ 예제: ① ② ③

연습

Sec6. Hamiltonian 그래프

이산수학 <Ch3> Path and cycles (10.4~10.6)

이상준 교수

(덕성여대 수학과)

강의 슬라이드 : 이상준, 오연주(15) 교재 : Robin J. Wilson

Introduction to Graph Theory, 4^th ed

Hamiltonian 그래프

„ 질문: 그래프 G의 각 정점을 정확히 한 번씩 지나가는 사이클(cycle)가 있나?

„ 정의:

„ ① Hamiltonian cycle은 G의 각 정점을 정확히 한 번씩 지나가는 사이클(cycle)이다.

„ ② 그래프 G가 Hamiltonian cycle을 가지고 있다면, G는 Hamiltonian이라고 한다.

„ ③ 모든 정점을 지나가는 경로(path)가 있다면, G는 semi-Hamiltonian이라고 한다.

„ 예제:

„ 정리(Ore 1960): G를 n(≥3)개의 정점을 가진 단순 그래프라고 가정하자.

인접하지 않은 정점 v와 w의 각각의 쌍에 대해서, deg(v)+deg(w) ≥ n 이면, G는 Hamiltonian이다.

„ 증명:

„ 따름정리: G를 n(≥3)개의 정점을 가진 단순 그래프라고 가정하자.

각 정점 v에 대해, deg(v)≥⁰_% 이면, G는 Hamiltonian이다.

„ 증명:

연습

Sec8. 몇몇의 문제와 알고리즘(algorithms)

이산수학 <Ch3> Path and cycles (10.4~10.6)

이상준 교수

(덕성여대 수학과)

강의 슬라이드 : 이상준, 오연주(15) 교재 : Robin J. Wilson

Introduction to Graph Theory, 4^th ed

최단경로 문제

„ 문제: 이 길의 길이가 표시된 것과 같을 때, A부터 L까지 가장 짧은 경로의 길이는 무엇일까?

„ 알고리즘:

중국인의 우편 배달부 문제

„ 문제: 우편 배달부는 최소한의 총 거리를 다니고, 그의 시작점으로 돌아오면서 그의 편지를 배달하기를 원한다. 그는 어떻게 다녀야 할까?

여행하는 외판원 문제

„ 문제: 외판원은 가능한 최소한의 총 거리를 다니면서, 몇 개의 주어진 도시를 방문하 고 그의 시작점으로 돌아오기를 원한다. 그는 어떻게 다녀야 할까?

연습