방향성 그래프는 arc안에서 완전 그래프 Kn의 변환하는 각 edge를 얻엇다면 유명한 n개의 정점을 가진 토너먼트이다. 다시말해서, 어떤 토너먼트는 완전그래프의 한 방향이다. 이 종류의 방향성는 그래프는게임들의 결과들을  기억하는데 사용한 뭔애기인지 모르겟음

토너먼트

방향성 없는 edge를 방향성 있는 edge인 arc로 바꾸고

A->B  A는 B를 이긴다? 뭐 이런 관계

Theorem 3.4  (해밀턴 그래프가 되기 위한 필요 조건)

IF G = (V, E) 는 해밀턴이고  어떤 V의 적어도 한개를 포함하고 있는  재대로된 서브 집합이면, 그래프 G-W는 거의|W|를 가진다.

Proof. Gi (i=1,2, . . . . . , k) 는 G-W의 분명한 요소들이며, 그리고  C는 그래프 G안에 어떤 해밀턴 사이클이다. G이다. 만약 C안의 최근 정점이 that  Gi에 속하고 ui에 의해 조짐이 보여지며, 사이클 안에 그 정점 즉시 후히 ui, 각 i 에 W안에 필요하다.. 그래서 각 요소 정의들은 W안에 한 독특한 정점이다. 이러한 이유로,  분명한 요소들의 수는 W의 카디널리티를 초과 할 수 없다.

example 5

이론 3.4의 과목은 실패이다. 그 완전 이분 그래프 K2,n (where n>2) 절단 정점을 가지며, 그러나 이것은 헤밀턴은 아니다.

우리는  spanning cycles들의 존재에 몇가지 충분 조건을 얻을 것이고  쳅터의 끝 풀이 문제들 안에 임의의 그래프 안에 spanning paths. n개의 정점이 있는 간단한 그래프와 많은 애지가 가능한 완벽 그래프, 어떤 카디널리 헤밀턴.  다시말해서, 각 정점의 차수가 n-1이면, 그 그래프는 해밀턴이다.  대체가능한  이 필요한 더 약한 상황이고 연결된 그래프 안에 해밀턴 사이클의 증명을 아직 보장하는가? 이점에서 , 앞에서 언급한 충분 기준은 우아한 결과이다.

