오일러 회로 (Euler's Path), 오일러 서킷(Euler's Circuit)

 

Introduction

"비밀이 뭐냐면... 대학생활이 끝나면 방학이 없어져요...
무언가를 할 수 있는 내 시간이 없어진다...
대학시절의 방학은 '금'과 같은 것
하지만 사람은 그렇게 안한다. 불안하다. 문제없지만 불안하다.
길게 쉰다는 게 힘들고, 불가피하게 쉬는 것은 편하지 않다...
* 노는 것 부터 채워라 * 
11주 정도의 방학기간. 반을 놀아라 부디
자발적으로 할 수 있는 것을 하면서 놀아라.
즉, 놀지 말라. 노는 듯하지만 놀지 마라"

 

 

HW4
폭과 높이를 먼저 구해야 된다.

Visual 하기 전에 Hasse Diagram을 Excel 로 그려봐라 -> Coordination에 대한 감각

Grid를 확장하고 Node를 붙여넣는 방식

 

Graph

 

Isomorphism of Graph

iso == Equivalent, morphic == appearance

one to one correspondence and onto function.

일대일 대응하는 함수를 일컫는다. NOT Overlapped.

현실 세계의 친구관계와 인스타 계정 상의 팔로우 관계의 일대응 대응함을 비유로..

 

2D에서 표현하다보면 Overlapped 되는 것 처럼 보이지만 Rearrange 하면 Iso 함이 보일 수 있다.

 

Isomorphism을 찾기 위한 방법

One to one correspodence 함을 보여서 Isomophism 함을 보여야 한다.

Graph의 모든 Node의 Degree가 동일하다면 Iso 할 가능성이 높고, Graph Invariant가 그것을 일컫는다.

즉 Graph의 특징들을 말한다. 예를 들어, degree of vertices, number of edges, degree sequence...

 

Invariant가 유사한 Graph를 찾는 것 자체로 굉장희 의미있는 작업이다. 

 

Same Invariant 인 경우

Number of edge와 Degree number of n 등등이 같은 Invariant의 Graph가 있다면 어떻게 해야 한는가?

One to One correspondence function doman -> codomain 에 대한 적용을 진행해야 한다.

degree number 2와 연결되는 degree number 2가 없다.

하지만 H의 경우 degree number 2 와 연결되는 degree number 2가 존재한다.

즉. 일대일 대응하지 못하는 성질이 존재한다. 

즉, Invariant 간의 관계성에 대한 특징을 Enumeration하고 Correspondence 한지를 살펴보면 된다.

 

 

Euler Path

Path 란?

The sequence of edges(vertices)를 말한다.

Length of the Path 란?

The number of edge이다. 

 

Attributes

동일한 edge를 두 번 이상 가지고 있지 않으면 graph is simple 이라고 한다.

모든 Graph는 Euler Circute 이 있는 것은 아니다. Euler Path는 한붓그리기가 가능한 것이고

Euler Circuti은 한붓그리기로 시작했던 Node로 돌아와야 한다.

 

Euler Circuit

각각의 Vertice가 even degree를 가지고 있어야 한다는 것이 필수 조건이다. 

Euler Circuit이었던 Graph의 한 edge를 없애 버리면 그 두 개만 odd degree하게 된다.

즉, Euler Path이려면 두 개만 odd degree여야 한다.

 

모든 vertex의 degree가 짝수여야  Euler Ciruit을 가질 수 있다.

하나의 vertex에서 나가는 길 하나와 돌고 돌아 들어오는(Income) edge 이렇게 두 개는 항상 있어야 짝이 된다. 두 개가 있다면 해당 vertex로 들어온다면 항상 나가는 길은 다른 나머지 하나의 길로 나가게 된다는 것이다. 

Intermediate vertex도 마찬가지로 두 개가 존재하고 동일한 원칙으로 작동하게 된다.

 

Degree가 2이상인 Vertice가 있는 Digraph의 경우

Path가 모자라는 Graph가 존재하면 해당 Circuit을 떼어내면 Euler Circuit 한 그래프를 만족할 수 있다.

떼어내는 경우 역시 동일하게 Input 과 ouput 되는 edge가 없어지는 것이기 때문에 동일하게 유지된다.

 

Ciruit임을 각각 나누어서 밝히고 그것이 Connection 되어있다면 전체 Graph가 Euler's Circuit이다.

 

 

 

Hamilton Paths and Circuits

모든 vertex가 정확히 한 번 통과해서 모든 경로가 그려지는 것.

이는 알고리즘 이 없다.