TAILIEUCHUNG - 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 .

• Toán học
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Đồ thị Euler
• Đồ thị Hamilton
• Thuật toán Bellman Ford
• Bài toán tìm đường đi ngắn nhất
• Toán rời rạc
• Bài giảng toán rời rạc
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• bài tập toán rời rạc
• lý thuyết toán rời rạc
• đề cương Toán rời rạc
• tìm hiểu Toán rời rạc
• Thuật toán Dijkstra
• Toán học rời rạc
• Cấu trúc rời rạc
• Phương pháp đếm dùng hàm sinh
• Hệ số hàm sinh
• Hàm sinh mũ
• Bài giảng Toán học rời rạc
• Tìm kiếm trên đồ thị
• Thuật toán tìm kiếm
• Ứng dụng của thuật toán tìm kiếm
• Công nghệ thông tin
• Giới thiệu môn học
• Trí tuệ nhân tạo
• Khái niệm về đồ thị
• Đđồ thị vô hướng
• Đồ thị có hướng
• Dạng đồ thị đặc biệt
• Biểu diễn đồ thị trên máy tính
• Biểu diễn đồ thị
• Biểu diễn đồ thị bằng danh sách kề
• Ma trận liên thuộc
• Chứng minh đồ thị là nửa Euler
• Toán rời rạc ứng dụng trong tin học
• Bài toán về đường đi
• Đường đi Euler
• Đường đi Hamilton
• Cây khung của đồ thị
• Hàm đơn ánh
• Độ tăng của hàm
• Thuật toán
• Thuật toán sắp xếp nổi bọt
• Hàm và thuật toán
• Độ phức tạp của thuật toán
• Nguyên lý bù trừ
• Hoán vị lặp
• Tổ hợp lặp
• Giải tích tổ hợp
• Hệ thức đệ qui
• Lý thuyết tập hợp
• Phép toán tập hợp
• Tích Descartes
• cơ sở dữ liệu
• hệ thống dữ liệu
• Bài giảng Hàm Bool
• Phép toán trên hàm Bool
• Dạng nối rời chính tắc của Hàm Bool
• Phương pháp biểu đồ Karnaugh
• Đồ thị vô hướng
• Biểu diễn đồ thị bằng ma trận kề
• Thuật toán tìm kiếm theo chiều sâu
• Bài giảng Quan hệ
• Quan hệ 2 ngôi
• Tính chất quan hệ 2 ngôi
• Tập hợp thương
• Bài giảng Toán rời rạc 1
• Toán rời rạc 1
• Bài toán liệt kê
• Thuật toán quay lui
• Thuật toán nhánh
• Nguyên lý Dirichlet
• Duyệt đồ thị
• Bài toán đường đi ngắn nhất
• Lý thuyết đồ thị
• Bài toán luồng cực đại