CHƯƠNG 5
ĐỒ THỊ
Nguyễn Quỳnh Diệp diepnq@tlu.edu.vn
File Bài giảng: goo.gl/Y3cpLF hoặc goo.gl/TYxXQD
1
Nguyễn Quỳnh Diệp
NỘI DUNG
• Các định nghĩa
• Các thuật ngữ về đồ thị
• Biểu diễn đồ thị
• Tính liên thông
• Đường đi Euler và đường đi Hamilton
• Bài toán đường đi ngắn nhất
Nguyễn Quỳnh Diệp
Toán rời rạc
2
5.1. CÁC ĐỊNH NGHĨA
Nguyễn Quỳnh Diệp
Toán rời rạc
3
ĐỒ THỊ
• Đồ thị là một cấu trúc rời rạc
Nguyễn Quỳnh Diệp
Toán rời rạc
• Gồm các đỉnh (V) và các cạnh (E) nối đỉnh
4
ĐỒ THỊ
Kĩ sư điện: dùng đồ thị để thiết kế các mạch điện Ngành khoa học: biểu diễn cấu trúc hóa học của các chất, cấu
• Dùng đồ thị cho các lĩnh vực khác nhau:
Ngành ngôn ngữ học: biểu diễn cây ngôn ngữ
trúc DNA…
• Các ứng dụng khác của đồ thị
Nguyễn Quỳnh Diệp
Toán rời rạc
Biểu diễn sự ảnh hưởng của một ai đó trong tổ chức Biểu diễn kết quả cuộc thi thể thao Mạng hàng không
5
PHÂN LOẠI ĐỒ THỊ - ĐƠN ĐỒ THỊ
Định nghĩa 1:
Một đơn đồ thị G = (V, E) gồm một tập không rỗng V mà các phẩn tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cạnh là các cặp không sắp thứ tự của các đỉnh phân biệt.
Ví dụ:
Nguyễn Quỳnh Diệp
Toán rời rạc
6
ĐA ĐỒ THỊ
Định nghĩa 2:
Một đa đồ thị G = (V, E) gồm một tập các đỉnh V, một tập các cạnh E và một hàm f từ E tới {(u,v)| u,v V , u v}. Các cạnh e1 và e2 được gọi là cạnh bội nếu f(e1) = f(e2).
Ví dụ:
Nguyễn Quỳnh Diệp
Toán rời rạc
7
GIẢ ĐỒ THỊ
Định nghĩa 3:
Một giả đồ thị G = (V, E) gồm một tập các đỉnh V, một tập các cạnh E và một hàm f từ E tới {{u,v}| u,v V }. Một cạnh là khuyên nếu f(e) = { u, u } = {u} với một đỉnh u nào đó
Ví dụ:
Nguyễn Quỳnh Diệp
Toán rời rạc
8
ĐỒ THỊ CÓ HƯỚNG
Định nghĩa 4:
Một đồ thị có hướng G = (V, E) gồm một tập các đỉnh V, một tập các cạnh E là các cặp có thứ tự của các phần tử thuộc V.
Ví dụ:
Nguyễn Quỳnh Diệp
Toán rời rạc
9
ĐA ĐỒ THỊ CÓ HƯỚNG
Định nghĩa 5:
Một đa đồ thị có hướng G = (V, E) gồm một tập các đỉnh V, một tập các cạnh E và một hàm f từ E tới {(u,v)| u, v V}. Cạnh e1 và e2 là các cạnh bội nếu f(e1) = f(e2).
Ví dụ:
Nguyễn Quỳnh Diệp
Toán rời rạc
10
ĐỒ THỊ
Bảng thuật ngữ đồ thị:
Đơn đồ thị
Vô hướng
Không
Không
Loại Cạnh Cạnh bội ? Có khuyên ?
Giả đồ thị
Vô hướng
Có
Có
Đa đồ thị Vô hướng Có Không
Đa đồ thị có hướng Có hướng
Có
Có
Nguyễn Quỳnh Diệp
Toán rời rạc
Đồ thị có hướng Có hướng Không Có
11
CÁC MÔ HÌNH ĐỒ THỊ
Ví dụ 1: Mạng xã hội
Nguyễn Quỳnh Diệp
Toán rời rạc
12
CÁC MÔ HÌNH ĐỒ THỊ
Ví dụ 2: Đồ thị ảnh hưởng
Nguyễn Quỳnh Diệp
Toán rời rạc
13
CÁC MÔ HÌNH ĐỒ THỊ
Ví dụ 3: Đồ thị các môđun phụ thuộc
Nguyễn Quỳnh Diệp
Toán rời rạc
14
CÁC MÔ HÌNH ĐỒ THỊ
Ví dụ 4: Đồ thị thi đấu
Nguyễn Quỳnh Diệp
Toán rời rạc
15
BÀI TẬP
16
Nguyễn Quỳnh Diệp
Toán rời rạc
Bài 1: Xác định các loại đồ thị cho hình bên dưới
16
BÀI TẬP
17
Nguyễn Quỳnh Diệp
Toán rời rạc
Bài 2: Xác định các loại đồ thị cho hình bên dưới
17
5.2. CÁC THUẬT NGỮ VỀ ĐỒ THỊ
Nguyễn Quỳnh Diệp
Toán rời rạc
18
ĐỒ THỊ VÔ HƯỚNG
Định nghĩa 1:
Cho đồ thị vô hướng G, hai đỉnh u và v được gọi là liền kề (hoặc láng giềng) nếu {u, v} là một cạnh của G. Nếu e = {u, v} thì e gọi là cạnh liên thuộc hoặc cạnh nối với các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của cạnh {u, v}.
Định nghĩa 2:
Trong đồ thị vô hướng, bậc của một đỉnh là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Kí hiệu bậc của đỉnh v là deg(v)
Nguyễn Quỳnh Diệp
Toán rời rạc
19
ĐỒ THỊ VÔ HƯỚNG
Ví dụ 1: Bậc của các đỉnh trong các đồ thị sau là bao nhiêu?
• Đỉnh bậc 0 gọi là đỉnh cô lập (ví dụ đỉnh g trong G)
Nguyễn Quỳnh Diệp
Toán rời rạc
• Đỉnh bậc 1 gọi là đỉnh treo (ví dụ đỉnh d trong G, c trong H)
20
ĐỒ THỊ VÔ HƯỚNG
Định lí 1:
ĐỊNH LÍ BẮT TAY. Cho G = (V, E) là một đồ thị vô hướng. Khi đó:
𝒅𝒆𝒈(𝒗)
𝟐|𝑬| = 𝒗∈𝑽 (Định lý đúng với cả khi đồ thị vô hướng có cạnh bội hoặc khuyên)
Định lí 2:
Một đồ thị vô hướng có một số chẵn các đỉnh bậc lẻ
Nguyễn Quỳnh Diệp
Toán rời rạc
21
ĐỒ THỊ CÓ HƯỚNG
Định nghĩa 3:
Trong đồ thị có hướng G, nếu (u, v) là cạnh của G thì u được gọi là nối tới v và v được gọi là được nối từ u. Đỉnh u gọi là đỉnh đầu, đỉnh v gọi là đỉnh cuối của cạnh (u,v). Đỉnh đầu và đỉnh cuối của khuyên trùng nhau.
Định nghĩa 4:
Trong đồ thị có hướng bậc-vào của đỉnh v kí hiệu deg(v) là số các cạnh có đỉnh cuối là v. Bậc-ra của đỉnh v, kí hiệu deg+(v) là số các cạnh có đỉnh đầu là v.
Nguyễn Quỳnh Diệp
Toán rời rạc
22
ĐỒ THỊ CÓ HƯỚNG
Ví dụ 2: Tìm bậc-vào và bậc-ra của mỗi định trong đồ thị sau:
Định lí 3:
Gọi G = (V,E) là một đồ thị có hướng. Khi đó:
𝒅𝒆𝒈+ 𝒗 = |𝑬|
𝒗∈𝑽
𝒅𝒆𝒈− 𝒗 = 𝒗 ∈𝑽
Nguyễn Quỳnh Diệp
Toán rời rạc
23
MỘT SỐ ĐỒ THỊ ĐẶC BIỆT
Đồ thị đầy đủ n đỉnh:
Kí hiệu Kn
Là đơn đồ thị
Giữa mỗi cặp đỉnh phân biệt chỉ có 1 cạnh nối chúng
Nguyễn Quỳnh Diệp
Toán rời rạc
24
MỘT SỐ ĐỒ THỊ ĐẶC BIỆT
Đồ thị vòng n đỉnh:
Kí hiệu Cn , n 3
Có n đỉnh v1, v2, ..., vn
Các cạnh {v1, v2}, {v2, v3},..., {vn-1, vn} và {vn, v1}
Nguyễn Quỳnh Diệp
Toán rời rạc
25
MỘT SỐ ĐỒ THỊ ĐẶC BIỆT
Đồ thị hình bánh xe:
Kí hiệu Wn , n 3
Là đồ thị vòng Cn bổ sung thêm 1 đỉnh mà đỉnh này nối
với mọi đỉnh đã có trong Cn tạo thành các cạnh mới
Nguyễn Quỳnh Diệp
Toán rời rạc
26
MỘT SỐ ĐỒ THỊ ĐẶC BIỆT
Các khối n chiều:
Ký hiệu Qn Là đồ thị có 2n đỉnh, mỗi đỉnh là 1 xâu nhị phân độ dài n
Hai đỉnh liền kề nếu các xâu nhị phân biểu diễn chúng chỉ
khác nhau đúng1 bit
Nguyễn Quỳnh Diệp
Toán rời rạc
27
ĐỒ THỊ PHÂN ĐÔI
Định nghĩa 5:
G là đồ thị phân đôi nếu G là đơn đồ thị và tập V các đỉnh có thể phân thành 2 tập con khác rỗng, rời nhau V1 và V2 sao cho mỗi cạnh của đồ thị nối một đỉnh của V1 với một đỉnh của V2.
Nguyễn Quỳnh Diệp
Toán rời rạc
Chú ý: G là đồ thị phân đôi thì không nhất thiết mỗi đỉnh của V1 phải nối với tất cả các đỉnh của V2
28
BÀI TẬP
Bài 3: Các đồ thị đã cho có là
29
Nguyễn Quỳnh Diệp
Toán rời rạc
phân đôi không?
29
ĐỒ THỊ CON
Định nghĩa 6:
Nguyễn Quỳnh Diệp
Toán rời rạc
Đồ thị con của đồ thị G = (V, E) là đồ thị H = (W, F), trong đó W V và F E
30
HỢP CỦA HAI ĐỒ THỊ
Định nghĩa 7:
Nguyễn Quỳnh Diệp
Toán rời rạc
Hợp của hai đơn đồ thị G1 = (V1, E1) và G2 = (V2, E2) là một đơn đồ thị có tập các đỉnh là V1 V2 và tập các cạnh E1 E2. Ta kí hiệu hợp của các đồ thị G1 và G2 là G1 G2.
31
BÀI TẬP
32
Nguyễn Quỳnh Diệp
Toán rời rạc
Bài 4: Tìm hợp của cặp hai đơn đồ thị sau
32
5.3. BIỂU DIỄN ĐỒ THỊ
Nguyễn Quỳnh Diệp
Toán rời rạc
33
BIỂU DIỄN ĐỒ THỊ
Biểu diễn đồ thị
• Danh sách kề
• Ma trận kề
• Ma trận liên thuộc
Nguyễn Quỳnh Diệp
Toán rời rạc
34
DANH SÁCH KỀ
Chỉ rõ các đỉnh nối với mỗi đỉnh của đồ thị không có
cạnh bội
Danh sách kề của đơn đồ thị
Đỉnh
Các đỉnh kề
Danh sách kề của đồ thị có hướng
Đỉnh đầu
Đỉnh cuối
Nguyễn Quỳnh Diệp
Toán rời rạc
35
MA TRẬN KỀ
• Giả sử G = (V, E) là một đơn đồ thị, trong đó |V| = n
• Ma trận kề A = [aij], là ma trận nn trong đó:
𝒂𝒊𝒋 =
𝟏 𝒏ế𝒖 𝒗𝒊, 𝒗𝒋 𝒍à 𝒎ộ𝒕 𝒄ạ𝒏𝒉 𝒄ủ𝒂 𝑮 𝟎 𝒏ế𝒖 𝒌𝒉ô𝒏𝒈 𝒄ó 𝒄ạ𝒏𝒉 𝒏ố𝒊 đỉ𝒏𝒉 𝒗𝒊 𝒗ớ𝒊 đỉ𝒏𝒉 𝒗𝒋
v4
v3
v2
v1
a23 = 1
v1 v2 v3 v4
Nguyễn Quỳnh Diệp
Toán rời rạc
36
MA TRẬN KỀ
• Có n! ma trận kề khác nhau của một đồ thị n đỉnh
• Trường hợp đa đồ thị, giả đồ thị thì phần tử vị trí (i,j) bằng số
• Trường hợp đồ thị có hướng: aij = {vi,vj}, vi : đỉnh đầu, vj: đỉnh
cạnh nối các đỉnh ai và aj
v4
v3
v2
v1
cuối Đỉnh cuối
Đỉnh đầu
a23 = 1
v1 v2 v3 v4
Nguyễn Quỳnh Diệp
Toán rời rạc
37
MA TRẬN KỀ
c
d
b
a
Ví dụ 1:
a b c d
Ví dụ 2:
c
d
b
a
a b c d
Nguyễn Quỳnh Diệp
Toán rời rạc
38
MA TRẬN LIÊN THUỘC
• Giả sử G = (V, E) là một đơn đồ thị vô hướng
• Có tập đỉnh v1, v2,...,vn và tập cạnh e1, e2, ..., em
• Ma trận liên thuộc gồm m cột, n hàng, M = [mij] trong đó:
𝒎𝒊𝒋 =
𝟏 𝒏ế𝒖 𝒆𝒋 𝒏ố𝒊 𝒗ớ𝒊 đỉ𝒏𝒉 𝒗𝒊 𝟎 𝒏ế𝒖 𝒆𝒋 𝒌𝒉ô𝒏𝒈 𝒏ố𝒊 𝒗ớ𝒊 đỉ𝒏𝒉 𝒗𝒊
m23 = 1
Nguyễn Quỳnh Diệp
Toán rời rạc
• Ma trận liên thuộc có thể biểu diễn các cạnh bội và khuyên
39
MA TRẬN LIÊN THUỘC
Ví dụ 3:
Nguyễn Quỳnh Diệp
Toán rời rạc
40
BÀI TẬP
Bài 5: Biểu diễn đồ thị sau bằng ma trận kề
41
Nguyễn Quỳnh Diệp
Toán rời rạc
Bài 6: Biểu diễn đồ thị sau bằng ma trận liên thuộc
41
5.4. TÍNH LIÊN THÔNG
Nguyễn Quỳnh Diệp
Toán rời rạc
42
ĐƯỜNG ĐI
Định nghĩa 1:
• Đường đi độ dài n từ u tới v, n Z+ của đồ thị vô hướng là dãy các cạnh e1, e2,..., en sao cho f(e1) = {x0, x1}, f(e2) = {x1, x2},..., f(en) = {xn-1, xn} với x0 = u và xn = v
• Đường đi gọi là chu trình nếu điểm đầu và điểm cuối của
đường đi trùng nhau.
• Đường đi gọi là đường đi đơn nếu nó không đi qua một
cạnh quá 1 lần
• Chu trình gọi là chu trình đơn nếu nó không đi qua một
cạnh quá 1 lần
Nguyễn Quỳnh Diệp
Toán rời rạc
43
ĐƯỜNG ĐI
Ví dụ 1:
• Chỉ ra một đường đi đơn độ dài 4?
• Chỉ ra một đường chu trình độ dài 4?
• Chỉ ra đường đi độ dài 5 không là đường đi đơn?
Nguyễn Quỳnh Diệp
Toán rời rạc
44
TÍNH LIÊN THÔNG – ĐỒ THỊ VÔ HƯỚNG
Định nghĩa 3:
• Một đồ thị vô hướng được gọi là liên thông nếu có đường
đi giữa mọi cặp đỉnh phân biệt của đồ thị
G1
G2
Nguyễn Quỳnh Diệp
Toán rời rạc
45
TÍNH LIÊN THÔNG – ĐỒ THỊ VÔ HƯỚNG
Định lí 1: Giữa mọi cặp đỉnh phân biệt của một đồ thị vô hướng liên thông luôn có đường đi đơn
liên thông
• Đồ thị KHÔNG liên thông sẽ là hợp của hai hay nhiều đồ thị con
• Các đồ thị con liên thông rời nhau gọi là các thành phần liên
• Đỉnh cắt: là đỉnh khi xóa đi tạo ra đồ thị con mới có nhiều thành phần liên thông hơn đồ thị ban đầu. Xóa đỉnh cắt sẽ tạo ra đồ thị con KHÔNG liên thông
• Cạnh cắt (cầu): là cạnh nếu bỏ đi sẽ tạo ra một đồ thị có nhiều
thông
Nguyễn Quỳnh Diệp
Toán rời rạc
thành phần liên thông hơn đồ thị ban đầu
46
TÍNH LIÊN THÔNG – ĐỒ THỊ VÔ HƯỚNG
Ví dụ 2: Tìm đỉnh cắt và cạnh cắt của đồ thị sau?
Nguyễn Quỳnh Diệp
Toán rời rạc
47
TÍNH LIÊN THÔNG – ĐỒ THỊ CÓ HƯỚNG
Định nghĩa 4: Đồ thị có hướng gọi là liên thông mạnh nếu có đường đi từ a tới b VÀ từ b tới a với MỌI đỉnh a và b của đồ thị.
Định nghĩa 5:
Nguyễn Quỳnh Diệp
Toán rời rạc
Đồ thị có hướng gọi là liên thông yếu nếu có đường đi giữa hai đỉnh bất kì của đồ thị vô hướng nền (có đường đi khi không quan tâm đến hướng)
48
BÀI TẬP
49
Nguyễn Quỳnh Diệp
Toán rời rạc
Bài 7: Các đồ thị sau có liên thông không?
49
BÀI TẬP
Bài 8: Chỉ ra các đồ thị sau đây có là liên thông mạnh không?
có là liên thông yếu không? Tìm các thành phần liên thông
50
Nguyễn Quỳnh Diệp
Toán rời rạc
mạnh
50
5.5. ĐƯỜNG ĐI EULER VÀ HAMILTON
Nguyễn Quỳnh Diệp
Toán rời rạc
51
ĐƯỜNG ĐI VÀ CHU TRÌNH EULER
Bài toán Königsberg
• Thành phố Königsberg chia thành 4 vùng bởi các nhánh sông
Pregel.
Nguyễn Quỳnh Diệp
Toán rời rạc
• Người ta đã xây 7 cây cầu để nối 4 vùng • Hỏi có thể xuất phát tại 1 điểm để đi qua tất cả các cầu, mỗi chiếc cầu không đi qua nhiều hơn 1 lần rồi trở về điểm xuất phát?
52
ĐƯỜNG ĐI VÀ CHU TRÌNH EULER
• Nhắc lại:
• Đường đi là một dãy các cạnh e1, e2,…, en
• Đường đi gọi là chu trình nếu điểm đầu và điểm cuối của đường đi trùng
nhau.
• Đường đi đơn là đường đi chỉ đi qua mỗi cạnh không quá 1 lần.
• Chu trình đơn là chu trình chỉ đi qua mỗi cạnh không quá 1 lần
Định nghĩa 1:
của G.
• Đường đi Euler trong G là đường đi đơn đi qua tất cả các cạnh
• Chu trình Euler là chu trình đơn đi qua tất cả các cạnh của đồ
Nguyễn Quỳnh Diệp
Toán rời rạc
thị G.
53
ĐƯỜNG ĐI VÀ CHU TRÌNH EULER
Ví dụ 1: Đồ thị nào sau đây có chu trình Euler?
Nguyễn Quỳnh Diệp
Toán rời rạc
54
ĐIỀU KIỆN CẦN VÀ ĐỦ CHO CHU TRÌNH EULER
Định lí 1:
Một đa đồ thị liên thông có chu trình Euler nếu và chỉ nếu mỗi đỉnh của nó đều có bậc chẵn.
Nguyễn Quỳnh Diệp
Toán rời rạc
55
CHU TRÌNH EULER
Bài toán Königsberg
• Thành phố Königsberg chia thành 4 vùng bởi các nhánh sông
Pregel.
Nguyễn Quỳnh Diệp
Toán rời rạc
• Người ta đã xây 7 cây cầu để nối 4 vùng • Hỏi có thể xuất phát tại 1 điểm để đi qua tất cả các cầu, mỗi chiếc cầu không đi qua nhiều hơn 1 lần rồi trở về điểm xuất phát?
56
XÂY DỰNG CHU TRÌNH EULER
THUẬT TOÁN : Xây dựng chu trình Euler
Procedure Euler (G: đa đồ thị liên thông với tất cả các đỉnh bậc chẵn) C := chọn 1 chu trình bất kì H := G đã xóa đi cạnh của C while H còn các cạnh begin
C’ = chu trình trong H có đi qua đỉnh trong C H := H xóa đi cạnh của C’ và đỉnh treo C := C cộng thêm C’ chèn vào tại một đỉnh thích hợp
Nguyễn Quỳnh Diệp
Toán rời rạc
end { chu trình C là chu trình Euler}
57
XÂY DỰNG CHU TRÌNH EULER
Ví dụ 2: Tìm chu trình Euler của đồ thị sau?
Nguyễn Quỳnh Diệp
Toán rời rạc
58
XÂY DỰNG CHU TRÌNH EULER
Giải: • Chọn C = chu trình {a, f, c, b, a} • H = các cạnh {c,d}, {c, e}, {e, d}
• C’ = chu trình {c, d, e, c} • H = • C: = C C’={a, f, c, b, a} { c, d, e, c} =
• Chu trình Euler là {a,f,c,d,e,c,b,a}
Nguyễn Quỳnh Diệp
Toán rời rạc
{a, f, c, d, e, c, b, a}
59
ĐƯỜNG ĐI EULER
Định lí 2:
Một đa đồ thị liên thông có đường đi Euler nhưng không có chu trình Euler nếu và chỉ nếu nó có đúng hai đỉnh bậc lẻ.
Ví dụ 3: Đồ thị nào có đường đi Euler?
Nguyễn Quỳnh Diệp
Toán rời rạc
60
ĐA ĐỒ THỊ CÓ HƯỚNG
• Đa đồ thị có hướng có chu trình Euler nếu và chỉ nếu đồ thị là liên thông yếu đồng thời bậc vào và bậc ra của mỗi đỉnh là bằng nhau
• Đa đồ thị có hướng không có đỉnh cô lập, có đường đi Euler nhưng không có chu trình Euler nếu và chỉ nếu đồ thị là liên thông yếu đồng thời bậc vào và bậc ra của mỗi đỉnh là bằng nhau, trừ hai đỉnh, một đỉnh có bậc vào lớn hơn bậc ra 1 đơn vị, đỉnh kia có bậc ra lớn hơn bậc vào 1 đơn vị.
Nguyễn Quỳnh Diệp
Toán rời rạc
61
BÀI TẬP
Bài 8: Xác định các đồ thị sau có chu trình Euler, đường đi Euler?
62
Nguyễn Quỳnh Diệp
Toán rời rạc
Nếu có hãy chỉ ra chu trình, đường đi Euler
62
ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON
Trò chơi đố vui của William Rowan Hamilton
Nguyễn Quỳnh Diệp
Toán rời rạc
63
ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON
Trò chơi đố vui của William Rowan Hamilton
Nguyễn Quỳnh Diệp
Toán rời rạc
64
ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON
Định nghĩa 2:
• Chu trình x0, x1,...,xn, x0 trong đồ thị G được gọi là chu trình
• Đường đi x0, x1,...,xn trong đồ thị G(V, E) được gọi là đường đi Hamilton nếu V= {x0, x1,..., xn-1 ,xn } và xi xj, 0 i < j n
Hamilton nếu x0, x1,...,xn là đường đi Hamilton.
Nguyễn Quỳnh Diệp
Toán rời rạc
Ví dụ 1: Đồ thị nào có chu trình Hamilton?
65
ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON
Định lí 3:
ĐỊNH LÍ DIRAC. Giả sử G là một đơn đồ thị liên thông với n đỉnh, trong đó n 3, G có chu trình Hamilton nếu bậc của mỗi đỉnh ít nhất bằng n/2.
Định lí 4:
ĐỊNH LÍ ORE. Nếu G là một đơn đồ thị n đỉnh, trong đó n 3, sao cho deg(u) + deg(v) n với mọi cặp đỉnh không liền kề u và v, khi đó G có chu trình Hamilton.
Nguyễn Quỳnh Diệp
Toán rời rạc
Cả hai định lí trên là các điều kiện đủ để trong một đơn đồ thị liên thông có tồn tại chu trình Hamilton
66
BÀI TẬP
67
Nguyễn Quỳnh Diệp
Toán rời rạc
Bài 9: Xác định các đồ thị sau có chu trình và đường đi Hamilton?
67
5.6. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT
Nguyễn Quỳnh Diệp
Toán rời rạc
68
ĐỒ THỊ CÓ TRỌNG SỐ
Đồ thị có trọng số là đồ thị mà mỗi cạnh của nó được gán một số (nguyên hoặc thực) gọi là trọng số của cạnh.
2534
KHOẢNG CÁCH
1855
722
957
2451
349
1090
Nguyễn Quỳnh Diệp
Toán rời rạc
69
ĐỒ THỊ CÓ TRỌNG SỐ
Ví dụ:
4:05
THỜI GIAN BAY
0:50
1:50
2:55
2:10
2:20
1:15
2:00
3:50
2:45
Nguyễn Quỳnh Diệp
Toán rời rạc
70
ĐỒ THỊ CÓ TRỌNG SỐ
Bài toán liên quan tới đồ thị có trọng số:
• Xác định đường đi ngắn nhất giữa hai đỉnh của một mạng
• Tìm đường đi có thời gian trả lời nhanh nhất cho một cuộc
• Tìm đường đi có chi phí rẻ nhất
Nguyễn Quỳnh Diệp
Toán rời rạc
truyền thông giữa các máy tính
71
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
• Do E.Dijkstra nhà toán học người Hà Lan đề xuất năm 1959
dài của đường đi ngắn nhất tới đỉnh thứ 2... cho tới đỉnh z
Nguyễn Quỳnh Diệp
Toán rời rạc
• Thực hiện tìm độ dài của đi ngắn nhất từ a tới đỉnh thứ nhất, độ
72
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
Ví dụ: Tìm đường đi ngắn nhất từ s đến t
đến t
tìm đường đi ngắn nhất từ s
• Tìm độ dài của đường đi ngắn nhất từ s tới các đỉnh kế tiếp cho
Nguyễn Quỳnh Diệp
Toán rời rạc
tới khi đạt tới đỉnh t
73
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
Ví dụ:
Nguyễn Quỳnh Diệp
Toán rời rạc
74
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
Nguyễn Quỳnh Diệp
Toán rời rạc
• Đường đi ngắn nhất là: s b d t • Độ dài đường đi ngắn nhất là: 6
75
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
Ví dụ:
Nguyễn Quỳnh Diệp
Toán rời rạc
76
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
Nguyễn Quỳnh Diệp
Toán rời rạc
77
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
THUẬT TOÁN : Thuật toán Dijkstra
Procedure Dijkstra(G: đa đồ thị liên thông có trọng số dương) {G có các đỉnh a = v0, v1, v2..., vn = z và trọng số w(vi, vj), với w(vi, vj) = nếu {vi,vj} không có cạnh trong G} L(a) := 0 for i :=1 to n L(vi) = S := while z S begin
u := đỉnh S có nhãn L(u) nhỏ nhất S := S {u} for tât cả các đỉnh v không thuộc S
if L(u) + w(u,v) < L(v) then L(v) := L(u) + w(u,v)
end { L(z) = độ dài đường đi ngắn nhất từ a tới z}
Nguyễn Quỳnh Diệp
Toán rời rạc
78
Video: Tìm đường đi ngắn nhất từ A đến G
Nguyễn Quỳnh Diệp
Toán rời rạc
79
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
Ví dụ: tìm đường đi ngắn nhất từ s đến t
ma trận trọng số
W =
Nguyễn Quỳnh Diệp
Toán rời rạc
s a b c d t 𝟎 𝟐 ∞ ∞ ∞ 𝟒 s 𝟓 ∞ ∞ 𝟏 𝟒 𝟎 a 𝟖 𝟏𝟎 ∞ 𝟎 𝟏 𝟐 b 𝟔 𝟐 ∞ 𝟓 𝟎 𝟖 c 𝟑 𝟎 ∞ ∞ 𝟏𝟎 𝟐 d 𝟎 𝟑 ∞ ∞ ∞ 𝟔 t
80
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
u S
a, b, c, d, t
[4, s]
[2, s]*
s
-
s, L(s)=0
s, b
a, c, d, t
[3, b]*
[10,b]
[12,b]
-
-
b, L(b)=2
s,b,a
c, d, t
[8,a]* [12,b]
-
-
-
a, L(a)=3
s, b, a, c
d, t
-
-
-
-
[10,c]* [14,c]
c, L(c)=8
s, b, a, c, d,
t
-
-
-
-
-
[13,d]*
d, L(d)=10
-
-
-
-
-
-
s, b, a, c, d, t
t, L(t)=13
v S s, a, b, c, d, t s 0 a b c d t
Nguyễn Quỳnh Diệp
Toán rời rạc
Đường đi ngắn nhất: s b a c d t, độ dài = 13
81
BÀI TẬP
82
Nguyễn Quỳnh Diệp
Toán rời rạc
Bài 10: Tìm độ dài đường đi ngắn nhất giữa a và z trong đồ thị sau:
82
BÀI TẬP
5
5
d
f
b
4
7
3
2
1
2
a
z
3
4
6
5
c
g
e
83
Nguyễn Quỳnh Diệp
Toán rời rạc
Bài 11: Tìm độ dài đường đi ngắn nhất giữa a và z trong đồ thị sau:
83
84
Nguyễn Quỳnh Diệp
