그래프 이론3

이론 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) 한 약한 연결된 이중글자는