TAILIEUCHUNG - CTDLGT_Chuong_7_Phan_2_Spanning_tree_Shortest_path

Chương 7Đồ 2 – Các bài toán đồ thị.(Buổi 13).Giới này trình bày các bài toán của đồ thị:.Tìm đường đi ngắn nhất: tìm đường đi từ này đến một đỉnh khác của đồ thị mà có số của đường đi là nhỏ nhấtCây phủ tối thiểu: tìm đồ thị con (không có ) kết nối tất cả các đỉnh của đồ thị và có số của các cạnh là nhỏ nhấtSắp thứ tự bộ phận (topological sorting).Trường Đại học Bách Khoa Khoa học và Kỹ thuật Máy tính.© 2011Nguyễn Trung TrựcCấu trúc dữ liệu và Giải 7: Đồ phủ tối đồ thị đơn G = (V, E) liên thông, vô có trọng số, trong đó V là tập đỉnh và E cạnh của đồ thịCây (tree) là một đồ thị G liên thông, vô không có chu trìnhCây phủ (spanning tree) của G, hoặc , là một cây trong G mà cây này chứa các đỉnh của GCây phủ tối thiểu (minimum spanning tree).trong G là cây phủ có tổng các trọng số cạnh của nó là nhỏ nhấtTrường Đại học Bách Khoa Khoa học và Kỹ thuật Máy tính.© 2011Nguyễn Trung TrựcCấu trúc dữ liệu và Giải 7: Đồ phủ tối xét:.Đồ thị G có thể có nhiều cây phủ tối thiểuCây phủ tối thiểu T có đúng n-1 cạnh với n là của toán: Cho đồ thị G = (V, E) liên thông, có trọng số. Tìm một cây phủ tối thiểu Đại học Bách Khoa Khoa học và Kỹ thuật Máy tính.© 2011Nguyễn Trung TrựcCấu trúc dữ liệu và Giải 7: Đồ phủ tối tự các vào cây thiểu.(1, 5).(2, 3).(10, 11).(5, 9).(0, 1).(2, 6).(6, 7).(0, 4).(9, 10).(1, 2).(8, 9)Hình . Cây phủ tối thiểu (minimum spanning tree).Trường Đại học Bách Khoa Khoa học và Kỹ thuật Máy tính.© 2011Nguyễn Trung TrựcCấu trúc dữ liệu và Giải 7: Đồ . | Chương 7 Đồ thị Phần 2 – Các bài toán đồ thị (Buổi 13) Giới thiệu Phần này trình bày các bài toán của đồ thị: Tìm đường đi ngắn nhất: tìm đường đi từ một đỉnh này đến một đỉnh khác của đồ thị mà có tổng trọng số của đường đi là nhỏ nhất. Cây phủ tối thiểu: tìm đồ thị con (không có chu trình) kết nối tất cả các đỉnh của đồ thị và có tổng trọng số của các cạnh là nhỏ nhất. Sắp thứ tự bộ phận (topological sorting). Trường Đại học Bách Khoa Khoa Khoa học và Kỹ thuật Máy tính © 2011 Nguyễn Trung Trực Cấu trúc dữ liệu và Giải thuật Chương 7: Đồ thị 2 Cây phủ tối thiểu Cho đồ thị đơn G = (V, E) liên thông, vô hướng và có trọng số, trong đó V là tập đỉnh và E là tập cạnh của đồ thị. Cây (tree) là một đồ thị G liên thông, vô hướng và không có chu trình. Cây phủ (spanning tree) của G, hoặc cây khung, là một cây trong G mà cây này chứa tất cả các đỉnh của G. Cây phủ tối thiểu (minimum spanning tree) trong G là cây phủ có tổng các trọng số của các cạnh của nó là nhỏ nhất. Trường Đại học Bách Khoa Khoa Khoa học và Kỹ thuật Máy tính © 2011 Nguyễn Trung Trực Cấu trúc dữ liệu và Giải thuật Chương 7: Đồ thị 3 Cây phủ tối thiểu Nhận xét: Đồ thị G có thể có nhiều cây phủ tối thiểu. Cây phủ tối thiểu T có đúng n-1 cạnh với n là số đỉnh của G. Bài toán: Cho đồ thị G = (V, E) liên thông, vô hướng có trọng số. Tìm một cây phủ tối thiểu T trong G. Trường Đại học Bách Khoa Khoa Khoa học và Kỹ thuật Máy tính © 2011 Nguyễn Trung Trực Cấu trúc dữ liệu và Giải thuật Chương 7: Đồ thị 4 Cây phủ tối thiểu 0 2 3 4 4 5 9 3 5 2 3 2 3 1 2 1 4 8 1 3 6 3 7 4 3 10 3 1 11 Thứ tự các cạnh đưa vào cây phủ tối thiểu (1, 5) (2, 3) (10, 11) (5, 9) (0, 1) (2, 6) (6, 7) (0, 4) (9, 10) (1, 2) (8, 9) Hình . Cây phủ tối thiểu (minimum spanning tree) Trường Đại học Bách Khoa Khoa Khoa học và Kỹ thuật Máy tính © 2011 Nguyễn Trung Trực Cấu trúc dữ liệu và Giải thuật Chương 7: Đồ .

• Sáng kiến kinh nghiệm