**Proof - Euler Trail Theorem (1)**

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 nar..

**The Handshake Theorem and Its Corollary**

Prove that for , .Intuition: Suppose n people shake hands with other people in the group. They don't shake hands twice with the same person.How many handshakes take place?각 사람을 노드로 본다면 두 사람이 악수를 하면 그 두 노드 사이에 Edge 가 생긴다.전체 악수의 수 = Number of Edges in the graph = 각 사람이 한 악수의 수의 총합 / 2 = Sum of degree of every vertex / 2Let be the vertices of G and their degrees respectively. Also, Then we know tha..

**Loop Invariant Practice - Merge() of MergeSort()**

How to Think about Algorithms by Edmonds has good in-depth explanation of how to actually go about thinking about designing algorithms and approaching algorithmic problems. I applied the process to understanding Merge() routine of the MergeSort algorithm.

**공지사항**

**최근에 올라온 글**

**최근에 달린 댓글**

- Total
- 1,105

- Today
- 0

- Yesterday
- 4

**링크**

**TAG**

- Induction
- subgraph
- Component
- TIP
- HTTAA
- #BMI
- codomain
- image
- #Mutual_Exclusivity
- #Counting
- #state
- #props
- proof
- Edmonds
- #Constructive_Counting
- Graph
- #controlled_components
- #Combinations
- degree
- #Circular_Permutations
- #Permutations
- Circuit
- #Mutual_Exhaustivity
- relation
- surjective
- cycle
- trail
- #onChange
- definitions
- #uncontrolled_components