Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen

Chapter 8
An Khuong, Le Hong
Trang

Introduction to Graphs
Discrete Structures for Computing on August 16, 2021

Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

Huynh Tuong Nguyen, Tran Tuan Anh, Nguyen An Khuong, Le

Hong Trang
Faculty of Computer Science and Engineering
University of Technology - VNUHCM
trtanh@hcmut.edu.vn - htnguyen@hcmut.edu.vn
8.1
Contents Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

1 Graph definitions
Terminology
Special Graphs

Contents

2 Representing Graphs and Graph Isomorphism Graph definitions

Terminology

Representing Graphs Special Graphs

Graph Isomorphism Representing Graphs

and Graph
Isomorphism
Representing Graphs

Exercise
Graph Isomorphism

3 Exercise
Graph Graph

Bipartie graph

Bipartie graph Isomorphism

Isomorphism

8.2
Course outcomes Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Course learning outcomes

L.O.1 Understanding of logic and discrete structures
L.O.1.1  Describe definition of propositional and predicate logic
L.O.1.2  Define basic discrete structures: set, mapping, graphs

L.O.2 Represent and model practical problems with discrete structures Contents
L.O.2.1  Logically describe some problems arising in Computing Graph definitions
L.O.2.2  Use proving methods: direct, contrapositive, induction Terminology

Special Graphs

L.O.2.3  Explain problem modeling using discrete structures

Representing Graphs
and Graph
L.O.3 Understanding of basic probability and random variables Isomorphism
L.O.3.1  Define basic probability theory
Representing Graphs

Graph Isomorphism

L.O.3.2  Explain discrete random variables Exercise

Graph

L.O.4 Compute quantities of discrete structures and probabilities Bipartie graph

L.O.4.1  Operate (compute/ optimize) on discrete structures Isomorphism

L.O.4.2  Compute probabilities of various events, conditional

ones, Bayes theorem

8.3
Motivations Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

The need of the graph Its applications

• Representation/Storing • Electric circuit/board

• Searching/sorting • Chemical structure Contents

Graph definitions
• Optimization • Networking Terminology

•
Special Graphs

Map, geometry, ... Representing Graphs

and Graph
Isomorphism
Representing Graphs

• Graph theory is useful for analysing things that are

Graph Isomorphism

Exercise
connected to other things. Graph

Bipartie graph

• Some difficult problems become easy when represented using Isomorphism

a graph.

8.4
Graph Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition
A graph (ç thà ) G is a pair of (V, E ), which are:

• V  nonempty set of vertices (nodes) (¿nh)

Contents
• E  set of edges (c¤nh) Graph definitions
Terminology

A graph captures abstract relationships between vertices. Special Graphs

Representing Graphs
and Graph
2 4 2 4 Isomorphism
Representing Graphs

Graph Isomorphism

1 3 Exercise
1 3
Graph

Bipartie graph

Undirected graph Directed graph Isomorphism

8.5
Undirected Graph (ç thà væ h÷îng) Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition (Simple graph (ìn ç thà))

• Each edge connects two different vertices, and
Contents
• No two edges connect the same pair of vertices
Graph definitions
An edge between two vertices u and v is denoted as {u, v} Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.6
Undirected Graph Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition (Multigraph (a ç thà))

Graphs that may have multiple edges connecting the same vertices.
Contents
An unordered pair of vertices {u, v} are called multiplicity m (bëi Graph definitions
m) if it has m different edges between.
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.7
Undirected Graph Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition (Pseudograph (gi£ ç thà))

Are multigraphs that have
Contents
• loops (khuy¶n) edges that connect a vertex to itself
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.8
Directed Graph Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition (Directed Graph (ç thà câ h÷îng))

A directed graph G is a pair of (V, E ), in which:

• V  nonempty set of vertices

Contents
• E  set of directed edges (c¤nh câ h÷îng, arcs ) Graph definitions
Terminology

A directed edge start at u and end at v is denoted as (u, v). Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.9
Terminologies For Undirected Graph Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Neighborhood
In an undirected graph G = (V, E),
• two vertices u and v ∈ V are called adjacent (li·n k· ) if they
are end-points (iºm ¦u mót ) of edge e ∈ E , and
e is incident with (c¤nh li¶n thuëc ) u and v
Contents
•
Graph definitions
• e is said to connect (c¤nh nèi ) u and v ; Terminology

Special Graphs

Representing Graphs
and Graph
The degree of a vertex Isomorphism

degree of a vertex (bªc cõa mët ¿nh), denoted by deg(v) is

Representing Graphs

The Graph Isomorphism

Exercise
the number of edges incident with it, except that a loop
Graph

contributes twice to the degree of that vertex. Bipartie graph

Isomorphism

• isolated vertex (¿nh cæ lªp ): vertex of degree 0

• pendant vertex (¿nh treo ): vertex of degree 1

8.10
Example Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen

Example An Khuong, Le Hong

Trang

What are the degrees and neighborhoods of the vertices in these

graphs?
b c d a b c

Contents
Graph definitions
Terminology

a f e g e d Special Graphs

Representing Graphs
G H and Graph
Isomorphism
Representing Graphs

Solution
Graph Isomorphism

Exercise
In G, deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d) = 1, . . . Graph

Bipartie graph

Neiborhoods of these vertices are Isomorphism

N (a) = {b, f }, N (b) = {a, c, e, f }, . . .

In H , deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, . . .
Neiborhoods of these vertices are
N (a) = {b, d, e}, N (b) = {a, b, c, d, e}, . . .
8.11
Basic Theorems Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Theorem (The Handshaking Theorem)

