離散數學›Ch6 圖論第 3 題/共 34 題
3. 圖論、尤拉迴路、有向圖
#LS-06-003中圖論尤拉迴路有向圖
Which ones of the following directed graphs are Eulerian?
參考答案與解析
答案 (C)。有向圖有 Eulerian circuit 若且唯若它連通,且每個頂點的入度等於出度。逐圖找入度與出度不相等的頂點:
- (A) 頂點 4 的入邊有 2→4、5→4、6→4、8→4 四條,出邊只有 4→8 一條,不是。
- (B) 頂點 3 的出邊有 3→4、3→7、3→8 三條,入邊只有 1→3、5→3 兩條,不是。
- (C) 8 個頂點的入度與出度都是 3,圖是強連通的,是。
- (D) 頂點 4 的出邊有 4→1、4→5、4→7、4→8 四條,入邊只有 6→4、2→4 兩條,不是(頂點 7 則是入度 4、出度 2)。
- (E) 與 (A) 相同,頂點 4 的入邊有 2→4、5→4、6→4、8→4 四條,出邊只有 4→8 一條,不是。
只有 (C) 符合。
📄 台大114
▤完整推導請見《WH 資工筆記 · 離散數學》Ch6 圖論