Chapter 9

Graphs
MAD101
Ly Anh Duong

duongla3@fe.edu.vn
 Table of Contents
1 Graphs and Graph Models

▶ Graphs and Graph Models

▶ Graph Terminology and Special Types of Graphs
▶ Some Special Simple Graphs
▶ Representing Graphs & Graph Isomorphism
▶ Connectivity
▶ Euler & Hamilton Paths
▶ Shortest-Path Problems
▶ Preview
 Introduction
1 Graphs and Graph Models

Relationship between

• Computers (in a computer

network,. . .)

• Cities (paths, google map,. . .)

• Webpages (on internet)

• People (in society)

• ...

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 3 / 68

 Introduction
1 Graphs and Graph Models

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 4 / 68

 Graph
1 Graphs and Graph Models

Definition 1.1
A graph G = (V, E) consists of V , a nonempty set of vertices (đỉnh) (or nodes) and E, a set of edges
(cạnh). Each edge has either one or two vertices associated with it, called its endpoints (đầu mút). An edge
is said to connect its endpoints.

Remark 1.1. G = (V, E) is called an infinite graph if |V | = +∞ or |E| = +∞;

otherwise, it is called a finite graph.
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 5 / 68
 Some Kind of Graphs
1 Graphs and Graph Models

Definition 1.2
A directed graph (or digraph) (V, E) consists of a nonempty set of vertices V and a set of directed edges
(or arcs) E. Each directed edge is associated with an ordered pair of vertices. The directed edge associated
with the ordered pair (u, v) is said to start at u and end at v.
Undirected graph: Each edge has no direction.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 6 / 68

 Some Kind of Graphs
1 Graphs and Graph Models

• Simple graph: No two edges connect the same pair of vertices

• Multigraph: Multiple edges connect the same pair of vertices

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 7 / 68

 Some Kind of Graphs
1 Graphs and Graph Models

• Pseudograph: Multigraph may have loops (khuyên, vòng)

• Simple directed graph: has no loops and has no multiple directed edges

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 8 / 68

 Some Kind of Graphs
1 Graphs and Graph Models

• Directed multigraphs (or multiple directed edges): have multiple directed

edges from a vertex to a second (possibly the same) vertex.

• Mixed graph: A graph with both directed and undirected edges.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 9 / 68

 Graph Models
1 Graphs and Graph Models

• An influence graph • An acquaintanceship graph

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 10 / 68

 Graph Models
1 Graphs and Graph Models

• A precedence graph

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 11 / 68

 Table of Contents
2 Graph Terminology and Special Types of Graphs

▶ Graphs and Graph Models

▶ Graph Terminology and Special Types of Graphs
▶ Some Special Simple Graphs
▶ Representing Graphs & Graph Isomorphism
▶ Connectivity
▶ Euler & Hamilton Paths
▶ Shortest-Path Problems
▶ Preview
 Basic Terminology
2 Graph Terminology and Special Types of Graphs

Definition 2.1
Two vertices u and v in an undirected graph G are called adjacent (or neighbors) (kề nhau) in G if u and
v are endpoints of an edge e of G. Such an edge e is called incident (cung/cạnh) with the vertices u and v
and e is said to connect u and v.

Definition 2.2
The degree of a vertex in an undirected graph is the number of edges incident with it, except that a
loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is
denoted by deg(v).

Remark 2.1.
1. A vertex of degree zero is called isolated (đỉnh cô lập)
2. A vertex is pendant (đỉnh treo) if and only if it has degree one.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 13 / 68

 Example
2 Graph Terminology and Special Types of Graphs

Example 2.1. What are the degrees of the vertices in the graphs G and H.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 14 / 68

 Example
2 Graph Terminology and Special Types of Graphs

Example 2.2. What are the degrees of the vertices in the graphs G and H.

Solution.
Graph G: deg(a) = 2, deg(b) = 4, deg(c) = 4, deg(d) = 1, deg(f ) = 4, deg(e) =
3, deg(g) = 0.
Graph H: deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, deg(d) = 5.
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 14 / 68
 THE HANDSHAKING THEOREM
2 Graph Terminology and Special Types of Graphs

Theorem 2.1
Let G = (V, E) be an undirected graph with m edges. Then
X
2m = deg(v)
v∈V

