Bài giảng Toán rời rạc 2 - Chương 4: Đồ thị Euler và Đồ thị Hamilton - Ngô Xuân Bách
Học viện Công nghệ Bưu chính Viễn thông
Khoa Công nghệ thông tin 1
Toán rời rạc 2
Đồ thị Euler và Đồ thị Hamilton
Ngô Xuân Bách
Khái niệm và ví dụ
Định nghĩa
o Chu trình đơn trong đồ thị 퐺 đi qua tất cả các cạnh của nó được
gọi là chu trình Euler
o Đường đi đơn trong đồ thị G đi qua tất cả các cạnh của nó được
gọi là đường đi Euler
o Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler
o Đồ thị được gọi là đồ thị nửa Euler nếu nó có đường đi Euler
Ví dụ 1
(Phương ND, 2013)
3
Điều kiện cần và đủ để đồ thị là Euler
Với đồ thị vô hướng
o Đồ thị vô hướng liên thông 퐺 =< 푉, 퐸 > là đồ thị Euler khi và chỉ
khi mọi đỉnh của 퐺 đều có bậc chẵn
Với đồ thị có hướng
o Đồ thị có hướng liên thông yếu 퐺 =< 푉, 퐸 > là đồ thị Euler khi và
chỉ khi tất cả các đỉnh của nó đều có bán bậc ra bằng bán bậc vào
(điều này làm cho đồ thị là liên thông mạnh)
5
Chứng minh đồ thị là Euler
Với đồ thị vô hướng
o Kiểm tra đồ thị có liên thông hay không?
. Kiểm tra 퐷퐹푆(푢) = 푉 hoặc 퐵퐹푆(푢) = 푉?
o Kiểm tra bậc của tất cả cả đỉnh có phải số chẵn hay không?
. Với ma trận kề, tổng các phần tử của hàng 푢 (cột 푢) là bậc của đỉnh 푢
Với đồ thị có hướng
o Kiểm tra đồ thị có liên thông yếu hay không?
. Kiểm tra đồ thị vô hướng tương ứng là liên thông, hoặc
. Kiểm tra nếu tồn tại đỉnh 푢 ∈ 푉 để 퐷퐹푆(푢) = 푉 hoặc 퐵퐹푆 푢 = 푉?
o Kiểm tra tất cả các đỉnh có thỏa mãn bán bậc ra bằng bán bậc vào
hay không?
. Với ma trận kề, bán bậc ra của đỉnh 푢 là 푑푒ꢀ+(푢) là số các số 1 của
hàng 푢, bán bậc vào của đỉnh 푢 là 푑푒ꢀ−(푢) là số các số 1 của cột 푢
6
Bài tập 1
Cho đồ thị vô
hướng 퐺 được biểu
diễn dưới dạng ma
trận kề như hình
bên. Chứng minh 퐺
là đồ thị Euler.
(Phương ND, 2013)
7
Bài tập 2
Cho đồ thị có
hướng 퐺 được biểu
diễn dưới dạng ma
trận kề như hình
bên. Chứng minh 퐺
là đồ thị Euler.
(Phương ND, 2013)
8
Thuật toán tìm chu trình Euler
Euler-Cycle(푢){
Bước 1: Khởi tạo
푠푡푎푐푘 = ∅; //khởi tạo 푠푡푎푐푘 là ∅
퐶퐸 = ∅; //khởi tạo mảng 퐶퐸 là ∅
p푢푠ℎ(푠푡푎푐푘, 푢); //đưa đỉnh 푢 vào ngăn xếp
Bước 2: Lặp
while(푠푡푎푐푘 ≠ ∅){
푠 = 품풆풕(푠푡푎푐푘); //lấy đỉnh ở đầu ngăn xếp
if(퐾푒(푠) ≠ ∅){
푡=<đỉnh đầu tiên trong 퐾푒(푠)>;
p푢푠ℎ(푠푡푎푐푘, 푡); //đưa đỉnh 푡 vào ngăn xếp
퐸 = 퐸\*(푠, 푡)+; //loại bỏ cạnh (푠, 푡)
}
else{
푠 = p표푝(푠푡푎푐푘); //loại bỏ s khỏi ngăn xếp
푠 ⇒ 퐶퐸; //đưa s sang 퐶퐸
}
}
Bước 3: Trả lại kết quả
<lật ngược lại các đỉnh trong 퐶퐸 ta được chu trình Euler>;
}
9
Kiểm nghiệm thuật toán (1/3)
Áp dụng thuật toán
tìm chu trình Euler
cho đồ thị vô
hướng được biểu
diễn bằng ma trận
kề như hình bên.
10
Kiểm nghiệm thuật toán (2/3)
#
Trạng thái Stack
CE #
Trạng thái Stack
CE
1 1
∅
∅
∅
∅
∅
∅
∅
∅
∅
1
1
1
14 1,2,3,4,7,5,2,6,5,3,11,4
1
1
1
1
2 1,2
15 1,2,3,4,7,5,2,6,5,3,11,4,8
3 1,2,3
16 1,2,3,4,7,5,2,6,5,3,11,4,8,7
17 1,2,3,4,7,5,2,6,5,3,11,4,8,7,6
18 1,2,3,4,7,5,2,6,5,3,11,4,8,7
19 1,2,3,4,7,5,2,6,5,3,11,4,8
4 1,2,3,4
5 1,2,3,4,7
1,6
6 1,2,3,4,7,5
7 1,2,3,4,7,5,2
8 1,2,3,4,7,5,2,6
9 1,2,3,4,7,5,2,6,1
10 1,2,3,4,7,5,2,6
11 1,2,3,4,7,5,2,6,5
12 1,2,3,4,7,5,2,6,5,3
1,6,7
1,6,7
1,6,7
1,6,7
1,6,7,8
1,6,7,8
1,6,7,8
20 1,2,3,4,7,5,2,6,5,3,11,4,8,9
21 1,2,3,4,7,5,2,6,5,3,11,4,8,9,10
22 1,2,3,4,7,5,2,6,5,3,11,4,8,9,10,8
23 1,2,3,4,7,5,2,6,5,3,11,4,8,9,10
24 1,2,3,4,7,5,2,6,5,3,11,4,8,9,10,11
25 1,2,3,4,7,5,2,6,5,3,11,4,8,9,10,11,12
13 1,2,3,4,7,5,2,6,5,3,11 1
26 1,2,3,4,7,5,2,6,5,3,11,4,8,9,10,11,12,9 1,6,7,8
11
Kiểm nghiệm thuật toán (3/3)
Bước
27
Trạng thái Stack
1,2,3,4,7,5,2,6,5,3,11,4,8,9,10,11,12,9,13
1,2,3,4,7,5,2,6,5,3,11,4,8,9,10,11,12,9,13,12
1,2,3,4,7,5,2,6,5,3,11,4,8,9,10,11,12,9,13,12,10
CE
1,6,7,8
1,6,7,8
1,6,7,8
28
29
Đưa lần lượt các đỉnh trong 푆푡푎푐푘 sang 퐶퐸 cho tới khi 푆푡푎푐푘 = ∅
퐶퐸 = 1,6,7,8,10,12,13,9,12,11,10,9,8,4,11,3,5,6,2,5,7,4,3,2,1
30-…
Lật ngược lại các đỉnh trong 퐶퐸 ta được chu trình Euler
1-2-3-4-7-5-2-6-5-3-11-4-8-9-10-11-12-9-13-12-10-8-7-6-1
12
Điều kiện cần và đủ để đồ thị là nửa Euler
Với đồ thị vô hướng
o Đồ thị vô hướng liên thông 퐺 =< 푉, 퐸 > là đồ thị nửa Euler khi và
chỉ khi 퐺 có 0 hoặc 2 đỉnh bậc lẻ
. 퐺 có 2 đỉnh bậc lẻ: đường đi Euler xuất phát tại một đỉnh bậc lẻ và kết
thúc tại đỉnh bậc lẻ còn lại
. 퐺 có 0 đỉnh bậc lẻ: G chính là đồ thị Euler
Với đồ thị có hướng
o Đồ thị có hướng liên thông yếu 퐺 =< 푉, 퐸 > là đồ thị nửa Euler
khi và chỉ khi:
. Tồn tại đúng hai đỉnh 푢, 푣 ∈ 푉 sao cho
푑푒ꢀ+(푢) − 푑푒ꢀ−(푢) = 푑푒ꢀ−(푣) − 푑푒ꢀ+(푣) = 1
. Các đỉnh 푠 ≠ 푢, 푠 ≠ 푣 còn lại có 푑푒ꢀ+(푠) = 푑푒ꢀ−(푠)
. Đường đi Euler sẽ xuất phát tại đỉnh 푢 và kết thúc tại đỉnh 푣
13
Chứng minh đồ thị là nửa Euler
Với đồ thị vô hướng
o Chứng tỏ đồ thị đã cho liên thông
. Sử dụng hai thủ tục 퐷퐹푆(푢) hoặc 퐵퐹푆(푢)
o Có 0 hoặc 2 đỉnh bậc lẻ
. Sử dụng tính chất của các phương pháp biểu diễn đồ thị để tìm ra bậc
của mỗi đỉnh
Với đồ thị có hướng
o Chứng tỏ đồ thị đã cho liên thông yếu
. Sử dụng hai thủ tục 퐷퐹푆(푢) hoặc 퐵퐹푆(푢)
o Có hai đỉnh 푢, 푣 ∈ 푉 thỏa mãn
푑푒ꢀ+(푢) − 푑푒ꢀ−(푢) = 푑푒ꢀ−(푣) − 푑푒ꢀ+(푣) = 1
o Các đỉnh 푠 ≠ 푢, 푠 ≠ 푣 còn lại có 푑푒ꢀ+(푠) = 푑푒ꢀ−(푠)
14
Bài tập 3
Cho đồ thị vô hướng
퐺 =< 푉, 퐸 > được
biểu diễn bằng ma
trận kề như hình
bênh. Chứng minh
rằng 퐺 là đồ thị nửa
Euler?
(Phương ND, 2013)
15
Bài tập 4
Cho đồ thị có hướng
퐺 =< 푉, 퐸 > được
biểu diễn bằng ma
trận kề như hình
bênh. Chứng minh
rằng 퐺 là đồ thị nửa
Euler?
(Phương ND, 2013)
16
Thuật toán tìm đường đi Euler
Thuật toán tìm đường đi Euler gần giống hệt thuật toán
tìm chu trình Euler
Tìm chu trình Euler
o Đầu vào thuật toán là đỉnh 푢 ∈ 푉 bất kỳ
Tìm đường đi Euler
o Đồ thị vô hướng
. Đầu vào thuật toán là đỉnh 푢 ∈ 푉 có bậc lẻ đầu tiên (trường hợp có 0
bậc lẻ thì dùng đỉnh bất kỳ)
o Đồ thị có hướng
. Đầu vào thuật toán là đỉnh 푢 ∈ 푉 thỏa mãn 푑푒ꢀ+(푢) − 푑푒ꢀ−(푢) = 1
17
Kiểm nghiệm thuật toán
Áp dụng thuật toán
tìm đường đi Euler
cho đồ thị vô hướng,
nửa Euler sau?
18
Khái niệm và ví dụ
Định nghĩa
o Đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần
được gọi là đường đi Hamilton
o Chu trình bắt đầu tại một đỉnh 푣 nào đó, qua tất cả các đỉnh còn
lại mỗi đỉnh đúng một lần, sau đó quay trở lại 푣, được gọi là chu
trình Hamilton
o Đồ thị được gọi là đồ thị Hamilton nếu có chu trình Hamilton
o Đồ thị được gọi là đồ thị nửa Hamilton nếu có đường đi Hamilton
Ví dụ
20
Tải về để xem bản đầy đủ
28 trang
19680
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc 2 - Chương 4: Đồ thị Euler và Đồ thị Hamilton - Ngô Xuân Bách", để 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:
- bai_giang_toan_roi_rac_2_chuong_4_do_thi_euler_va_do_thi_ham.pdf