Let G = (V, E) be an undirected graph with m edges. Then
Contents
X
2m = deg(v)
Graph definitions
v∈V Terminology

Special Graphs

(Note that this applies even if multiple edges and loops are Representing Graphs
and Graph
present.) Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.12
Basic Theorems Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Theorem (The Handshaking Theorem)

Let G = (V, E) be an undirected graph with m edges. Then
Contents
X
2m = deg(v)
Graph definitions
v∈V Terminology

Special Graphs

(Note that this applies even if multiple edges and loops are Representing Graphs
and Graph
present.) Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Theorem Graph

Bipartie graph

An undirected graph has an even number of odd-degree vertices. Isomorphism

8.12
Prove that ... Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

...
If the number of vertices in an undirected graph is an odd number,
then there exists an even-degree vertex.
Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.13
Prove that ... Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

...
If the number of vertices in an undirected graph is an odd number,
then there exists an even-degree vertex.
Contents
Graph definitions
... Terminology

Special Graphs

If the number of vertices in an undirected graph is an odd number,

Representing Graphs
then the number of vertices with even degree is odd. and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.13
Prove that ... Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

...
If the number of vertices in an undirected graph is an odd number,
then there exists an even-degree vertex.
Contents
Graph definitions
... Terminology

Special Graphs

If the number of vertices in an undirected graph is an odd number,

Representing Graphs
then the number of vertices with even degree is odd. and Graph
Isomorphism
Representing Graphs

... Graph Isomorphism

Exercise
If the number of vertices in an undirected graph is an even Graph

number, then the number of vertices with even degree is even.

Bipartie graph

Isomorphism

8.13
Terminologies for Directed Graph Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen

Neighborhood An Khuong, Le Hong

Trang

In an directed graph G = (V, E),

• u is said to be adjacent to (nèi tîi ) v and v is said to be
adjacent from (÷ñc nèi tø ) u if (u, v) is an arc of G, and
• u is called initial vertex (¿nh ¦u ) of (u, v)
• v is called terminal (¿nh cuèi ) or end vertex of (u, v) Contents
Graph definitions
• the initial vertex and terminal vertex of a loop are the same. Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.14
Terminologies for Directed Graph Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen

Neighborhood An Khuong, Le Hong

Trang

In an directed graph G = (V, E),

• u is said to be adjacent to (nèi tîi ) v and v is said to be
adjacent from (÷ñc nèi tø ) u if (u, v) is an arc of G, and
• u is called initial vertex (¿nh ¦u ) of (u, v)
• v is called terminal (¿nh cuèi ) or end vertex of (u, v) Contents
Graph definitions
• the initial vertex and terminal vertex of a loop are the same. Terminology

Special Graphs

Representing Graphs
and Graph
The degree of a vertex Isomorphism
Representing Graphs

In a graph G with directed edges: Graph Isomorphism

• in-degree (bªc v o ) of a vertex v, denoted by deg −

(v), is
Exercise
Graph

the number of edges with v as their terminal vertex. Bipartie graph

out-degree (bªc ra) of a vertex v, denoted by deg+ (v), is

Isomorphism

•
the number of edges with v as their initial vertex.

Note: a loop at a vertex contributes 1 to both the in-degree and

the out-degree of this vertex.

8.14
Basic Theorem Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Theorem
Contents
Let G = (V, E) be a graph with directed edges. Then Graph definitions
Terminology

deg− (v) = deg+ (v) = |E|.

X X Special Graphs

Representing Graphs
v∈V v∈V and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.15
Complete Graphs Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

A complete graph (ç thà ¦y õ ) on n vertices, Kn , is a simple

graph that contains exactly one edge between each pair of distinct
vertices.

Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

K5 K4

8.16
Cycles Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

A cycle (ç thà váng ) Cn , n ≥ 3, consists of n vertices

v1 , v2 , . . . , vn and edges {v1 , v2 }, {v2 , v3 }, . . . , {vn−1 , vn }, and
{vn , v1 }.
Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

C5 C4

8.17
Wheels Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

We obtain a wheel (ç thà h¼nh b¡nh xe ) 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 .
Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

W5 W4

8.18
n-cube
Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

An n-dimensional hypercube (khèi n chi·u ), Qn , is a graph that

has vertices representing the 2n bit strings of length n. Two
vertices are adjacent iff the bit strings that they represent differ in
exactly one bit position.

Contents
110 111
Graph definitions
Terminology

10 11 100 101 Special Graphs

Representing Graphs
and Graph
Isomorphism
010 011 Representing Graphs

0 1 Graph Isomorphism

Exercise
Graph

00 01 000 001 Bipartie graph

Isomorphism

Q1 Q2 Q3

8.19
n-cube
Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

An n-dimensional hypercube (khèi n chi·u ), Qn , is a graph that

has vertices representing the 2n bit strings of length n. Two
vertices are adjacent iff the bit strings that they represent differ in
exactly one bit position.

Contents
110 111
Graph definitions
Terminology

10 11 100 101 Special Graphs

Representing Graphs
and Graph
Isomorphism
010 011 Representing Graphs

0 1 Graph Isomorphism

Exercise
Graph

00 01 000 001 Bipartie graph

Isomorphism

Q1 Q2 Q3

What's about Q4 ?
8.19
Applications of Special Graphs Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

• Local networks topologies Contents

• Star, ring, hybrid Graph definitions
•
Terminology

Parallel processing Special Graphs

• Linear array Representing Graphs

and Graph
• Mesh network Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.20
Graph Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

• One goat, a cabbage and a wolf are on a side of river; a

boatman wishes to transport them to the other side but, his
boat being too small, he could transport only one of them at
once.

• How does he proceed not to leave them together without Contents