(Note that this applies even if multiple edges and loops are present.)

Example 2.3. How many edges are there in a graph with 10 vertices each of
degree six?

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 15 / 68

 THE HANDSHAKING THEOREM
2 Graph Terminology and Special Types of Graphs

Theorem 2.3
Let G = (V, E) be an undirected graph with m edges. Then
X
2m = deg(v)
v∈V

(Note that this applies even if multiple edges and loops are present.)

Example 2.4. How many edges are there in a graph with 10 vertices each of
degree six?
Solution. 2m = 10.6 =⇒ m = 30

Theorem 2.4
An undirected graph has an even number of vertices of odd degree.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 15 / 68

 Example
2 Graph Terminology and Special Types of Graphs

Example 2.5. Is there an undirected graph with degree sequence 7, 5, 4, 3, 2, 2.

Example 2.6. How many edges does a graph have if its degree sequence is
5, 5, 4, 3, 2, 1, 0.

Example 2.7. Is there an simple undirected graph with degree sequence

4, 3, 2, 1, 0? How many edges are there? Draw a such graph (if exist).

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 16 / 68

 Example
2 Graph Terminology and Special Types of Graphs

Example 2.8. Is there an undirected graph with degree sequence 7, 5, 4, 3, 2, 2.

Example 2.9. How many edges does a graph have if its degree sequence is
5, 5, 4, 3, 2, 1, 0.

Example 2.10. Is there an simple undirected graph with degree sequence

4, 3, 2, 1, 0? How many edges are there? Draw a such graph (if exist).
Solution.
1. No. 3 vertices of odd degree: 7,5,3.
2. 10 edges.
3. Yes, 5 edges.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 16 / 68

 In-degree & Out-degree
2 Graph Terminology and Special Types of Graphs

Definition 2.3
When (u, v) is an edge of the graph G with directed edges, u is said to be adjacent to v and v is said to be
adjacent from u.
a −→ b
• a is initial vertex
• b is terminal vertex (or end vertex)
The initial vertex and terminal vertex of a loop are the same.

• In-degree (deg − (v)): the number of edges with v as their terminal vertex,
• Out-degree (deg + (v)): the number of edges with v as their initial vertex.
Remark 2.2. A loop v have deg − (v) = deg + (v) = 1.
Theorem 2.5
Let G = (V, E) be a graph with directed edges. Then deg − (v) = deg + (v) = |E|
P P
v∈V v∈V

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 17 / 68

 In-degree & Out-degree - Example
2 Graph Terminology and Special Types of Graphs

Example 2.11. Find the in-degree and out-degree of each vertex in the graph G
with directed edges shown in Figure.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 18 / 68

 In-degree & Out-degree - Example
2 Graph Terminology and Special Types of Graphs

Example 2.12. Find the in-degree and out-degree of each vertex in the graph G
with directed edges shown in Figure.

Solution.
• deg − (a) = 2, deg + (a) = 4
• deg − (b) = 2, deg + (b) = 1
• deg − (c) = 3, deg + (c) = 2
• deg − (d) = 2, deg + (d) = 2
• deg − (e) = 3, deg + (e) = 3
• deg − (f ) = deg + (f ) = 0

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 18 / 68

 Table of Contents
3 Some Special Simple Graphs

▶ Graphs and Graph Models

▶ Graph Terminology and Special Types of Graphs
▶ Some Special Simple Graphs
▶ Representing Graphs & Graph Isomorphism
▶ Connectivity
▶ Euler & Hamilton Paths
▶ Shortest-Path Problems
▶ Preview
 Complete Graphs
3 Some Special Simple Graphs

Definition 3.1
A complete graph on n vertices, denoted by Kn , is a simple graph that contains exactly one edge
between each pair of distinct vertices.

n(n − 1) n!
 
• Kn has n vertices and = Cn2 edges. Cnk =
2 k!(n − k)!
• The degree of each vertex is n − 1.
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 20 / 68
 Cycles
3 Some Special Simple Graphs

Definition 3.2
A cycle Cn , n ≥ 3, consists of n vertices v1 , v2 , ..., vn and edges {v1 , v2 }, {v2 , v3 }, ..., {vn−1 , vn }, and
{vn , v1 }.

• Cn has n vertices and n edges.

