【離散數學】Graph models

• Def：Graph
  
  
  一個 Graph G = (V, E) 由 V 與 E 兩個集合所組成，其中 V 為有限集合，其元素稱為頂點 (vertices)；而 E 之元素稱為連線 (edges)，為相異的頂點所成之配對。
  
  
  雖然我們稱 V 中元素為頂點，然而事實上 V 可為任意集合，不過是名字的差異。
  
  我們稱 E 中元素為連線，然而事實上我們只定義了其元素為兩個相異頂點的配對，通常我們使用數對來表示，而既然表示的是配對，順序便不構成差別：(a, b) = (b, a)。
  
  我們並未規定 E 包含了多少相異頂點之配對。
  
  
  我們可使用圖形來表示一個 Graph ，使用點代表每一個頂點，使用兩點間之連線代表兩頂點之配對。
  
  
  Graph 的圖形不會出現連回到同一點的線(loops)，那不是一個配對。

####

• Def：adjacent、path、circuit、 connected 
  
  
  1. 在一個 Graph 中，若 E 中存在某兩頂點之配對，則我們說該兩頂點相鄰 (adjacent)。
  
  2. 一個 path 是一個由相異的 vertices 組成之數列，記為 P = x₁-x₂- ... -x_n，而其中任意 x_i  與 x_i+1 及 x_i-1 必須相鄰。
  
  3. 若是  x₁-x₂- ... -x_n 中， x₁ 與 x_n 相鄰，則我們稱之為 circuit ，記做  x₁-x₂- ... -x₁ 。
  
  4. 若一個 Graph 中，任意兩頂點間，皆可找到一個 path 相連，我們稱這樣的 Graph connected。

• Def：disconnect
  
  
  disconnect 一個 connected  Graph 所指的是，透過自 V 中移除某些頂點，或自 E 中移除某些配對，使得剩下的 Graph 不再是一個  connected Graph。
  
  
  因為我們考慮的是剩下的 "Graph" ，因此若有一個頂點被移除掉，則與之相關的配對也要跟著移除，否則無法構成一個 Graph。
  而此剩餘的 Graph 被分解成數個互相不相連之區塊，而這些區塊有可能是一個 vertex，或是數個相連的 vertices。值得注意的是：若一個 Graph 存在一個孤立的頂點，則此 Graph 必不 connected ；然而反過來並不成立：若有一個 disconnected Graph ，並不代表此 Graph 中存在孤立的頂點。

• Def：directed Graph
  
  
  有方向性的 Graph 仍然是由 V 與 E 兩個集合組成，只是 E 中的元素不再只是配對，而是【有序的配對】，也就是說，順序不同的配對為不同之配對，我們以在數對上加一個箭號做為表示，而在圖形中，以連線加上箭號做為表示。
  
  
  在這樣的定義下，兩個不同的頂點間，可以有兩種配對。