6-1. 圖的種類及術語

Define Directed and Undirected Graph

$V \ne \emptyset$ ($V$: vertices set/nodes set), $E \subseteq V \times V$($E$: edges set) =

• { ($a$, $b$) | $a$, $b \in V$ }, 稱 $G$ = ($V$, $E$) 為一個 有向圖(directed graph/digraph)

  其中 ($a$, $b$) $\in E$ 為一個有序對(ordered pair), 表示一個有向邊(directed edge)

  • $a$: 起點(origin/source/initial vertex)
  • $b$: 終點(terminal node/terminus)

• { { $a$, $b$ } | $a$, $b \in V$ }, 稱 $G$ = ($V$, $E$) 為一個 無向圖(undirected graph)

  其中 { $a$, $b$ } = { $b$, $a$ } $\in E$ 為一個無序對(unordered pair), 表示一個無向邊(undirected edge)

  • 無向圖視為一有向圖時: { $a$, $b$ } = { ($a$, $b$), ($b$, $a$) }

Pseudograph Underlying G

將有向圖 $G$ 視為一無向圖時，此無向圖稱為以 $G$ 為基礎的虛擬圖(pseudograph underlying $G$)

Loop and Isolated Vertex

• 迴圈(loop): 一個邊起點與終點相同
  • 有向圖: ($a$, $a$)
  • 無向圖: { $a$, $a$ }
• 孤立點(isolated vertex): 一個點不為任何邊的起點

Define Simple Graph and Multigraph

$G$ = ($V$, $E$): graph, 重數(multiplicity): 兩點之間的邊數, 若 $G$ 中任兩點間

• 至多一邊相連: multiplicity $\le 1$，稱 $G$ 為簡單圖(simple graph)或線性圖(linear graph)

  至多一邊相連: 無 loop & 無重邊

• 至少兩邊相連: multiplicity $\ge 2$，稱 $G$ 為多重圖(multigraph)

$\rightarrow$ 往後章節在未特別指定下，一個 graph 視為 undirected simple graph!

Define Walk, Trail and Path

$G$ = ($V$, $E$): undirected graph, $P$: $v_0$ = x , $e_1$, $v_1$, $e_2$, $v_2$, ..., $e_n$, $v_n$ = y , $v_0$, ..., $v_n \in V$, $e_1$, ..., $e_n \in E$, 稱 $P$ 為 x-y 路(walk)

• 若 $P$ 不含重複點，稱 $P$ 為路徑(path)

• 若 $P$ 不含重複邊，稱 $P$ 為路線(trail)

  path $\Rightarrow$ trail, but trail 不一定 $\Rightarrow$ path

• x $=$ y: closed; x $\ne$ y: open

  • closed path: 環路(cycle)，規定至少含 3 邊，其中重複點不包括 x 及 y
  • closed trail: 迴路(circuit)，規定至少含 1 邊 $\therefore$ loop is a circuit, not a cycle.

    cycle $\Rightarrow$ circuit, but circuit 不一定 $\Rightarrow$ cycle

Define Connected Graph

$G$ = ($V$, $E$): undirected graph, 若 $G$ 中任兩點($\forall x$, $y \in V$, $x \ne y$)皆有 path 相連，則稱 $G$ 為連通圖(connected graph)，否則稱 $G$ 為不連通圖(disconnected graph)

當 $G$ 為 digraph 時，稱 $G$ 為(強)連通圖((strongly) connected graph)