Cây_Steiner_Bài toán Steiner hay bài_toán tìm đường đi ngắn nhất từ 2 điểm cho trước được phát_triển trên bài_toán Fermat của nhà toán_học nổi_tiếng người Pháp Vào thế_kỷ thứ 19 Steiner đã tổng_quát bài_toán của Fermat bằng cách không hạn_chế số điểm cần tìm Thực_ra ngay từ thời Gauß người ta đã biết tới những loại bài_toán kiểu như thế_này Trong cuốn sách What is Mathematics của Robbins và Courant xuất_bản năm 1941 bài_toán của Gauß được công_bố dưới tên của Steiner_Bài toán Steiner_Thuật toán BULLET Cho đồ_thị G V E có trọng_số V tập các đỉnh E tập các cạnh của đồ_thị và tập W V Tìm cây T W F trong G nhỏ nhất bao_trùm tất_cả các đỉnh của W Cây_T gọi là Cây_Steiner của W và W W gọi là các điểm Steiner của W ứng với cây T BULLET Cây_Steiner là mạng tối_ưu trong bài_toán Steirner_Mạng này phải liên_thông và không có chu_trình do điều_kiện tối_ưu của nó nếu có chu_trình ta có bỏ bớt một cạnh trên chu_trình mà không ảnh_hưởng tới sự liên_thông của đồ_thị Tư_tưởng của thuật_toán Xét đồ_thị G sau BULLET Cho tập W 3 4 5 6 Đồ_thị R sinh bởi W có tập đỉnh 3 4 5 6 và tập cạnh là 3 4 3 5 4 5 4 6 5 6 Dễ_dàng thấy được cây khung nhỏ nhất của R có các cạnh 3 4 4 6 6 5 với tổng trọng_số là 13 Tuy_nhiên với tập đỉnh 3 4 5 6 1 có cây khung là 3 4 4 1 1 6 6 5 chỉ có tồng trọng_số là 12 13 Ở đây 1 được gọi là điểm Steiner_BULLET_Bây giờ ta sẽ xây_dựng phương_pháp giải bài_toán Steiner bằng cách sử_dụng thuật_toán Floyd_Warshall tìm khoảng_cách và đường đi ngắn nhất và thuật_toán Kruskal để tìm cây khung nhỏ nhất Các bước thực_hiện BULLET Đầu vào Trọng đồ_thị liên_thông G V E w gồm n đỉnh và tập W V m đỉnh m n BULLET Đầu_ra Cây_Steiner của W trong G BULLET Các bước BULLET Bước 1 Xây_dựng đồ đơn đủ có trọng_số G V F w bằng thuật_toán Floyd_Warshall trong đó w u v là khoảng_cách ngắn nhất từ u đến v với mọi cặp u v BULLET Bước 2 Với mỗi S V W card S m 2 tìm cây khung nhỏ nhất của đồ_thị W S sinh bởi W S trong G Trong các cây khung đó tìm cây T có trọng_số nhỏ nhất dùng thuật_toán Kruskal hoặc Prim_BULLET_Bước 3 Xây_dựng cây Steiner_T từ T bằng cách thay mỗi cạnh nối hai đỉnh trong G bằng đường đi nối chúng với nhau trong G Các đỉnh thuộc T mà không thuộc W là những đỉnh Steiner_Mã giã codice _ 1 Ví_dụ Cho đồ_thị G 7 đỉnh sau Câu hỏi Tìm cây Steiner của W 3 6 7 của đồ_thị G BULLET Ta có ma_trận trọng_số như sau BULLET Với dòng màu vàng là tập_hợp các đỉnh BULLET Ta có V 1 2 3 4 5 6 7 và W 3 6 7 vậy tập S ta có là 1 2 4 5 BULLET Các tập S W sẽ lần_lượt là W1 3 6 7 W2 3 6 7 1 W3 3 6 7 2 W4 3 6 7 4 W5 3 6 7 5 BULLET Từ các tập sinh_từ phép hội ta tính được trọng_số nhỏ nhất thông_qua thuật_toán tìm cây khung nhỏ nhất lần_lượt là BULLET W1 11 BULLET W2 8 BULLET W3 11 BULLET W4 9 BULLET W5 13 BULLET Ta chọn đồ_thị sinh bởi W2 cây có độ phủ nhỏ nhất Tại_sao đồ_thị W2 có cạnh nối giữa đỉnh 1 và 3 Trả_lời Do không có cạnh nối giữa 1 và 3 nên BULLET Cạnh 3 1 trong cây T sẽ được thay bằng đường đi ngắn nhất 3 4 1 BULLET Cuối_cùng ta được cây Steiner như sau BULLET Các điểm Steiner 1 và 4 Ứng_dụng của thuật_toán Trong thực_tế hiện_nay có rất nhiều ứng_dụng cần dùng đến bài_toán Steiner để giải_quyết Cụ_thể các ứng_dụng của cây Steiner là BULLET Bố_trí mạch điện trong bo_mạch điện_tử BULLET Nối hệ_thống mạng với chi_phí nhỏ nhất BULLET Và các ứng_dụng liên_quan đến tìm khoảng_cách nhỏ nhất trong mặt_phẳng như hệ_thống giao_thông hệ_thống cấp_nước hệ_thống cung_cấp điện cáp mạng Tài_liệu BULLET Trần_Quốc_Chiến_Giáo trình lý_thuyết đồ_thị Đại_học Sư_phạm Đà_Nẵng BULLET V K Balakrishnan_Theory and Problems of Graph_Theory_McGRAW_HILL 1997 bản điện_tử BULLET Nguyễn_Xuân_Quỳnh_Cơ_sở Toán rời_rạc và ứng_dụng Nhà_xuất_bản Giáo_dục Hà_Nội 1995 BULLET Derek_R_Dreyer_Michael L Overton_Two_Heuristics for the Euclidean_Steiner_Tree_Problem ngày 30 tháng 9 năm 2002 BULLET M R Garey_R_L_Graham D S Johnson_The complexity of computing Steiner minimal trees SIAM Journal on Applied_Mathematics 32 4 835 859 June 1977
Cây_Steiner