surveillance: the wolf and the goat, as well as the goat and Graph definitions
Terminology

the cabbage? Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.21
Graph Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

• One goat, a cabbage and a wolf are on a side of river; a

boatman wishes to transport them to the other side but, his
boat being too small, he could transport only one of them at
once.

• How does he proceed not to leave them together without Contents

surveillance: the wolf and the goat, as well as the goat and Graph definitions
Terminology

the cabbage? Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.21
Exercise Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

Exercise (1) Trang

Is there any undirected simple graph including four vertices that

their degrees are respectively 1, 1, 2, 2 ?

Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.22
Exercise Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

Exercise (1) Trang

Is there any undirected simple graph including four vertices that

their degrees are respectively 1, 1, 2, 2 ?

Exercise (2)
Contents
Is there any undirected simple graph including six vertices that Graph definitions
their degree are respectively 2, 3, 3, 3, 3, 3 ? Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.22
Exercise Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

Exercise (1) Trang

Is there any undirected simple graph including four vertices that

their degrees are respectively 1, 1, 2, 2 ?

Exercise (2)
Contents
Is there any undirected simple graph including six vertices that Graph definitions
their degree are respectively 2, 3, 3, 3, 3, 3 ? Terminology

Special Graphs

Representing Graphs
and Graph
Exercise (3) Isomorphism
Representing Graphs

What is the largest number of edges a undirected simple graph Graph Isomorphism

with 10 vertices can have ? Exercise

Graph

Bipartie graph

Isomorphism

8.22
Exercise Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

Exercise (1) Trang

Is there any undirected simple graph including four vertices that

their degrees are respectively 1, 1, 2, 2 ?

Exercise (2)
Contents
Is there any undirected simple graph including six vertices that Graph definitions
their degree are respectively 2, 3, 3, 3, 3, 3 ? Terminology

Special Graphs

Representing Graphs
and Graph
Exercise (3) Isomorphism
Representing Graphs

What is the largest number of edges a undirected simple graph Graph Isomorphism

with 10 vertices can have ? Exercise

Graph

Bipartie graph

Exercise (4) Isomorphism

An undirected simple graph G has 15 edges, 3 vertices of degree 4

and other vertices having degree 3. What is the number of vertices
of the graph G?

8.22
Exercise Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

Exercise (5) Trang

Give the number of edges in function of number of vertices in a

complete graph Kn .

Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.23
Exercise Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

Exercise (5) Trang

Give the number of edges in function of number of vertices in a

complete graph Kn .

Exercise (6)
Contents
Give an undirected simple graph G = (V, E) with |V | = n, show Graph definitions
that
Terminology

Special Graphs

a) ∀v ∈ V , deg(v) < n, Representing Graphs

and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.23
Exercise Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

Exercise (5) Trang

Give the number of edges in function of number of vertices in a

complete graph Kn .

Exercise (6)
Contents
Give an undirected simple graph G = (V, E) with |V | = n, show Graph definitions
that
Terminology

Special Graphs

a) ∀v ∈ V , deg(v) < n, Representing Graphs

and Graph
b) there does not exist simultaneously both a vertex of degree 0 Isomorphism
Representing Graphs

and a vertex of degree (n − 1), Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.23
Exercise Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

Exercise (5) Trang

Give the number of edges in function of number of vertices in a

complete graph Kn .

Exercise (6)
Contents
Give an undirected simple graph G = (V, E) with |V | = n, show Graph definitions
that
Terminology

Special Graphs

a) ∀v ∈ V , deg(v) < n, Representing Graphs

and Graph
b) there does not exist simultaneously both a vertex of degree 0 Isomorphism
Representing Graphs

and a vertex of degree (n − 1), Graph Isomorphism

Exercise
c) deduce that there are at least two vertices of the same degree. Graph

Bipartie graph

Isomorphism

8.23
Exercise Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

Exercise (5) Trang

Give the number of edges in function of number of vertices in a

complete graph Kn .

Exercise (6)
Contents
Give an undirected simple graph G = (V, E) with |V | = n, show Graph definitions
that
Terminology

Special Graphs

a) ∀v ∈ V , deg(v) < n, Representing Graphs

and Graph
b) there does not exist simultaneously both a vertex of degree 0 Isomorphism
Representing Graphs

and a vertex of degree (n − 1), Graph Isomorphism

Exercise
c) deduce that there are at least two vertices of the same degree. Graph

Bipartie graph

Isomorphism

Exercise (7)
Is it possible that each person has exactly 5 friends in the same
group of 9 people ?

8.23
Prove that ... Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

...
There are 101 invited people in a party. Contents
Suppose that A knows B ⇒ B knows A. Graph definitions
Prove that Terminology

Special Graphs

1 at least one people knows an even number of other people. Representing Graphs
and Graph
2 at least two people who know the same number of people (but not Isomorphism
considering himself). Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.24
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

A chess tournament of n persons plays according to the circle competition. Trang

Prove that at any moment of the tournament there are always two players
having identical number of games played.
And if n ≥ 4, at any intermediate moment of the tournament, there are
always two players having identical number of games that they are the winner.

Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.25
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

A chess tournament of n persons plays according to the circle competition. Trang

Prove that at any moment of the tournament there are always two players
having identical number of games played.
And if n ≥ 4, at any intermediate moment of the tournament, there are
always two players having identical number of games that they are the winner.

Contents
In a tournament with n teams participated (n ≥ 4), n + 1 competition games
Graph definitions
were happening. Prove that there exists a team that has played at least three Terminology

matches. Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.25
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

A chess tournament of n persons plays according to the circle competition. Trang

Prove that at any moment of the tournament there are always two players
having identical number of games played.
And if n ≥ 4, at any intermediate moment of the tournament, there are
always two players having identical number of games that they are the winner.

