그래프이론 1

다이그래프 ( digraph )라고도 하는데, 간선에 방향이 있는 그래프

방향 그래프에서 정점 Vi에서 정점 Vj를 연결하는 간선, 즉 Vi→Vj를 <Vi, Vj>로 표현하고 화살표로 타나낸다.

그리고 Vi를 꼬리(Tail) Vj를 머리(head)라고 한다.

=> <Vi, Vj> ≠ <Vj, Vi>

참고 : http://jinsolkim.kr/50190210566

G 그래프 안의 두개의 분명한 정점들 사이에 한 흔적은 Eulerian trail이다  

그러면 G의 모든 edges 들어있다.

한 노선이 모든 edge를 포함하고 있는게 Eulerian circuit이다

한 그래프 semi-Eulerian(or unicursal)라고 하면 Eulerian trail 가진다.

한 Eulerian graph 는 한 Eulerian circuit 가지고 있는 graph이다.

그림 3-1 안에 (a)는, 노선{e1,e2,...e11}은 노드 1과 4 사이에 Eulerian trail, 이 그래프는 unicursal이다

그러나 Eulerian 아니다.

그림 3-1 안에 (b) graph는 하지만  Eulerian circuit{e1..e10}와 함께 Eulerian graph이다

이론 3.1 graph G=(V,E) 안에, 그 다음 4 상태들은 동등하다. (i) G는 Eulerian이다. (ii) G는 연결된 even 안에 각각의 정점이다, (iii)G는 연결되고 여기에 존재한다 분할 E의 각 edge 마다의 G안에 사이클에 나누어진 부분집합, and (iv) G는 연결되어있고 G안에 각 edge는 G안에 사이클의 홀 수 안에 edge이다.

예 1. 연결된 그래프 그림 3-1 각각 차수가 짝수이다. edge의 집합 분할 할 수 있다. into E1={e1,e4,e8}, E2={e2,e3},E3={e5,e6,e},and E4={e9,e10} 각 부분집합 안의 edge들 Eulerian graph 안에 cycle된다. edge e1에 합류하는 정점들 1과 2  한 edge  그래프 안에 15 cycle개가 있다.

1.

...

15.

Eulerian circuit

사이클 경우 수

우리는 G의 Eulerian circuit 에서 얻을 수 있다. 왜나하면 Eulerian graph G안에 edges의 집합은 edge-disjoint의 합이다. 그 알고리즘 다음과 같다:

step 1. 어느 정점 v 그리고 cycle C 구성으로부터 시작한다

step 2. 만약 C가 그래프의 모든 edges 포함한다면, 멈춘다. 만약 아니면, 선택한 정점 w을 C에 공통 구리고 subgraph G'는 C의 모든 에지를 삭제하면서 G를 얻는다.

step 3. w로 시작하면서, G'안에 사이클을 포함한다. 라고 C'를 말한다.

step 4. C와 C'의 edge와 G안에  circuit 얻는다. 그 새로운 circulit은 C이다. 그리고 step2 되돌아간다.

(문제 3.5 풀어보았다.)

우리는 지금 존재하는 다른 방법(Fleury's algorithm) 어느 노점각 정점은 짝수이며, 연결된  graph G=(V,E)  어느 정점으로 부터  Eulerian circuit 시작을 얻는다.

step 1. 처음에, i=0. 정점 v0 부터 시작하여 정의 T0 :v0

step 2. 

Example 2. 그림 3-2안에 그래프 G 연결되어(6개 정점 그리고 11개 edges), 그 각 정점의 degree는 짝수이다. Fleury 알고리즘을 사용하면, 그래프 안에 한 Eulerian circuit을  다음과 같이 얻을 수 있다.

여기서 11번 반복할 것이다, 그리고 결국에는, 우리는 서브 그래프와 함께 6개 정점에서 각 정점의 차수는 0이다.