圖論 - 1 定義

無向圖 G = (V, E)

V : Vertex 點 

E : Edge 邊

--

e = {u, v} 

   e : edge 邊

   e is in E

   u, v 邊兩端點

   u, v is in V

--

deg(v) : 該點的度數 : 多少邊從該點引出

--

握手引理 : handshaking lemma

對任意無向圖 G = (V, E) , 

所有點的度數和, 為邊數量的兩倍: Sum( deg(V) ) = 2|E|

 

--

奇點 : 該點的邊數量為奇數個

偶點 : 該點的邊數量為偶數個

根據 握手引理 可知, 無向圖的奇點數目為偶數個

--

walk 道路 : 點邊的序列 : v0e1v1e2v2...eivi

trail 行跡： 一條邊不重複的道路

path 路徑 : 一條點不重複的道路

Euler trail / 歐拉行跡 : 有條行跡可以經過所有的邊

Euler tour / 歐拉迴路 : 封閉的歐拉行跡 

歐拉行跡 可以搭配 Leetcode 332 之類的題目來看 - kotlin leetcode 332

--

如果無向圖有一條歐拉迴路, 那麼每一點一定是偶點 

如果無向圖有一條開放的歐拉行跡, 那麼一定恰好有兩個奇點