¶ Ứng dụng của luồng trên mạng
Tác giả:
- Võ Đức Đoàn - THPT Chuyên Nguyễn Tất Thành, Quãng Ngãi.
Reviewer:
- Nguyễn Tiến Mạnh - Đại học Bách khoa Hà Nội.
- Phạm Vũ Phương - Trường THPT Chuyên Hà Tĩnh, Hà Tĩnh.
- Nguyễn Hoàng Dương - Trường Đại học Công nghệ, ĐHQGHN.
- Nguyễn Tấn Minh - Trường Đại học Khoa học Tự nhiên, ĐHQG-HCM.
¶ Giới thiệu
Bài viết này nói về một số ứng dụng tiêu biểu và mở rộng của bài toán luồng trên mạng. Để nắm rõ nội dung trong bài viết, ta tham khảo nội dung có trong bài Bài toán Luồng cực đại trên mạng.
¶ Nhiều đỉnh nguồn, đỉnh thu
Giả sử ta được cho một mạng với vô số đỉnh nguồn () và đỉnh thu () và ta được yêu cầu phải tìm luồng cực đại trên mạng này. Ta có thể thay đổi bài toán trên thành bài toán tìm luồng cực đại trên mạng thông thường bằng cách thêm hai đỉnh có tên gọi là đỉnh siêu nguồn (supersource) và đỉnh siêu thu (supersink) . Sau đó, ta thêm các cung nối với và với với sức chứa . Bằng việc cho luồng đi qua từ đỉnh đến đỉnh , về cơ bản ta đã tìm được luồng cực đại trên mạng gốc.
¶ Tìm các đường đi phân biệt cạnh
Ta có một đồ thị có hướng, và nhiệm vụ của ta là tìm đường đi từ đỉnh đến đỉnh sao cho các đường đi phân biệt cạnh (các cung trên đồ thị xuất hiện nhiều nhất một lần trong tất cả các đường đi). Ở ví dụ dưới đây, ta tìm được hai đường đi phân biệt cạnh được tô hai màu lục và đỏ trên đồ thị sau:
Để giải quyết bài toán, ta xây dựng mạng đơn vị từ đồ thị có hướng trên (mạng đơn vị là mạng với các cạnh có sức chứa ). Nếu ta có thể cho luồng đi qua mạng này thì tức là ta đã tìm được đường đi phân biệt cạnh.
Nếu ta được yêu cầu in ra các đường đi thì sau khi cho luồng (mỗi cạnh hoặc là không có luồng đi qua, hoặc là có đúng đơn vị luồng đi qua mạng), ta có thể sử dụng các cạnh có để tìm các đường đi phân biệt cạnh:
- Bắt đầu từ đỉnh nguồn, xét đỉnh hiện tại, chọn cạnh có và di chuyển đến đỉnh .
- Nếu đỉnh hiện tại không phải đỉnh thu, lặp lại bước trên.
Từ giá trị luồng cực đại của mạng đơn vị được xây dựng từ đồ thị gốc, ta có thể biết được số lượng tối đa đường đi phân biệt cạnh trên đồ thị sẽ bằng bao nhiêu từ định lí sau:
Tồn tại tối đa đường đi phân biệt cạnh khi và chỉ khi giá trị luồng cực đại bằng .
Giả sử ta có luồng cực đại . Khi , ta có một danh sách các cạnh với . Từ danh sách cạnh này, ta có thể tìm được đường đi phân biệt luồng với phương pháp tìm các đường đi phân biệt luồng đã được nói ở trên.
¶ Vận dụng
- Hai đường đi (kết hợp với luồng với chi phí cực tiểu)
¶ Mở rộng
¶ Sức chứa đỉnh
Một số mạng không những có sức chứa cạnh mà nó còn có cả sức chứa đỉnh.
Để giải quyết trường hợp này, ta có thể biến đổi mạng này thành một mạng thông thường bằng cách tạo hai đỉnh mới , với mỗi đỉnh trong mạng. Ta nối hai đỉnh này bằng một cung có sức chứa bằng với sức chứa đỉnh.
Các cạnh trong mạng từ đây cũng được nối lại thành các cạnh .
¶ Tìm các đường đi phân biệt đỉnh
Để tìm các đường đi từ đỉnh đến đỉnh trên đồ thị có hướng sao cho mỗi đỉnh xuất hiện nhiều nhất một lần trên tất cả các đường đi, ta sẽ xây dựng một mạng từ đồ thị có hướng. Ta tạo một mạng từ đồ thị và cho sức chứa của các cạnh với các đỉnh bằng , sau đó ta giải bài toán theo cách tương tự với bài toán tìm các đường đi phân biệt cạnh.
¶ Cặp ghép trên đồ thị hai phía
Các bài toán cặp ghép (matching) trong lí thuyết đồ thị yêu cầu ta tìm một danh sách cạnh sao cho các đỉnh đầu mút của các cạnh không giống nhau.
Ta sẽ tập trung giải quyết một biến thể của bài toán này: tìm cặp ghép trên đồ thị hai phía.
Để tìm cặp ghép cực đại trên đồ thị hai phía (Max Cardinality Bipartite Matching - MCBM), ta xây dụng một mạng đơn vị như sau:
- Nối đỉnh nguồn với các đỉnh bằng một cung.
- Nối các đỉnh với các đỉnh nếu là một cạnh trong đồ thị gốc.
- Nối các đỉnh với đỉnh thu bằng một cung.
Khi này, giá trị luồng cực đại của đồ thị bằng giá trị cặp ghép cực đại, với các cạnh thoả mãn là các cạnh trong cặp ghép.
Vì sức chứa của các cạnh bằng , ta có thể sử dụng các thuật toán luồng cực đại đơn giản hơn như Ford-Fulkerson để tìm luồng cực đại.
¶ Vận dụng
- COCI 2020/2021 - Contest 3 - Selotejp
- VOI 16 Bài 5 - Tạo đề thi
- Phân công hoàn thành sớm nhất
- AtCoder Beginner Contest 445 - Knight Placement
¶ Bài toán phân việc
Bài toán cặp ghép cực đại trên đồ thị hai phía là một phần nhỏ của bài toán phân việc (assignment problem).
Một bài toán phân việc không trọng số trên đồ thị hai phía sẽ bao gồm hai tập hợp và . Nhiệm vụ của ta là tìm số lượng cặp nhiều nhất có thể với với các điều kiện sau:
- Các phần tử có thể xuất hiện trong tối đa cặp.
- Các phần tử có thể xuất hiện trong tối đa cặp.
- Các cặp có thể xuất hiện tối đa lần.
Bài toán cặp ghép cực đại trên đồ thị hai phía là một dạng đặc biệt của bài toán phân việc với và bằng hoặc tuỳ vào việc cạnh có tồn tại trong đồ thị hay không.
Ta có thể hình dung với bài toán ví dụ sau: có học sinh đi đến một thư viện, mỗi học sinh có nhu cầu mượn cuốn sách. Trong thư viện có đầu sách khác nhau, mỗi đầu sách thì lại có cuốn sách. Theo quy định của thư viện, mỗi học sinh chỉ được mượn tối đa cuốn sách với mỗi đầu sách. Bạn, với tư cách là một thủ thư, sẽ cho các bạn học sinh mượn sách từ thư viện sao số số cuốn sách được cho mượn là nhiều nhất có thể.
Để giải bài toán này, ta xây dụng một mạng gần giống với bài toán cặp ghép cực đại, với những thay đổi về sức chứa của các cung như sau:
- Tạo các cung với sức chứa với mỗi đỉnh .
- Tạo các cung với sức chứa với mỗi đỉnh .
- Tạo các cung với sức chứa với mỗi cặp .
Sau khi tìm được luồng cực đại của đồ thị, vì các giá trị luồng đi qua các cạnh là một số nguyên, ta có thể biết được các thông tin như sau:
- Các phần tử xuất hiện trong cặp.
- Các phần tử xuất hiện trong cặp.
- Tồn tại cặp .
¶ Vận dụng
¶ Vòng loại bóng chày
Bài toán vòng loại bóng chày (baseball elimination) được phát biểu như sau: có một giải đấu bóng chày bao gồm đội, mỗi đội có trận thắng, trận thua, trận còn lại cần phải chơi, và trận với các đội . Nhiệm vụ của ta là xét xem những đội nào không còn khả năng vô địch, tức là dù kết quả ra sao thì đội đó cũng không đứng nhất bảng. Ta giả sử không có trận hoà và tất cả trận đấu đều được diễn ra.
Dễ nhất, ta có thể xác định đội không có khả năng vô địch giải đấu nếu tồn tại một đội sao cho . Ta không cần luồng để giải quyết trường hợp này.
Đối với các trường hợp còn lại, ta sử dụng luồng trên mạng để kiểm tra. Ta xây dựng mạng như sau:
- Nối đỉnh nguồn với các đỉnh tượng trưng cho trận đấu giữa hai đội bằng một cung có sức chứa . Không tính các trận đấu có sự tham gia của đội . Ta quy ước các đỉnh thuộc tập .
- Nối các đỉnh với hai đỉnh và bằng một cung có sức chứa . Ta quy ước các đỉnh thuộc tập .
- Nối các đỉnh với đỉnh thu bằng một cung có sức chứa .
Đội không có khả năng vô địch nếu tập trong lát cắt cực tiểu (sau khi thực hiện lát cắt cực tiểu , tập hợp đỉnh được chia làm phần: tập là một tập con chứa đỉnh nguồn , tập là tập chứa các đỉnh còn lại) tồn tại một tập con sao cho và điều kiện dưới đây thoả mãn:
Đơn giản hơn, ta có thể xác định đội có khả năng vô địch giải đấu nếu giá trị luồng cực đại bằng tổng sức chứa các cung và không thể nếu ngược lại.
Nếu bài toán có điều kiện rằng nhiều đội đồng hạng nhất thì không có nhà vô địch thì ta sửa lại sức chứa các cung bằng .
¶ Vận dụng
¶ Chọn dự án
Bài toán chọn dự án được phát biểu như sau: hiện tại có một công ty đang thực hiện dự án , mỗi dự án sẽ đem về số tiền . Các dự án có thể sinh lời ( - các khoá học, khu vui chơi, mở cửa hàng, v.v.) hoặc thu lỗ ( - xây dựng cơ sở hạ tầng, cập nhật trang thiết bị, v.v.). Các dự án có thể phụ thuộc lẫn nhau, được biểu thị bằng các cặp trong , ví dụ: nếu , thì nếu thực hiện dự án thì trước tiên ta cần phải thực hiện dự án . Nhiệm vụ của ta là chọn các dự án sao cho thoả mãn điều kiện, đồng thời số tiền thu được từ các dự án phải lớn nhất có thể.
Các dự án sinh lời là các ô tròn, các dự án thu lỗ là các ô vuông, các mũi tên chỉ sự phụ thuộc của các dự án
Ta sẽ xây dựng mạng để giải quyết bài toán trên:
- Nối đỉnh nguồn với các dự án sinh lời bằng một cung với sức chứa .
- Nối các dự án thu lỗ với đỉnh thu bằng một cung với sức chứa .
- Nối các cặp dự án phụ thuộc lẫn nhau bằng một cung với sức chứa .
Ta quy ước .
Số tiền ta thu được, đồng thời cũng là lợi nhuận tối đa, bằng:
- với và là giá trị của lát cắt cực tiểu.
- với là tập hợp các đỉnh trong lát cắt cực tiểu .
Các dự án sinh lời là các ô tròn, các dự án thu lỗ là các ô vuông, các mũi tên chỉ sự phụ thuộc của các dự án
Ta có , , suy ra lợi nhuận tối đa sẽ bằng .
Ta có thể chứng minh lí do vì sao hai công thức và lại cùng trả về đáp án đúng.
Chứng minh
Vì mạng tồn tại các cạnh có sức chứa , nên lát cắt cực tiểu sẽ chỉ bao gồm các cung và . Khi này, sẽ bằng:
Từ đây, với , ta suy ra:
¶ Vận dụng
¶ Lưu thông theo cung cầu
Bài toán lưu thông theo cung cầu (circulation with demands) là một bài toán về một mạng nhiều đỉnh nguồn và đỉnh thu. Mỗi đỉnh nguồn , hay đỉnh "cung" theo cách gọi của bài toán, sẽ có giá trị , tức là đỉnh nguồn này có khả năng gửi đi đơn vị luồng. Các đỉnh thu , hay đỉnh "cầu", sẽ có giá trị , tức là các đỉnh thu này có khả năng nhận đơn vị luồng. Các đỉnh còn lại trong đồ thị sẽ có giá trị .
Khi thực hiện lưu thông trên mạng, ta cần thoả mãn hai điều kiện:
- Với mỗi cạnh ,
- Với mỗi đỉnh ,
Dễ thấy, điều kiện để có lưu thông trên mạng là:
Từ đây, ta xây dựng một mạng mới với các thay đổi:
- Thêm đỉnh siêu nguồn và đỉnh siêu thu
- Nối đỉnh với từng đỉnh nguồn bằng cung có sức chứa .
- Nối các đỉnh thu với đỉnh bằng cung có sức chứa .
Ta xác định mạng có thể thực hiện lưu thông nếu giá trị luồng cực đại của bằng .
¶ Trường hợp có cận dưới
Một số bài toán lưu thông theo cung cầu sẽ cho ta thêm điều kiện cận dưới cho các cung trên đồ thị. Cụ thể hơn, gọi giá trị là cận dưới của cạnh . Khi này, lượng luồng đi qua cạnh phải thoả mãn:
Ý tưởng của bài toán này khá đơn giản: ta sẽ cho đỉnh cung cấp một lượng luồng đi qua cạnh . Sau khi đã cho đơn vị luồng đi qua, ta cập nhật lại các giá trị liên quan: thành , thành , thành .
Sau khi đã cập nhật xong, ta thực hiện việc giải quyết bài toán này như bình thường.
Giả sử ta có là lượng luồng đi qua cạnh sau khi cập nhật các giá trị. Từ đây, lượng luồng đi qua cạnh ban đầu sẽ bằng: