zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Lý thuyết đồ thị: Chương 3 - Ngô Hữu Phúc

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:18

Báo xấu

47
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

"Bài giảng Lý thuyết đồ thị - Chương 3: Đồ thị Euler và đồ thị Hamilton" với những kiến thức về đồ thị Euler; đồ thị Hamilton. Để nắm chi tiết nội dung kiến thức, phục vụ cho học tập và nghiên cứu, mời các bạn cùng tham khảo bài giảng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 3 - Ngô Hữu Phúc

CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 1. Đồ thị EULER: - 1736 Euler (1707-1783) công bố lời giải “bài toán về các cầu ở Konigsberg”. Bài toán tìm đường đi qua tất cả các cầu, mỗi cầu chỉ qua một lần có thể được phát biểu lại bằng mô hình như sau:  Có tồn tại chu trình đơn trong đa đồ thị G chứa tất cả 49 các cạnh?
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 1. Đồ thị EULER: - Đường đi qua mỗi cạnh của đồ thị đúng một lần được gọi là đường đi Euler. - Chu trình qua mỗi cạnh của đồ thị đúng một lần được gọi là chu trình Euler. - Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler, và gọi là đồ thị nửa Euler nếu nó có đường đi Euler - Nhận xét: mọi đồ thị Euler luôn là nửa Euler, nhưng điều ngược lại không luôn đúng. 50
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 1. Đồ thị EULER: - Ví dụ 1: Xét 3 đồ thị G1, G2, G3 bên dưới: Đồ thị G1 trong hình là đồ thị Euler vì nó có chu trình Euler a, e, c, d, e, b, a. Đồ thị G3 không có chu trình Euler nhưng nó có đường đi Euler a, c, d, e, b, d, a, b, vì thế G3 là đồ thị nửa Euler. Đồ thị G2 không có chu trình cũng như đường đi Euler.51
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 1. Đồ thị EULER: - Ví dụ 2: Xét 3 đồ thị H1, H2, H3 bên dưới: Đồ thị H2 trong hình là đồ thị Euler vì nó có chu trình Euler a, b, c, d, e, a. Đồ thị H3 không có chu trình Euler nhưng nó có đường đi Euler c, d, b, c, a, b, vì thế H3 là đồ thị nửa Euler. Đồ thị H1 không có chu trình cũng như đường đi Euler. 52
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 1.Đồ thị EULER:  Định lý 1 (Euler): G là đồ thị vô hướng liên thông. G là đồ thị Euler  mọi đỉnh của G đều có bậc chẵn.  Bổ đề: Nếu bậc của mỗi đỉnh của đồ thị G không nhỏ hơn 2 thì G chứa chu trình.  Hệ quả: Đồ thị vô hướng liên thông G là nửa Euler khi và chỉ khi nó có không quá 2 đỉnh bậc lẻ. 53
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 1.Đồ thị EULER:  Thuật toán Flor: Xuất phát từ một đỉnh u nào đó của G ta đi theo các cạnh của nó một cách tuỳ ý chỉ cần tuân thủ 2 qui tắc sau: (1) Xoá bỏ cạnh đã đi qua đồng thời xoá bỏ đỉnh cô lập tạo thành. (2) Ở mỗi bước ta chỉ đi qua cầu khi không còn cách lựa chọn nào khác. 54
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 1.Đồ thị EULER: Xét ví dụ: Tìm chu trình Euler trong đồ thị:  Định lý 2. G có hướng liên thông mạnh G là đồ thị Euler  deg+(v) = deg-(v), vV. 55
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 1.Đồ thị EULER:  Bài toán người phát thư Trung Hoa (Guan 1960): Một NV đi từ Sở BĐ, qua một số đường phố để phát thư, rồi quay về Sở. Phải đi qua các đường theo trình tự nào để đường đi là ngắn nhất? Xét bài toán: Cho đồ thị liên thông G. Một chu trình qua mọi cạnh của G gọi là một hành trình trong G. Hãy tìm hành trình ngắn nhất (qua ít cạnh nhất). Nếu G là đồ thị Euler thì chu trình Euler trong G là hành trình ngắn nhất cần tìm. Xét trường hợp G có một số đỉnh bậc lẻ. Khi đó, mọi hành trình trong G phải đi qua ít nhất hai lần một số cạnh nào đó. 56
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 1.Đồ thị EULER:  Bài toán người phát thư Trung Hoa (Guan 1960): Định lý (Gooodman và Hedetniemi, 1973). Nếu G là một đồ thị liên thông có q cạnh thì hành trình ngắn nhất trong G có chiều dài q + m(G), trong đó m(G) là số cạnh mà hành trình đi qua hai lần và được xác định như sau: Gọi V0(G) là tập hợp các đỉnh bậc lẻ (2k đỉnh) của G. Ta phân 2k phần tử của G thành k cặp, mỗi tập hợp k cặp gọi là một phân hoạch cặp của V0(G). Gọi độ dài đường đi ngắn nhất từ u đến v là khoảng cách d(u,v). Đối với mọi phân hoạch cặp Pi, tính khoảng cách giữa hai đỉnh trong từng cặp, tính tổng d(Pi). Số m(G) bằng cực tiểu của các d(Pi): m(G)=min d(Pi). 57
1.Đồ thị EULER: VO(G)={B, G, H, K} tập hợp các phân hoạch cặp là: P={P1, P2, P3}, trong đó: P1 = {(B, G), (H, K)} → d(P1) = d(B, G)+d(H, K) = 4+1 = 5 P2 = {(B, H), (G, K)} → d(P2) = d(B, H)+d(G, K) = 2+1 = 3, P3 = {(B, K), (G, H)} → d(P3) = d(B, K)+d(G, H) = 3+2 = 5. m(G) = min(d(P1), d(P2), d(P3)) = 3. GT có được từ G bằng cách thêm vào 3 cạnh: (B, I), (I, H), (G, K) và GT là đồ thị Euler. Vậy hành trình ngắn nhất cần tìm là đi theo chu trình Euler trong GT: A, B, C, D, E, F, K, G, K, E, C, J, K, H, J, I, H, I, B, I, A. 58
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 2. Đồ thị HAMILTON - Đườ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. - Chu trình bắt đầu từ một đỉnh v nào đó qua tất cả các đỉnh còn lại mỗi đỉnh đúng một lần rồi quay trở về v được gọi là chu trình Hamilton. - Đồ thị G được gọi là đồ thị Hamilton nếu nó chứa chu trình Hamilton và gọi là đồ thị nửa Hamilton nếu nó có đường đi Hamilton. 59
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 2. Đồ thị HAMILTON Ví dụ 3. Trong hình: Đồ thị G3 là Hamilton, G2 là nửa Hamilton còn G1 không là nửa Hamilton. Cho đến nay việc tìm một tiêu chuẩn nhận biết đồ thị Hamilton vẫn còn là mở. Phần lớn các phát biểu đều có dạng "nếu G có số cạnh đủ lớn thì G là Hamilton" 60
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 2. Đồ thị HAMILTON  Định lý 1 (Dirak 1952). Đơn đồ thị vô hướng G với n>2 đỉnh, mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton.  Định lý 2 Nếu G là đồ thị phân đôi với hai tập đỉnh là V1, V2 có số đỉnh cùng bằng n (n ≥ 2) và bậc của mỗi đỉnh lớn hơn n/2 thì G là một đồ thị Hamilton.  Định lý 3. Giả sử G là đồ có hướng liên thông với n đỉnh. Nếu deg+(v)≥n/2, deg–(v) ≥ n/2, v thì G là Hamilton. 61
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 2. Đồ thị HAMILTON Đồ thị G này có 8 đỉnh, Đồ thị phân đôi này có bậc của đỉnh nào cũng có bậc 4, mỗi đỉnh bằng 2 hoặc 3 (> 3/2), nên G là đồ thị Hamilton. nên nó là đồ thị Hamilton. 62
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 2. Đồ thị HAMILTON Ví dụ 4. Hình dưới đây mô tả cây tìm kiếm tất cả các chu trình Hamilton của đồ thị. 63
2. Đồ thị HAMILTON Bài toán sắp xếp chỗ ngồi: Có n đại biểu đến dự hội nghị. Mỗi ngày họp một lần ngồi quanh một bàn tròn. Hỏi phải bố trí bao nhiêu ngày và bố trí như thế nào sao cho trong mỗi ngày, mỗi người có hai người kế bên là bạn mới. Lưu ý rằng n người đều muốn làm quen với nhau. Xét đồ thị gồm n đỉnh, mỗi đỉnh ứng với mỗi người dự hội nghị, hai đỉnh kề nhau khi hai đại biểu tương ứng muốn làm quen với nhau. Như vậy, ta có đồ thị đầy đủ Kn. 64
CHƯƠNG III ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 2. Đồ thị HAMILTON Mỗi chu trình Hamilton là một cách sắp xếp như yêu cầu của bài toán. Bái toán trở thành tìm các chu trình Hamilton phân biệt của đồ thị đầy đủ Kn (hai chu trình Hamilton gọi là phân biệt nếu chúng không có cạnh chung). Định lý: Đồ thị đầy đủ Kn với n lẻ và n ≥ 3 có đúng (n −1)/2 chu trình Hamilton phân biệt. 65
2. Đồ thị HAMILTON Giải bài toán sắp xếp chỗ ngồi với n=11. Có (11−1)/2=5 cách sắp xếp chỗ ngồi phân biệt như sau: 1 2 3 4 5 6 7 8 9 10 11 1 1 3 5 2 7 4 9 6 11 8 10 1 1 5 7 3 9 2 11 4 10 6 8 1 1 7 9 5 11 3 10 2 8 4 6 1 1 9 11 7 10 5 8 3 6 2 4 1 66

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.