zunia.vn

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

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Toán rời rạc: Đồ thị euler và đồ thị hamilton - ThS. Hoàng Thị Thanh Hà

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

Báo xấu

7
lượt xem 2
download

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

Bài giảng Toán rời rạc - Đồ thị euler và đồ thị hamilton được biên soạn gồm các nội dung chính sau: Đường đi euler và đồ thị euler; Đường đi và đồ thị hamilton. Mời các bạn cùng tham khảo!

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 Toán rời rạc: Đồ thị euler và đồ thị hamilton - ThS. Hoàng Thị Thanh Hà

Nội dung 1. ĐƯỜNG ĐI EULER VÀ ĐỒ THỊ EULER Toán rời rạc (4): 2. ĐƯỜNG ĐI VÀ ĐỒ THỊ HAMILTON ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON Ts. Hoàng Thị Thanh Hà Khoa Thống kê –Tin học Trường Đại học Kinh tế Đại học Đà Nẵng 22 October 2012 1 22 October 2012 2 ĐƯỜNG ĐI & ĐỒ THỊ EULER ĐƯỜNG ĐI & ĐỒ THỊ EULER Có thể coi năm 1736 là năm khai sinh lý thuyết đồ thị, Sông Pregel và 7 chiếc cầu nối các vùng này với nhau. với việc công bố lời giải “bài toán về các cầu ở Konigsberg” của nhà toán học lỗi lạc Euler (1707- 1783) Thành phố Konigsberg thuộc Phổ (nay gọi là Kaliningrad thuộc Nga) được chia thành bốn vùng bằng các nhánh sông Pregel, các vùng này gồm hai vùng bên bờ sông, đảo Kneiphof và một miền nằm giữa hai nhánh của sông Pregel. Vào thế kỷ 18, người ta xây bảy chiếc cầu nối các vùng này với nhau. 22 October 2012 3 22 October 2012 4 1
ĐƯỜNG ĐI & ĐỒ THỊ EULER ĐƯỜNG ĐI & ĐỒ THỊ EULER “Có thể nào đi dạo qua tất cả bảy cầu, mỗi cầu chỉ một lần thôi không?” Nếu ta coi mỗi khu vực A, B, C, D như một đỉnh và mỗi cầu qua lại 2 khu vực là 1 cạnh nối hai đỉnh thì ta có sơ đồ của Konigsberg là một đa đồ thị G: 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 này như sau: Có tồn tại chu trình đơn trong đa đồ thị G chứa tất cả các cạnh? 22 October 2012 5 22 October 2012 6 ĐƯỜNG ĐI & ĐỒ THỊ EULER ĐƯỜNG ĐI & ĐỒ THỊ EULER a) ĐN1: Đường đi và đồ thị Euler a b a b a b i) Đường đi Euler là đường đi qua tất cả các cạnh (cung) mỗi cạnh đúng một lần. e e Chu trình Euler là chu trình đi qua tất cả các cạnh của đồ thị mỗi cạnh đúng một lần. d c d c c d e ii) Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler G1 G2 G3 iii) Đồ thị được gọi là đồ thị nửa Euler nếu nó có dường đi Euler Đ th G1 là đ th Euler vì có chu trình Euler: Nhận xét: Đường đi (t.ư chu trình ) Euler là đường đi (t.ư chu trình) đơn a,e,c,d,e,b,a Đ th G2 không có chu trình cũng như đư ng đi Euler Đ th G3 là đ th n a Euler vì có đư ng đi Euler: 22 October 2012 7 a,c,d,e,b,d,a,b 22 October 2012 8 2
ĐƯỜNG ĐI & ĐỒ THỊ EULER ĐƯỜNG ĐI & ĐỒ THỊ EULER b) Đ nh lý1 c) Thu t toán Fleury đ tìm chu trình Euler i) Cho G=(V,E) là đ th vô hư ng liên thông. B t đ u t m t đ nh b t kỳ c a G và tuân theo G là đ th Euler ⇔ M i đ nh c a G đ u có b c qui t c sau: ch n. – M i khi đi qua m t c nh nào đó thì xoá nó đi, sau đó xoá đ nh cô l p n u có. ii) N u G có hai đ nh b c l còn m i đ nh khác – Không bao gi đi qua m t c u tr phi không còn đ u có b c ch n thì G có đư ng đi Euler. cách đi nào khác 22 October 2012 9 22 October 2012 10 ĐƯỜNG ĐI & ĐỒ THỊ EULER BÀI TOÁN NGƯỜI PHÁT THƯ TRUNG HOA Ví d : chu u v w s trình Euler Một nhân viên đi từ Sở Bưu Điện, qua một số uvwyswzyxtvx đường phố để phát thư, rồi quay về Sở. Người ấy u phải đi qua các đường theo trình tự nào để đường t x y z đi là ngắn nhất? T u, theo (u,v) ho c (u,x), gi s (u,v) (xoá (u,v)). T v ch n 1 trong: (v,w), (v,x), (v,t), gi s (v,w) (xoá (v,w)). Theo 1 trong Bài toán được nhà toán học Trung Hoa Guan nêu 3: (w,s), (w,y), (w,z), gi s (w,s) (xoá (w,s)). Theo (s,y) (xoá lên đầu tiên (1960), vì vậy thường được gọi là “bài (s,y) và s). Vì (y,x) là c u nên theo 1 trong 2: (y,w), (y,z), gi s (y,w) (xoá (y,w)). Theo (w,z) (xoá (w,z) & w) & theo (z,y) (xoá toán người phát thư Trung Hoa”. (z,y) & z). Theo (y,x) (xoá (y,x) và y). Vì (x,u) là c u nên theo (x,v) ho c (x,t), gi s (x,v) (xoá (x,v)). Theo (v,t) (xoá (v,t) và v), theo (t,x) (xoá (t,x) và t), theo (x,u) (xoá (x,u), x & u) 22 October 2012 11 22 October 2012 12 3
BÀI TOÁN NGƯỜI PHÁT THƯ TRUNG HOA BÀI TOÁN NGƯỜI PHÁT THƯ TRUNG HOA (ti p) Bài toán quy v d ng: Cho đ th liên (ti p) D th y r ng m t hành trình qua m t c nh thông G. M t hành trình c a ngư i đưa thư là (u,v) nào đó quá hai l n thì không ph i là hành trình m t chu trình qua m i c nh c a G, hãy tìm ng n nh t trong G. Vì v y, ta ch c n xét nh ng hành hành trình ng n nh t, t c là qua ít c nh nh t. trình T đi qua hai l n m t s c nh nào đó c a G N u G là đ th Euler (m i đ nh đ u có b c Ta quy ư c xem m i hành trình T trong G là m t ch n) thì chu trình Euler trong G (qua m i hành trình trong đ th Euler GT, có đư c t G b ng c nh c a G đúng m t l n) là hành trình ng n cách v thêm m t c nh song song đ i v i nh ng nh t c n tìm. c nh mà T đi qua hai l n. Bài toán đ t ra đư c đưa v bài toán sau: Ch còn ph i 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 Trong các đ th Euler GT, tìm đ th có s c nh ít qua ít nh t hai l n m t s c nh nào đó. nh t (khi đó chu trình Euler trong đ th này là hành trình ng n nh t). 22 October 2012 13 22 October 2012 14 BÀI TOÁN NGƯỜI PHÁT THƯ TRUNG HOA BÀI TOÁN NGƯỜI PHÁT THƯ TRUNG HOA Đ nh lý (Gooodman & Hedetniemi) N u G là m t Gi i bài toán ngư i phát thư Trung Hoa cho đ th đ th liên thông có q c nh thì hành trình ng n nh t sau: D trong G có chi u dài: q + m(G), m(G) là s c nh mà C E 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 B J K F 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) – Ta 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, ta tính kho ng A I H G cách gi a hai đ nh trong t ng c p, r i 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). 22 October 2012 15 22 October 2012 16 4
BÀI TOÁN NGƯỜI PHÁT THƯ TRUNG HOA BÀI TOÁN NGƯỜI PHÁT THƯ TRUNG HOA T p h p các đ nh b c l VO(G)={B, G, H, K} và t p h p A, B, C, D, E, F, K, G, K, E, C, J, K, H, J, I, H, I, B, I, A các phân ho ch c p là P={P1, P2, P3}, trong đó D P1 ={(B, G), (H, K)}→ d(P1) = d(B, G)+d(H, K) =4+1 =5, C E P2 ={(B, H), (G, K)}→ d(P2)= d(B, H)+d(G, K)=2+1= 3, B J K F 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 A I H G Do đó 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: 22 October 2012 17 22 October 2012 18 A, B, C, D, E, F, K, G, K, E, C, J, K, H, J, I, H, I, B, I, A ĐƯỜNG ĐI & ĐỒ THỊ HAMILTON ĐƯỜNG ĐI & ĐỒ THỊ HAMILTON Năm 1857, nhà toán h c ngư i Ailen là Hamilton a) ĐN (1805-1865) đưa ra trò chơi “đi vòng quanh th Đư ng đi Hamilton là đư ng đi qua t t c các gi i” như sau: đ nh c a đ th m i đ nh đúng m t l n. Cho m t hình th p nh di n đ u (đa di n đ u có Chu trình b t đ u t m t đ nh v nào đó và đi qua 12 m t, 20 đ nh và 30 c nh), m i đ nh c a hình t t c các đ nh còn l i, m i đ nh đúng m t l n g i mang tên m t thành ph n i ti ng, m i c nh c a là chu trình Hamilton (m ch Hamilton) hình (n i hai đ nh) là đư ng đi l i gi a hai thành ph tương ng. Xu t phát t m t thành ph , hãy Đ th g i là đ th Hamilton n u nó có chu trình tìm đư ng đi thăm t t c các thành ph khác, m i Hamilton, g i là n a Hamilton n u nó có đư ng thành ph ch m t l n, r i tr v ch cũ. đi Hamilton 22 October 2012 19 22 October 2012 20 5
ĐƯỜNG ĐI & ĐỒ THỊ HAMILTON ĐƯỜNG ĐI & ĐỒ THỊ HAMILTON C b) Điều kiện đủ (cho đồ thị đơn vô hướng). J i) ĐL Ore (1960). Cho đồ thị G có n đỉnh. Nếu K I deg(i)+deg(j) ≥ n≥ 3 với i và j là hai đỉnh không B D L O P H kề nhau tuỳ ý thì G là Hamilton. N Q ii) ĐL Dirac (1952) Cho đồ thị G có n đỉnh. Nếu M R G deg(i) ≥ n/2 với i tuỳ ý thì G là Hamilton T S F A E 22 October 2012 21 22 October 2012 22 ĐƯỜNG ĐI & ĐỒ THỊ HAMILTON ĐƯỜNG ĐI & ĐỒ THỊ HAMILTON iii) ĐL (Rédei): Nếu G là một đồ thị có hướng v) ĐL3: Đồ thị đầy đủ Kn với n lẻ và n ≥ 3 có đầy đủ thì G là đồ thị nửa Hamilton. đúng (n-1)/2 chu trình Hamilton phân biệt. Hệ quả: Nếu G là đơn đồ thị có n đỉnh và mọi đỉnh của G đều có bậc không nhỏ hơn n/2 thì G là đồ thị nửa Hamilton. iv) ĐL2: Nếu G là đồ thị phân đôi với hai tập đỉnh là V1, V2 có số đỉnh là n (n ≥ 2) và bậc của mỗi đỉnh lớn hơn n/2 thì G là đồ thị Hamilton 22 October 2012 23 22 October 2012 24 6
ĐƯỜNG ĐI & ĐỒ THỊ HAMILTON ĐƯỜNG ĐI & ĐỒ THỊ HAMILTON Bài toán sắp xếp chỗ ngồi: Có n đại biểu từ n Xét đồ thị gồm n đỉnh, mỗi đỉnh ứng với mỗi nước đến dự hội nghị quốc tế. Mỗi ngày họp người dự hội nghị, hai đỉnh kề nhau khi hai đại một lần ngồi quanh một bàn tròn. Hỏi phải bố trí biểu tương ứng muốn làm quen với nhau. Như vậy, ta có đồ thị đầy đủ Kn. Đồ thị này là bao nhiêu ngày và bố trí như thế nào sao cho Hamilton và rõ ràng mỗi chu trình Hamilton là trong mỗi ngày, mỗi người có hai người kế bên một cách sắp xếp như yêu cầu của bài toán. là bạn mới. Lưu ý rằng n người đều muốn làm Bái toán trở thành tìm các chu trình Hamilton quen với nhau. 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) 22 October 2012 25 22 October 2012 26 ĐƯỜNG ĐI & ĐỒ THỊ HAMILTON ĐƯỜNG ĐI & ĐỒ THỊ HAMILTON Theo định lý 3, với đồ thị đầy đủ Kn, có đúng c)Qui t c đ xây d ng m t chu trình (n-1)/2 chu trình Hamilton. Hamilton H ho c ch ra đ th vô hư ng Với n=11, ta có (11-1)/2 =5 chu trình Hamilton. không là Hamilton. Đó là: 1 2 3 4 5 6 7 8 9 10 11 1 1 3 5 2 7 4 9 6 11 8 10 1 Qui t c 1:T t c các c nh k v i đ nh b c 2 1 5 7 3 9 2 11 4 10 6 8 1 ph i trong H 1 7 9 5 11 3 10 2 8 4 6 1 Qui t c 2: Không có chu trình con (chu trình 1 9 11 7 10 5 8 3 6 2 4 1 có chi u dài
ĐƯỜNG ĐI & ĐỒ THỊ HAMILTON Qui t c 3: Trong quá trình xây d ng H, sau khi đã l y 2 c nh t i 1 đ nh x đ t vào H r i thì không th l y thêm c nh nào t i x n a. Xóa m i c nh còn l i k x (vì không đư c dùng đ n n a). Đi u này l i có th cho ta m t s đ nh b c 2 và ta l i dùng qui t c 1. Qui t c 4: Không có đ nh cô l p hay c nh treo nào đư c t o nên sau khi áp d ng qui t c 3. 22 October 2012 29 8

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.