tailieunhanh - GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - CHƯƠNG 2

BIỂU DIỄN ĐỒ THỊ TRÊN MÁY VI TÍNH Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần phải tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị. Việc chọn cấu trúc dữ liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả của thuật toán. | CHƯƠNG 2 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY VI TÍNH Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần phải tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị. Việc chọn cấu trúc dữ liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả của thuật toán. Vì vậy việc chọn lựa cấu trúc dữ liệu để biểu diễn đồ thị phụ thuộc vào từng tình huống cụ thể bài toán và thuật toán cụ thể . Trong mục này chúng ta sẽ xét một số phương pháp cơ bản được sử dụng để biểu diễn đồ thị trên máy tính đồng thời cũng phân tích một cách ngắn gọn những ưu điểm cũng như những nhược điểm của chúng. 1. MA TRẬN KỀ. MA TRẬN TRỌNG SỐ Xét đơn đồ thị vô hướng G V E với tập đỉnh V 1 2 . . . n tập cạnh E ei e2 . . . em . Ta gọi ma trận kề của đồ thị G là ma trận. A ai j i j 1 2 . . . n Với các phần tử được xác định theo qui tắc sau đây ai j 0 nếu i j I E và ai j 1 nếu i j ĩ E i j 1 2 . . . n. JThí dụ 1. Ma trận trận kề của đồ thị vô hướng cho trong hình 1 là 1 2 3 4 5 6 1 0 110 10 2 10 10 10 3 110 10 0 4 0 0 10 11 5 110 10 1 6 0 0 0 1 1 0 Hình 1. Đồ thị vô hướng G và Đồ thị có hướng G1 --Các tính chất của ma trận kề 1 Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng tức là a i j a j i i j 1 2 . . . n. ngược lại mỗi 0 1 -ma trận đối xứng cấp n sẽ tương ứng chính xác đến cách đánh số đỉnh còn nói là chính xác đến đẳng cấu với một đơn đồ thị vô hướng n đỉnh. 2 Tổng các phần từ trên dòng i cột j của ma trận kề chính bằng bậc của đỉnh i đỉnh j . 3 nếu ký hiệu aịjp i j 1 2 . . . n là phần tử của ma trận Ap . . .A p thừa số Khi đó aịjp i j 1 2 . . . n cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j qua p-1 đỉnh trung gian. Ma trận kề của đồ thị có hướng được định nghĩa một cách hoàn toàn tương tự. JThí dụ 2. Đồ thị có hướng G1 cho trong hình 1 có ma trận kề là ma trận sau 1 2 3 4 5 6 1 0 110 0 0 2 0 0 0 0 0 0 3 0 10 10