Graphic Theory (1)

A graph is a triple(V, E, g), where
(i) V is a finite none empty set, called the set of vertices;
(ii)E is a finite set(may be empty), called the set of edges; and
(iii)For none empty set E, g is a function, called an incidence function, that assigns to each edge, , a one-element subset {v} or a two-element subset {v,w}, where v and w are vertices.

在text中將連結v,w兩點的edge表示為g(e) = {v,w}

的endpoint v 和 e incident(相連)，相連的兩點v和w為adjacent(相鄰)。兩個共享同一vertex的edge也稱作adjacent，如果g(e) = {v}，則e is a loop on the vertex v or at the vertex v.

The incidence function 可用incidence table 來表達：

edge             | e1      | e2      | e3      | e4       | e5      |
end vertices | v1,v2 | v1,v2 | v4,v3 | v3, v4 | v4,v1 |

Let v be a vertex of a graph G. Then

Ng(v)稱作all neighbors of v, 也可以簡寫為N(v)。

使得

那麼Ng[v] (或N[v])稱作 the set of closed neighbors of v. (它包含v自己)

G is called a k-regular graph if the degree of each vertex is k.

而 Petersen graph 即為一個 3-regular graph。

Petersen graph的定義請見網路，是一個很優雅的圖形。