• The degree of each vertex is 2.
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 21 / 68
 Wheels
3 Some Special Simple Graphs

Definition 3.3
We obtain a wheel Wn when we add an additional vertex to a cycle Cn , for n ≥ 3, and connect this new
vertex to each of the n vertices in Cn , by new edges.

• Wn has n + 1 vertices and 2n edges.

• There are 3-degree of n vertices and one vertex has n-degree.
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 22 / 68
 n-Cubes
3 Some Special Simple Graphs

Definition 3.4
An n-dimensional hypercube, or n-cube, denoted by Qn , is a graph that has vertices representing the 2n
bit strings of length n. Two vertices are adjacent if and only if the bit strings that they represent differ in
exactly one bit position.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 23 / 68

 n-Cubes
3 Some Special Simple Graphs

Contruct Q4 from two copies of Q3 .

• Qn has 2n vertices and n2n−1 edges.

• The degree of each vertex is 2.
(Mỗi đỉnh nằm trong đồ thị Qn có bậc là n, tổng số bậc nằm trong đồ thị Qn là
n2n , áp dụng định lý HANDSHAKING ta có kết quả trên.)
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 24 / 68
 Bipartite Graphs
3 Some Special Simple Graphs

Definition 3.5
A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V1 and V2
such that every edge in the graph connects a vertex in V1 and a vertex in V2 (so that no edge in G
connects either two vertices in V1 or two vertices in V2 ). When this condition holds, we call the pair
(V1 , V2 ) a bipartition of the vertex set V of G.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 25 / 68

 Bipartite Graphs
3 Some Special Simple Graphs
Theorem 3.1
A simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex of
the graph so that no two adjacent vertices are assigned the same color.

Remark 3.1. How to check?

• Let color the vertices using 2 different colors.
• Two adjacent vertices must have different colors (e.g., red and black).
Example 3.1. Are the graphs G and H displayed in the Figure bipartite?

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 26 / 68

 Complete Bipartite Graphs
3 Some Special Simple Graphs
Definition 3.6
A complete bipartite graph Km,n is a graph that has its vertex set partitioned into two subsets of m and n
vertices, respectively with an edge between two vertices if and only if one vertex is in the first subset and
the other vertex is in the second subset.

• Km,n has m + n vertices and mn edges.

• There are n-degree of m vertices and m-degree of n vertices.
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 27 / 68
 Table of Contents
4 Representing Graphs & Graph Isomorphism

▶ Graphs and Graph Models

▶ Graph Terminology and Special Types of Graphs
▶ Some Special Simple Graphs
▶ Representing Graphs & Graph Isomorphism
▶ Connectivity
▶ Euler & Hamilton Paths
▶ Shortest-Path Problems
▶ Preview
 Adjacency List (Danh sách kề)
4 Representing Graphs & Graph Isomorphism

Adjacency list: For each vertex u in the graph, there is a list of vertex v which
there is an edge between u and v.
Example 4.1. Use adjacency lists to describe the simple graph given in Figure.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 29 / 68

 Adjacency List (Danh sách kề)
4 Representing Graphs & Graph Isomorphism

Example 4.2. Represent the directed graph shown in Figure by listing all the
vertices that are the terminal vertices of edges starting at each vertex of the
graph.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 30 / 68

 Adjacency Matrices
4 Representing Graphs & Graph Isomorphism

Definition 4.1

the number of edges that are associated to {vi , vj }
Adjacency matrix A = [aij ] with aij =
0, Otherwise

Example 4.3. Use an adjacency matrix to represent the graph shown in Figure.
Solution. The matrix repre-
senting this graph is

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 31 / 68

 Adjacency Matrices - Example
4 Representing Graphs & Graph Isomorphism

Example 4.4. Use an adjacency matrix Example 4.5. Draw a graph with the
to represent the pseudograph shown in adjacency matrix.
Figure.

Solution.
Solution.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 32 / 68

 Adjacency Matrices - Example
4 Representing Graphs & Graph Isomorphism

Example 4.6. Given the adjacency matrix representing an undirected graph G.

1. Find the deg c.
2. How many edges are there?

Solution.
1. deg(c) = 1 + 2 + 1.2 + 0 = 5 (c is loop).
2. 9.
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 33 / 68
 Incidence Matrices