Contents
In a tournament with n teams participated (n ≥ 4), n + 1 competition games
Graph definitions
were happening. Prove that there exists a team that has played at least three Terminology

matches. Special Graphs

Representing Graphs
and Graph
Isomorphism
With any four of the n people (n ≥ 4), there exists a person who knows the Representing Graphs

three others. Prove that there exists a person who knows all n − 1 others. Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.25
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

A chess tournament of n persons plays according to the circle competition. Trang

Prove that at any moment of the tournament there are always two players
having identical number of games played.
And if n ≥ 4, at any intermediate moment of the tournament, there are
always two players having identical number of games that they are the winner.

Contents
In a tournament with n teams participated (n ≥ 4), n + 1 competition games
Graph definitions
were happening. Prove that there exists a team that has played at least three Terminology

matches. Special Graphs

Representing Graphs
and Graph
Isomorphism
With any four of the n people (n ≥ 4), there exists a person who knows the Representing Graphs

three others. Prove that there exists a person who knows all n − 1 others. Graph Isomorphism

Exercise
Graph

Bipartie graph

In a party of 6 people, prove that there are 3 people who know each other or 3 Isomorphism

people who do not know each other.

8.25
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

A chess tournament of n persons plays according to the circle competition. Trang

Prove that at any moment of the tournament there are always two players
having identical number of games played.
And if n ≥ 4, at any intermediate moment of the tournament, there are
always two players having identical number of games that they are the winner.

Contents
In a tournament with n teams participated (n ≥ 4), n + 1 competition games
Graph definitions
were happening. Prove that there exists a team that has played at least three Terminology

matches. Special Graphs

Representing Graphs
and Graph
Isomorphism
With any four of the n people (n ≥ 4), there exists a person who knows the Representing Graphs

three others. Prove that there exists a person who knows all n − 1 others. Graph Isomorphism

Exercise
Graph

Bipartie graph

In a party of 6 people, prove that there are 3 people who know each other or 3 Isomorphism

people who do not know each other.

During a summer vacation, 7 friends are vacationing away. They promised

each other that during the holidays each person must write to exactly three of
them. Prove that there is someone who does not write back to the his sender.
8.25
Bipartite Graphs Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

Definition Trang

A simple graph G is called bipartite (ç

thà ph¥n æi ) if its vertex
set V V1 and V2 such that
can be partitioned into two disjoint sets
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 ) Contents
Graph definitions

Example
Terminology

Special Graphs

Representing Graphs
C6 is bipartite and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

C6

8.26
Complete Bipartite Graphs Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition
A complete bipartite 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 iff one vertex is in the first Contents

subset and the other is in the second one Graph definitions

Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

K3,3

8.27
Bipartite graphs Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Example (Bipartite graphs?)

• C6
• Cn
• K3
Contents
• Kn Graph definitions
• the
Terminology

following graph Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.28
New Graph From Old Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition
A subgraph (ç thà con) of a graph G = (V, E) is a graph
H = (W, F ) where W ⊆V and F ⊆ E.

Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.29
New Graph From Old Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition
A subgraph (ç thà con) of a graph G = (V, E) is a graph
H = (W, F ) where W ⊆V and F ⊆ E.

Definition Contents

The union (hñp) of two simple graphs G1 = (V1 , E1 ) and Graph definitions
Terminology

G2 = (V2 , E2 ) is a simple graph with vertex set V1 ∪ V2 and edge Special Graphs

set E1 ∪ E2 . The union of G1 and G2 is denoted by G1 ∪ G2 . Representing Graphs

and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.29
New Graph From Old Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition
A subgraph (ç thà con) of a graph G = (V, E) is a graph
H = (W, F ) where W ⊆V and F ⊆ E.

Definition Contents

The union (hñp) of two simple graphs G1 = (V1 , E1 ) and Graph definitions
Terminology

G2 = (V2 , E2 ) is a simple graph with vertex set V1 ∪ V2 and edge Special Graphs

set E1 ∪ E2 . The union of G1 and G2 is denoted by G1 ∪ G2 . Representing Graphs

and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

G1 G2 G1 ∪ G2

8.29
Planar Graphs Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.30
Planar Graphs Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.30
Planar Graphs Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition
• A graph is called planar (ph¯ng ) if it can be drawn in the
plane without any edges crossing.

• Such a drawing is called planar representation (biºu di¹n

ph¯ng ) of the graph. Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

K4 K4 with no crossing

8.31
Important Corollaries Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen

Corollary An Khuong, Le Hong

Trang

• If G is a connected planar simple graph with e edges and v

vertices where v ≥ 3, then e ≤ 3v − 6.

Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.32
Important Corollaries Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen

Corollary An Khuong, Le Hong

Trang

• If G is a connected planar simple graph with e edges and v

vertices where v ≥ 3, then e ≤ 3v − 6.
• If G is a connected planar simple graph with e edges and v
vertices where v ≥ 3, and no circuits of length 3, then
Contents
e ≤ 2v − 4.
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

K3,3

8.32
Important Corollaries Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen

Corollary An Khuong, Le Hong

Trang

• If G is a connected planar simple graph with e edges and v

vertices where v ≥ 3, then e ≤ 3v − 6.
• If G is a connected planar simple graph with e edges and v
vertices where v ≥ 3, and no circuits of length 3, then
Contents
e ≤ 2v − 4.
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

K3,3
Non-planar

8.32
Important Corollaries Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen

Corollary An Khuong, Le Hong

Trang

• If G is a connected planar simple graph with e edges and v

