Chapter 7

Graphs
MAD101
Ly Anh Duong

duongla3@fe.edu.vn
 Table of Contents
1 G. & G.Models

▶ G. & G.Models

▶ G.Ter. & Spec. Types of G.

▶ Repre. G. & G. Iso.

▶ Connectivity

▶ Euler & Hamilton Paths

▶ S. Path Prob.

▶ Problems
 Introduction
1 G. & G.Models

Relationship between
• Computers (in a computer network,...)
• Cities (paths, google map,..)
• Webpages (on internet)
• People (in society)
• ...

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 3 / 120

 Introduction
1 G. & G.Models

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 4 / 120

 Introduction
1 G. & G.Models

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 5 / 120

 Google Pagerank-Sergey Brin & Larry Page
1 G. & G.Models

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 6 / 120

 Definition
1 G. & G.Models

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.

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

 Some Kind of Graphs
1 G. & G.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 7 Graphs duongla3@fe.edu.vn 8 / 120

 Some Kind of Graphs
1 G. & G.Models
• Pseudograph: Multigraph may have loops (khuyên, vòng)

• Undirected graph: Each edge has no direction

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

 Directed Graph
1 G. & G.Models

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.
• Simple directed graph has no loops and has no multiple directed edges

• Directed multigraphs (or multiple directed edges):

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 10 / 120

 Directed Graph
1 G. & G.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 7 Graphs duongla3@fe.edu.vn 11 / 120

 Graph Terminology
1 G. & G.Models

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 12 / 120

 Graph Models
1 G. & G.Models

• An influence graph • An acquaintanceship graph

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 13 / 120

 Graph Models
1 G. & G.Models
• A precedence graph

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 14 / 120

 Table of Contents
2 G.Ter. & Spec. Types of G.

▶ G. & G.Models

▶ G.Ter. & Spec. Types of G.

▶ Repre. G. & G. Iso.

▶ Connectivity

▶ Euler & Hamilton Paths

▶ S. Path Prob.

▶ Problems
 Basic Terminology
2 G.Ter. & Spec. Types of G.

• 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.
• 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).
Notes.
• A vertex of degree zero is called isolated (đỉnh cô lập)
• A vertex is pendant (đỉnh treo) if and only if it has degree one.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 16 / 120

 Example.
2 G.Ter. & Spec. Types of G.

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

Solutions
Graph G: deg(a)=2, deg(b)=4, deg(c)=4, deg(d)=1, deg(f)=4, deg(e)=3, deg(g)=0.
Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 17 / 120
 THE HANDSHAKING THEOREM
2 G.Ter. & Spec. Types of G.

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. How many edges are there in a graph with 10 vertices each of degree
six?
Solution. 2m = 10.6 =⇒ m = 30
Theorem. An undirected graph has an even number of vertices of odd degree.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 18 / 120

 Example.
2 G.Ter. & Spec. Types of G.

1. Is there an undirected graph with degree sequence 7, 5, 4, 3, 2, 2. (No. 3 vertices

of odd degree:7,5,3)
2. How many edges does a graph have if its degree sequence is 5, 5, 4, 3, 2, 1, 0.
(10 edges)
3. 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). (Yes, 5 edges)

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 19 / 120

 Definition
2 G.Ter. & Spec. Types of G.

a −→ b

• a is initial vertex
• b is terminal vertex (or end vertex)
Note. 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.
Note. A loop v have deg − (v) = deg + (v) = 1

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 20 / 120

 Example.
2 G.Ter. & Spec. Types of G.

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

• 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 7 Graphs duongla3@fe.edu.vn 21 / 120

 Theorem
2 G.Ter. & Spec. Types of G.

Let G = (V, E) be a graph with directed edges. Then

deg − (v) =
X X
deg + (v) = |E|
v∈V v∈V

Example. In the previous example, we have

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 22 / 120

 Complete Graphs (Đồ thị đầy đủ)
2 G.Ter. & Spec. Types of G.

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!
 