4 Representing Graphs & Graph Isomorphism
Definition 4.2
Let G = (V, E) be an undirected graph. Suppose that v1 , v2 , . . . , vn are the vertices and e1 , e2 , . . . , em are
the edges of G. Then the incidence matrix with respect to this ordering of V and E is the n × m matrix
M = [mij ], where 
1, when edge ej is incident with vi
mij =
0, Otherwise

Example 4.7. Represent the graph shown in Figure with an incidence matrix.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 34 / 68

 Incidence Matrices - Examples
4 Representing Graphs & Graph Isomorphism

Example 4.8. How many column are there in the incidence matrix of W9 ?

Example 4.9. How many 1s are there in the incidence matrix representing the
complete graph K10 ?

Example 4.10. How many loops are there? Find deg(v4 ).

Solution. 18; 90; loops: 2, deg(v4 ) = 1 + 1.2 = 3 (loop).

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 35 / 68
 Isomorphism of Graphs (Đẳng cấu)
4 Representing Graphs & Graph Isomorphism

Two Simple Graphs are isomorphic.

In this way, they have:
• The same number of vertices.
• The same number of edges.
• The same degrees of the vertices
(deg(v)=deg[f(v)]).
• a and b are adjacent if f (a) and
f (b) are adjacent.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 36 / 68

 Isomorphism of Graphs
4 Representing Graphs & Graph Isomorphism

Definition 4.3
The simple graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) are isomorphic if there exists a bijection f from V1
to V2 with the property that a and b are adjacent in G1 if and only if f (a) and f (b) are adjacent in G2 , for
all a and b in V1 .

Example 4.11. Show that the graphs G = (V, E) and H = (W, F), displayed in
Figure, are isomorphic.

Solution. f (u1 ) = v1 , f (u2 ) = v4 , f (u3 ) = v3 , and f (u4 ) = v2

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 37 / 68
 Isomorphism of Graphs - Example
4 Representing Graphs & Graph Isomorphism

Example 4.12. Show that the graphs displayed in Figure are not isomorphic

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 38 / 68

 Isomorphism of Graphs - Example
4 Representing Graphs & Graph Isomorphism

Example 4.13. Determine whether the graphs shown in Figure are isomorphic.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 39 / 68

 Isomorphism of Graphs - Example
4 Representing Graphs & Graph Isomorphism

Example 4.14. Determine whether the graphs shown in Figure are isomorphic.

Solution. Not isomorphic because vertex a (2-degree) in G adjacent with b, d (all

of them have 3-degree) and in H, there is not exist a vertex which have the same
characteristic.
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 39 / 68
 Table of Contents
5 Connectivity

▶ Graphs and Graph Models

▶ Graph Terminology and Special Types of Graphs
▶ Some Special Simple Graphs
▶ Representing Graphs & Graph Isomorphism
▶ Connectivity
▶ Euler & Hamilton Paths
▶ Shortest-Path Problems
▶ Preview
 Paths & Circuit/Cycle
5 Connectivity
Definition 5.1
Let n be a nonnegative integer and G an undirected graph.
• A path (đường đi) of length n from u to v in G is a sequence of n edges e1 , ..., en of G for which
there exists a sequence x0 = u, x1 , ..., xn−1 , xn = v of vertices such that ei has, for i = 1, ..., n, the
endpoints xi−1 and xi . When the graph is simple, we denote this path by its vertex sequence
x0 , x1 , ..., xn .
• The path is a circuit (chu trình) if it begins and ends at the same vertex.
• A path or circuit is simple (đơn) if it does not contain the same edge more than once.

Example 5.1.
• a, d, c, f, e is a simple path of
length 4.

• d, e, c, a is not a path.

• b, c, f, e, b is a circuit of length 4.
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 41 / 68
 Connectedness In Undirected Graphs
5 Connectivity

Definition 5.2
An undirected graph is called connected (liên thông) if there is a path between every pair of distinct
vertices of the graph. An undirected graph that is not connected is called disconnected.

Theorem 5.1
There is a simple path between every pair of distinct vertices of a connected undirected graph.

Example 5.2. G1 is connected, G2 is disconnected, H is disconnected with 3

connected components (H1 , H2 , H3 )

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 42 / 68

 Strongly connected & Weakly connected
