Download miễn phí Luận văn Một số vấn đề ứng dụng của đồ thị trong Tin học
Lý thuyết về chu trình, đường đi Euler và Hamilton đã có từ lâu và được nghiên cứu nhiều. Ta có thể bắt gặp nhiều bài toán trong thực tiễn mà có thể sử dụng các lý thuyết về chu trình, đường đi Euler và Hamilton để giải quyết, ví dụ sử dụng lý thuyết đường đi, chu trình Euler để tìm hành trình đường đi cho người phát thư, cho xe rửa đường. sao cho hành trình là tối ưu nhất. hay là trong một hệ thống mạng, một máy đơn cần gửi 1 thông điệp đến tất cả các máy còn lại vậy thì đường truyền tin sẽ đi như thế nào để cho hiệu quả nhất, bài toán này có thể được giải quyết bằng cách vận dụng các lý thuyết chu trình và đường đi Hamilton.
http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-01-17-luan_van_mot_so_van_de_ung_dung_cua_do_thi_trong_t.jjNbjzPLPF.swf /tai-lieu/de-tai-ung-dung-tren-liketly-54366/Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
thể tô màu đồ thị như trên với X: xanh; Đ: đỏ; V: vàng. Từ đồ thị ta có lịch sắp xếp các cuộc họp như sau:
Đợt họp
Tên nhóm
I
1
II
2, 3
III
4
Mỗi màu tương ứng cho 1 đợt họp, những nhóm được tô cùng màu có thể họp trong cùng một đợt.
Chương 3
CHU TRÌNH, ĐƯỜNG ĐI EULER VÀ HAMILTON TRONG ĐỒ THỊ
Lý thuyết về chu trình, đường đi Euler và Hamilton đã có từ lâu và được nghiên cứu nhiều. Ta có thể bắt gặp nhiều bài toán trong thực tiễn mà có thể sử dụng các lý thuyết về chu trình, đường đi Euler và Hamilton để giải quyết, ví dụ sử dụng lý thuyết đường đi, chu trình Euler để tìm hành trình đường đi cho người phát thư, cho xe rửa đường... sao cho hành trình là tối ưu nhất. hay là trong một hệ thống mạng, một máy đơn cần gửi 1 thông điệp đến tất cả các máy còn lại vậy thì đường truyền tin sẽ đi như thế nào để cho hiệu quả nhất, bài toán này có thể được giải quyết bằng cách vận dụng các lý thuyết chu trình và đường đi Hamilton.
I. CHU TRÌNH VÀ ĐƯỜNG ĐI EULER
1. Chu trình Euler
1.1 Định nghĩa
Cho đồ thị vô hướng G = . Một chu trình trong đồ thị G được gọi là chu trình Euler nếu nó đi qua tất cả các cạnh của G và đi qua mỗi cạnh đúng một lần.
Định lý 1: Đồ thị vô hướng G = có chu trình Euler khi và chỉ khi G là liên thông và bậc của tất cả các đỉnh trong đồ thị G là số chẵn.
Chứng minh
- Điều kiện cần: Giả sử đồ thị G = có chu trình Euler. Ta cần chứng minh G là đồ thị liên thông và với mỗi x Î X có m(x) = 2k với k là một số nguyên dương nào đó.
Thật vậy, giả sử G = không liên thông hay G có ít nhất hai thành phần liên thông G1 = và G2 = . Trong đó X1 È X2 = X , U1 È U2 = U, giữa các đỉnh trong X1 và trong X2 không có cạnh hay đường nối với nhau. Giả sử w là 1 chu trình Euler trong G. Theo định nghĩa của chu trình Euler thì w là chu trình đi qua tất cả các cạnh trong G, mỗi cạnh đúng 1 lần. Nếu w có đỉnh chung với G1 = thì w là chu trình nằm gọn trong đồ thị G1. Điều này mâu thuẫn với định nghĩa của w. Chứng tỏ đồ thị G = là liên thông.
Bây giờ ta chứng minh mỗi đỉnh x Î X trong G đều có bậc chẵn, tức là cần chỉ ra m(x) = 2k, với k Î {1,2,...}. Trước hết thấy rằng k ¹ 0 bởi vì nếu k = 0 thì x là điểm cô lập trong G, tức là G không liên thông, trái với điều đã chỉ ra. Giả sử ngược lại tồn tại một đỉnh xi Î X mà m(xi) là một số lẻ, chẳng hạn m(xi) = 3. Đối với xi có 3 cạnh đi vào nó, giả sử đó là các cạnh (xi, xk), (xi, xj) và (xi, x1) Î U. Chu trình Euler w sẽ đi qua 3 cạnh đó. Khi đó một trong 3 cạnh trên có ít nhất một cạnh mà chu trình Euler w đi qua 2 lần. Điều đó mâu thuẫn với định nghĩa của chu trình w. Vậy m(x) là một số chẵn với mọi x Î X.
- Điều kiện đủ: Giả sử G = là đồ thị liên thông và mỗi đỉnh x Î X đều có bậc chẵn: m(x) = 2k, k Î {1, 2,...} ta chứng minh trong đồ thị G tồn tại một chu trình Euler.
Với giả thiết trên, trước hết ta chứng minh rằng tại mỗi đỉnh của G có tồn tại chu trình đơn (tức là chu trình đi qua các cạnh, mỗi cạnh đúng một lần). Đề chứng minh điều đó, ta lưu ý rằng không thể có một đỉnh x mà m(x) = 2. Điều đó đúng bởi vì khi đó tại đỉnh x có khuyên và do đó x cũng là một đỉnh cô lập, trái với giả thiết đồ thị G là liên thông.
Giả sử x Î X là một đỉnh nào đó. Ta chỉ ra có chu trình đơn P qua x. Do m(x) > 2 suy ra tồn tại các đỉnh x1 sao cho x1 ¹ x và x kề với x1. Do m(x1) > 2 suy ra tồn tại các đỉnh xi sao cho xi ¹ xi-1 và xi kề với xi-1. Khi tới bước thứ i thì ta đã có một đường đi tư x đến xi, qua các cạnh, mỗi cạnh đúng một lần. Quá trình trên không thể kéo dài vô hạn do tính hữu hạn của đồ thị G. Giả sử số bước hữu hạn đó là i. Điều này chứng tỏ x và xi kề nhau, tức là có cạnh nối x và xi. Điều đó là đúng vì bước i là bước cuối cùng. Như vậy tại đỉnh x có chu trình đơn P đi qua.
Bây giờ ta chứng minh rằng trong đồ thị G = có chu trình Euler. Theo chứng minh trên với đỉnh x Î X có chu trình đơn đi qua là P1 và P1 là chu trình trong đồ thị G. Hãy "đánh dấu xoá" các cạnh trong P1. Nếu sau khi "đánh dấu xoá" các cạnh trên đường P1 tạo ra một số đỉnh cô lập mới thì hãy "đánh dấu loại bỏ" các đỉnh cô lập mới đó. Kết quả thu được sẽ là một đồ thị mới G1 = là đồ thị con của đồ thị G = đã cho. Ta chỉ ra đồ thị G1 thoả mãn một số tính chất sau:
- Chu trình P1 trong đồ thị G và G1 có đỉnh chung, bởi vì G là đồ thị liên thông.
- Đồ thị G1 gồm các đỉnh x Î X1 có bậc chẵn.
Thật vậy, nếu x Î X1 mà x không thuộc các đỉnh trong P1 thì m(x1) hiển nhiên là một số chẵn.
Còn nếu x1 Î X1 mà x1 là đỉnh thuộc P1 thì sau khi "đánh dấu bỏ " hai cạnh của P1 chứa đỉnh đó thì bậc của đỉnh x1 sẽ giảm đi 2 đơn vị, do đó m(x1) cũng là chẵn.
Tóm lại với mọi x Î X1 thì m(x) là một số chẵn.
Ta có thể minh hoạ đồ thị với chu trình đơn P1 và đồ thị con G1 như hình vẽ dưới đây:
G1 =
x
x1
x1 là đỉnh chung giữa P1 và G1. Đối với G1 = tại đỉnh x1 Î X1 có tồn tại chu trình đơn P2 mà cách xây dựng P2 cũng đối với P1.
Trong P2 bỏ tất cả các cạnh, giữ lại các đỉnh có cạnh hay đường nối với các đỉnh khác trong G1 ta được đồ thị con G2 = của G1. Đồ thị cũng có tính chất như G1, là liên thông, mọi x Î X2 đều có bậc chẵn và G2 và P2 có điểm chung chẳng hạn x2
G2 =
x
x1
x2
Do tính hữu hạn của đồ thịi G, quá trình xây dựng các chu trình đơn sẽ dừng lại ở bước thứ k nào đó. Như vậy, trước khi sang bước thứ k ta đã có k - 1 chu trình đơn P1, P2, ..., Pk-1 và đồ thị Gk-1 = là đồ thị con của đồ thị Gk-2 = . Đồ thị Gk-1 là liên thông và mọi đỉnh x Î Xk-1 có bậc chẵn, đồng thời Gk-1 và Pk-1 có điểm chung là xk. Vì quá trình trên dừng lại sau k bước nên đồ thị Gk-1 là một chu trình đơn qua xk và bao gồm hết các cạnh trong đồ thị Gk-1. Vì nếu không sẽ dẫn tới mâu thuẫn do k là bước cuối cùng.
x
x1
x2
xk-1
P1
P2
Pk-1
Gk-1= Pk
xk
Ghép các chu trình đơn P1, P2,...,Pk tại các đỉnh chung ta được tập các chu trình Euler trong đồ thị G = . Định lý được chứng minh.
Định lý 2: Cho đồ thị có hướng G = G có chu trình Euler khi và chỉ khi G là liên thông và mỗi đỉnh đều có bậc vào bằng bậc ra.
1.2 Thuật toán tìm chu trình Euler
Cho đồ thị G = xây dựng thuật toán tìm chu trình Euler
Bước 1: Kiểm tra xem G có là đồ thị liên thông hay không. Nếu G là liên thông thì chuyển sang bước 2. Ngược lại thì thuật toán dừng và kết luận rằng đồ thị không có chu trình Euler
Bước 2: Kiểm tra xem tất cả các đỉnh trong G đều có bậc chẵn hay không.
Nếu tất cả các đỉnh đều có bậc là chẵn thì chuyển sang bước tiếp theo. Nếu không dừng lại và kết luận đồ thị đã cho không có chu trình Euler.
Bước 3: Xây dựng các chu trình đơn trong G sao cho tất cả các cạnh của đồ thị đều có các chu trình đơn đi qua và mỗi cạnh chỉ đi qua một lần. Ghép các chu trình đơn như trên tại các đỉnh chung nhau ta được tập các chu trình Euler cần tìm.
2. Đường đi Euler
2.1 Định nghĩa
Đường Euler trong đồ thị G = là đường đi qua tất cả các cạnh của đồ thị, mỗi cạnh đi qua đúng một lần.
Đinh lý 3: Cho G = là đồ thị vô hướng liê...
