第十二章：簡單圖

簡單圖由頂點和邊組成，邊連接兩個頂點，且不包含自環或重邊。它是描述對稱關係的基本模型。

12.1 頂點鄰接與度數

頂點的度數： 與該頂點相連的邊數。
握手引理： 對於任何圖，所有頂點的度數之和等於邊數的兩倍。
$\sum_{v \in V} \deg(v) = 2|E|$

這個定理之所以稱為「握手引理」，是因為如果一個人與另一個人握手，這件事會被雙方各算一次。

操作說明： 點擊空白處新增頂點，拖曳頂點連接邊，右鍵點擊頂點刪除。觀察下方的數值變化。

頂點數 (V): 0 邊數 (E): 0 度數和 ($\sum \deg$): 0 驗證: ✅

圖著色的目標是為每個頂點分配一種顏色，使得相鄰的頂點顏色不同。所需的最少顏色數稱為「色數」。

試著用下方的顏色為左邊的圖上色，目標是相鄰節點顏色不同。

選擇顏色：

目標： 這是一個 $K_4$ 完全圖。

提示：每個點都與其他點相連。

準備中...

如果兩個圖可以透過重新標記頂點而變得相同，則它們是「同構」的。這意味著它們在結構上是等價的。

下方的兩個圖看起來不同，但它們是同構的嗎？

教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)