5 Connectivity
Definition 5.3
• A directed graph is strongly connected if there is a path from a to b and from b to a whenever a and
b are vertices in the graph.
• A directed graph is weakly connected if and only if there is always a path between two vertices when
the directions of the edges are disregarded (không quan tâm) (underlying undirected).

Remark 5.1. Any strongly connected directed graph is also weakly connected.
Example 5.3. G is strongly connected, H is weakly connected.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 43 / 68

 Counting Paths Between Vertices
5 Connectivity

Definition 5.4: (with directed or undirected edges, with multiple edges and loops allowed)
• Let G be a graph with adjacency matrix A with respect to the ordering v1 , v2 , ..., vn of the vertices of
the graph,
• The number of different paths of length r from vi to vj equals the (i, j) th entry of Ar , where r is
a positive integer.

Example 5.4. How many paths of length four are there from a to d in the simple
graph G in figure

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 44 / 68

 Solution of Example 5.4
5 Connectivity

• The adjacency matrix of G (ordering the vertices as a, b, c, d) is

• Thus, we have

• There are 8 paths of length four from a to d.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 45 / 68

 Cut vertices & Cut edges
5 Connectivity

Definition 5.5
• Cut vertex (or articulation point) (điểm cắt, đỉnh khớp): the removal from a graph of a vertex and
all incident edges produces a subgraph with more connected components.
• Cut edge (or bridge) (cạnh cắt, cầu nối): An edge whose removal produces a graph with more
connected components than in the original graph.

Example 5.5. Find the cut vertices and cut edges in the graph shown in Figure.

Solution. Cut vertices: b, c, e; Cut edges: {a, b} and {c, e}.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 46 / 68
 Path and Isomorphism
5 Connectivity

Example 5.6. Using path to determine whether two graphs are isomorphic.
G and H have the same
• Number of vertices
• Number of edges
• 2 vertices degree 2
• 4 vertices degree 3
But, H has a simple circuit
with length 3 and G has a
simple circuit with length 4.
Thus, they are not isomor-
phic.
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 47 / 68
 Path and Isomorphism
5 Connectivity

Example 5.7. Using path to determine whether two graphs are isomorphic

They are isomorphic.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 48 / 68

 Table of Contents
6 Euler & Hamilton Paths

▶ Graphs and Graph Models

▶ Graph Terminology and Special Types of Graphs
▶ Some Special Simple Graphs
▶ Representing Graphs & Graph Isomorphism
▶ Connectivity
▶ Euler & Hamilton Paths
▶ Shortest-Path Problems
▶ Preview
 Introduction
6 Euler & Hamilton Paths
The town of Konigsberg, Prussia (now called Kaliningrad and part of the Russian
republic),was divided into four sections by the branches of the Pregel River. These
four sections included the two regions on the banks of the Pregel, Kneiphof Island,
and the region between the two branches of the Pregel. In the eighteenth century
seven bridges connected these regions. Figure depicts these regions and bridges.
The townspeople took long walks through town on Sundays. They wondered
whether it was possible to start at some location in the town, travel across all the
bridges once without crossing any bridge twice, and return to the starting point.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 50 / 68

 Introduction
6 Euler & Hamilton Paths

The Swiss mathematician Leonhard Euler solved this problem. His solution,
published in 1736, may be the first use of graph theory.

Figure: Euler (1707 − 1783)

Can once travel across all the bridges once and return to starting point?
His answer: All of vertices must have even-degree.
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 51 / 68
 Euler Paths & Circuits
6 Euler & Hamilton Paths
Definition 6.1
• An Euler circuit in a graph G is a simple circuit containing every edge of G,
• An Euler path in G is a simple path containing every edge of G.

Theorem 6.1
1. A connected multigraph with at least two vertices has an Euler circuit if and only if each of its
vertices has even degree.
2. A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two
vertices of odd degree.

Example 6.1. G1 : has an Euler circuit, G2 : has no Euler circuit.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 52 / 68

 Hamilton Paths & Circuits
6 Euler & Hamilton Paths

Definition 6.2
• A simple path in a graph G that passes through every vertex exactly once is called a Hamilton path.
• A simple circuit in a graph G that passes through every vertex exactly once is called a Hamilton
circuit.

