TAILIEUCHUNG - Bài giảng lý thuyết đồ thị - Chương 3

CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THị VÀ ỨNG DỤNG Trong lý thuyết đồ thị, có rất nhiều thuật toán được xây dựng dựa trên cơ sở duyệt qua tất cả các đỉnh của đồ thị sao cho mỗi đỉnh chỉ được duyệt đúng một lần. Do vậy, việc xây dựng các thuật toán cho phép duyệt qua tất cả các đỉnh của đồ thị một cách có hệ thống là một vấn đề quan trọng thu hút sự quan tâm nghiên cứu của nhiều nhà khoa học. . | Giáo án môn Lý Thuyết Đô Thị Chương 3 CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ VÀ ỨNG DỤNG Trong lý thuyết đồ thị có rất nhiều thuật toán được xây dựng dựa trên cơ sở duyệt qua tất cả các đỉnh của đồ thị sao cho mỗi đỉnh chỉ được duyệt đúng một lần. Do vậy việc xây dựng các thuật toán cho phép duyệt qua tất cả các đỉnh của đồ thị một cách có hệ thống là một vấn đề quan trọng thu hút sự quan tâm nghiên cứu của nhiều nhà khoa học. Các thuật toán như vậy được gọi chung là thuật toán tìm kiếm trên đồ thị. Trong chương này chúng ta sẽ nghiên cứu hai thuật toán tìm kiếm cơ bản trên đồ thị là Thuật toán tìm kiếm theo chiều sâu Depth First Search và Thuật toán tìm kiếm theo chiều rộng Breadth First Search và một vài ứng dụng của hai thuật toán này. Để đơn giản cho việc trình bày chúng ta sẽ xét đồ thị vô hướng G V E V n E m Đồ thị có hướng sẽ được suy ra một cách tương tự với một vài điểm đặc biệt cần chú ý. Để đánh giá hiệu quả của các thuật toán này chúng ta chỉ chú trọng đến việc đánh giá độ phức tạp tính toán của thuật toán tức số phép toán mà thuật toán cần thực hiện trên mọi bộ dữ liệu vào trong trường hợp xấu nhất. Độ phức tạp tính toán này được biểu diễn bằng một hàm số của kích thước dữ liệu đầu vào. Cụ thể ở đây kích thước của dữ liệu vào sẽ là số đỉnh n và số cạnh m của đồ thị. Khi đó độ phức tạp tính toán của thuật toán sẽ được biểu diễn bằng hàm hai biến f n m là số phép toán nhiều nhất mà thuật toán cần phải thực hiện đối với mọi đồ thị n đỉnh m cạnh. Để so sánh tốc độ tăng của hai hàm nhận giá trị không âm f n và g n chúng ta sử dụng ký hiệu f n O g n . Điều này có nghĩa tương đương với việc tìm được các hằng số dương C và N sao cho f n Cg n Vn N Trường hợp mở rộng nếu f n1 n2 . nk và g n1 n2 . nk là các hàm biểu diễn ta viết f n1 n2 . nk O g n1 n2 . nk Tìm được các hằng số dương C và N sao cho f ni n2 . nk Cg ni n2 . nk với Vn N Nếu độ phức tạp tính toán của thuật toán là O g n thì ta nói là thuật toán có thời gian tính toán cỡ O g n . Thuật toán tìm kiếm .

• Toán học
• biểu diễn đồ thị
• thuật toán
• đồ thị euler
• phương pháp biểu diễn
• cây khung
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Biểu diễn đồ thị bằng danh sách kề
• Ma trận liên thuộc
• Phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế giải thuật
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• biểu diễn hình học
• biêu diễn đồ thị bằng ma trận
• biểu diễn đồ thị bằng bảng
• sự đẳng cấu của các đồ thị
• Số cạnh của đồ thị
• Cách biểu diễn đồ thị
• Ma trận trọng số
• Bài toán trên đồ thị
• Gom cụm đồ thị
• Khối thông điệp
• Diễn đàn thảo luận
• Bài toán gom cụm phẳng
• Biểu diễn văn bản bằng đồ thị
• Gom cụm đồ thị bằng mạng Kohonen
• tài liệu về đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Bài giảng Toán rời rạc
• Đồ thị liên thông
• Biểu diễn đồ thị bằng ma trận
• Bài toán đường đi ngắn nhất
• Tiếp cận kết thúc mở
• Biểu diễn trực quan
• Biểu diễn đồ thị hàm số
• Hàm bậc hai
• Tính chất của dãy số
• Dạy học toán
• Khái niệm đồ thị
• đồ thị con
• đồ thị riêng
• sự đẳng hình của đồ thị
• định nghĩa đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• Đồ thị phẳng
• bài toán luồng trên mạng
• tài liệu lý thuyết đồ thị
• đồ thị có hướng
• đồ thị hữu hạn
• đồ thị vô hạn
• Tìm kiếm trên đồ thị
• Đồ thị Hamilton
• Thuật toán đồ thị
• Ứng dụng tìm kiếm trên đồ thị
• Bài toán cây khung nhỏ nhất
• Thuật toán duyệt đồ thị