vertices where v ≥ 3, then e ≤ 3v − 6.
• If G is a connected planar simple graph with e edges and v
vertices where v ≥ 3, and no circuits of length 3, then
Contents
e ≤ 2v − 4.
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

K3,3
Non-planar
K5

8.32
Important Corollaries Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen

Corollary An Khuong, Le Hong

Trang

• If G is a connected planar simple graph with e edges and v

vertices where v ≥ 3, then e ≤ 3v − 6.
• If G is a connected planar simple graph with e edges and v
vertices where v ≥ 3, and no circuits of length 3, then
Contents
e ≤ 2v − 4.
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

K3,3
Non-planar
K5
Non-planar

8.32
Elementary Subdivision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition
• Given a planar graphG, an elementary subdivision (ph¥n chia
sì c§p ) is removing an edge {u, v} and adding a new vertex
w together with edges {u, w} and {w, v}.
Contents
• Graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) are called Graph definitions
homeomorphic (çng phæi ) if they can obtained from the Terminology

Special Graphs

same graph by a sequence of elementary subdivisions. Representing Graphs

and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.33
Kuratowski's Theorem Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Theorem
A graph is nonplanar iff it contains a subgraph homeomorphic to
K3,3 or K5 .
Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.34
Kuratowski's Theorem Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Theorem
A graph is nonplanar iff it contains a subgraph homeomorphic to
K3,3 or K5 .
Contents
Graph definitions
a Terminology

Special Graphs

Representing Graphs
f and Graph
Isomorphism
e b Representing Graphs

j g
Graph Isomorphism

Exercise
i h Graph

Bipartie graph

d c Isomorphism

8.34
Kuratowski's Theorem Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Theorem
A graph is nonplanar iff it contains a subgraph homeomorphic to
K3,3 or K5 .
Contents
Graph definitions
a Terminology

Special Graphs

Representing Graphs
f f d and Graph
c j Isomorphism
e b Representing Graphs

j g
Graph Isomorphism
a g
Exercise
i h Graph
e Bipartie graph
i h
d c Isomorphism

8.34
Kuratowski's Theorem Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Theorem
A graph is nonplanar iff it contains a subgraph homeomorphic to
K3,3 or K5 .
Contents
Graph definitions
a Terminology

Special Graphs

Representing Graphs
f f d and Graph
c j Isomorphism
e b Representing Graphs

j g
Graph Isomorphism
a g
Exercise
i h Graph
e Bipartie graph
i h
d c Isomorphism

8.34
Exercise Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Exercise
• Is K4 planar?
• Is Q3 planar?

110 111 Contents

Graph definitions
Terminology

100 101 Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

010 011 Graph Isomorphism

Exercise
Graph

Bipartie graph

000 001 Isomorphism

K4 Q3

8.35
Adjacency Lists (Danh s¡ch k·) Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Vertex Adjacent vertices Initial vertex Terminal vertices

a b, c, e a b, c, d, e
b a b b, d
c a, d, e c a, c, e
Contents
d c, e d c, e
Graph definitions
e a, c, d e b, c, d Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.36
Adjacency Matrices Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

Definition Trang

Adjacency matrix (Ma trªn k· ) AG of G = (V, E)

• Dimension |V | × |V |
• Matrixelements
1 if (vi , vj ) ∈E
aij = Contents
0 otherwise
Graph definitions
Terminology

Special Graphs

a b Representing Graphs
and Graph
Isomorphism

 a b c d 
Representing Graphs

Graph Isomorphism

a 0 1 1 1 Exercise
b 
 1 0 1 0 

Graph

Bipartie graph

c  1 1 0 0  Isomorphism

d 1 0 0 0

c d

8.37
Examples Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Example
Give the graph defined by the following adjacency matrix

Contents

 A B C D E  Graph definitions
Terminology

Special Graphs

A  0 0 1 1 0  Representing Graphs
and Graph
 
B 
 0 0 0 1 0 
 Isomorphism
C 
 1 0 0 1 0 

Representing Graphs

Graph Isomorphism

D 
 1 1 1 0 1 
 Exercise
E  0 0 0 1 0  Graph

Bipartie graph

Isomorphism

8.38
Adjacency Matrices Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Example
Give the directed graph defined by the following adjacency matrix

Contents

 A B C D E  Graph definitions
Terminology

Special Graphs

A  1 0 1 1 0  Representing Graphs
and Graph
 
B 
 0 0 0 0 0 
 Isomorphism
C 
 1 0 0 0 0 

Representing Graphs

Graph Isomorphism

D 
 1 1 1 0 1 
 Exercise
E  1 0 0 0 0  Graph

Bipartie graph

Isomorphism

8.39
Incidence Matrices Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong

Definition Trang

Incidence matrix (ma trªn li¶n thuëc ) MG of G = (V, E)

• Dimension |V | × |E|
• Matrix 
elements
1 if ej is incident with vi
mij = Contents
0 otherwise
Graph definitions
Terminology

Special Graphs

a e2 b Representing Graphs
and Graph
Isomorphism

 e1 e2 e3 e4 
Representing Graphs

Graph Isomorphism

a 1 1 1 0 Exercise
e1 b  0 1 0 1  Graph

e4 e3   Bipartie graph

c  1 0 0 1  Isomorphism

d 0 0 1 0

c d

8.40
Examples Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Example
Give incidence matrix according to the following graph

Contents
F
Graph definitions
Terminology

B C Special Graphs

Representing Graphs
and Graph
Isomorphism
A Representing Graphs

Graph Isomorphism

Exercise
Graph
E D Bipartie graph

G Isomorphism

