第5章 圖、walk、path與連通
5.1 圖由頂點和邊決定，不由畫法決定
本冊先用有限簡單無向圖 G=(V,E)。一條邊是兩個不同頂點組成的無序對；沒有自環，也不把同一對重複計為兩邊。畫在紙上的線若相交，只有交點被明確指定為頂點時才算接通。頂點的度數 deg(v) 是接到它的邊數；每條邊貢獻兩個端點，故所有度數和是 2|E|。
walk（遊走）是至少含一個頂點的序列，每相鄰兩項都要有邊，長度是步數，頂點與邊可以重複。頂點全不重複的 walk 稱簡單道路；只停在一個頂點是長度零的道路。若 walk 兩次到同一頂點，可剪去兩次之間的閉段。步數每次減少，最後得到同端點的道路。簡單環是至少三步的封閉 walk，起終點相同，其餘頂點互不重複且與起點不同。
能以道路相連的頂點構成連通關係：長度零保證自己連自己，反走保證對稱，接兩條再剪除重複保證傳遞。因此頂點分成互不相交的連通分量，孤立頂點各自成一分量。
5.2 四個例題
例題1 剪去中途折返
令頂點 A、B、C、D，邊 AB、BC、BD。A,B,C,B,D 每步有邊，是長度 4 的 walk，重訪 B 也重用 BC，故不是道路。剪去 B,C,B 的閉段，保留一次 B，得到 A,B,D，長度 2。
例題2 從邊表找全部分量
頂點 A 到 F，邊 AB、BC、DE。從 A 可達 B、C，不能到 D、E；D 和 E 互通；F 沒有邊。分量依次是 {A,B,C}、{D,E}、{F}，共三個。
例題3 度數和核對邊數
頂點 A 到 D，邊 AB、AC、BC、CD。度數分別是 2、2、3、1，總和 8，所以邊數 4。反過來，若抄到度數和 7，這張無向圖的抄表必有錯。
例題4 找不到路，也要給理由
在例題2，若 A 到 E 有道路，途中必第一次離開 {A,B,C}。但邊表中沒有跨出此集合的邊，所以不存在。只列幾條失敗的路不足以證明不連通。
5.3 練習
- B10-C05-Q01 頂點 A、B、C，邊 AB、BC。A,C 是 walk 嗎？
- B10-C05-Q02 同圖，A,B,A 是 walk 或道路？
- B10-C05-Q03 在 A、B、C 上沒有邊。分量數與度數和？
- B10-C05-Q04 A 到 D，邊 AB、AC、AD。求各點度數。
- B10-C05-Q05 某簡單無向圖有 7 條邊，度數和多少？
- B10-C05-Q06 在例題2加邊 CE，列出新分量。
- B10-C05-Q07 一條道路有 6 個頂點，長度幾步？
- B10-C05-Q08 圖畫上 AB 和 CD 交叉但沒標交點，A 能走到 D 嗎？若沒有其他邊。
- B10-C05-Q09 一張簡單無向圖若有兩個頂點度數為奇數，能斷定它連通嗎？
- B10-C05-Q10 為何同一頂點到自身允許長度零道路？
5.4 完整解答
Q01
不是。這是一步序列，需要 AC；兩步 A,B,C 才合法。
Q02
是 walk，因無向的 AB 可反向走。它重訪 A，也重用 AB，所以不是道路。
Q03
三點互相不可達，每點各一分量，度數和 0。
Q04
A 接到三條，其他三點各接一條，所以是 3、1、1、1，總和 6。
Q05
每邊的兩端各加一，故 2·7=14。
Q06
CE 把原來的 ABC 和 DE 連起來，F 仍無邊。新分量是 ABCDE 與 F。
Q07
相鄰頂點間各一步，6 個頂點有 5 個間隔，所以長度 5。
Q08
不能。邊只有兩個各自的端點對；交叉不新增頂點或邊，因此分量 AB 和 CD 分開。
Q09
不能。只含 AB 這一條邊，再加孤立頂點 C，度數為 1、1、0，仍有兩分量。
Q10
序列只含該點，沒有相鄰兩項需要檢查，且不重複頂點。這也讓孤立點與自己連通。