Euler Trail

○Euler Trail

 ▷그래프의 한 vertex로부터 모든 edge들을 단 한번만 지나서 다른 vertex로 가는 길.

 ▷모든 edge를 지나는 Trail

 

 ▶Existence

 ▷전제: Undirected graph, Multigraph인 G가 isolated vertices를 가지지 않는다면

 ▷Euler Trail은 존재한다. ↔ G가 connected하고, 단 2개의 Vertices만 홀수의 degree를 가진다.

 ▷홀수 degree의 vertex: Trail의 시작과 끝.

 

 

○Euler Circuit

 ▷그래프의 한 vertex로부터 모든 edge들을 단 한번만 지나서 다시 vertex로 돌아오는 길.

 ▷모든 edge를 지나는 Circuit

 

 ▶Existence (Undirected)

 ▷전제: Undirected graph, Multigraph인 G가 isolated vertices를 가지지 않는다면

 ▷Euler Circuit은 존재한다. ↔ G가 connected하고, 모든 vertex가 짝수의 degree를 가진다.

 ▷짝수 Vertex이면 들어가고 나가는 길이 존재하기 때문.

 

 ▶Existence (Directed)

 ▷전제: Directed graph, Multigraph인 G가 isolated vertices를 가지지 않는다면

 ▷Euler Circuit은 존재한다. ↔ G가 connected하고, 모든 vertex가 id(v) = od(v)이다.

 ▷id(v) : Vertex에 들어오는 edge의 개수

 ▷od(v): Vertex에서 나가는 edge의 개수