Phân tích và thiết kế giải thuật : Độ phức tạp của các giải thuật đồ thị - Chương 4

Bài Giảng điện tử Phân tích và thiết kế giải thuật. Tiến sĩ Dương Tuấn Anh. Chương 4: Phân tích độ phức tạp của các giải thuật đồ thị. Có nhiều bài toán được định nghĩa theo đối tượng và kết nối giữa các đối tượng ấy.
Nội dung trích xuất từ tài liệu:
Phân tích và thiết kế giải thuật : Độ phức tạp của các giải thuật đồ thị - Chương 4Ch ng 4 ph c t p c a các gi i thu t th 1N i dung1. Các gi i thu t th c n b n2. th có tr ng s3. th có h ng 21.Các gi i thu t th c n b nCó nhi u bài toán c nh ngh a theo it ng và cáck t n i gi a các i t ng y.M t th là m t i t ng toán h c mà mô t nh ng bàitoán nh v y.Các ng d ng trong các lãnh v c: Giao thông Vi n thông i nl c M ng máy tính C s d li u Trình biên d ch Các h i u hành Lý thuy t th 3M t thí d A H I B C G D E J K F L M Hình 4.1a M t th thí d 4Thu t ngM t th là m t t p các nh và các c nh. Các nh lành ng i t ng n mà có th có tên và có m t s tínhch t khác và c nh là ng k t n i gi a hai nh.M t l i i t x n y trong m t th là m t danh sáchnh ng nh mà nh ng nh k ti p nhau c k t n i nhvào nh ng c nh trên th .M t th là liên thông n u có m t l i i t m i nút nm t nút khác trong th . M t th mà không liên thôngthì bao g m nhi u thành ph n liên thông.M tl i i n là m t l i i mà trên ó không có nh nàol p l i. 5Thu t ng (tt.)M t chu trình (cycle ) là m t l i i n ngo i tr nh utiên và nh cu i cùng trùng nhau (m t l i i t m t nhquay v chính nó).M t th không có chu trình c g i là cây (tree). M tnhóm các cây không liên thông c g i là r ng ( forest ).Cây bao trùm c a m t th là m t th con mà ch a t t ccác nh trong cây nh ng m t s c nh ch m n m i nh.G is nh trong m t th là V, s c nh là E, s c nh c a th có th có t 0 n V (V-1)/2. (Ch ng minh truy ch ng). th có t t c m i c nh hi n di n gi a m i c p nh cg i là th y (complete graphs). 6Thu t ng (tt.)Các th v i s c nh t ng i ít c g i là th th a;các th v i ch m t s ít c nh m t i c g i là th dày.Các th mô t cho n gi là nh ng th vô h ng(undirected graphs). Trong các th có tr ng s (weightedgraphs), nh ng giá tr s (tr ng s ) c g n vào m i c nhdi n t thí d kho ng cách hay chi phí.Trong th có h ng (directed graphs) các c nh là “m tchi u”: m t c nh i t x sang y ch không ph i i t y sang x.Các th có h ng, có tr ng s còn c g i là các m ng(networks). 7Cách bi u di n thTa ph i ánh x các tên nh thành nh ng s nguyên trongt m tr gi a 1 và V.Gi s có t n t i hai hàm: - hàm index: chuy n i t tên nh thành s nguyên - hàm name: chuy n i s nguyên thành tên nh.Có hai cách bi u di n th : - dùng ma tr n k c n - dùng t p danh sách k c n 8Cách bi u di n ma tr n k c n A B C D E F G H I J K L M M t ma tr n VA 1 1 1 0 0 1 1 0 0 0 0 0 0B 1 1 0 0 0 0 0 0 0 0 0 0 0 hàng V c t ch aC 1 0 1 0 0 0 0 0 0 0 0 0 0 các giá tr BooleanD 0 0 0 1 1 1 0 0 0 0 0 0 0 mà a[x, y] là true ifE 0 0 0 1 1 1 1 0 0 0 0 0 0 n ut nt im tF 1 0 0 1 1 1 0 0 0 0 0 0 0 c nh t nh x nG 1 0 0 0 1 0 1 0 0 0 0 0 0H 0 0 0 0 0 0 0 1 1 0 0 0 0 nh y và false n uI 0 0 0 0 0 0 0 1 1 0 0 0 0 ng c l i.J 0 0 0 0 0 0 0 0 0 1 1 1 1K 0 0 0 0 0 0 0 0 0 1 1 0 0 Hình 4.1b: Ma tr n kL 0 0 0 0 0 0 0 0 0 1 0 1 1 c nc a th hìnhM 0 0 0 0 0 0 0 0 0 1 0 1 1 4.1a 9Ghi chú v cách bi u di n ma tr n k c nM i c nh t ng ng v i 2 bit trong ma tr n: m ic nh n i gi a x và y c bi u di n b ng giá tr truet i c a[x, y] và a[y, x]. ti n l i gi nh r ng có t n t i m t c nh n i m i nh v chính nó.L i bi u di n này ch thích h p khi các th là d y. 10Gi i thu tprogram adjmatrix (input, output);const maxV = 50;var j, x, y, V, E: integer; a: array[1..maxV, 1..maxV] of boolean;begin readln (V, E); for x: = 1 to V do /*initialize the matrix */ for y: = 1 to V do a[x, y]: = false; for x: = 1 to V do a[x, y]: = true; for j: = 1 to E do begin readln (v1, v2); x := index(v1); y := index(v2); ...