圖論基礎 flashcards

Question 1

什麼是圖 $G=(V,E)$？

Accepted Answer

圖是一個有序對 $G=(V,E)$，其中 $V$ 是頂點（節點）的集合，而 $E$ 是邊的集合；每一條邊連接兩個頂點（在無向圖中，一條邊是無序對 $\{u,v\}$）。

Question 2

走訪（walk）、路徑（path）與迴圈（cycle）有何不同？

Accepted Answer

走訪可以重複頂點/邊。路徑是不重複頂點的走訪。迴圈是封閉的路徑（起點 = 終點），且除了第一個/最後一個頂點外不重複頂點。

Question 3

圖是平面圖（planar）代表什麼？連通平面圖的歐拉公式是什麼？

Accepted Answer

平面圖表示它可以畫在平面上且邊不交叉（除非在頂點處相交）。對於一個連通的平面嵌入，$$V-E+F=2,$$ 其中 $F$ 是面的數量（包含外部面）。

用 AI 掌握數學