그래프 이론 5

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보다 더하다?