PHÂN TÍCH MẠNG VÀ MỘT VÀI THUẬT TOÁN CƠ BẢN

1. Giới thiệu :
      Mạng là hệ thống các đối tượng đường được kết nối với nhau. Việc phân tích hệ thống này gọi là phân tích mạng.
       Phương pháp phân tích mạng giúp giải quyết các bài toán liên quan đến đối tượng đường trên bản đồ. Phương pháp này liên quan đến hai vấn đề : cấu trúc kết nối giữa các đường và sự di chuyển trong hệ thống các đường được kết nối đó.
      Đường trên bản đồ được phân làm hai loại : đường tự nhiên (physical lines) và đường ảo ( virtual lines). Những đường tự nhiên như là các loại đường giao thông và đường ảo như là các đường ranh giới chính trị, ranh giới hành chính. Đường tự nhiên là đối tượng phân tích chủ yếu của phương pháp phân tích mạng.  
2. Nội dung phương pháp phân tích mạng :
2.1 Yêu cầu về dữ liệu :
      Mỗi đường trong hệ thống mạng phải được xác định bằng điểm đầu và điểm cuối bằng điểm cuối có thể qua các điểm đỉnh (vertex).
            Một hệ số cản trở ( impedance factor) cũng được tính đến trong việc phân tích mạng. Chẳng hạn, yếu tố đường một chiều, đường đang sửa chữa có thể được tính như là hệ số cản trở trong việc tìm đường đi ngắn nhất trong hệ thống đường giao thông.

Hình 1 Mạng không tính đến hệ số cản trở


Hình 2 Mạng có hệ số cản trở
Xem toàn bộ tại đây
NNS