Maths(三)---Graphs and Trees(1)

Definition of a Graph

undirected graph

例一.

vertex-set V(G) = {u, v, w, z}

edge-set E(G) = {e1, e2, e3, e4}

edge-endpoint function

Edge e1 e2 e3 e4

Endpoints {u, v} {u, w} {v, w} {w, z}

G = {V(G), E(G)}= {{u, v, w, z}, {e1, e2, e3, e4}}

directed graph

例一.
Vertex-set V(G) = {u, v, w, z
edge-set E(G) = {e1, e2, e3, e4}

edge-endpoint function:

Edge e1 e2 e3 e4

Endpoints (u, v) (w, u) (w, v) (z, w)

simple graph

V(G) = {u, v, w, z}

E(G) = {e1, e2, e3, e4, e5, e6, e7}

deg u = 6, deg v = 5, deg w = 2, deg z = 1

total degree = 6 + 5 + 2 + 1 = 14

edge-endpoint function:

Edge e1 e2 e3 e4 e5 e6 e7

Edgepoints {u, u} {u, w} {v, w} {v, z} {u, v} {u, v} {u, v}

Complete graph

Furthermore, the graph Kn is regular of degree n − 1, and has ( ) 0.5n (n −1) edges.

The Handshaking Lemma

例一.

the number of edges = 7

the sum of all the vertex-degrees = 6 + 5 + 2 + 1 = 14 (even)

= 2 × 7= twice the number of edges

the number of odd degree = 2 (even)