Graph
Graph
A graph(or undirected graph) G consists of a set V of vertices(or nodes) and a set E of edges(or arcs) such that each edge e∈E is associated with an unordered pair of vertices.
G = (V , E)
A simple graph is a graph without loops or parallel edges.
Subgraph
Let G = (V, E) be a graph, we call (V', E') a subgraph of G if
(a) V'⊆V
(b) E'⊆E such that for every edge e'∈E', if e' is incident on v' and w', then v',w'∈V'.
Degree
The degree of a vertex v, denoted by δ(v), is the number of edges incident on v.
Theorems
if G is a graph with n vertices and m edges, then
sum(δ(vi))[i=1~n] = 2m
Path
A path from vo to vn of length n is an alternation sequence of n+1 vertices and n edges beginning with vertex vo and ending with vertex vn,
(vo, e1, v1, e2, v2, ..., vn-1, en, vn),
in which edge ei is incident on vertices vi-1 and vi for i = 1, ..., n
A simple path from v to w is a path from v to w with no repeated vertices.
Theorems
A graph has a path with no repeated edges from v to w(v≠w) containing all the edges and all vertices if and only if it is connected and v and w are the only vertices having odd degrees.
Cycle
A cycle(or circuit) is a path of nonzero length from v to v with no repeated edges.
A simple cycle is a cycle from v to v in which, except for the beginning and ending vertices that are both equal to v, there are no repeated vertices.
Theorems
If a graph G contains a cycle from v to v, G contains a simple cycle from v to v
connected
The connected graph is the graph in which for any vertices v and w in G, there is a path from v to w.
Complete
The complete graph on n vertices, denoted Kn, is the simple graph with n vertices in which there is an edge between every pair of distinct vertices.
Bipartite
The bipartite graph is the graph whose vertex set V is partitioned into sets V1 and V2 such that V1∩V2 = Φ, V1∪V2 = V, and each edge in E is incident on one vertex in V1 and one vertex in V2.
The complete bipartite graph on m and n vertices, denoted Km,n, is the simple graph whose vertex set is partitioned into sets V1 with m vertices and V2 with n vertices, and the edge set consists of all edges of the form (v1, v2) with v1∈V1, and v2∈V2.