Chương 3 Đồ thị Euler và đồ thị Hamilton

Chia sẻ: Nguyen Dang Tan | Ngày: | Loại File: PPT | Số trang:19

Thêm vào BST

Báo xấu

104
lượt xem 12
download

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

Tham khảo tài liệu 'chương 3 đồ thị euler và đồ thị hamilton', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: Chương 3 Đồ thị Euler và đồ thị Hamilton

Chương 3 Đồ thị Euler và đồ thị Hamilton Giảng viên: Nguyen Ngoc Trung nguyenngoctrung.dhsp@gmail.com
Phần 3.1. Đồ thị Euler Giảng viên: Nguyen Ngoc Trung nguyenngoctrung.dhsp@gmail.com
Bài toán 7 cái cầu ở TP Konigsberg A B D C Graph Theory 07/17/11 3
Bài toán 7 cái cầu ở Tp. Konigsberg A A Mô hình thành B Đồ thị B D D C C Graph Theory 07/17/11 4
Đặt vấn đề (tt) Hãy vẽ các hình sau bằng đúng một nét bút (không  được nhấc bút lên trong khi vẽ) Không vẽ được bằng 1 nét. Không vẽ được bằng 1 nét. Tối thiểu phải vẽ bằng 6 Tối thiểu phải vẽ bằng 2 nét. nét. Lý thuyết đồ thị 07/17/11 5
Đặt vấn đề (tt) Hãy vẽ các hình sau bằng đúng một nét bút (không  được nhấc bút lên trong khi vẽ) Lý thuyết đồ thị 07/17/11 6
Đường đi, chu trình Euler Xét đồ thị G = .  Một đường đi trên đồ thị được gọi là đường đi Euler nếu  nó đi qua tất cả các cạnh, mỗi cạnh một lần.  Một chu trình trên đồ thị được gọi là chu trình Euler nếu nó đi qua tất cả các cạnh, mỗi cạnh một lần. VD: Đồ thị sau có các đường đi Euler là: 3 d1: 1 2 3 4 2 5 4 1 5 d2: 1 2 4 3 2 5 1 4 5 2 4 … 5 1 Lý thuyết đồ thị 07/17/11 7
Đường đi, chu trình Euler (tt) VD: Đồ thị sau có các chu trình Euler là: 3 d1: 1 2 3 4 2 5 4 1 5 6 1 d2: 1 2 4 3 2 5 1 4 5 6 1 2 4 … 1 5 6 Lý thuyết đồ thị 07/17/11 8
Đồ thị Euler Xét đồ thị G = .  Đồ thị G được gọi là đồ thị Euler nếu và chỉ nếu tồn tại  một chu trình Euler trong G.  Đồ thị G được gọi là đồ thị nửa Euler nếu và chỉ nếu tồn tại một đường đi Euler trong G. 3 3 2 4 2 4 Đồ thị Euler (hiển nhiên cũng là đồ thị nửa 1 5 5 1 Euler). Đồ thị nửa Euler 6 Lý thuyết đồ thị 07/17/11 9
Định lý Euler Định lý. Đồ thị vô hướng, liên thông G là đồ thị  Euler nếu và chỉ nếu mọi đỉnh của nó đều có bậc chẵn. Hệ quả. Đồ thị vô hướng, liên thông G là đồ thị nửa  Euler nếu và chỉ nếu nó có không quá hai đỉnh bậc lẻ . Lý thuyết đồ thị 07/17/11 10
Thuật toán xây dựng chu trình Euler Thuật toán Fleury  Bắt đầu từ một đỉnh bất kỳ của đồ thị và tuân theo các  quy tắc sau: tắc 1. Khi đi qua một cạnh nào đó thì xóa nó đi và xóa  Quy luôn đỉnh cô lập, nếu có.  Quy tắc 2. Không bao giờ đi qua cầu (cạnh cắt) tr ừ phi không còn cách nào khác. VD: Tìm chu trình Euler trong đồ thị sau:  a b c d e h g f Lý thuyết đồ thị 07/17/11 11
Định lý Euler cho đồ thị có hướng Định lý: Xét G là đồ thị có hướng, liên thông mạnh.  Khi đó G là đồ thị Euler nếu và chỉ nếu mọi đỉnh của G đều có bán bậc ra bằng bán bậc vào. Lý thuyết đồ thị 07/17/11 12
Phần 3.2. Đồ thị Hamilton Giảng viên: Nguyen Ngoc Trung nguyenngoctrung.dhsp@gmail.com
Đường đi, chu trình Hamilton Xét đồ thị G = .  Một đường đi trên đồ thị được gọi là đường đi Hamilton  nếu nó đi qua tất cả các đỉnh, mỗi đỉnh một lần.  Một chu trình trên đồ thị được gọi là chu trình Hamilton nếu nó đi qua tất cả các đỉnh, mỗi đỉnh một lần. VD: Đồ thị sau có các đường đi và chu trình Euler là: 3 d1: 1 2 3 4 5 d2: 1 5 2 4 3 2 4 … C1: 1 2 3 4 5 1 5 1 C2: 2 5 1 4 3 2 … Lý thuyết đồ thị 07/17/11 14
Đồ thị Hamilton Xét đồ thị G = .  Đồ thị G được gọi là đồ thị Hamilton nếu và chỉ nếu tồn  tại một chu trình Hamilton trong G.  Đồ thị G được gọi là đồ thị nửa Hamilton nếu và chỉ nếu tồn tại một đường đi Hamilton trong G. 3 3 2 4 2 4 Đồ thị Hamilton (hiển nhiên cũng là đồ thị nửa Hamilton). 1 5 5 1 Đồ thị nửa Hamilton 6 Lý thuyết đồ thị 07/17/11 15
Một số kết quả trên đồ thị Hamilton Định lý (Dirak, 1952). Xét G là đơn đồ thị vô hướng  với n đỉnh (n>2). Nếu mỗi đỉnh của G đều có bậc không nhỏ hơn n/2 thì G là đồ thị Hamilton Định lý (Dirak, 1952). Xét G là đơn đồ thị có hướng,  liên thông mạnh với n đỉnh. Nếu mọi đỉnh của G đều có bán bậc ra và bán bậc vào không nhỏ hơn n/2 thì G là đồ thị Hamilton Lý thuyết đồ thị 07/17/11 16
Một số kết quả trên đồ thị Hamilton (tt) Định lý.  Mọi đồ thị đấu loại là nửa Hamilton   Mọi đồ thị đấu loại, liên thông mạnh là Hamilton Định lý (Ore, 1960). Cho đồ thị G có n đỉnh. Nếu hai  đỉnh không kề nhau bất kỳ của G đều có tổng bậc không nhỏ hơn n thì G là đồ thị Hamilton. Nghĩa là: ( ∀u, v ∈V , (u, v) ∉ E ⇒ deg(u ) + deg(v) ≥ n ) ⇒ G Hamilton Lý thuyết đồ thị 07/17/11 17
Kiểm tra đồ thị Hamilton??? Các quy tắc để xác định chu trình Hamilton (H) của  đồ thị: Quy tắc 1: Nếu có 1 đỉnh bậc 2 thì hai cạnh của đỉnh này  bắt buộc phải nằm trong H  Quy tắc 2: Không được có chu trình con (độ dài nhỏ hơn n) trong H  Quy tắc 3: Ứng với một đỉnh nào đó, nếu đã chọn đủ 2 cạnh vào H thì phải loại bỏ tất cả các cạnh còn lại (vì không thể chọn thêm)  Không có đỉnh cô lập hoặc đỉnh treo nào khi áp dụng quy tắc 3. Lý thuyết đồ thị 07/17/11 18
Kiểm tra đồ thị Hamilton (tt) Đồ thị sau đây có Hamilton không?  3 2 1 5 6 4 9 7 8 Lý thuyết đồ thị 07/17/11 19