티스토리 뷰
An Euler trail is a walk that uses every edge of a graph exactly once.
An Euler circuit is a circuit that uses every edge of a graph exactly once.
A Euler trail with same endpoints is a Euler circuit.
Here are some examples:
Letbe a finite connected graph and
denote the number of vertices that have odd degrees.
Prove that G has a Euler trail if and only if .
First, by the Handshake Theorem, we can narrow down our range of :
An arbitrary can have
. We will now try to show that some subset of
, those that have Euler trails, have
.
Proof() : We know
such that
includes all edges of
exactly once.
Case 1 : has endpoints
It has middle vertices (vertices that are not endpoints).
By definition of a middle vertex, the trail does not end at , i.e. if it enters
it has to leave it through
an edge.
Therefore, we can easily see that has an even degree.
Now consider . They may appear in
multiple times but but each time they do so, they have a pair of edges entering and leaving them, EXCEPT when they are endpoints. In this case there's only
one edge leaving , the start of
, and only one entering
.
Hence have one more edge entering and one more edge leaving, respectively.
, so the claim holds in this direction.
Case 2 : has endpoints
, so we have an Eulerian cycle that starts and ends at
.
For every vertex other than
, edges in
leave it and every time they enter
.
has an even degree.
Consider . When it appears in
not as the start/end point of the cycle, same things happens to it as
.
As the 종점 of the cycle, an edge leaves in the beginning and enters it at the end.
has an even degree
as well.
, so the claim holds in this direction.
Contrapositives rule out the possibility of Euler trails in graphs with more than 2 odd degrees.
Proof() : See Proof - Euler Trail Theorem (2)
Generalize to a trail :
Consider a trail in any graph. If we see the trail as a subgraph on its own, this is an Euler trail. Then we can apply the Euler Trail Theorem to learn something about the degree of vertices in the trail.
'Comp Sci > Algorithms' 카테고리의 다른 글
[Math] Permutations, Combinations, and Multiplication (0) | 2018.06.19 |
---|---|
Proof - Euler Trail Theorem (2) (2) | 2017.12.23 |
Proof - Euler Trail Theorem (1) (2) | 2017.12.22 |
The Handshake Theorem and Its Corollary (0) | 2017.12.21 |
Loop Invariant Practice - Merge() of MergeSort() (0) | 2017.11.28 |
Java Implementation of Karatsuba's Algorithm (카라츠바 곱셈 알고리즘 구현) (0) | 2017.11.26 |
- TAG
- degree, Euler, Euler_circuit, Euler_trail_theorem, Graph, Handshake_theoerm, iff, proof, trail, vertex
-
jeongtaebang Component of subgraph G' partition G' because components by definition are maximally connected 2017.12.23 17:03 신고
-
jeongtaebang Need to revise conclusion
Finite connected simple graphs:
1) r = 0 <=> euler circuit exists
2) r = 2 <=> euler trail exists 2018.07.05 17:15 신고
- Total
- 1,011
- Today
- 0
- Yesterday
- 0
- TIP
- Component
- #BMI
- #Counting
- definitions
- relation
- Circuit
- Induction
- trail
- surjective
- Edmonds
- #Constructive_Counting
- image
- codomain
- #state
- #Mutual_Exhaustivity
- #onChange
- #Permutations
- proof
- #props
- #controlled_components
- #Mutual_Exclusivity
- #uncontrolled_components
- Graph
- #Combinations
- subgraph
- degree
- #Circular_Permutations
- HTTAA
- cycle