DM Graphs

CHAPTER 7
Graph Theory
7.1. Graphs
7.1.1. Graphs. Consider the following examples:
1. A road map, consisting of a number of towns connected with

roads.
2. The representation of a binary relation defined on a given set.
The relation of a given element x to another element y is rep-
resented with an arrow connecting x to y.
The former is an example of (undirected) graph. The latter is an

example of a directed graph or digraph.
a b
d c
Figure 7.1. Undirected Graph.
In general a graph G consists of two things:
1. The vertex set V , whose elements are called vertices, nodes or

points.
2. The edge set E or set of edges connecting pairs of vertices. If
the edges are directed then they are also called directed edges
or arcs. Each edge e ∈ E is associated with a pair of vertices.
82
7.1. GRAPHS 83
a b
d c
Figure 7.2. Directed Graph.
A graph is sometimes represented by the pair (V, E) (we assume V

and E finite).
If the graph is undirected and there is a unique edge e connecting x
and y we may write e = {x, y}, so E can be regarded as set of unordered
pairs. In this context we may also write e = (x, y), understanding that
here (x, y) is not an ordered pair, but the name of an edge.
If the graph is directed and there is a unique edge e pointing from
x to y, then we may write e = (x, y), so E may be regarded as a set
of ordered pairs. If e = (x, y), the vertex x is called origin, source or
initial point of the edge e, and y is called the terminus, terminating
vertex or terminal point.
b
a
d c
Figure 7.3. Graph with parallel edges.
Two vertices connected by an edge are called adjacent. They are

also the endpoints of the edge, and the edge is said to be incident to
each of its endpoints. If the graph is directed, an edge pointing from
vertex x to vertex y is said to be incident from x and incident to y. An
edge connecting a vertex to itself is called a loop. Two edges connecting
the same pair of points (and pointing in the same direction if the graph
is directed) are called parallel or multiple.
7.1. GRAPHS 84
A graph with neither loops nor multiple edges is called a simple

graph. If a graph has multiple edges but no loops then it is called a
multigraph. If it has loops (and possible also multiple edges) then it is
called a pseudograph.
The following table summarizes the graph terminology
Table 7.1.1. Graph Terminology

Type Edges Multiple Edges Allowed? Loops Allowed?
Simple graph indirected no no
Multigraph indirected yes no
Pseudograph indirected yes yes
Directed graph directed no yes
Directed multigraph directed yes yes
The degree of a vertex v, represented deg(v), is the number of edges

that contain it (loops are counted twice). A vertex of degree zero (not
connected to any other vertex) is called isolated. A vertex of degree 1
is called pendant.
The Handshaking Theorem. Let G = (V, E) be an undirected graph
with e edges. Then
X
2e = deg (v) .
v∈V
(This applies even if multiple edges and loops are present.)
In a graph with directed edges, the in-degree of a vertex v, denoted
−
deg (v), is the number of edges with v as their terminal vertex. The
out-degree of a vertex v, denoted deg+ (v), is the number of edges with
v as their initial vertex. (Note that a loop at a vertex contributes 1 to
both the in-degree and the out-degree of this vertex.)
Number of vertices of odd degree. An undirected graph has an even
number of vertices of odd degree. Proof: Let Ve and Vo respectively
the set of vertices of even degree and the set of vertices of odd degree
in an undirected graph G = (V, E). Then
X X X
2e = deg (v) = deg (v) + deg (v) .
v∈V v∈Ve v∈Vo
Since deg(v) is even for v ∈ Ve , the first sum in the right hand side of
the equality is even. The total sum must be 2e, which is even, so the
second sum must be even too. But its terms are all odd, so there must
be an even number of them.
7.1. GRAPHS 85
Sum of degrees in an directed graph. Let G = (V, E) be a directed

graph. Then X X
deg− (v) = deg+ (v) = |E| .
v∈V v∈V
A weighted graph is a graph whose edges have been labeled with

