Định nghĩa
▶ Chu trình chứa mọi đỉnh của đồ thị gọi là chu trình
Hamilton.
▶ Hành trình dùng mỗi cạnh đúng một lần gọi là hành trình
Euler.
Tìm chu trình Hamilton của đồ thị tạo bởi các đỉnh và cạnh của
khối lập phương.
10.7 P
K4 Drawn
sings.
FIGURE 4 The
Graph Q3.
FIGURE 5
Represent
56 / 57Bài tập
Năm tới, Dr Chunner và Dr Dodder định đi thăm đảo Mianda. Các
địa điểm hấp dẫn và đường đi nối giữa chúng được biểu diễn bởi
đồ thị có danh sách kề là
0 1 2 3 4 5 6 7 8
1 0 1 0 3 0 1 0 1
3 2 3 2 5 4 5 2 3
5 6 7 4 6 7 6 5
7 8 8 8 8 7
▶ Liệu họ có thể tìm đường đi trên đảo để thăm mỗi địa điểm
đúng một lần và trở về vị trí xuất phát?
▶ Liệu họ có thể tìm cách để đi hết các con đường, mỗi đường
đúng một lần; địa điểm bắt đầu và kết thúc có thể khác nhau?
57 trang |
Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 381 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng Toán rời rạc - Bài 4: Đồ thị - Trần Vĩnh Đức, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Đồ thị
Trần Vĩnh Đức
HUST
Ngày 24 tháng 7 năm 2018
1 / 57
Tài liệu tham khảo
▶ Norman L. Biggs, Discrete Mathematics, Oxford University
Press, 2002.
2 / 57
1/26/16, 10:42 AMHồ Hoàn Kiếm đến Bách Khoa, Hai Bà Trưng - Google Maps
Page 1 of 1https://www.google.com/maps/dir/Hồ+Hoàn+Kiếm,+Hàng+Trống,+Hoàfe1abd:0x22b136bcf1c08e2a!2m2!1d105.8459098!2d21.0042694!3e2
Dữ liệu bản đồ ©2016 Google 1 ki lô mét
50 p
4,1 km
via Phố Huế
51 p
4,2 km
via Hàng Bài
52 p
4,2 km
via Bà Triệu
Đi bộ 4,1 km, 50 pHồ Hoàn Kiếm đến Bách Khoa, Hai Bà Trưng
3 / 57
Nội dung
Đồ thị và biểu diễn
Một số đồ thị đặc biệt
Đẳng cấu
Bậc
Đường đi và chu trình
Định nghĩa
Một đồ thị G là một cặp có thứ tự G = (V,E), ở đây V là một
tập, còn E là tập với các phần tử là các tập con hai phần tử của V.
Các phần tử của V được gọi là các đỉnh, còn các phần tử của E
gọi là các cạnh của G.
Ví dụ
Xét đồ thị G = (V,E) trong đó
V = {a, b, c, d, z}
E = {{a, b}, {a, d}, {b, z}, {c, d}, {d, z}}.
a
z b
d c
5 / 57
Định nghĩa
▶ Hai đỉnh x và y gọi là kề nhau (hay hàng xóm) nếu {x, y} là
một cạnh của đồ thị.
▶ Ta biểu diễn đồ thị G = (V,E) bởi danh sách kề, trong đó
mỗi đỉnh v giữ một danh sách các đỉnh kề với v.
Ví dụ a
z b
d c
a b c d z
b a d a b
d z c d
z
6 / 57
Bài tập
Có ba ngôi nhà A,B,C, mỗi ngôi nhà đều kết nối với cả ba nhà
cung cấp ga, nước, và điện: G,W,E.
1. Hãy viết danh sách kề cho đồ thị biểu diễn bài toán này và
vẽ nó.
2. Liệu bạn có thể vẽ đồ thị này trên mặt phẳng để không có
cạnh cắt nhau không?
7 / 57
Ví dụ
▶ GS Mc Brain và vợ là bà April tới một bữa tiệc ở đó có 4 đôi
vợ chồng khác.
▶ Có một vài cặp bắt tay nhau nhưng không ai bắt tay với vợ
hoặc chồng mình.
▶ GS hỏi mọi người khác xem họ bắt tay bao nhiêu người và
ông ấy nhận được 9 con số khác nhau.
▶ Hỏi có bao nhiêu người đã bắt tay April?
8 / 57
Nội dung
Đồ thị và biểu diễn
Một số đồ thị đặc biệt
Đẳng cấu
Bậc
Đường đi và chu trình
Đồ thị đầy đủ
Định nghĩa
Đồ thị đầy đủ gồm n đỉnh, ký hiệu là Kn là đồ thị có đúng một
cạnh nối mỗi cặp đỉnh phân biệt.
10.2 Graph Terminology and Special Types of Graphs 655
EXAMPLE 5 Complete Graphs A complete graph on n vertices, denoted by Kn, is a simple graph
that contains exactly one edge between each pair of distinct vertices. The graphs Kn, for
n = 1, 2, 3, 4, 5, 6, are displayed in Figure 3. A simple graph for which there is at least one
pair of distinct vertex not connected by an edge is called noncomplete. ▲
K1 K2 K3 K4 K5 K6
FIGURE 3 The Graphs Kn for 1 ≤ n ≤ 6.
EXAMPLE 6 Cycles A cycle Cn, n ≥ 3, consists of n vertices v1, v2, . . . , vn and edges {v1, v2},
{v2, v3}, . . . , {vn−1, vn}, and {vn, v1}. The cycles C3, C4, C5, and C6 are displayed in
Figure 4. ▲
C3 C4 C5 C6
FIGURE 4 The Cycles C3, C4, C5, and C6.
EXAMPLE 7 Wheels 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. The wheelsW3,W4,
W5, andW6 are displayed in Figure 5. ▲
W3 W4 W5 W6
FIGURE 5 TheWheelsW3,W4,W5, andW6.
EXAMPLE 8 n-Cubes Ann-dimensional hypercube, orn-cube, denoted byQn, 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. We displayQ1,Q2, andQ3 in Figure 6.
Note that you can construct the (n+ 1)-cube Qn+1 from the n-cube Qn by making two
copies ofQn, prefacing the labels on the vertices with a 0 in one copy ofQn and with a 1 in the
other copy of Qn, and adding edges connecting two vertices that have labels differing only in
the first bit. In Figure 6,Q3 is constructed fromQ2 by drawing two copies ofQ2 as the top and
bottom faces ofQ3, adding 0 at the beginning of the label of each vertex in the bottom face and
1 at the beginning of the label of each vertex in the top face. (Here, by face we mean a face of
a cube in three-dimensional space. Think of drawing the graph Q3 in three-dimensional space
with copies ofQ2 as the top and bottom faces of a cube and then drawing the projection of the
resulting depiction in the plane.) ▲
10 / 57
Câu hỏi
Đồ thị Kn có bao nhiêu cạnh?
11 / 57
Đồ thị vòng
Định nghĩa
Đồ thị vòng Cn, với n ≥ 3 là một đồ thị có n đỉnh v1, v2, . . . , vn và
các cạnh
{v1, v2}, {v2, v3}, · · · , {vn−1, vn}, và {vn, v1}
10.2 Graph Terminology and Special Types of Graphs 655
EXAMPLE 5 Complete Graphs A complete graph on n vertices, denoted by Kn, is a simple graph
that contains exactly one edge between each pair of distinct vertices. The graphs Kn, for
n = 1, 2, 3, 4, 5, 6, are displayed in Figure 3. A simple graph for which there is at least one
pair of distinct vertex not connected by an edge is called noncomplete. ▲
K1 K2 K3 K4 K5 K6
FIGURE 3 The Graphs Kn for 1 ≤ n ≤ 6.
EXAMPLE 6 Cycles A cycle Cn, n ≥ 3, consists of n vertices v1, v2, . . . , vn and edges {v1, v2},
{v2, v3}, . . . , {vn−1, vn}, and {vn, v1}. The cycles C3, C4, C5, and C6 are displayed in
Figure 4. ▲
C3 C4 C5 C6
FIGURE 4 The Cycles C3, C4, C5, and C6.
EXAMPLE 7 Wheels 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. The wheelsW3,W4,
W5, andW6 are displayed in Figure 5. ▲
W3 W4 W5 W6
FIGURE 5 TheWheelsW3,W4,W5, andW6.
EXAMPLE 8 n-Cubes Ann-dimensional hypercube, orn-cube, denoted byQn, 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. We displayQ1,Q2, andQ3 in Figure 6.
Note that you can construct the (n+ 1)-cube Qn+1 from the n-cube Qn by making two
copies ofQn, prefacing the labels on the vertices with a 0 in one copy ofQn and with a 1 in the
other copy of Qn, and adding edges connecting two vertices that have labels differing only in
the first bit. In Figure 6,Q3 is constructed fromQ2 by drawing two copies ofQ2 as the top and
bottom faces ofQ3, adding 0 at the beginning of the label of each vertex in the bottom face and
1 at the beginning of the label of each vertex in the top face. (Here, by face we mean a face of
a cube in three-dimensional space. Think of drawing the graph Q3 in three-dimensional space
with copies ofQ2 as the top and bottom faces of a cube and then drawing the projection of the
resulting depiction in the plane.) ▲
12 / 57
Câu hỏi
Đồ thị Cn có bao nhiêu cạnh?
13 / 57
Đồ thị bánh xe
Định nghĩa
Khi thêm một đỉnh vào vòng Cn với n ≥ 3 và nối đỉnh này với mỗi
đỉnh trong Cn bằng một cạnh mới ta sẽ nhận được đồ thị bánh xe
Wn.
10.2 Graph Terminology and Special Types of Graphs 655
EXAMPLE 5 Complete Graphs A complete graph on n vertices, denoted by Kn, is a simple graph
that contains exactly one edge between each pair of distinct vertices. The graphs Kn, for
n = 1, 2, 3, 4, 5, 6, are displayed in Figure 3. A simple graph for which there is at least one
pair of distinct vertex not connected by an edge is called noncomplete. ▲
K1 K2 K3 K4 K5 K6
FIGURE 3 The Graphs Kn for 1 ≤ n ≤ 6.
EXAMPLE 6 Cycles A cycle Cn, n ≥ 3, consists of n vertices v1, v2, . . . , vn and edges {v1, v2},
{v2, v3}, . . . , {vn−1, vn}, and {vn, v1}. The cycles C3, C4, C5, and C6 are displayed in
Figure 4. ▲
C3 C4 C5 C6
FIGURE 4 The Cycles C3, C4, C5, and C6.
EXAMPLE 7 Wheels 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. The wheelsW3,W4,
W5, andW6 are displayed in Figure 5. ▲
W3 W4 W5 W6
FIGURE 5 TheWheelsW3,W4,W5, andW6.
EXAMPLE 8 n-Cubes Ann-dimensional hypercube, orn-cube, denoted byQn, 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. We displayQ1,Q2, andQ3 in Figure 6.
Note that you can construct the (n+ 1)-cube Qn+1 from the n-cube Qn by making two
copies ofQn, prefacing the labels on the vertices with a 0 in one copy ofQn and with a 1 in the
other copy of Qn, and adding edges connecting two vertices that have labels differing only in
the first bit. In Figure 6,Q3 is constructed fromQ2 by drawing two copies ofQ2 as the top and
bottom faces ofQ3, adding 0 at the beginning of the label of each vertex in the bottom face and
1 at the beginning of the label of each vertex in the top face. (Here, by face we mean a face of
a cube in three-dimensional space. Think of drawing the graph Q3 in three-dimensional space
with copies ofQ2 as the top and bottom faces of a cube and then drawing the projection of the
resulting depiction in the plane.) ▲
14 / 57
Câu hỏi
Đồ thị Wn có bao nhiêu cạnh?
15 / 57
Các khối n chiều
Định nghĩa
Các khối n chiều, ký hiệu Qn, là các đồ thị có 2n đỉnh, mỗi đỉnh
được biểu diễn bằng xâu nhị phân độ dài n. Hai đỉnh liền kề nếu và
chỉ nếu các xâu nhị phân biểu diễn chúng khác nhau đúng một bit.656 10 / Graphs
Q1 Q2
0 1
00 01
10 11
Q3
000 001
100 101
111110
010 011
FIGURE 6 The n-cubeQn, n = 1, 2, 3.
Bipartite Graphs
Sometimes a graph has the property that its vertex set can be divided into two disjoint subsets
such that each edge connects a vertex in one of these subsets to a vertex in the other subset.
For example, consider the graph representing marriages between men and women in a village,
where each person is represented by a vertex and a marriage is represented by an edge. In this
graph, each edge connects a vertex in the subset of vertices representing males and a vertex in
the subset of vertices representing females. This leads us to Definition 5.
DEFINITION 6 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.
In Example 9 we will show that C6 is bipartite, and in Example 10 we will show that K3 is
not bipartite.
EXAMPLE 9 C6 is bipartite, as shown in Figure 7, because its vertex set can be partitioned into the two sets
V1 = {v1, v3, v5} and V2 = {v2, v4, v6}, and every edge of C6 connects a vertex in V1 and a
vertex in V2. ▲
EXAMPLE 10 K3 is not bipartite. To verify this, note that if we divide the vertex set of K3 into two disjoint
sets, one of the two sets must contain two vertices. If the graph were bipartite, these two vertices
could not be connected by an edge, but in K3 each vertex is connected to every other vertex by
an edge. ▲
EXAMPLE 11 Are the graphs G and H displayed in Figure 8 bipartite?
V1 V2v1
v3
v5
v2
v4
v6
FIGURE 7 Showing That C6 Is
Bipartite.
a b
c
e d
f
g
G
a b
e d
H
f c
FIGURE 8 The Undirected Graphs G and H .
16 / 57
Câu hỏi
Đồ thị Qn có bao nhiêu cạnh?
17 / 57
Đồ thị hai phần
Định nghĩa
Một đồ thị được gọi là hai phần nếu tập đỉnh V có thể phân hoạch
thành hai tập V1 và V2 sao cho mỗi cạnh của đồ thị nối một đỉnh
của V1 tới một đỉnh của V2.
656 10 / Graphs
Q1 Q2
0 1
00 01
10 11
Q3
000 001
100 101
111110
010 011
FIGURE 6 The n-cubeQn, n = 1, 2, 3.
Bipartite Graphs
Sometimes a graph has the property that its vertex set can be divided into two disjoint subsets
such that each edge connects a vertex in one of these subsets to a vertex in the other subset.
For example, consider the graph representing marriages between men and women in a village,
where each person is represented by a vertex and a marriage is represented by an edge. In this
graph, each edge connects a vertex in the subset of vertices representing males and a vertex in
the subset of vertices representing females. This leads us to Definition 5.
DEFINITION 6 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.
In Example 9 we will show that C6 is bipartite, and in Example 10 we will show that K3 is
not bipartite.
EXAMPLE 9 C6 is bipartite, as shown in Figure 7, because its vertex set can be partitioned into the two sets
V1 = {v1, v3, v5} and V2 = {v2, v4, v6}, and every edge of C6 connects a vertex in V1 and a
vertex in V2. ▲
EXAMPLE 10 K3 is not bipartite. To verify this, note that if we divide the vertex set of K3 into two disjoint
sets, one of the two sets must contain two vertices. If the graph were bipartite, these two vertices
could not be connected by an edge, but in K3 each vertex is connected to every other vertex by
an edge. ▲
EXAMPLE 11 Are the graphs G and H displayed in Figure 8 bipartite?
V1 V2v1
v3
v5
v2
v4
v6
FIGURE 7 Showing That C6 Is
Bipartite.
a b
c
e d
f
g
G
a b
e d
H
f c
FIGURE 8 The Undirected Graphs G and H .
18 / 57
Câu hỏi
Đồ thị nào dưới đây là đồ thị hai phần?
656 10 / Graphs
Q1 Q2
0 1
00 01
10 11
Q3
000 001
100 101
111110
010 011
FIGURE 6 The n-cubeQn, n = 1, 2, 3.
Bipartite Graphs
Sometimes a graph has the property that its vertex set can be divided into two disjoint subsets
such that each edge connects a vertex in one of these subsets to a vertex in the other subset.
For example, consider the graph representing marriages between men and women in a village,
where each person is represented by a vertex and a marriage is represented by an edge. In this
graph, each edge connects a vertex in the subset of vertices representing males and a vertex in
the subset of vertices representing females. This leads us to Definition 5.
DEFINITION 6 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.
In Example 9 we will show that C6 is bipartite, and in Example 10 we will show that K3 is
not bipartite.
EXAMPLE 9 C6 is bipartite, as shown in Figure 7, because its vertex set can be partitioned into the two sets
V1 = {v1, v3, v5} and V2 = {v2, v4, v6}, and every edge of C6 connects a vertex in V1 and a
vertex in V2. ▲
EXAMPLE 10 K3 is not bipartite. To verify this, note that if we divide the vertex set of K3 into two disjoint
sets, one of the two sets must contain two vertices. If the graph were bipartite, these two vertices
could not be connected by an edge, but in K3 each vertex is connected to every other vertex by
an edge. ▲
EXAMPLE 11 Are the graphs G and H displayed in Figure 8 bipartite?
V1 V2v1
v3
v5
v2
v4
v6
FIGURE 7 Showing That C6 Is
Bipartite.
a b
c
e d
f
g
G
a b
e d
H
f c
FIGURE 8 The Undirected Graphs G and H .
19 / 57
Câu hỏi
Đồ thị C5 và C6 có phải là những đồ thị hai phần?
20 / 57
Đồ thị hai phần đầy đủ
Định nghĩa
Đồ thị hai phần đầy đủ Km,n là đồ thị có tập đỉnh được phân
hoạch thành hai tập con tương ứng có m đỉnh và n đỉnh và có một
cạnh nối hai đỉnh nếu có một đỉnh thuộc tập này và một đỉnh
thuộc tập kia.
658 10 / Graphs
EXAMPLE 13 Complete Bipartite Graphs A complete bipartite graphKm,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.
The complete bipartite graphs K2,3, K3,3, K3,5, and K2,6 are displayed in Figure 9. ▲
K2,3 K3,3
K3,5 K2,6
FIGURE 9 Some Complete Bipartite Graphs.
Bipartite Graphs and Matchings
Bipartite graphs can be used to model many types of applications that involve matching the
elements of one set to elements of another, as Example 14 illustrates.
EXAMPLE 14 Job Assignments Suppose that there are m employees in a group and n different jobs that
need to be done, where m ≥ n. Each employee is trained to do one or more of these n jobs. We
would like to assign an employee to each job. To help with this task, we can use a graph to model
employee capabilities. We represent each employee by a vertex and each job by a vertex. For
each employee, we include an edge from that employee to all jobs that the employee has been
trained to do. Note that the vertex set of this graph can be partitioned into two disjoint sets, the
set of employees and the set of jobs, and each edge connects an employee to a job. Consequently,
this graph is bipartite, where the bipartition is (E, J ) where E is the set of employees and J is
the set of jobs. We now consider two different scenarios.
First, suppose that a group has four employees: Alvarez, Berkowitz, Chen, and Davis;
and suppose that four jobs need to be done to complete Project 1: requirements, architecture,
implementation, and testing. Suppose that Alvarez has been trained to do requirements and
testing; Berkowitz has been trained to do architecture, implementation, and testing; Chen has
been trained to do requirements, architecture, and implementation; and Davis has only been
trained to do requirements. We model these employee capabilities using the bipartite graph in
Figure 10(a).
Second, suppose that a group has second group also has four employees:Washington, Xuan,
Ybarra, and Ziegler; and suppose that the same four jobs need to be done to complete Project 2 as
are needed to complete Project 1. Suppose that Washington has been trained to do architecture;
Xuan has been trained to do requirements, implementation, and testing;Ybarra has been trained
to do architecture; and Ziegler has been trained to do requirements, architecture and testing.We
model these employee capabilities using the bipartite graph in Figure 10(b).
To complete Project 1, we must assign an employee to each job so that every job has an
employee assigned to it, and so that no employee is assigned more than one job. We can do this
by assigning Alvarez to testing, Berkowitz to implementation, Chen to architecture, and Davis
to requirements, as shown in Figure 10(a) (where blue lines show this assignment of jobs).
To complete Project 2, we must also assign an employee to each job so that every job has
an employee assigned to it and no employee is assigned more than one job. However, this is
21 / 57
658 10 / Graphs
EXAMPLE 13 Complete Bipartite Graphs A complete bipartite graphKm,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.
The complete bipartite graphs K2,3, K3,3, K3,5, and K2,6 are displayed in Figure 9. ▲
K2,3 K3,3
K3,5 K2,6
FIGURE 9 Some Complete Bipartite Graphs.
Bipartite Graphs and Matchings
Bipartite graphs can be used to model many types of applications that involve matching the
elements of one set to elements of another, as Example 14 illustrates.
EXAMPLE 14 Job Assignments Suppose that there are m employees in a group and n different jobs that
need to be done, where m ≥ n. Each employee is trained to do one or more of these n jobs. We
would like to assign an employee to each job. To help with this task, we can use a graph to model
employee capabilities. We represent each employee by a vertex and each job by a vertex. For
each employee, we include an edge from that employee to all jobs that the employee has been
trained to do. Note that the vertex set of this graph can be partitioned into two disjoint sets, the
set of employees and the set of jobs, and each edge connects an employee to a job. Consequently,
this graph is bipartite, where the bipartition is (E, J ) where E is the set of employees and J is
the set of jobs. We now consider two different scenarios.
First, suppose that a group has four employees: Alvarez, Berkowitz, Chen, and Davis;
and suppose that four jobs need to be done to complete Project 1: requirements, architecture,
implementation, and testing. Suppose that Alvarez has been trained to do requirements and
testing; Berkowitz has been trained to do architecture, implementation, and testing; Chen has
been trained to do requirements, architecture, and implementation; and Davis has only been
trained to do requirements. We model these employee capabilities using the bipartite graph in
Figure 10(a).
Second, suppose that a group has second group also has four employees:Washington, Xuan,
Ybarra, and Ziegler; and suppose that the same four jobs need to be done to complete Project 2 as
are needed to complete Project 1. Suppose that Washington has been trained to do architecture;
Xuan has been trained to do requirements, implementation, and testing;Ybarra has been trained
to do architecture; and Ziegler has been trained to do requirements, architecture and testing.We
model these employee capabilities using the bipartite graph in Figure 10(b).
To complete Project 1, we must assign an employee to each job so that every job has an
employee assigned to it, and so that no employee is assigned more than one job. We can do this
by assigning Alvarez to testing, Berkowitz to implementation, Chen to architecture, and Davis
to requirements, as shown in Figure 10(a) (where blue lines show this assignment of jobs).
To complete Project 2, we must also assign an employee to each job so that every job has
an employee assigned to it and no employee is assigned more than one job. However, this is
22 / 57
Câu hỏi
Đồ thị Km,n có bao nhiêu cạnh?
23 / 57
Bài tập
Hãy xây dựng một đồ thị với 5 đỉnh và 6 cạnh mà không chứa C3
(tam giác) nào.
24 / 57
Nội dung
Đồ thị và biểu diễn
Một số đồ thị đặc biệt
Đẳng cấu
Bậc
Đường đi và chu trình
Định nghĩa
Hai đồ thị G1 và G2 được gọi là đẳng cấu nếu có một song ánh α
từ tập đỉnh của G1 đến tập đỉnh của G2 sao cho {α(x), α(y)} là
một cạnh của G1 nếu và chỉ nếu {x, y} là một cạnh của G2.
Song ánh α được gọi là một đẳng cấu.
26 / 57
Ví dụ
Hai đồ thị sau đây đẳng cấu với nhau và đẳng cấu α định nghĩa
bởi:
α(a) = t, α(b) = v, α(c) = w, α(d) = u.
a b
cd uv
w
t
27 / 57
Ví dụ
Hai đồ thị sau có đẳng cấu không?
a
e b
d c
a
e b
d c
28 / 57
Bài tập
Hãy chứng minh rằng hai đồ thị sau không đẳng cấu.
29 / 57
Nội dung
Đồ thị và biểu diễn
Một số đồ thị đặc biệt
Đẳng cấu
Bậc
Đường đi và chu trình
Định nghĩa
Bậc của một đỉnh v trong đồ thị G = (V,E) là số cạnh của G
chứa v. Ta ký hiệu deg(v) là bậc của đỉnh v. Có nghĩa rằng
deg(v) = |Dv| với Dv = {e ∈ E | v ∈ e }.
Ví dụ a
z b
d c
đỉnh deg
a 2
b 2
c 1
d 3
z 2
31 / 57
Định lý
Tổng các bậc deg(v), lấy trên mọi đỉnh v của đồ thị G = (V,E),
bằng hai lần số cạnh: ∑
v∈V
deg(v) = 2|E|.
Ví dụ a
z b
d c
đỉnh thuộc vào cạnh
a {a, b}, {a, d}
b {a, b}, {b, z}
c {c, d}
d {a, d}, {c, d}, {d, z}
z {b, z}, {d, z}
32 / 57
Một đỉnh của đồ thị G là lẻ nếu bậc của nó là lẻ, và là chẵn nếu
bậc của nó là chẵn.
Hệ quả
Số đỉnh lẻ của đồ thị là số chẵn.
Chứng minh. ∑
v∈Vlẻ
deg(v) +
∑
v∈Vchẵn
deg(v) = 2|E|
33 / 57
Bậc và đẳng cấu
▶ Nếu α : V1 → V2 là một đẳng cấu giữa G1 và G2 và
α(v) = w, vậy
deg(v) = deg(w).
Tại sao?
▶ Nếu trong G1 có đỉnh x với deg(x) = δ0 và trong G2 không có
đỉnh nào có bậc δ0, vậy thì G1 và G2 không đẳng cấu.
34 / 57
Bài tập
Các dãy số sau đây có thể là các bậc của mọi đỉnh của đồ thị nào
đó không? Nếu có hãy vẽ một đồ thị như vậy.
1. 2, 2, 2, 3
2. 1, 2, 2, 3, 4
3. 2, 2, 4, 4, 4
4. 1, 2, 3, 4.
35 / 57
Bài tập
▶ Xét đồ thị G = (V,E), phần bù G của G là đồ thị có cùng
tập đỉnh là V và tập cạnh là tất cả các cặp đỉnh phân biệt
không kề nhau trong G.
▶ Giả sử G có n đỉnh và các bậc của nó là
d1, d2, . . . , dn.
Các bậc của G là gì?
36 / 57
Đồ thị chính quy
▶ Đồ thị mà trong đó mọi đỉnh đều có cùng bậc r được gọi là
chính quy. Khi đó r|V| = 2|E|.
▶ Đồ thị Kn là đồ thị chính quy bậc n− 1.
▶ Đồ thị vòng Cn là đồ thị chính quy bậc 2.
▶ Đồ thị Qn là đồ thị chính quy bậc mấy ?
37 / 57
ae b
d c
0
4 1
3 2
Hình: Đồ thị đầy đủ K5 và đồ thị chu trình C5
38 / 57
Bài tập
Liệt kê các đồ thị chính quy bậc 4 (đôi một không đẳng cấu) với
bảy đỉnh.
39 / 57
Bài tập
Chứng minh rằng trong mọi đồ thị với ít nhất hai đỉnh luôn có hai
đỉnh cùng bậc.
40 / 57
Nội dung
Đồ thị và biểu diễn
Một số đồ thị đặc biệt
Đẳng cấu
Bậc
Đường đi và chu trình
Định nghĩa
Một hành trình trong đồ thị G là một dãy đỉnh
v1, v2, . . . , vk,
thỏa mãn vi và vi+1 kề nhau (với 1 ≤ i ≤ k− 1).
a
e b
d c
42 / 57
Định nghĩa
Hành trình mà trong đó mọi đỉnh đều khác nhau được gọi là
đường đi .
a
e b
d c
43 / 57
Đồ thị cộng tác
▶ Đỉnh: các tác giả
▶ Đỉnh a nối b nếu hai tác giả a và b
viết chung bài báo.
▶ Số Erdös của nhà toán học m là
đường đi ngắn nhất giữa m và Paul
Erdös.
10.4 Connectivity 681
TABLE 1 The Number
of Mathematicians
with a Given Erdo˝s
Number (as of early
2006).
Erdo˝s Number
Number of People
0 1
1 504
2 6,593
3 33,605
4 83,642
5 87,760
6 40,014
7 11,591
8 3,146
9 819
10 244
11 68
12 23
13 5
TABLE 2 The Number
of Actors with a Given
Bacon Number (as of
early 2011).
Bacon Number
Number of People
0 1
1 2,367
2 242,407
3 785,389
4 200,602
5 14,048
6 1,277
7 114
8 16
game where participants where challenged to find a sequence of movies leading from each actor
named to Kevin Bacon.We can find a number similar to a Bacon number using any actor as the
center of the acting universe. !
Connectedness in Undirected Graphs
When does a computer network have the property that every pair of computers can share infor-
mation, if messages can be sent through one or more intermediate computers? When a graph
is used to represent this computer network, where vertices represent the computers and edges
represent the communication links, this question becomes:When is there always a path between
two vertices in the graph?
DEFINITION 3 An undirected graph is called connected if there is a path between every pair of distinct
vertices of the graph. An undirected graph that is not connected is called disconnected. We
say that we disconnect a graph when we remove vertices or edges, or both, to produce a
disconnected subgraph.
Thus, any two computers in the network can communicate if and only if the graph of this network
is connected.
EXAMPLE 4 The graph G1 in Figure 2 is connected, because for every pair of distinct vertices there is a
path between them (the reader should verify this). However, the graph G2 in Figure 2 is not
connected. For instance, there is no path in G2 between vertices a and d . !
We will need the following theorem in Chapter 11.
44 / 57
Đồ thị Hollywood
▶ Đỉnh: các diễn viên
▶ Diễn viên a nối với diễn viên b nếu
a và b đóng chung một bộ phim
▶ Số Bacon của diễn viên c là đường
đi ngắn nhất giữa c và Kevin
Bacon.
10.4 Connectivity 681
TABLE 1 The Number
of Mathematicians
with a Given Erdo˝s
Number (as of early
2006).
Erdo˝s Number
Number of People
0 1
1 504
2 6,593
3 33,605
4 83,642
5 87,760
6 40,014
7 11,591
8 3,146
9 819
10 244
11 68
12 23
13 5
TABLE 2 The Number
of Actors with a Given
Bacon Number (as of
early 2011).
Bacon Number
Number of People
0 1
1 2,367
2 242,407
3 785,389
4 200,602
5 14,048
6 1,277
7 114
8 16
game where participants where challenged to find a sequence of movies leading from each actor
named to Kevin Bacon.We can find a number similar to a Bacon number using any actor as the
center of the acting universe. !
Connectedness in Undirected Graphs
When does a computer network have the property that every pair of computers can share infor-
mation, if messages can be sent through one or more intermediate computers? When a graph
is used to represent this computer network, where vertices represent the computers and edges
represent the communication links, this question becomes:When is there always a path between
two vertices in the graph?
DEFINITION 3 An undirected graph is called connected if there is a path between every pair of distinct
vertices of the graph. An undirected graph that is not connected is called disconnected. We
say that we disconnect a graph when we remove vertices or edges, or both, to produce a
disconnected subgraph.
Thus, any two computers in the network can communicate if and only if the graph of this network
is connected.
EXAMPLE 4 The graph G1 in Figure 2 is connected, because for every pair of distinct vertices there is a
path between them (the reader should verify this). However, the graph G2 in Figure 2 is not
connected. For instance, there is no path in G2 between vertices a and d . !
We will need the following theorem in Chapter 11.
45 / 57
Định nghĩa
Ta ký hiệu x ∼ y nếu hai đỉnh x và y trong G có thể nối với nhau
bằng một đường đi. Có nghĩa rằng, tồn tại một đường đi
v1, v2, · · · , vk
trong G với x = v1 và y = vk.
a
e b
d c
46 / 57
Dễ thấy, quan hệ ∼ là quan hệ tương đương trên tập đỉnh V của G.
Vậy thì V được phân hoạch thành các lớp tương đương rời nhau.
Hai đỉnh nằm trong cùng một lớp nếu giữa chúng có đường đi, và
trong hai lớp khác nhau nếu không có đường đi.
Ví dụ
Với đồ thị bên, ta có phân hoạch:
V = Vđỏ ∪ Vxanh
a
b
c
d
e
f
47 / 57
Định nghĩa
Giả sử G = (V,E) là một đồ thị và phân hoạch của V tương ứng
với quan hệ tương đương ∼ là
V = V1 ∪V2 ∪ · · · ∪ Vr.
Ký hiệu Ei (với 1 ≤ i ≤ r) là các tập con của E bao gồm các cạnh
với đầu mút nằm trong Vi. Vậy thì các đồ thị Gi = (Vi,Ei) được
gọi là các thành phần liên thông của G.
Ta nói G liên thông nếu nó chỉ có một thành phần liên thông.
48 / 57
Ví dụ
Đồ thị dưới đây không liên thông. Nó có hai thành phần liên thông.
a
b
c
d
e
f
49 / 57
Bài tập
Tìm số thành phần liên thông của đồ thị với danh sách kề là
a b c d e f g h i j
f c b h c a b d a a
i g e g i c f f
j g j e
50 / 57
Bài tập
Đồ thị mô tả bữa tiệc của bà April có bao nhiêu thành phần liên
thông?
51 / 57
Định nghĩa
Một hành trình
v1, v2, · · · , vr+1
trong đó mọi đỉnh đều phân biệt ngoại trừ v1 = vr+1 được gọi là
một chu trình.
Vì nó có r đỉnh phân biệt và r cạnh nên ta cũng thường gọi nó là
r-chu trình, hay chu trình độ dài r.
a
e b
d c
52 / 57
Bài tập
▶ Hình dưới đây thể hiện các địa điểm thú vị trên đảo Wanda và
đường đi giữa chúng.
▶ Hãy tìm đường đi trên đảo để thăm mỗi địa điểm đúng một
lần và trở về vị trí xuất phát.
p q
s
tr
u
53 / 57
Bài tập
Hãy tìm cách để đi hết các con đường, mỗi đường đúng một lần.
Địa điểm bắt đầu và kết thúc có thể khác nhau.
p q
s
tr
u
54 / 57
Định nghĩa
▶ Chu trình chứa mọi đỉnh của đồ thị gọi là chu trình
Hamilton.
▶ Hành trình dùng mỗi cạnh đúng một lần gọi là hành trình
Euler .
55 / 57
Bài tập
Tìm chu trình Hamilton của đồ thị tạo bởi các đỉnh và cạnh của
khối lập phương.
10.7 Planar Graphs 719
FIGURE 2 The
Graph K4.
FIGURE 3 K4 Drawn
with No Crossings.
FIGURE 4 The
GraphQ3.
FIGURE 5 A Planar
Representation ofQ3.
DEFINITION 1 A graph is called planar if it can be drawn in the plane without any edges crossing (where
a crossing of edges is the intersection of the lines or arcs representing them at a point other
than their common endpoint). Such a drawing is called a planar representation of the graph.
A graph may be planar even if it is usually drawn with crossings, because it may be possible
to draw it in a different way without crossings.
EXAMPLE 1 Is K4 (shown in Figure 2 with two edges crossing) planar?
Solution: K4 is planar because it can be drawn without crossings, as shown in Figure 3. !
EXAMPLE 2 IsQ3, shown in Figure 4, planar?
Solution: Q3 is planar, because it can be drawn without any edges crossing, as shown in
Figure 5. !
We can show that a graph is planar by displaying a planar representation. It is harder to
show that a graph is nonplanar. We will give an example to show how this can be done in an ad
hoc fashion. Later we will develop some general results that can be used to do this.
EXAMPLE 3 Is K3,3, shown in Figure 6, planar?
Solution: Any attempt to draw K3,3 in the plane with no edges crossing is doomed. We now
showwhy. In any planar representation ofK3,3, the vertices v1 and v2 must be connected to both
v4 and v5. These four edges form a closed curve that splits the plane into two regions, R1 and
R2, as shown in Figure 7(a). The vertex v3 is in either R1 or R2. When v3 is in R2, the inside
of the closed curve, the edges between v3 and v4 and between v3 and v5 separate R2 into two
subregions, R21 and R22, as shown in Figure 7(b).
v1 v2
v6
v3
v5v4
FIGURE 6 The Graph K3,3.
v1
v4
v5
v2
v1
v4
v5
v2
v3R2 R1 R1
R21
(a) (b)
R22
FIGURE 7 Showing that K3,3 Is Nonplanar.
56 / 57
Bài tập
Năm tới, Dr Chunner và Dr Dodder định đi thăm đảo Mianda. Các
địa điểm hấp dẫn và đường đi nối giữa chúng được biểu diễn bởi
đồ thị có danh sách kề là
0 1 2 3 4 5 6 7 8
1 0 1 0 3 0 1 0 1
3 2 3 2 5 4 5 2 3
5 6 7 4 6 7 6 5
7 8 8 8 8 7
▶ Liệu họ có thể tìm đường đi trên đảo để thăm mỗi địa điểm
đúng một lần và trở về vị trí xuất phát?
▶ Liệu họ có thể tìm cách để đi hết các con đường, mỗi đường
đúng một lần; địa điểm bắt đầu và kết thúc có thể khác nhau?
57 / 57
Các file đính kèm theo tài liệu này:
- bai_giang_toan_roi_rac_bai_4_do_thi_tran_vinh_duc.pdf