Example 6.2. G1 has Hamilton circuit: a, b, c, d, e, a; G2 has no Hamilton

circuit; G3 has neither a Hamilton circuit nor a Hamilton path.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 53 / 68

 Hamilton Circuits - Sufficient conditions
6 Euler & Hamilton Paths
Although no useful necessary and sufficient conditions for the existence of
Hamilton circuits are known, quite a few sufficient conditions have been found.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 54 / 68

 Table of Contents
7 Shortest-Path Problems

▶ Graphs and Graph Models

▶ Graph Terminology and Special Types of Graphs
▶ Some Special Simple Graphs
▶ Representing Graphs & Graph Isomorphism
▶ Connectivity
▶ Euler & Hamilton Paths
▶ Shortest-Path Problems
▶ Preview
 Introduction
7 Shortest-Path Problems

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 56 / 68

 Introduction
7 Shortest-Path Problems

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 57 / 68

 Introduction
7 Shortest-Path Problems

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 58 / 68

 A weighted simple graph
7 Shortest-Path Problems

Use Dijkstra’s algorithm to find the length of a shortest path between the vertices
a and z in the weighted graph displayed in Figure.
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 59 / 68
 Example
7 Shortest-Path Problems

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 60 / 68

 Solution
7 Shortest-Path Problems

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 61 / 68

 A Shortest-Path Algorithm
7 Shortest-Path Problems

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 62 / 68

 Dijkstra’s Algorithm
7 Shortest-Path Problems
Theorem 7.1
Dijkstra’s algorithm finds the length of a shortest path between two vertices in a connected simple
undirected weighted graph.

Theorem 7.2
Dijkstra’s algorithm uses O(n2 ) operations (additions and comparisons) to find the length of a shortest
path between two vertices in a connected simple undirected weighted graph with n vertices.

Example 7.1. Find the length of a shortest path between a and z in the given
weighted graph.

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 63 / 68

 Dijkstra’s Algorithm
7 Shortest-Path Problems
Theorem 7.3
Dijkstra’s algorithm finds the length of a shortest path between two vertices in a connected simple
undirected weighted graph.

Theorem 7.4
Dijkstra’s algorithm uses O(n2 ) operations (additions and comparisons) to find the length of a shortest
path between two vertices in a connected simple undirected weighted graph with n vertices.

Example 7.2. Find the length of a shortest path between a and z in the given
weighted graph.

Solution. A shortest path between a and z is a, c, d, e, g, z and the length of the

shortest path from a to z is 16.
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 63 / 68
 Table of Contents
8 Preview

▶ Graphs and Graph Models

▶ Graph Terminology and Special Types of Graphs
▶ Some Special Simple Graphs
▶ Representing Graphs & Graph Isomorphism
▶ Connectivity
▶ Euler & Hamilton Paths
▶ Shortest-Path Problems
▶ Preview
 Quiz
8 Preview

Q1. Study a simple graph having the Q2. For which values of n do Kn have
degree sequence an Euler path but no Euler circuit?
{5, 5, 4, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1}. If the Select one:
graph has n edges, then n = . . .
a. 2
Select one:
a. 38 b. 1
b. 19
c. 3
c. 20
d. 17 d. 2m, ∀m > 1

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 65 / 68

 Quiz
8 Preview

Q3. Every Euler circuit in K11 is a path Q4. If Kn has x edges and y vertices,
of length . . . then x = . . ., y = . . .
Select one: Select one:
a. 45 a. n + 1, n
b. 2n, n + 1
b. 22
n(n + 1)
c. 11 c. , n
2
d. 55 n(n − 1) n
d. , 2
2

Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 66 / 68

 Quiz
8 Preview

Q5. The incidence matrix of the graph Q6. Study the statements:
K2,3 has the size of i. K2,3 has no an Euler circuit, but
Select one: has an Euler path.
ii. K2,3 has an Euler circuit.
a. 30
Which statements is true?
b. 5 × 6 Select one:
a. None
c. 2 × 3
b. i
d. 6 × 5 c. ii
d. Both
n(n − 1)
Answer. Q1. 19; Q2. 2; Q3. 55; Q4. , n; Q5. 5 × 6; Q6. i
2
Ly Anh Duong Chapter 9 Graphs duongla3@fe.edu.vn 67 / 68
 Q&A
Thank you for listening!