numbers. The length of a path in a weighted graph is the sum of the
weights of the edges in the path.
a b
6 3
6
d 4 c
Figure 7.4. Weighted Graph.
7.1.2. Special Graphs. Here we examine a few special graphs.

The n-cube: A graph with with 2n vertices labeled 0, 1, . . . , 2n − 1
so that two of them are connected with an edge if their binary repre-
sentation differs in exactly one bit.
110 111
010 011
100 101
000 001
Figure 7.5. 3-cube.
Complete Graph: a simple undirected graph G such that every pair

of distinct vertices in G are connected by an edge. The complete graph
of n vertices is represented Kn (fig. 7.6). A complete directed graph is
a simple directed graph G = (V, E) such that every pair of distinct
vertices in G are connected by exactly one edge—so, for each pair of
distinct vertices, either (x, y) or (y, x) (but not both) is in E.
7.1. GRAPHS 86
e b
d c
Figure 7.6. Complete graph K5 .
Bipartite Graph: a graph G = (V, E) in which V can be partitioned

into two subsets V1 and V2 so that each edge in G connects some vertex
in V1 to some vertex in V2 . A bipartite simple graph is called complete
if each vertex in V1 is connected to each vertex in V2 . If |V1 | = m and
|V2 | = n, the corresponding complete bipartite graph is represented
Km,n (fig. 7.7).
A graph is bipartite iff its vertices can be colored with two colors
so that every edge connects vertices of different color.
Question: Is the n-cube bipartite. Hint: color in red all vertices

whose binary representation has an even number of 1’s, color in blue
the ones with an odd number of 1’s.
p
a
q
b
r
c
s
Figure 7.7. Complete bipartite graph K3,4 .
Regular Graph: a simple graph whose vertices have all the same
degree. For instance, the n-cube is regular.
7.1.3. Subgraph. Given a graph G = (V, E), a subgraph G0 =

(V , E 0 ) of G is another graph such that V 0 ⊆ V and E 0 ⊆ E. If
0
V 0 = V then G0 is called a spanning subgraph of G.

7.1. GRAPHS 87
Given a subset of vertices U ⊆ V , the subgraph of G induced by

U , denoted hU i, is the graph whose vertex set is U , and its edge set
contains all edges from G connecting vertices in U .

DM Graphs

Uploaded by

Copyright:

Available Formats

DM Graphs

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DM Graphs

Uploaded by

Copyright:

Available Formats

CHAPTER 7

7.1.1. Graphs. Consider the following examples:

1. A road map, consisting of a number of towns connected with

The former is an example of (undirected) graph. The latter is an

Figure 7.1. Undirected Graph.

In general a graph G consists of two things:

1. The vertex set V , whose elements are called vertices, nodes or

Figure 7.2. Directed Graph.

A graph is sometimes represented by the pair (V, E) (we assume V

Figure 7.3. Graph with parallel edges.

Two vertices connected by an edge are called adjacent. They are

A graph with neither loops nor multiple edges is called a simple

Table 7.1.1. Graph Terminology

The degree of a vertex v, represented deg(v), is the number of edges

Sum of degrees in an directed graph. Let G = (V, E) be a directed

A weighted graph is a graph whose edges have been labeled with

Figure 7.4. Weighted Graph.

7.1.2. Special Graphs. Here we examine a few special graphs.

Figure 7.5. 3-cube.

Complete Graph: a simple undirected graph G such that every pair

Figure 7.6. Complete graph K5 .

Bipartite Graph: a graph G = (V, E) in which V can be partitioned

Question: Is the n-cube bipartite. Hint: color in red all vertices

Figure 7.7. Complete bipartite graph K3,4 .

7.1.3. Subgraph. Given a graph G = (V, E), a subgraph G0 =

V 0 = V then G0 is called a spanning subgraph of G.

Given a subset of vertices U ⊆ V , the subgraph of G induced by

You might also like