Cây Steiner

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Bài toán Steiner[1] là 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 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 RobbinsCourant 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[sửa | sửa mã nguồ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[sửa | sửa mã nguồn]

Xét đồ thị G sau:

Đồ thị G

Các bước thực hiện[sửa | sửa mã nguồn]

  • Đầ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.
  • Đầu ra: Cây Steiner của W trong G.
  • Các bước:
    • 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).
    • 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).
    • 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ã[sửa | sửa mã nguồn]

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).
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. 
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. 
Bước 4: Xây dựng cây Steiner cho cây phủ T’ tìm được ở bước 3.
Bước 5: Kết xuất giá trị sang file lưu trữ. 
Bước 6: Kết thúc.

Ví dụ[sửa | sửa mã nguồn]

Cho đồ thị G (7 đỉnh) sau:

Đồ thị G

Câu hỏi: Tìm cây Steiner của W = {3,6,7} của đồ thị G.

Đồ thị G
  • 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}
    • 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}
  • Ta chọn đồ thị sinh bởi W2 cây có độ phủ nhỏ nhất:
Đồ thị G

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:

  • Cạnh (3,1) trong cây T’ sẽ được thay bằng đường đi ngắn nhất 3-4-1
  • Cuối cùng ta được cây Steiner như sau:
Đồ thị G
  • Các điểm Steiner: 1 và 4

Ứng dụng của thuật toán[sửa | sửa mã nguồ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à:

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Takahashi, Hiromitsu, and Akira Matsuyama. "An approximate solution for the Steiner problem in graphs." Math. Japonica 24.6 (1980): 573-577.
  2. ^ Courant, Richard, and Herbert Robbins. What is Mathematics?: an elementary approach to ideas and methods. Oxford University Press, USA, 1996. http://www.amazon.com/Mathematics-Elementary-Approach-Ideas-Methods/dp/0195105192/ref=sr_1_1?ie=UTF8&qid=1368012398&sr=8-1&keywords=What+is+Mathematics
  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[sửa | sửa mã nguồn]

  • 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. NXB Giáo dục. Hà Nội 1995]]
  • Derek R. Dreyer, Michael L. Overton, Two Heuristics for the Euclidean Steiner Tree Problem, September 30, 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.