8.41
Graph Isomorphism Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition
G1 = (V1 , E1 ) and G2 = (V2 , E2 ) are isomorphic (¯ng c§u ) if
there is a one-to-one function f from V1 to V2 with the property
that a b are adjacent in G1 iif f (a) and f (b) are adjacent
and in
G2 , a and b in V1 . Such a function f is called an
for all Contents

isomorphism (mët ¯ng c§u). Graph definitions

Terminology

(i.e. there is a one-to-one correspondence between vertices of the Special Graphs

two graphs that preserves the adjacency relationship.) Representing Graphs

and Graph
Isomorphism
Representing Graphs

u1 u2 v1 v2 Graph Isomorphism

Isomorphism function f : U −→ Exercise

V with Graph

f (u1 ) = v1 f (u2 ) = v4 Bipartie graph

Isomorphism

f (u3 ) = v3 f (u4 ) = v2
u3 u4 v3 v4

8.42
Bipartie graph Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.43
Isomorphism ? Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Contents
Graph definitions
Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.44
Isomorphism? Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

A B
Contents
B
Graph definitions
Terminology

Special Graphs

F C
C Representing Graphs
and Graph
Isomorphism
Representing Graphs

D
Graph Isomorphism

E D Exercise
G2 Graph

F E Bipartie graph

G1 Isomorphism

8.45
Isomorphism? Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

A1 A2 B2

Contents
Graph definitions

D1 E1 E2 F2 Terminology

Special Graphs

Representing Graphs
and Graph
F1 Isomorphism
Representing Graphs

Graph Isomorphism

C1 B1 D2 C2 Exercise
Graph

G1 G2 Bipartie graph

Isomorphism

8.46
Isomorphism Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Are the simple graphs with the following adjacency matrices

isomorphic ?
   
0 0 1 0 1 1
Contents
1  0 0 1   1 0 0  Graph definitions
1 1 0 1 0 0 Terminology

Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.47
Isomorphism Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Are the simple graphs with the following adjacency matrices

isomorphic ?
   
0 0 1 0 1 1
Contents
1  0 0 1   1 0 0 
Graph definitions
1 1 0 1 0 0 Terminology

    Special Graphs

0 1 0 1 0 1 1 1 Representing Graphs
 1 and Graph
0 0 1   1 0 0 1  Isomorphism
2 
 0
  
0 0 1   1 0 0 1  Representing Graphs

Graph Isomorphism

1 1 1 0 1 1 1 0 Exercise
Graph

Bipartie graph

Isomorphism

8.47
Isomorphism Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Are the simple graphs with the following adjacency matrices

isomorphic ?
   
0 0 1 0 1 1
Contents
1  0 0 1   1 0 0 
Graph definitions
1 1 0 1 0 0 Terminology

    Special Graphs

0 1 0 1 0 1 1 1 Representing Graphs
 1 and Graph
0 0 1   1 0 0 1  Isomorphism
2 
 0
  
0 0 1   1 0 0 1  Representing Graphs

Graph Isomorphism

1 1 1 0 1 1 1 0 Exercise
    Graph

0 1 1 0 0 1 0 1 Bipartie graph

 1 0 0 1   1 0 0 0  Isomorphism

3 
 1
  
0 0 1   0 0 0 1 
0 1 1 0 1 0 1 0

8.47
Isomorphism Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Determine whether the graphs (without loops) with the incidence

matrices are isomorphic.
   
1 0 1 1 1 0 Contents
•  0 1 1   1 0 1  Graph definitions
Terminology
1 1 0 0 1 1 Special Graphs

Representing Graphs
and Graph
Isomorphism
Representing Graphs

Graph Isomorphism

Exercise
Graph

Bipartie graph

Isomorphism

8.48
Isomorphism Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Determine whether the graphs (without loops) with the incidence

matrices are isomorphic.
   
1 0 1 1 1 0 Contents
•  0 1 1   1 0 1  Graph definitions
Terminology
1 1 0 0 1 1 Special Graphs

Representing Graphs
   
1 1 0 0 0 0 1 0 0 1 and Graph
 1 0 1 0 1   0 1 1 1 0  Isomorphism
•     Representing Graphs

 0 0 0 1 1   1 0 0 1 0  Graph Isomorphism

0 1 1 1 0 1 0 1 0 1 Exercise
Graph

Bipartie graph

Isomorphism

8.48
Isomorphism Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Determine whether the graphs (without loops) with the incidence

matrices are isomorphic.
   
1 0 1 1 1 0 Contents
•  0 1 1   1 0 1  Graph definitions
Terminology
1 1 0 0 1 1 Special Graphs

Representing Graphs
   
1 1 0 0 0 0 1 0 0 1 and Graph
 1 0 1 0 1   0 1 1 1 0  Isomorphism
•     Representing Graphs

 0 0 0 1 1   1 0 0 1 0  Graph Isomorphism

0 1 1 1 0 1 0 1 0 1 Exercise
Graph

• Extend the definition of isomorphism of simple graphs to Bipartie graph

Isomorphism

undirected graphs containing loops and multiple edges.

• Define isomorphism of directed graphs

8.48
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

ç thà G1 v  G2 t÷ìng ùng vîi c¡c ma trªn li·n k· v  li¶n thuëc

d÷îi ¥y.
(G1 ) A B C D E  (G2 )  e1 e2 e3 e4 e5 e6 e7
A 0 1 1 1 1 1 0 0 0 1 1 0

A
B  1 0 0 1 0  B  1 1 0 1 0 0 0 Contents

0 1 1 0 1 0 0
   
C  1 0 0 1 0  C  Graph
 definitions

0 0 1 1 0 0 1
  
D  1 1 1 0 1  D  
Terminology

E 1 0 0 1 0 E 0 0 0 0 0 1 1 Special Graphs

