Mạng và luồng

Mạng và khả năng thông qua

Mạng (network) là đồ thị có hướng có đúng 1 đỉnh có bán bậc vào bằng 0, gọi là đỉnh nguồn (source), và đúng 1 đỉnh có bán bậc ra bằng 0, gọi là đỉnh đích (sink). Trên mỗi cung của mạng, định nghĩa là khả năng thông qua (capacity) của cung

• với mọi trong mạng. Quy ước nếu

Luồng

Luồng (flow) là một ánh xạ thỏa mãn các điều kiện dưới đây

• (1) Luồng không vượt quá khả năng thông qua, tức là
• (2) Điều kiện cân bằng đỉnh, với mỗi , trừ đỉnh nguồn và đỉnh đích, tổng luồng trên các cung đi vào bằng tổng luồng trên các cung đi ra khỏi Từ điều kiện (2), gọi là đỉnh nguồn và là đỉnh đích, ta có Giá trị được gọi là giá trị của luồng, kí hiệu

Bài toán tìm luồng cực đại

• Trong số các luồng trên mạng , ta cần tìm luồng có giá trị lớn nhất.

Lát cắt

Lát cắt là một phân hoạch của tập đỉnh V sao cho và Khả năng thông qua của lát cắt là tổng khả năng thông qua của các cung đi từ một đỉnh thuộc đến một đỉnh thuộc

• Lát cắt hẹp nhất là lát cắt có khả năng thông qua nhỏ nhất. Giá trị nhỏ nhất này cũng là giá trị của luồng cực đại. Nói cách khác, giá trị của mọi luồng trong mạng đều không vượt quá khả năng thông qua của lát cắt hẹp nhất

Thuật toán Fold-Fulkerson

Đồ thị dư và đường tăng luồng

• Xét mạng có khả năng thông qua trên cạnh là .
• Xét luồng trên .
• Xây dựng đồ thị :
  • Với mỗi cạnh , thêm cạnh vào có trọng số là và cạnh có trọng số
  • Loại bỏ các cạnh có trọng số bằng 0
• Đồ thị được gọi là đồ thị tăng luồng hoặc đồ thị dư (residual graph)
• Nhận xét: nếu không phải luồng cực đại, ta luôn tìm được đường đi từ đến trong . Đường này được gọi là đường tăng luồng

Mô tả thuật toán

• Bước 1: Xây dựng luồng có với mọi . Xây dựng tương ứng
• Bước 2: Tìm đường đi từ đến trong . Nếu không có, kết thúc thuật toán
• Bước 3: Đặt là trọng số nhỏ nhất của cung trong đường đi vừa tìm được ở Bước 2
• Bước 4: Cập nhật :
  • nếu
  • nếu
• Bước 5: Cập nhật và lặp lại bước 2

Thuật toán Edmonds-Karp

• Việc tìm đường tăng luồng ở Bước 2 quyết định đến độ hiệu quả của thuật toán
• Trong thuật toán Edmonds-Karp, ở bước 2, ta thực hiện duyệt theo chiều rộng