›
›

Giáo trình Toán rời rạc - Bài 4: Đồ thị - Trần Vĩnh Đức

Download
Đồ 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  
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ụ  
a
z
b
Xét đồ thị G = (V, E) trong đó  
V = {a, b, c, d, z}  
E = {{a, b}, {a, d}, {b, z}, {c, d}, {d, z}}.  
c
d
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.  
a
Ví dụ  
z
b
a
b
d
b
a
z
c
d
d
a
c
z
z
b
d
c
d
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.  
K1  
K2  
K3  
K4  
K5  
K6  
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}  
C3  
C4  
C5  
C6  
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.  
W3  
W4  
W5  
W6  
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.  
110  
111  
101  
10  
00  
11  
01  
100  
010  
011  
0
1
000  
001  
Q1  
Q2  
Q3  
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.  
V1  
V2  
v1  
v3  
v2  
v4  
v6  
v5  
18 / 57  
Câu hỏi  
Đồ thị nào dưới đây là đồ thị hai phần?  
a
b
a
b
d
c
g
c
f
f
e
d
e
G
H
19 / 57  
Câu hỏi  
Đồ thị C5 và C6 có phải là những đồ thị hai phần?  
20 / 57  
Tải về để xem bản đầy đủ
pdf 57 trang Thùy Anh 20900 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 4: Đồ thị - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfgiao_trinh_toan_roi_rac_bai_4_do_thi_tran_vinh_duc.pdf