Representing Graphs
H¢y cho bi¸t quan h» cõa hai ç thà G1 v  G2 . and Graph
Isomorphism
A) ¯ng c§u Representing Graphs

Graph Isomorphism

B) Khæng ¯ng c§u Exercise

C)
Graph

Thù tü Bipartie graph

D)
Isomorphism

T֓ng ֓ng

8.49
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

X²t ç thà ¦y õ K5 v  ç thà ph¥n æi ¦y õ K3,2 . Khi â ta

câ:
Contents
Graph definitions
Terminology

A) K3,2 v  K5 l  khæng ¯ng c§u. Special Graphs

Representing Graphs
B) K3,2 v  K5 câ còng sè ¿nh. and Graph
Isomorphism
C) K3,2 v  K5 câ còng sè c¤nh.
Representing Graphs

Graph Isomorphism

D) K3,2 v  K5 l  ¯ng c§u.

Exercise
Graph

E) C¡c ¡p ¡n kh¡c ·u sai.

Bipartie graph

Isomorphism

8.50
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Chån ph¡t biºu óng vîi ç thà ìn væ h÷îng (undirected simple
graph) câ n ¿nh. Contents
Graph definitions
A)
Terminology

Bªc cõa mët ¿nh b§t ký trong ç thà nhä hìn n − 2. Special Graphs

B) Tçn t¤i mët ¿nh trong ç thà câ bªc l  1. Representing Graphs

and Graph
Isomorphism
C) Khæng thº chùa ¿nh cæ lªp. Representing Graphs

D)
Graph Isomorphism

Tçn t¤i hai ¿nh trong ç thà câ còng sè bªc.

Exercise
E) C¡c ¡p ¡n kh¡c ·u sai. Graph

Bipartie graph

Isomorphism

8.51
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen

Trong ký Hoa Sìn luªn vã, n«m và cao thõ ¢ g°p nhau º x¡c ành An Khuong, Le Hong
Trang
danh hi»u » nh§t: æng T , T¥y ëc, Nam ¸, B­c C¡i v  Trung
Th¦n Thæng.
º ph¥n bi»t th­ng thua th¼ hå §u tøng c°p æi v  khæng giîi h¤n thíi
gian. Nh  væ àch l  ng÷íi câ nhi·u trªn th­ng nh§t.
æng T  khæng thº ¡nh b¤i Nam ¸, nh÷ng æng ta ¢ ¡nh b¤i T¥y
ëc. Contents
Do dòng nhi·u sùc trong méi trªn §u n¶n Nam ¸ ch¿ th­ng hai trªn Graph definitions
¦u ti¶n. Terminology

B­c C¡i ch¿ th­ng ÷ñc Nam ¸. Special Graphs

Representing Graphs
T¥y ëc khæng thº chi¸n th­ng Trung Th¦n Thæng, nh÷ng l¤i chi¸n and Graph
th­ng Nam ¸ v  B­c C¡i. Isomorphism

Ri¶ng Trung Th¦n Thæng ch¿ bà th§t b¤i mët trªn §u.
Representing Graphs

Graph Isomorphism

H¢y cho bi¸t Trung Th¦n Thæng ¢ bà ¡nh b¤i bði và n o? Exercise
Graph

Bipartie graph

A) Nam ¸ Isomorphism

B) Nam ¸ ho°c æng T 

C) æng T 
D) T¥y ëc

8.52
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Mët dü ¡n gçm c¡c cæng vi»c A, B , C , D , E , F v  G c¦n thüc

hi»n. Thíi l÷ñng (theo ng y) c¦n thi¸t º xû lþ c¡c cæng vi»c l¦n
l÷ñt l 

pA pB pC pD pE pF pG
5 2 6 7 9 3 2 Contents
Graph definitions
Ta kþ hi»u
Terminology

Special Graphs

Representing Graphs
X1 + X2 + . . . + Xn  Y1 + Y2 + . . . + Ym and Graph
Isomorphism
Representing Graphs

biºu di¹n c¡c cæng vi»c Xi (i = 1, . . . , n) ·u c¦n ho n th nh Graph Isomorphism

Exercise
tr÷îc khi khði ëng c¡c cæng vi»c Yk (k = 1, . . . , m).
Graph

X²t thíi gian b­t ¦u khði ëng dü ¡n l  0. Dü ¡n ÷ñc gåi l  Bipartie graph

Isomorphism

k¸t thóc khi t§t c£ c¡c cæng vi»c trong dü ¡n ·u ho n th nh.
Bi¸t r¬ng: A  B + C ; B + C  D; C  F + G; E  F .
Häi dü ¡n n y s³ k¸t thóc sîm nh§t v o ng y n o?

8.53
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Mët ban ch¿ huy qu¥n sü muèn thi¸t lªp mët m°t trªn gçm c¡c
cù iºm a, b, . . ., g . C¡c cù iºm n y v  ÷íng nèi trüc ti¸p giúa
chóng t¤o n¶n mët ç thà ìn væ h÷îng.
Do sè l÷ñng thi¸t gi¡p câ giîi h¤n n¶n
Contents
ban ch¿ huy quy¸t ành ch¿ çn tró thi¸t
Graph definitions
b c gi¡p t¤i mët sè cù iºm m  thæi. Tuy Terminology

nhi¶n, º £m b£o t½nh t¡c chi¸n nhanh Special Graphs

châng n¶n ta y¶u c¦u: n¸u cù iºm n o Representing Graphs

and Graph
a g d khæng câ çn tró thi¸t gi¡p th¼ ½t nh§t Isomorphism
Representing Graphs

