Đang chuẩn bị liên kết để tải về tài liệu:
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 . 3.1 Thuật toán tìm kiếm .