1-1강 - Introduction (Euler' Graph)

1. Euler's Graph Modeling 9Seven Bridges of Konisberg)

cf> path & cycle

• walk : vertex와 edge가 교대로 나타나는 sequence (sequence 내의 edge는 앞 뒤의 vertex를 이어야 한다.)
• trail : [1] edge가 중복되지 않으며 [2] walk : vertex와 edge가 교대로 나타나는 sequence
• path : [1] vertex가 중복되지 않으며 [2] edge가 중복되지 않으며 [3] walk : vertex와 edge가 교대로 나타나는 sequence
• cycle : [1] 시작점과 끝점이 같은 [2] walk : vertex와 edge가 교대로 나타나는 sequence(사실상 trail과 path는 거의 같은 개념이다.)

1) Euler Cycle Problem

0> 문제 상황

• Given a graph G = (V, E) (V : set of vertices) (E : set of edges)

1> 문제 

• (조건에 맞는 경로가 존재한다면),
• [1] E의 모든 edge를 한 번씩만 지나는
• [2] cycle 찾기 (시작 vertex와 끝 vertex가 같은 walk)

2) Euler Path Problem

0> 문제 상황

• Given a graph G = (V, E) (V : set of vertices) (E : set of edges)

1> 문제

• (조건에 맞는 경로가 존재한다면),
• [1] E의 모든 edge를 한 번씩만 지나는
• [2] path(trail) 찾기 (vertex, edge가 각각 중복되지 않는 walk)

cf> 예제

- G1 : Euler Cycle

- G2 : Euler Path

- G3 : 존재하지 않는다.

 

3) Hamiltonian Path(Cycle) Problem

0> 문제 상황

• Given a graph G = (V, E) (V : set of vertices) (E : set of edges)

1> 문제

• (조건에 맞는 경로가 존재한다면),
• [1] V의 모든 vertex를 한 번씩만 지나는
• [2] cycle(path) 찾기 (vertex, edge가 각각 중복되지 않는 walk)

4) Travelling Sales Problem (TSP)

Hamiltonaian Cycle을 구할 때 edge cost의 합이 최소인 cycle 구하는 문제