[PDF] Đường đi Euler Và đường đi Hamilton - te

Search

• Categories
• Top Downloads
• Login
• Register
Search

• Home
• 10. Euler Hamilton

10. Euler Hamilton March 20, 2018 | Author: Anonymous | Category: N/A DOWNLOAD PDF Share Embed Report this link

Short Description

Download 10. Euler Hamilton...

Description

Đường đi Euler và đường đi Hamilton 1 Đường đi Định nghĩa: Cho G = (X, E). • Đường đi (path) là một dãy các cạnh liên tiếp nhau (x0, x1, x2, …, xk) trong đó xixi+1 là một cạnh E. Độ dài (length) của đường đi = k. • Đường đi đơn (simple) nếu không có cạnh nào xuất hiện quá một lần. • Đường đi sơ cấp (elementary) nếu không có đỉnh nào xuất hiện quá một lần. • Đường đi là chu trình (cycle) nếu đỉnh đầu trùng đỉnh cuối x0 = xk. 2 Ví dụ đường đi • (u, y, w, v) là một đường đi độ dài 3. • (z, u, y, v, u) là một đường đi đơn nhưng không sơ cấp. • (u, y, w, v, u) là một chu trình. Có thể xem chu trình này như chu trình (w, v, u, y, w). 3 Định lý ĐL: Nếu mọi đỉnh của một đồ thị G đều có bậc 2 thì G có ít nhất một chu trình đơn. Chứng minh (Xem giáo trình) 4 Tính liên thông của đồ thị ĐN: Hai đỉnh x và y của một đồ thị vô hướng được gọi là liên thông (connected) với nhau nếu x = y hoặc có đường đi giữa hai đỉnh x, y. Nhận xét: • Quan hệ liên thông là một quan hệ tương đương. • Mỗi lớp tương đương là một thành phần liên thông (component) của G. • Nếu G chỉ có một thành phần liên thông thì G được gọi là đồ thị liên thông (luôn có đường đi giữa hai đỉnh x, y bất kỳ). 5 Ví dụ tính liên thông • G liên thông • H không liên thông • H có 2 thành phần liên thông Khớp Cầu 6 Đối chu trình ĐN: Cho G = (X,E) và A X. Đối chu trình của A, ký hiệu w(A), gồm các cạnh của G có một đỉnh trong A, một đỉnh ngoài A. VD: • Với A = {x, y}, w(A) = {xu, yu, yv, yw}. • Với B = {x, u}, w(B) = {xy, uz, uv, uy}. 7 Đối chu trình sơ cấp ĐN: w = w(A) được gọi là đối chu trình sơ cấp (tập cắt) nếu: – G – w không liên thông – G – w’ còn liên thông với mọi tập con w’ của w. VD: với A = {x, y}, w(A) = {xu, yu, yv, yw} là một tập cắt. Với B = {x, u}, w(B) = {xy, uz, uv, uy} không là một tập cắt vì G – {uz} không liên thông. 8 Biểu diễn đồ thị bằng ma trận 9 Ma trận của đồ thị vô hướng A(i,i) = 0, A(i,j) = 1 nếu đỉnh i kề j.       A :=       0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1   0  1  0  0 10 Ma trận của đồ thị có hướng B(i,i) = 0, B(i,j) = 1 nếu có cung ij.       B :=       0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 1 0   0  0  0  0 11 Ma trận khoảng cách của đồ thị vô hướng có trọng lượng K(i,j) = trọng lượng của cạnh ij. K(i,i) = 0, K(i,j) = nếu không có cạnh ij.  0  5    0 7  1    K :  5 7 0 1       1 0 2     1  2 0  12 Ma trận khoảng cách của đồ thị có hướng có trọng lượng K(i,j) = trọng lượng của cung ij. K(i,i) = 0, K(i,j) = nếu không có cung ij.  0 6     0  5    K :  6 1 0      8   0      3  5 0  13 Đường đi Euler ĐN: Một đường đi trong đồ thị G được gọi là đường đi Euler nếu nó đi qua tất cả các cạnh của G, mỗi cạnh đúng một lần. • Nếu G có chu trình Euler thì G được gọi là đồ thị Euler. VD: đồ thị G bên có chu trình Euler a g e abdhbcdefa nên G là một đồ thị Euler. 14 Sự tồn tại đường đi Euler ĐL: Cho G liên thông. Khi MĐ: Cho G liên thông. Khi đó, G có đường đi Euler đó, G Euler khi và chỉ (nhưng không có chu khi mọi đỉnh của G đều trình Euler) khi và chỉ có bậc chẵn. khi G có đúng hai bậc lẻ. Vẽ được một nét 15 Thuật toán Fleury tìm đường đi Euler • Xuất phát từ một đỉnh bất kỳ, tạo đường đi Euler thoả hai quy tắc sau: 1. Xoá các cạnh đã đi qua và các đỉnh cô lập (nếu có). 2. Tại mỗi đỉnh, ta chỉ đi qua cầu nếu không còn sự lựa chọn nào khác. 1 9 Nếu đồ thị có đúng hai bậc lẻ (có đường đi Euler) thì xuất phát từ một đỉnh bậc lẻ 12 5 10 8 2 4 6 11 3 7 16 Đồ thị Hamilton ĐN: Một đường đi trong đồ thị G được gọi là đường đi Hamilton nếu nó đi qua tất cả các đỉnh của G, mỗi đỉnh đúng một lần. • Nếu G có chu trình Hamilton thì G được gọi là đồ thị Hamilton. VD: đồ thị G bên có chu trình Hamilton 17 Quy tắc kiểm tra đồ thị Hamilton Giả sử đồ thị G có chu trình Hamilton H. Khi đó 1. Tất cả các cạnh kề với đỉnh bậc hai phải thuộc H. 2. Không có chu trình con nào được hình thành trong quá trình xây dựng H. 3. Khi trong H có đường đi qua đỉnh u thì xoá các cạnh kề u còn lại mà không sử dụng.  tạo nên đỉnh có bậc mới. 4. Không có đỉnh treo hoặc đỉnh cô lập được tạo nên khi áp dụng Qui tắc 3. VD: theo quy tắc 1, các cạnh fa, fe, ga, ge phải thuộc H. • Khi đó có chu trình con agef  vi phạm quy tắc 2. •  đồ thị không Hamilton. 18 Đường đi ngắn nhất • Trong đồ thị có trọng lượng, có thể có nhiều con đường đi giữa hai đỉnh a, b bất kỳ. • Trong thực tế ta thường muốn tìm phương án tối ưu  đường đi ngắn nhất Nhà chàng Nhà nàng 19 Thuật toán Dijsktra tìm đường đi ngắn nhất • Input: đồ thị G không có trọng lượng âm, đỉnh xuất phát x0. • Output: đường đi ngắn nhất từ x0 đến các đỉnh còn lại Nguồn: ThS. Trịnh Thanh Đèo 20 Thuật toán Dijkstra 1. Khởi tạo: T = V; p(x0) = 0. Với mọi đỉnh i x0, đặt p(i) = , đánh dấu đỉnh i là ( , -). 2. Tìm i T sao cho p(i) = min{p(j), j T}. Cập nhật T := T – {i}. Nếu T = thì dừng. Ngược lại đến bước 3. 3. Nếu Kề(i) T thì trong các đỉnh j Kề(i) T, chọn p(j) = min{p(j), p(i) + Dij}. Nếu p(j) được chọn là p(i) + Dij thì đánh dấu j là (p(j),i). Quay lại bước 2. Đỉnh i có nhãn (x,y) nghĩa là trên đường đi ngắn nhất từ x0 đến i , trước khi đến i thì qua y, tổng độ dài là x. 21 Ví dụ trên đồ thị vô hướng Nguồn: ThS. Trịnh Thanh Đèo 22 Ví dụ trên đồ thị có hướng Nguồn: ThS. Trịnh Thanh Đèo 23 Bài tập 1. 2. 3. 4. Cho một ví dụ đồ thị Euler nhưng không Hamilton. Cho một ví dụ đồ thị Hamilton nhưng không Euler. Cho một ví dụ đồ thị vừa Euler vừa Hamilton. Tìm đường đi ngắn nhất của đồ thị sau, xuất phát từ đỉnh 3. 24 5. Cho đồ thị G sau. Tìm đường đi ngắn nhất từ đỉnh 2 đến các đỉnh còn lại. 25 View more...

Comments

Report "10. Euler Hamilton"

Please fill this form, we will try to respond as soon as possible.

Your name Email Reason -Select Reason- Pornographic Defamatory Illegal/Unlawful Spam Other Terms Of Service Violation File a copyright complaint Description Close Submit Share & Embed "10. Euler Hamilton"

Please copy and paste this embed script to where you want to embed

Embed Script Size (px) 750x600 750x500 600x500 600x400 URL Close Copyright © 2017 DOCUMEN Inc.