Xem mẫu
- Đồ thị
Trần Vĩnh Đức
HUST
Ngày 24 tháng 7 năm 2018
CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 57
- Tài liệu tham khảo
▶ Norman L. Biggs, Discrete Mathematics, Oxford University
Press, 2002.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 / 57
- CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Đị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ụ
a
Xét đồ thị G = (V, E) trong đó z b
V = {a, b, c, d, z}
E = {{a, b}, {a, d}, {b, z}, {c, d}, {d, z}}.
d c
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
a b c d z
b a d a b
d z c d
z
d c
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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?
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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?
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Đồ thị đầy đủ
10.2 Graph Terminology and Special Types of Grap
Định nghĩa
Đồ thị đầy đủ5 gồm
EXAMPLE n đỉnh,
Complete Graphský Ahiệu là Kgraph
complete n là on
đồn thị có đúng
vertices, denotedmột
by Kn , is a simple
that contains exactly one edge between each pair of distinct vertices. The graphs K
cạnh nối mỗi cặpn =đỉnh
1, 2, 3,phân
4, 5, 6, biệt.
are displayed in Figure 3. A simple graph for which there is at le
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 {
{v2 , v3 }, . . . , {vn−1 , vn }, and {vn , v1 }. The cycles C3 , C4 , C5 , and C6 are displa
Figure 4.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 57
- Câu hỏi
Đồ thị Kn có bao nhiêu cạnh?
CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 / 57
- Đồ thị vòng
K3 K4 K5
Định nghĩa
he Graphs n forC1n ,≤
Đồ thịKvòng vớin n≤≥6.3 là một đồ thị có n đỉnh v1 , v2 , . . . , vn và
các cạnh
LE 6 Cycles A cycle Cn , n ≥ 3, consists of n vertices v1 , v2 , . . .
{v , v }, {v , v }, · · · , {v , vn }, và {vn , v1 }
{v2 , v3 }, . . .1, {v2n−1 , 2vn },3 and {vnn−1
, v1 }. The cycles C3 , C4 , C5 , a
Figure 4.
C3 C4 C5 C6
FIGURE 4 The Cycles C3 , C4 , C5 , and C6 .
CuuDuongThanCong.com https://fb.com/tailieudientucntt 12 / 57
- Câu hỏi
Đồ thị Cn có bao nhiêu cạnh?
CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 57
- Đồ thị bánh xe
C3 C4 C5 C6
FIGURE 4 The Cycles C3 , C4 , C5 , and C6 .
Định nghĩa
MPLE Khi thêm mộtWe
7 Wheels đỉnhobtain
vào vòng Cn W
a wheel ≥ 3 we
vớin nwhen và nối
addđỉnh này với mỗi
an additional vertex to
đỉnhand
trong C bằng một cạnh mới ta sẽ nhận được đồ thị bánh xe
connect this new vertex to each of the n vertices in Cn , by new edge
n
Wn . W5 , and W6 are displayed in Figure 5.
W3 W4 W5 W6
FIGURE 5 The Wheels W3 , W4 , W5 , and W6 .
MPLE 8 n-Cubes An n-dimensional hypercube, or n-cube, denoted by Qn , is a
CuuDuongThanCong.com n bit strings of length n. Two vertices are adjacent
representing the 2https://fb.com/tailieudientucntt 14 if
/ 57an
- Câu hỏi
Đồ thị Wn có bao nhiêu cạnh?
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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à
56 chỉ nếu các xâu nhị phân biểu diễn chúng khác nhau đúng một bit.
10 / Graphs
110 111
10 11 100 101
010 011
0 1
00 01 000 001
Q1 Q2 Q3
FIGURE 6 The n-cube Qn , n = 1, 2, 3.
Bipartite Graphs
CuuDuongThanCong.com https://fb.com/tailieudientucntt 16 / 57
- Câu hỏi
Đồ thị Qn có bao nhiêu cạnh?
CuuDuongThanCong.com https://fb.com/tailieudientucntt 17 / 57
- Đồ thị hai phần
EXAMPLE 11 Are the graphs G and
Đị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 .
V1 V2
v1 v2
v3 v4
v5 v6
FIGURE 7 Showing That C6 Is
CuuDuongThanCong.com Bipartite. https://fb.com/tailieudientucntt 18 / 57
- Câu hỏi8 bipartite?
ed in Figure
Đồ thị nào dưới đây là đồ thị hai phần?
a b a b
g c
f c
f
e d e d
G H
FIGURE 8 The Undirected Graphs G and H .
CuuDuongThanCong.com https://fb.com/tailieudientucntt 19 / 57
- Câu hỏi
Đồ thị C5 và C6 có phải là những đồ thị hai phần?
CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 57
nguon tai.lieu . vn