이론 3.5 (Ore's Theorem: A sufifcient condition for a graph to be Hamiltonian). n개의(where n>2) 정점들을 가진 간단한 그래프는 해밀턴 그래프이다. 만약 인접해있지 않은 정점들의 모든 pair의 차수들의 합이 최근에 n이다.

proof n개의 정점들을 가진 그래프 G를 가정하고 불평등조건을가진며 해밀턴이 아니다. 그래서 t소수의 edge와 함께 완전그래프 Kn의 서브그래프이다. 우리는 그래프에 edge들을 인접하지 않은 정점들을 재귀적으로  더한다. 아직 우리는 그래프 H  각각 that 더한다 하나 더 edge 연결하여 두 인접하지 않은 정점들 H안에 

이건 나중에하자 번역힘듬

이론3.6 n 정점들(where n>2)가진 심플 그래프는 해밀턴이면 모든 정점의 차수는 최근 n/2이다

pfoof.

Example 6 이론 3.5와 이론 3.6 둘다 다루어보자 실패이다. 5개에서 좀더 많은 정점들을 가진 순환 그래프는 해밀턴 그래프이며, 그러나  그래프안에 모든 정점 차수는 오직 2이다.  정점들의 모든 쌍의 차수의 합은 오직 4이다.

이론 3.7 n개의 정점들을 가진 그래프 G는 해밀턴 연결이다. 어느 두개의 인접하지 않은 정점들의 차수의 합이 n보다 더하다?. 특히, 이것이 해밀턴 연결이면 각 정점의 차수는 n/2보다 더하다?

http://itphotostory.tistory.com/53

http://www.mediawiki.org/wiki/Manual:Enable_TeX/ko#.EB.A6.AC.EB.88.85.EC.8A.A4.EC.97.90.EC.84.9C_.EC.84.A4.EC.B9.98.ED.95.98.EA.B8.B0

Hamiltonian graphs and digraphs

한 그래프 안에 두 정점들 사이에 한 path는 해밀턴 path 이면 이것은 그래프의 모든 정점들을 통하는 pass이다. 한 가까운 해밀턴 path는 그래프 안에  해밀턴 사이클이라고 불린다. 다시 말해서, 한 해밀턴 path는 spanning path이며, 또 해밀턴 cycle은 spanning cycle이다. 해밀턴 그래프는 해밀턴 사이클을 가진 그래프이다. 모든 해밀턴 그래프는 해밀턴 path 가지고 있으며, 그러나 정반대는 진실이 아니다; 그래프에 path를 고려해야된다. 해밀턴 그래프의 우리의 논의는, 우리는 간단한 그래프들 우리의 주의를 제한한다. 왜냐하면 즉시 정점을 통한 pass를 고려해야된다. 유도된 그래프들의 경우 안에, 정의들 유사하다.

오일러 그래프와 달리, 여긴 해밀턴 그래프들의 묘사는 우아하지 않으며(쉽게 검증가능), 많은 필요족건을 통하여 짝수이고 많은 충분 조건은 알려진 spanning cycles의 존재이고 연속된 그래프안에 spanning paths고 약한 연결 방항성그래프이다. 물론, 어떤 해밀턴 그래프는 필연적으로 2-연결된 이전 정점의 삭제로부터 그래프 결과들 연결된 그래프 안에 해밀턴 path를 가진다.(??)   그 결과, 그래프 아님과 함께 절단 정점 해밀턴이다. 모든 사이클 그래프는 해밀턴이며, 또한 모든 완전 그래프 이며 3개 또는 더 많은 정점들을 가진다. 연결된 상호 그래프 Km.n은 해밀턴이면 오직 m=n 성립한다.

따라서 필요한 조건은 fact의 간단한 일반화  그것은 해밀턴 그래프의  정점이 없는 절단 정점이다.

이론 3.2 한 연결된 그래프 경우만 semi-Eulerian이며, 오직 그래프가 연결되고 홀수 정점들의 수 정확히 두 경우 이다.(몰겟다..) 더욱이, 한 semi-Eulerian graph 안이면, 어떤 Eulerian 흔적 두 홀수 정점들 사이이다.

(문제 3.11. 풀면 볼 수 있다.)

Example3.  그림 3-1(a) 안에 semi-Eulerian 그래프 안에, 정점들 1과 4는 홀수이고 남아있는 정점들은 짝수이다.  그래프 안에 어떤 Eulerian trail은 정점 1과 4사이에 trail이다.

우리는 여기서 유도된 그래프 개념의 몇가지의 간단한 확대를 현재 고려해야한다. D는 약한 연결 이중글자라고 하자.  정점 v에 다른 정점 w에서 D 안의 유도된  Eulerian trail은 D의 모든 arcs(아크s)에 포함된 유도된 trail이며, 그리고 유도된 D는 semi-Eulerian 이면 이것은 유도된 Eulerian trail을 가진다.

D안에 유도된 Eulerian circuit는 유도된 노선이고 모든 arcs 포함되며, 그리고 이중글자는 만약 모든 arcs가 포함되면  Eulerian이다. 수치는 3-14(a) 보여준다. Eulerian trail 1->5->1->4->5->4->3->2->5->2 정점 1에서 정점 2로부터, 그리고 이 이중글자 semi-Eulerian이다. 수치 3-14(b)는 이중글자와 함께 Eulerian 노선 1->2->3->2->5->3->4->1->4->5->1보여주며, 그리고 이것은 이중글자 Eulerian이다.

다음 이론은 Eulerian and semi-eulerian digraphs의 특징이 된다.

이론 3.3. (i) 한 약한 연결된 이중글자는 

반복1: 우리는 정점 2로 시작면서,  v(0)이다. 이것이 현재 정점이다. e(1)로  edge {2,4} 선택한다. 이것은 현재 edge이며, 그걸 삭제한다. 정점 4 지금부터 v(1)된다.그 갱신된 G(1) 그래프는 그림 3-3안에 보여준다.

반복2: 현재 정점은 v(1)과 우리는 현재 edge e(2)로 {v(1),6} 선택한다.  그걸 삭제한다. 정점 6은 지금 v(2)이다. 갱신한 그래프 G(2)는 그림 3-4안에 보여준다.

반복3: e(3)으로 {v(2),5} 선택하며, 이것을 삭제한다. 정점 5는 v(3)이다. 갱신한 그래프 G(3)은 그림 3-5안에 보여준다.

반복4:  현재의 edge e(4)로써 v(3)와 정점3 사이의 하나 선택한다. 그리고 삭제한다. 정점 3은 v(4)이며, 갱신한 그래프 G(4)는 3-6에서 보여준다.

반복5: 현재 정점은 v(4)이며, 우리는 정점과 함께 edge 사건을 선택을 가진다. 그 edge는 v(4) 그리고 v(0)에 연결되며 이후 bridge이며 선택되지 않는다. 대신에, 우리는 v(4) and v(1) edge를 연결하고 e(5)쪽의 edge는 삭제한다. 이 단계에서, 정점 v(1)은 갱신된 레이블에서 v(5) 가진다. 그 갱신된 그래프 G(5)는 그림 3-7안에서 보여준다.

반복6: 현재 정점은 v(5)이며, 그리고 오직 edge만으로 정점은 정점 v(3)과 연결되는 bridge  이다.그것은(v3) 현재 레이블 v(6) 얻는다. bridge e(6) 삭제하며, 마킹하면서 v(5) 또한 떨어진 정점이며, 3-8안에 그림에서 보여준다.

반복7: v(6),v(4) edge 연결을 선택하고 e(7) 삭제한다. v(4)의 새로운 래이블에 v(7)이며, 3-9에 그림으로 보여준다.

반복8: {v(4),v(0)} 선택하고 e(8), 삭제한다. 지금 v(0)은 레이블 v(8)을 가진며, 그림 3-10과 같이 나타낸다.

반복9: {v(8), 1} 선택하고 e(9), 삭제한다.

반복10: {(9),v(2)} 선택하고 e(10), 삭제한다. 정점 v(2) 레이블 수정되어 v(10) 이며, 그림 3-12에서 보여준다.

반복11: {v(10), v(8)} 선택하고 e(11), 삭제한다. 정점 v(8)은 레이블 v(11) 수정되며, 그림 3-13과 같이 나타넨다. 이 단계에서, 우리는 edge가 없는 그래프를 가지며, 알고리즘은 종료된다. edge들의 순서 e(1),e(2)....e(3)은 그래프 안에  Eulerian circuit 가진다.

다이그래프 ( 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이다.