Section 3.1: Euler Circuits
Definition: 將G的所有edges包含在內的circuit稱作Euler circuit。
Definition: 如果G為trivial graph，或G擁有Euler circuit，則G稱為Eulerian。
Theorem: 如果G是Eulerian，那麼G中的所有vertex的degree都為even。
Proof: 跳過。
Lemma: 如果G只有1或2個點，且每個頂點的degree都為even，那麼G有Euler circuit。
Theorem: 如果G是connected graph，且每個頂點的degree都為even，那麼G有Euler circuit。
Fleury's Algorithm: 用來在所有頂點的degree都為even的connected graph中建構Euler circuit，請見講義。
Hierholzerís Algorithm: 也是用來找出Euler circuit，講義寫的很麻煩，但其實就是把每個獨立的circuit找出來之後加入原本的circuit，請見講義。
Definition: 一個包含所有edges的open trail稱為Euler trail。
Theorem: Connected graph G有Euler trail若且唯若G只有兩個vertices其degree為odd。
在上面這個例子中，即是v6和v2。
Open trail不會回到原點。
Definition: Directed Euler circuit是在有向圖中包含了所有arcs的circuit。
Theorem: D是為一個weakly connected graph(某些點之間的連通為單向)，那麼D有directed Euler circuit若且唯若D中的每個vertex的indeg(v) = outdeg(v)。
也就是說出去和進來的數量相同!
Definition: (2, k)de Bruijn sequence是一個長度為2^k的word，由0和1組成，在依序掃過這個word的時候，長度為k的2^k個可能的word都會出現剛好一次。
例如說，10100011即是一個de Bruijn sequence。從第一個位元開始數起，會依序獲得101, 010, 100, 000, 001, 011, 111, 110。
Definition: (2, k)de Bruijn diagraph記作D 2,k，用寫的太麻煩了，請看講義。
Diagraph D 2,3為Eulerian。
Theorem: D 2,k均為Eulerian，k > 1。
Hamiltonian cycle, path
maximal non-Hamiltonian graph
Dirac Theorem and Ore Theorem
G + {uv}是什麼意思?
(Hamiltonian) closure of G, or cl(G)
Every tournament graph has a Hamiltonian directed path
Definition: 將G的所有edges包含在內的circuit稱作Euler circuit。
Definition: 如果G為trivial graph，或G擁有Euler circuit，則G稱為Eulerian。
Theorem: 如果G是Eulerian，那麼G中的所有vertex的degree都為even。
Proof: 跳過。
Lemma: 如果G只有1或2個點，且每個頂點的degree都為even，那麼G有Euler circuit。
Theorem: 如果G是connected graph，且每個頂點的degree都為even，那麼G有Euler circuit。
Fleury's Algorithm: 用來在所有頂點的degree都為even的connected graph中建構Euler circuit，請見講義。
Hierholzerís Algorithm: 也是用來找出Euler circuit，講義寫的很麻煩，但其實就是把每個獨立的circuit找出來之後加入原本的circuit，請見講義。
Definition: 一個包含所有edges的open trail稱為Euler trail。
在上面這個例子中，即是v6和v2。
Open trail不會回到原點。
Definition: Directed Euler circuit是在有向圖中包含了所有arcs的circuit。
Theorem: D是為一個weakly connected graph(某些點之間的連通為單向)，那麼D有directed Euler circuit若且唯若D中的每個vertex的indeg(v) = outdeg(v)。
也就是說出去和進來的數量相同!
Definition: (2, k)de Bruijn sequence是一個長度為2^k的word，由0和1組成，在依序掃過這個word的時候，長度為k的2^k個可能的word都會出現剛好一次。
例如說，10100011即是一個de Bruijn sequence。從第一個位元開始數起，會依序獲得101, 010, 100, 000, 001, 011, 111, 110。
Definition: (2, k)de Bruijn diagraph記作D 2,k，用寫的太麻煩了，請看講義。
Theorem: D 2,k均為Eulerian，k > 1。
Hamiltonian cycle, path
maximal non-Hamiltonian graph
Dirac Theorem and Ore Theorem
G + {uv}是什麼意思?
(Hamiltonian) closure of G, or cl(G)
Every tournament graph has a Hamiltonian directed path
留言
張貼留言