mët cù iºm b¶n c¤nh (¿nh k·) ph£i câ Graph Isomorphism

ìn và thi¸t gi¡p çn tró. Exercise

f e Graph

Häi câ bao nhi¶u c¡ch triºn khai thi¸t Bipartie graph

gi¡p ¸n c¡c cù iºm cho m°t trªn nh÷ Isomorphism

ç thà b¶n ?

8.54
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

C
Contents
Graph definitions
Terminology

D Special Graphs

Representing Graphs
F and Graph
Isomorphism
E Representing Graphs

Graph Isomorphism

a) H¢y x¡c ành danh s¡ch k·, ma trªn k· v  ma trªn li¶n thuëc Exercise
Graph

cõa ç thà tr¶n. Bipartie graph

b)
Isomorphism

H¢y cho bi¸t ç thà n y câ ph£i l  ç thà ph¥n æi khæng.
N¸u câ, h¢y v³ l¤i d÷îi d¤ng mët ç thà ph¥n æi.

8.55
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Do khâi, böi v  hìi n÷îc bèc l¶n tø mët mi»ng nói lûa b¶n d÷îi
m°t sæng b«ng Eyjafjallajokull ð Iceland v o ng y thù t÷

(14/04/2010), hìn 90.000 chuy¸n bay ð ch¥u …u ¢ bà hõy. ¥y

công l  mët minh chùng v· sü b§t ên cõa thi¶n nhi¶n câ thº g¥y
tên h¤i tîi cæng vi»c kinh doanh to n c¦u.
Contents
º gi£m thiºu thi»t h¤i v· kinh t¸, cì quan qu£n lþ tèi ÷u hâa v 
Graph definitions
lªp làch ÷íng bay EuroControl cè g­ng ti¸p töc duy tr¼ mët sè Terminology

Special Graphs

÷íng bay i v  ¸n Vi»t Nam, li¶n quan ¸n c¡c th nh phè lîn
Representing Graphs
nh÷: Hç Ch½ Minh (A), Paris (B ), Berlin (C ), v  London (D ). Tuy and Graph
Isomorphism
nhi¶n, do £nh h÷ðng cõa mæi tr÷íng thi¶n nhi¶n nâi tr¶n, ch¿ câ Representing Graphs

mët v i chuy¸n bay câ thº ho¤t ëng: tø A h÷îng ¸n B v  D, tø Graph Isomorphism

Exercise
B h÷îng ¸n C, tø C h÷îng ¸n A v  D, tø D h÷îng ¸n B . Graph

a) H¢y v³ ç thà câ h÷îng t÷ìng ùng.

Bipartie graph

Isomorphism

b) Vi¸t ma trªn k· M cho ç thà câ h÷îng n y

c) H¢y t½nh M + M2 + M3 v  cho bi¸t þ ngh¾a cõa ma trªn n y.

8.56
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Hai lîp ÷ñc ành ngh¾a nh÷ c¡c h¼nh b¶n d÷îi tr¡i. H¢y v³ ç thà biºu Tran Tuan Anh, Nguyen
An Khuong, Le Hong

di¹n h m th nh vi¶n câ thº ÷ñc gåi tø mët h m. Trang

(Chó þ : Mët cung tø h m u ¸n h m v biºu di¹n

class X r¬ng v câ thº ÷ñc gåi bði u.)
public:
X();
 X();
a(); Contents
protected: Graph definitions
b();
Terminology

Special Graphs

private: Representing Graphs

and Graph
c(); Isomorphism
Representing Graphs

class Y
Graph Isomorphism

Exercise
public: Graph

Y();
Bipartie graph

Isomorphism

 Y();
e();
private:
d();

8.57
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Hai lîp ÷ñc ành ngh¾a nh÷ c¡c h¼nh b¶n d÷îi tr¡i. H¢y v³ ç thà biºu Tran Tuan Anh, Nguyen
An Khuong, Le Hong

di¹n h m th nh vi¶n câ thº ÷ñc gåi tø mët h m. Trang

(Chó þ : Mët cung tø h m u ¸n h m v biºu di¹n

class X r¬ng v câ thº ÷ñc gåi bði u.) V½ dö.
public:
X();
 X();
a(); X :: b() Contents
protected: Graph definitions
b();
Terminology

Special Graphs

private: Representing Graphs

and Graph
c(); X :: a() X :: c()
Isomorphism
Representing Graphs

class Y
Graph Isomorphism

Exercise
public: Graph

Y();
Bipartie graph

Isomorphism

 Y(); Y :: e() Y :: d()

e();
private:
d();

8.57
Revision Introduction to Graphs

Huynh Tuong Nguyen,

Hai lîp ÷ñc ành ngh¾a nh÷ c¡c h¼nh b¶n d÷îi tr¡i. H¢y v³ ç thà biºu Tran Tuan Anh, Nguyen
An Khuong, Le Hong

di¹n h m th nh vi¶n câ thº ÷ñc gåi tø mët h m. Trang

(Chó þ : Mët cung tø h m u ¸n h m v biºu di¹n

class X r¬ng v câ thº ÷ñc gåi bði u.) V½ dö.
public:
X();
 X();
a(); X :: b() Contents
protected: Graph definitions
b();
Terminology

Special Graphs

private: Representing Graphs

and Graph
c(); X :: a() X :: c()
Isomorphism
Representing Graphs

class Y
Graph Isomorphism

Exercise
public: Graph

Y();
Bipartie graph

Isomorphism

 Y(); Y :: e() Y :: d()

e();
private:
d();
Câ bao nhi¶u ÷íng i ìn kh¡c nhau tø ¿nh X::a() ¸n ¿nh Y::d() ?
8.57