Chapter 12
Graphs
Main topics
? Definition of graphs and some terminology
? Three common graph representations
? Some algorithms
12.1 Definition and terminologies
1,Definition of graphs:
Graph=(V,E)
V,nonempty finite vertice set
E,edge set
? Undirected praph,
If the tuple denoting an edge is unordered,
then (v1,v2) and (v2,v1) are the same
edge.
12.1 Definition and terminologies
? Directed graph:
If the tuple denoting an edge is ordered,then
(v1,v2) and (v2,v1) are different edges.
12.1 Definition and terminologies
? Example:
V2
V4
V3
V1 V(G
1)={V1,V2,V3,V4}
E(G1)={(V1,V2),(V1,V3),(V1,V
4),(V2,V3),(V2,V4),(V3,V4)}
V1 V2
V(G2)={V1,V2,,V3}
E(G2)={<V1,V2>,<V2,V1>,<V2,V3>}
V3
12.1 Definition and terminologies
? We will not discuss graphs of the following
types
12.1 Definition and terminologies
2.Complete graph
In an undirected graph with n nodes,the
number of edges <=n*(n-1)/2,If,=,is
satisfied,then it is called a complete
undirect graph.
V2
V4
V3
V1
12.1 Definition and terminologies
In a directed graph with n nodes,the number
of edges <=n*(n-1),If,=,is satisfied,then
it is called a complete directed graph.
12.1 Definition and terminologies
3.degree di of vertex i,TD(v):
is the number of edges incident on vertex i,
In a directed graph,
? in-degree of vertex i is the number of edges
incident to i,ID(v).
? out-degree of vertex i is the number of edges
from the i,OD(v),
12.1 Definition and terminologies
? TD(v)=ID(v)+OD(v)
Generally,if there are n vertices and e edges in
a graph,then
e=(?TD(vi))/2
v1 v2 v3 ID(v2)=1
OD(v2)=2
TD(v2)=3
i=1
n
12.1 Definition and terminologies
4,Subgraph
Graph G=(V,E),G’=(V’,E’),if V’?V,E’?E,
and the vertices incident on the edges in E’
are in V’,then G’ is the subgraph of G.
For example:
1
3 4
2 1 1
3 3
1
4
12.1 Definition and terminologies
? Another example:
V2
V4
V3
V1
V2 V3
V1
V1
12.1 Definition and terminologies
5.path.
? A sequence of vertices P=i1,i2,……i k is an i1 to ik path
in the graph of digraph G=(V,E) iff the edge(ij,ij+1)is in
E for every j,1<=j<k.
6,Simple path and cycle
? A Simple path is a path in which all vertices except
possibly the first and last,are different.
? A cycle is a simple path with the same start and end
vertex.
12.1 Definition and terminologies
? An example of a cycle
12.1 Definition and terminologies
7.Connected graph & connected component
? In a undirected graph,if there is a path from
vertex v1 to v2,then v1 and v2 are connected.
? In a undirected graph,if two arbitrary
vertices are connected,then the graph is a
connected graph.
12.1 Definition and terminologies
? Examples,
?Non-connected graph
?Maximum connected
subgraph(极大连通子图 )
is called connected
component,
12.1 Definition and terminologies
8,Strong connected graph
? A digraph is strongly connected iff it contains a
directed path from i to j and from j to i for every
pair of distinct vertices i and j.
? The maximum strong connected subgraph (极大
强连通子图 ) of a non-strongly connected graph is
called strongly connected conponent (强连通分
量 ).
12.1 Definition and terminologies
9,Network
? When weights and costs are assigned to
edges,the resulting data object is called
weighted graph and weighted digraph.
? The term network refers to weighted
connected graph and weighted connected
digraph,
12.1 Definition and terminologies
? Example of a network
V1
V3
V2
V4
V55
2
3
4
8
6
11
10
12.1 Definition and terminologies
10,Spanning tree
? A spanning tree of a connected graph is its
minimum connected subgraph(极小连通子图 ),
An n-vertex spanning tree has n-1 edges.
? For example:
1 1
2 23 3
4 4
12.2 ADT Graph and Digraph
? ADT 12.1
AbstractDataType Graph{
instances
a set V of vertices and a set E of edges
operations
Create(n):create an undirected graph with n
vertices and no edges
Exist(i,j),return true if edge(i,j)exists; false
otherwise
12.2 ADT Graph and Digraph
Edges():return the number of edges in the graph
Vertices():return the number of vertices in the graph
Add(i,j),add the edge(i,j) to the graph
Delete(i,j):delete the edge (i,j)
Degree(i),return the degree of vertex i
InDegree(i),synonym for degree
OutDegree(i),synonym for degree
}
12.2 ADT Graph and Digraph
? ADT 12.2
AbstractDataType Digraph{
instances
a set V of vertices and a set E of edges
operations
Create(n),create a directed graph with n
vertices and no edges
Exist(i,j),return true if edge(i,j)exists; false
otherwise
12.2 ADT Graph and Digraph
Edges():return the number of edges in the graph
Vertices():return the number of vertices in the graph
Add(i,j),add the edge(i,j) to the graph
Delete(i,j):delete the edge (i,j)
InDegree(i),return the in-degree of vertex i
OutDegree(i),return the out-degree of vertex i
}
12.3 Representation of graphs
and digraphs
1.Adjacency Matrix
G=(V,E),V={V1,V2,……,V n}
then the adjacency matrix of graph G:
A(i,j)=
1 If <i,j>,<j,i>?E or (i,j)?E
0 otherwise
12.3 Representation of graphs
and digraphs
? For example:
graph
V1
V2 V3
V4 A(i,j)=
0 1 1 1
1 0 1 1
1 1 0 0
1 1 0 0
1)Adjacency matrix of graph is a symmetric matrix
2) ?A(i,j)= ?A(j,i)=di (degree of vertex I)n
J=1
n
i=1
12.3 Representation of graphs
and digraphs
? Digraph
V1 V2
V5 V4
V3 A(i,j)=
0 1 0 0 0
1 0 0 0 1
0 1 0 1 0
1 0 0 0 0
0 0 0 1 0
1) ?A(i,j)= diout ?A(j,i)=diin
j=1
n n
j=1
12.3 Representation of graphs
and digraphs
? Representation of networks,replace 1 with
weights,others with ∞
W(i,j) If i!=j and <i,j>,<j,i>?E or(i,j)?E
∞ otherwise
A(i,j)=
12.3 Representation of graphs
and digraphs
? For example:
3 4
1 2
8
6
23
1
4
9 5
A(i,j)=
∞ 1 ∞ 4
∞ ∞ 9 2
3 5 ∞ 8
∞ ∞ 6 ∞
12.3 Representation of graphs
and digraphs
2,Linked-adjacency Lists
reduce the storage requirement if the number
of edges in the graph is small.
V1
V3V2
V4 4 3 02
4 3 01
1 2 0
1 2 0
1
2
3
4
h Data link
12.3 Representation of graphs
and digraphs
? Digraph:
V1 V2
V3
11
3
4
6
2
2 4 3 11 0
3 2 01 6
1 3 0
1
2
3
h Data cost link
2 6 3 3 0
2 2 0
1 4 0
1 11
1
2
3
h