• How many vertices and edges in Kn ? n, Cn2 = Cnk =
2 k!(n − k)!
• What is the degree of each vertex? n − 1

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 23 / 120

 Cycles (Đồ thị vòng
2 G.Ter. & Spec. Types of G.

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 7 Graphs duongla3@fe.edu.vn 24 / 120

 Wheels (Đồ thị bánh xe)
2 G.Ter. & Spec. Types of G.

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 7 Graphs duongla3@fe.edu.vn 25 / 120

 n-Cubes (Đồ thị khối n-chiều)
2 G.Ter. & Spec. Types of G.

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 7 Graphs duongla3@fe.edu.vn 26 / 120

 n-Cubes (Đồ thị khối n-chiều)
2 G.Ter. & Spec. Types of G.

Contruct Q4 from two copies of Q3 .

Qn has 2n vertices and n2n−1 edges.

Lưu ý: 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 7 Graphs duongla3@fe.edu.vn 27 / 120
 Exercise
2 G.Ter. & Spec. Types of G.

a/ & b/ = 1/4; c/ = 1/2

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 28 / 120
 Bipartite Graphs (Đồ thị lưỡng phân)
2 G.Ter. & Spec. Types of G.

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 7 Graphs duongla3@fe.edu.vn 29 / 120
Example. Non-Bipartite

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 30 / 120

 Theorem
2 G.Ter. & Spec. Types of G.

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.
How to check?
• Let color the vertices using 2 different colors,
• Two adjacent vertices must have different colors (e.g., red and black)
Are the graphs G and H displayed in the Figure bipartite?

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 31 / 120

 Complete Bipartite Graphs
2 G.Ter. & Spec. Types of G.

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.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 32 / 120
 Table of Contents
3 Repre. G. & G. Iso.

▶ G. & G.Models

▶ G.Ter. & Spec. Types of G.

▶ Repre. G. & G. Iso.

▶ Connectivity

▶ Euler & Hamilton Paths

▶ S. Path Prob.

▶ Problems
 Adjacency List
3 Repre. G. & G. Iso.

Using 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 1. Use adjacency lists to describe the simple graph given in Figure

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 34 / 120

 Adjacency List
3 Repre. G. & G. Iso.

Example 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 7 Graphs duongla3@fe.edu.vn 35 / 120

 Adjacency Matrices
3 Repre. G. & G. Iso.

Adjacency matrix A = [aij ] with

(
the number of edges that are associated to {vi , vj }
aij =
0, Otherwise

Example. Use an adjacency matrix to represent the graph shown in Figure.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 36 / 120

 Adjacency Matrices
3 Repre. G. & G. Iso.

Example. Use an adjacency matrix to represent the pseudograph shown in Figure

Example. Draw a graph with the adjacency matrix

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 37 / 120

 Adjacency Matrices
3 Repre. G. & G. Iso.

Example. Use an adjacency matrix to represent the directed graph shown in

Figure

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 38 / 120

 Exercise.
3 Repre. G. & G. Iso.

deg(c) = 1 + 2 + 1.2 + 0 = 5 (c is loop).

How many edges are there? (9).
Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 39 / 120
 Incidence Matrices (ma trận liên thuộc)
3 Repre. G. & G. Iso.

M = [mij ], where
(
1, when edge ej is incident with vi
mij =
0, Otherwise
Example. Represent the graph shown in Figure with an incidence matrix.
Solution.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 40 / 120

 Example.
3 Repre. G. & G. Iso.

Represent the graph shown in Figure with an incidence matrix

Solution.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 41 / 120

 Example.
3 Repre. G. & G. Iso.

In directed graph,
• 0 is used to represent row edge which is not connected to column vertex.
• 1 is used to represent row edge which is connected as outgoing edge to
column vertex.
• −1 is used to represent row edge which is connected as incoming edge to
column vertex.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 42 / 120

 Exercises.
3 Repre. G. & G. Iso.

1. How many column are there in the incidence matrix of W9 . (18)

2. How many 1s are there in the incidence matrix representing the complete
graph K10 . (90)
3. .

loops : 2; deg(v4 ) = 1 + 1.2 = 3 (loop)

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 43 / 120
 Isomorphism of Graphs (Đẳng cấu)
3 Repre. G. & G. Iso.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 44 / 120

 Isomorphism of Graphs (Đẳng cấu)
3 Repre. G. & G. Iso.

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.
Definition. 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 .

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 45 / 120

 Example.
3 Repre. G. & G. Iso.

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

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

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 46 / 120
 Example.
3 Repre. G. & G. Iso.

Show that the graphs displayed in Figure are not isomorphic

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 47 / 120

 Example
3 Repre. G. & G. Iso.

Determine whether the graphs shown in Figure are isomorphic.

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 7 Graphs duongla3@fe.edu.vn 48 / 120
 Table of Contents
4 Connectivity

▶ G. & G.Models

▶ G.Ter. & Spec. Types of G.

▶ Repre. G. & G. Iso.

▶ Connectivity

▶ Euler & Hamilton Paths

▶ S. Path Prob.

▶ Problems
 Example.
4 Connectivity

• 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.
• The path a, b, e, d, a, b, which is of length 5, is not simple because it contains
the edge {a, b} twice.
Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 50 / 120
 Paths (đường đi)
4 Connectivity

Defintion 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.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 51 / 120

 Connectedness (liên thông) In Undirected
Graphs
4 Connectivity

G1 is called connected and G2 is dis- A disconnected with 3 connected

connected. components
Definition. An undirected graph is called connected if there is a path between
every pair of distinct vertices of the graph.
Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 52 / 120
 Theorem
4 Connectivity

There is a simple path between every pair of distinct vertices of a connected

undirected graph.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 53 / 120

 Example.
4 Connectivity

• G is strongly connected → weakly connected.

• H is not strongly connected (There is no directed path from a to b in this
graph) but the underlying undirected graph of H is connected → weakly
connected.
Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 54 / 120
 Connectedness In Directed Graphs
4 Connectivity

Definition.
• 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).
Notes.
• Any strongly connected directed graph is also weakly connected.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 55 / 120

 Counting Paths Between Vertices
4 Connectivity

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

Theorem. (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
Ly j) th
(i,Anh Duongentry of Ar , where rChapter
is a positive
7 Graphsinteger. duongla3@fe.edu.vn 56 / 120
 Solution.
4 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 7 Graphs duongla3@fe.edu.vn 57 / 120

 CONNECTED COMPONENTS
4 Connectivity

• A connected component (thành phần liên thông) of a graph G is a

connected subgraph of G that is not a proper subgraph(không là đồ thị con) of
another connected subgraph of G. That is, a connected component of a graph
G is a maximal connected subgraph of G.
• A graph G that is not connected has two or more connected components that
are disjoint and have G as their union(hợp).

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 58 / 120

 Definition
4 Connectivity

• Cut vertex (articulation point) (điểm cắt,đỉnh khớp): It’s removal will
produce disconnected subgraph from original connected graph.
• Cut edge (bridge) (cạnh cắt, cầu): It’s removal will produce subgraphs which
are more connected components than in the original graph.
Example. Find the cut vertices and cut edges in the graph shown in Figure.

Solution: Cut vertices: b,c,e; Cut edges:

Ly Anh Duong
{a, b} and {c, e}
Chapter 7 Graphs duongla3@fe.edu.vn 59 / 120
 Path and Isomorphism
4 Connectivity

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 isomorphic.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 60 / 120

 Path and Isomorphism
4 Connectivity

Using path to determine whether two graphs are isomorphic

They are isomorphic.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 61 / 120

 Table of Contents
5 Euler & Hamilton Paths

▶ G. & G.Models

▶ G.Ter. & Spec. Types of G.

▶ Repre. G. & G. Iso.

▶ Connectivity

▶ Euler & Hamilton Paths

▶ S. Path Prob.

▶ Problems
 Introduction
5 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 7 Graphs duongla3@fe.edu.vn 63 / 120

 Introduction
5 Euler & Hamilton Paths

Hình: The seven bridges of Konigsberg Hình: Multigraph model

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 7 Graphs duongla3@fe.edu.vn 64 / 120
 Euler Paths and Circuits
5 Euler & Hamilton Paths

G1 : has an Euler circuit:

a,e,c,d,e,b,a

G3 : has no Euler circuit but it has

Euler path a,c,d,e,b,d,a,b
Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 65 / 120
 Euler Paths and Circuits
5 Euler & Hamilton Paths

G2 :
• 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.

has no Euler circuit and also has no Euler path.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 66 / 120

 Theorem
5 Euler & Hamilton Paths

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.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 67 / 120

 Exercises
5 Euler & Hamilton Paths

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

 Solution
5 Euler & Hamilton Paths

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 69 / 120

 Examples.
5 Euler & Hamilton Paths

The graph have deg(a) = deg(b) = deg(c) = deg(d) = deg(e) = 2. So, there is an
Euler circuit a, b, e, d, c, e, a.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 70 / 120

 Examples.
5 Euler & Hamilton Paths

The graph have deg(a) = deg(b) = 3; deg(c) = 4; deg(d) = deg(e) = 2. So, there is
an Euler path a, d, c, e, b, c, a, b.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 71 / 120

 Examples.
5 Euler & Hamilton Paths

The graph have neither Euler circuit nor Euler path.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 72 / 120

 Hamilton Paths and Circuits
5 Euler & Hamilton Paths
Definition.
• 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.
Examples.

G1 has Hamilton circuit: a, b, c, d, e, a.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 73 / 120
 Hamilton Paths and Circuits
5 Euler & Hamilton Paths
Examples.
• G2 has no Hamilton circuit.

• G has Hamilton path a,b,c,d,e,f.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 74 / 120

 Hamilton Paths and Circuits
5 Euler & Hamilton Paths

Examples.
• G3 has neither a Hamilton circuit nor a Hamilton

path.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 75 / 120

 Hamilton circuit - Sufficient conditions
5 Euler & Hamilton Paths
Sufficient conditions for the existence of Hamilton circuits

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 76 / 120

 Table of Contents
6 S. Path Prob.

▶ G. & G.Models

▶ G.Ter. & Spec. Types of G.

▶ Repre. G. & G. Iso.

▶ Connectivity

▶ Euler & Hamilton Paths

▶ S. Path Prob.

▶ Problems
 Introduction
6 S. Path Prob.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 78 / 120

 Introduction
6 S. Path Prob.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 79 / 120

 Introduction
6 S. Path Prob.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 80 / 120

 A weighted simple graph
6 S. Path Prob.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 81 / 120

 Example.
6 S. Path Prob.
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 7 Graphs duongla3@fe.edu.vn 82 / 120

 L(a) L(b) L(c) L(d) L(e) L(z) S
0 ∞ ∞ ∞ ∞ ∞ ∅
∞ ∞ ∞ ∞ ∞ {a}
4 2 ∞ ∞ ∞ {a, c}
3 10 12 ∞ {a, c, b}
8 12 ∞ {a, c, b, d}
10 14 {a, c, b, d, e}
13 {a, c, b, d, e, z}

z(13) ←− e(10) ←− d(8) ←− b(3) ←− c(2) ←− a(0)

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 83 / 120

 Solution
6 S. Path Prob.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 84 / 120

 Dijkstra’s Algorithm
6 S. Path Prob.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 85 / 120

 Theorem
6 S. Path Prob.

1. Dijkstra’s algorithm finds the length of a shortest path between two vertices
in a connected simple undirected weighted graph.
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.

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 86 / 120

 Example.
6 S. Path Prob.

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

A shortest path between a and z is a, b, e, d, z and the length of the shortest path
from a to z is 7.
Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 87 / 120
 Example.
6 S. Path Prob.

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

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 7 Graphs duongla3@fe.edu.vn 88 / 120

 Example.
6 S. Path Prob.

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

A shortest path between a and z is a, d, e, z and the length of the shortest path
from a to z is 6

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 89 / 120

 Example.
6 S. Path Prob.

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

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 90 / 120

 Table of Contents
7 Problems

▶ G. & G.Models

▶ G.Ter. & Spec. Types of G.

▶ Repre. G. & G. Iso.

▶ Connectivity

▶ Euler & Hamilton Paths

▶ S. Path Prob.

▶ Problems
 Quizz
7 Problems

Ans: 19
Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 92 / 120
 Quizz
7 Problems

Ans: n = 2

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 93 / 120

 Quizz
7 Problems

Ans: 55
Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 94 / 120
 Quizz
7 Problems

Ans: n(n-1)/2, n

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 95 / 120

 Quizz
7 Problems

Ans: 5 × 6

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 96 / 120

 Quizz
7 Problems

Ans: (i)
Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 97 / 120
 Quizz
7 Problems

Ans: 6
Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 98 / 120
 Quizz
7 Problems

Ans:LyNone of the others

Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 99 / 120
 Quizz
7 Problems

Ans: G has Euler circuit, G has Hamilton circuit, G has 10 edges

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 100 / 120

 Graphs and Graph Models
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 101 / 120

 Graph Terminology and Special Types of
Graphs
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 102 / 120

 Graph Terminology and Special Types of
Graphs
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 103 / 120

 Graph Terminology and Special Types of
Graphs
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 104 / 120

 Graph Terminology and Special Types of
Graphs
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 105 / 120

 Representing Graphs and Graph Isomorphism
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 106 / 120

 Representing Graphs and Graph Isomorphism
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 107 / 120

 Representing Graphs and Graph Isomorphism
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 108 / 120

 Representing Graphs and Graph Isomorphism
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 109 / 120

 Representing Graphs and Graph Isomorphism
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 110 / 120

 Connectivity
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 111 / 120

 Connectivity
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 112 / 120

 Connectivity
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 113 / 120

 Euler and Hamilton Paths
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 114 / 120

 Euler and Hamilton Paths
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 115 / 120

 Euler and Hamilton Paths
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 116 / 120

 Euler and Hamilton Paths
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 117 / 120

 Shortest-Path Problems
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 118 / 120

 Shortest-Path Problems
7 Problems

Ly Anh Duong Chapter 7 Graphs duongla3@fe.edu.vn 119 / 120

 Q&A
Thank you for listening!