공장설계및실습 과제10.The Chinese Postman Problem
- 최초 등록일
- 2017.03.07
- 최종 저작일
- 2017.03
- 23페이지/ 한컴오피스
- 가격 3,000원
목차
Ⅰ. Introduction
Ⅱ. Solving procedures
Ⅲ. Solution
Ⅳ. 결론
본문내용
Find : why in which made procession could cross all seven bridges exactly once!
b. Definition
Euler path(tour) : A path(circuit) of a graph which traverses every edge of the graph exactly once. It begins & ends at the same node.
c. Euler Theorem
- A connected undirected graph possesses
- An Euler tour if & only if all nodes have even degree
- An Euler path if & only if exactly two nodes have odd degree
- A connected diagraph possesses
- An Euler tour if & only if the polarity of each made is zero.
d. Finding on Euler tour
- Begin at any node.
Traverse the edges deleting each as it is traversed
The choice of the edge from a node is arbitrary, except for the rules : Never traverse an edge which is a bridge(an edge whose deletion would disconnect the graph)
Ⅱ. Solving procedures
If and Euler tour exists, it is optimal route otherwise
- Add “artificial” edges, parallel to the existing edges, which turn all odd-degree nodes into even-degree nodes(there must be an even number of such odd-degree-nodes)
참고 자료
없음