tailieunhanh - Bài giảng Toán rời rạc 2: Phần 2

Nối tiếp phần 1, "Bài giảng Toán rời rạc 2: Phần 2" tiếp tục cung cấp cho học viên những kiến thức về đồ thị Euler, đồ thị Hamilton; thuật toán tìm chu trình Euler; thuật toán tìm đường đi Euler; thuật toán tìm tất cả các chu trình Hamilton; cây khung của đồ thị; xây dựng cây khung của đồ thị dựa vào thuật toán DFS; bài toán tìm đường đi ngắn nhất; thuật toán Bellman-Ford; . Mời các bạn cùng tham khảo! | HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG - - KHOA CÔNG NGHỆ THÔNG TIN BÀI GIẢNG TOÁN RỜI RẠC 2 NGUYỄN DUY PHƯƠNG HàNội 2016 CHƢƠNG 4. ĐỒ THỊ EULER ĐỒ THỊ HAMIL TON . Đồ thị Euler đồ thị nửa Euler Đị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. Rõ ràng mọi đồ thị Euler đều là nửa Euler nhƣng điều ngƣợc lại không đúng. Ví dụ 1. Xét các đồ thị G1 G2 G3 trong Hình . a b a b a b e e d c d c c d e G1 G2 G3 Hình . Đồ thị vô hướng G1 G2 G3. Đồ thị G1 là đồ thị Euler vì nó có chu trình Euler a e c d e b a. Đồ thị G3 không có chu trình Euler nhƣng chứa đƣờng đi Euler a c d e b d a b vì thế G3 là nửa Euler. G2 không có chu trình Euler cũng nhƣ đƣờng đi Euler. Ví dụ 2. Xét các đồ thị có hƣớng H1 H2 H3 trong Hình . a b a b a b c c d e d d c H1 H2 H3 Hình . Đồ thị có hướng H1 H2 H3. Đồ thị H2 là đồ thị Euler vì nó chứa chu trình Euler a b c d e a vì vậy nó là đồ thị Euler. Đồ thị H3 không có chu trình Euler nhƣng có đƣờng đi Euler a b c a d c nên nó là đồ thị nửa Euler. Đồ thị H1 không chứa chu trình Euler cũng nhƣ chu trình Euler. . Thuật toán tìm chu trình Euler Để tìm một chu trình Euler của đồ thị ta sử dụng kết quả của định lý sau. Định lý 1. Điều kiện cần và đủ để đồ thị G là Euler. Đồ thị vô hƣớng liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. Đồ thị có 68 hƣớng liên thông yếu G 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 . . Chứng minh đồ thị là Euler Đối với đồ thị vô hƣớng để chứng minh đồ thi có là Euler hay không ta chỉ cần thực hiện Kiểm tra đồ thị có liên thông hay không Điều này dễ dàng thực hiện bằng cách kiểm tra DFS u V hoặc BFS u V thì ta kết luận đồ thị là liên .