Bài toán cây Steiner

Bài toán cây Steiner^[1] 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 dựa 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^[2] 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

• 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.
• 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:

Đồ thị G

• 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.
• 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.

Mã giả

1. Bước 1: Đọc file dữ liệu đầu vào của đồ thị G đã cho (file có cấu trúc) Đối với file dữ liệu đầu vào aij = 0 khi không có đường đi từ i->j, thủ tục đọc file sẽ chuyển các giá trị 0 này thành 99999 (vô cực dương).
2. Bước 2: Gọi thủ tục tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị bằng thuật toán Floyd-Warshall.
3. Bước 3: Gọi thủ tục tìm cây khung nhỏ nhất cho từng đồ thị con của G’ tìm được ở bước 2, G’=(V,E,w’) (đồ thị con <W∪S> sinh bởi W∪S trong G’ với S ⊂ V-W, card(S) ≤ m-2). Trong các cây phủ đó tìm cây T’ có tổng trọng số nhỏ nhất.
4. Bước 4: Xây dựng cây Steiner cho cây phủ T’ tìm được ở bước 3.
5. Bước 5: Kết xuất giá trị sang file lưu trữ.
6. Bước 6: Kết thúc.

Ứ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à:

• Bố trí mạch điện trong bo mạch điện tử.^[3]
• Nối hệ thống mạng với chi phí nhỏ nhất.^[4]
• Và các ứng dụng liên quan đến tìm khoảng cách nhỏ nhất^[5] 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…

Tham khảo

1. Takahashi, Hiromitsu, and Akira Matsuyama. "An approximate solution for the Steiner problem in graphs." Math. Japonica 24.6 (1980): 573-577.
2. "What Is Mathematics? An Elementary Approach to Ideas and Methods: Richard Courant, Herbert Robbins, Ian Stewart: 9780195105193: Amazon.com: Books". Truy cập ngày 12 tháng 2 năm 2015.
3. Garey, Michael R., and David S. Johnson. "The rectilinear Steiner tree problem is NP-complete." SIAM Journal on Applied Mathematics 32.4 (1977): 826-834.
4. Steiner, Jennifer G., Clifford Neuman, and Jeffrey I. Schiller. "Kerberos: An authentication service for open network systems." USENIX conference proceedings. Vol. 191. 1988.
5. KHOKHANI, K. H.; PATEL, A. M. The chip layout problem: A placement procedure for lsi. In: Proceedings of the 14th Design Automation Conference. IEEE Press, 1977. p. 291-297.

Tài liệu

• Trần Quốc Chiến, Giáo trình lý thuyết đồ thị, Đại học Sư phạm Đà Nẵng.
• V.K. Balakrishnan, Theory and Problems of Graph Theory. McGRAW-HILL 1997 (bản điện tử)
• 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]]
• Derek R. Dreyer, Michael L. Overton, Two Heuristics for the Euclidean Steiner Tree Problem, ngày 30 tháng 9 năm 2002.
• 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.