›
›

Bài giảng Toán rời rạc 2 - Chương 4: Đồ thị Euler - Đồ thị Hamilton

Download
ĐỒ THỊ EULER  
ĐỒ THỊ HAMILTON  
Toán rời rạc 2  
Nội dung  
• Đồ thị Euler  
• Đồ thị Hamilton  
2
Đồ thị Euler  
Khái niệm đồ thị Euler (1/2)  
• Định nghĩa.  
– Chu trình đơn trong đồ thị G đi qua mỗi cạnh của đồ thị đúng  
một lần được gọi là chu trình Euler.  
– Đường đi đơn trong G đi qua mỗi cạnh của nó đúng một lần  
được gọi là đường đi Euler.  
– Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler.  
– Đồ thị có đường đi Euler được gọi là nửa Euler.  
• Ví dụ 1:  
4
Khái niệm đồ thị Euler (2/2)  
• Ví dụ 2:  
5
Điều kiện cần và đủ để đồ thị là Euler  
• Đồ thị vô hướng  
– Đồ thị vô hướng liên thông G=<V,E> là đồ thị Euler  
khi và chỉ khi mọi đỉnh của G đều có bậc chẵn.  
• Đồ thị có hướng  
– Đồ thị có hướng liên thông yếu G=<V,E> là đồ thị  
Euler khi và chỉ khi tất cả các đỉnh của nó đều có bán  
đỉnh bậc ra bằng bán đỉnh bậc vào (điều này làm cho  
đồ thị là liên thông mạnh)  
6
Chứng minh đồ thị là Euler  
• Với đồ thị vô hướng:  
– Kiểm tra đồ thị có liên thông hay không?  
• Kiểm tra DFS(u) = V hoặc BFS(u) = V l iên thông  
– Kiểm tra bậc của tất cả cả đỉnh có phải số chẵn hay không?  
• Với ma trận kề, tổng các phần tử của hàng u�(cột u) là bậc của đỉnh u.  
• Với đồ thị có hướng:  
– Kiểm tra đồ thị có liên thông yếu hay không?  
• Kiểm tra đồ thị vô hướng tương ứng là liên thông, hoặc  
• Kiểm tra nếu tồn tại đỉnh u∈V để DFS(u)=V hoặc BFS(u)=V?  
– Kiểm tra tất cả các đỉnh có thỏa mãn bán bậc ra bằng bán bậc  
vào hay không?  
• Với ma trận kề, bán bậc ra của đỉnh u là deg+(u) là số các số 1 của hàng u,  
bán bậc vào của đỉnh u là deg-(u) là số các số 1 của cột u.  
7
Ví dụ với đồ thị vô hướng  
• Cho đồ thị vô hướng được biểu diễn dưới dạng ma  
trận kề như hình dưới. Chứng minh là đồ thị Euler .  
• Vì BFS(1) = { 1, 2, 6, 3, 5,  
7, 4, 11, 8, 10, 12, 9, 13} =  
V. Do vậy, G liên thông.  
• Ta lại có:  
• deg(1) = deg(13) = 2.  
• deg (2) = deg(3) = 4  
• deg(4) = deg(5) = 4  
• deg(6) = deg(7) = 4  
• deg(8) = deg(9) = 4  
• deg(10) = deg(11) =  
• deg(12) = 4  
8
Ví dụ với đồ thị có hướng  
• Cho đồ thị có hướng được biểu diễn dưới dạng ma  
trận kề như hình dưới. Chứng minh là đồ thị Euler .  
9
Thuật toán tìm chu trình Euler  
10  
Kiểm nghiệm thuật toán (1/3)  
• Tìm chu trình  
Euler cho đồ  
thị vô hướng  
được biểu  
diễn dưới  
dạng ma trận  
kề như bên  
cạnh.  
11  
Kiểm nghiệm thuật toán (2/3)  
12  
Kiểm nghiệm thuật toán (3/3)  
13  
Cài đặt thuật toán  
• Thủ tục Init(): đọc dữ liệu theo khuôn dạng biểu diễn ma  
trận kề.  
• Thủ tục Kiemtra(): Kiểm tra xem G có là Euler hay  
không.  
• Thủ tục EulerCycle (u) : Xây dựng chu trình Euler bắt  
đầu tại đỉnh u.  
Xem code minh họa  
14  
Điều kiện cần và đủ để đồ thị là nửa Euler  
• Với đồ thị vô hướng  
– Đồ thị vô hướng liên thông G=<V,E> là đồ thị nửa  
Euler khi và chỉ khi G có 0 hoặc 2 đỉnh bậc lẻ  
• G có 2 đỉnh bậc lẻ: đường đi Euler xuất phát tại một đỉnh bậc  
lẻ và kết thúc tại đỉnh bậc lẻ còn lại  
• G có 0 đỉnh bậc lẻ: G chính là đồ thị Euler.  
• Đồ thị có hướng  
– Đồ thị có hướng liên thông yếu G =<V,E> là đồ thị  
nửa Euler khi và chỉ khi:  
• Tồn tại đúng hai đỉnh u, v V sao cho  
deg+(u) - deg-(u)= deg-(v) - deg+(v)=1.  
• Các đỉnh su, sv còn lại có deg+(s)=deg-(s).  
• Đường đi Euler sẽ xuất phát tại đỉnh u và kết thúc tại đỉnh v.  
15  
Chứng minh đồ thị là nửa Euler  
• Với đồ thị vô hướng:  
– Chứng tỏ đồ thị đã cho liên thông  
• Sử dụng hai thủ tục DFS() hoặc BFS()  
– Có 0 hoặc 2 đỉnh bậc lẻ  
• Sử dụng tính chất của các phương pháp biểu diễn đồ thị để tìm ra bậc của  
mỗi đỉnh.  
• Với đồ thị có hướng:  
– Chứng tỏ đồ thị đã cho liên thông yếu  
• Sử dụng hai thủ tục DFS() hoặc BFS()  
– Có hai đỉnh u,v ∈ V thỏa mãn  
deg+(u) - deg-(u)= deg-(v) - deg+(v)=1  
– Các đỉnh su, sv còn lại có deg+(s) = deg-(s).  
16  
Ví dụ với đồ thị vô hướng  
• Cho đồ thị vô hướng được biểu diễn dưới dạng ma  
trận kề như hình dưới. Chứng minh là đồ thị nửa Euler  
.
• Theo tính chất của ma trận  
kề, tổng các phần tử hàng u  
là bậc của đỉnh u. Vậy ta có:  
• deg(1) = deg(13) = 3  
• deg (2) = deg(3) = deg(11) = 4  
• deg(12) = deg(6) = deg(7) = 4  
• deg(8) = deg(9) = 4  
• deg(5) = deg(4) = deg(10) = 6  
• G liên thông và có 2 đỉnh  
bậc lẻ u=1 và u=13 nên G là  
nửa Euler.  
17  
Ví dụ với đồ thị có hướng  
• Cho đồ thị có hướng được biểu diễn dưới dạng ma  
trận kề như hình dưới. Chứng minh là đồ thị nửa Euler  
.
18  
Thuật toán tìm đường đi Euler (1/2)  
• Thuật toán tìm đường đi Euler và chu trình Euler chỉ  
khác nhau duy nhất ở một điểm đó là đầu vào của thuật  
toán.  
• Đối với thuật toán tìm chu trình Euler, đầu vào thuật toán  
là đỉnh uV bất kỳ.  
• Đối với thuật toán tìm đường đi trình Euler, đầu vào  
thuật toán là đỉnh uV  
– là đỉnh bậc lẻ đầu tiên trong đối với đồ thị vô hướng.  
– là đỉnh uV có deg+ (u)-deg- (u)=1 đối với đồ thị có  
hướng,  
19  
Thuật toán tìm đường đi Euler (2/2)  
20  
Tải về để xem bản đầy đủ
pdf 32 trang myanh 22820 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc 2 - Chương 4: Đồ thị Euler - Đồ thị Hamilton", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_toan_roi_rac_2_chuong_4_do_thi_euler_do_thi_hamilt.pdf