無向圖 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
--
如果無向圖有一條歐拉迴路, 那麼每一點一定是偶點
如果無向圖有一條開放的歐拉行跡, 那麼一定恰好有兩個奇點
沒有留言:
張貼留言