Memeriksa apakah kedudukan menang-kalah dari suatu liga dimungkinkan

Anda menjamu liga basket 1 v 1 dengan jadwal pertandingan. Di akhir liga, Anda meminta setiap pemain untuk melaporkan rekor menang-kalah (tidak ada ikatan), tetapi Anda ingin memeriksa apakah kedudukan yang diusulkan benar-benar dimungkinkan berdasarkan jadwal.

Misalnya: Anda memiliki empat pemain (Alice + Bob + Carol + Dave) dan jadwal Anda adalah round robin sederhana. Klasemen yang dilaporkan [ A: 3-0 B: 1-2 C: 1-2 D: 1-2] dan [ A: 2-1 B: 1-2 C: 1-2 D: 2-1] adalah mungkin, tetapi kedudukan [ A: 3-0 B: 0-3 C: 0-3 D: 3-0] tidak akan terjadi.

Sekarang anggaplah jadwalnya adalah pertandingan 3 head to head antara Alice + Bob dan Carol + Dave. Posisi yang dilaporkan [ A: 3-0 B: 0-3 C: 0-3 D: 3-0] sekarang dimungkinkan, tetapi [ A: 3-0 B: 1-2 C: 1-2 D: 1- 2] tidak akan lagi.

(Jadwal tidak perlu simetris dengan cara apa pun. Anda bisa membuat Alice hanya bermain melawan Bob 10 kali, lalu membuat Bob + Carol + Dave bermain 58 round robins satu sama lain.)

Soal : Mengingat jadwal dengan k peserta dan n jumlah game, efisien memeriksa apakah klasemen menang-kalah yang diusulkan benar-benar bisa terjadi dari jadwal itu.

Metode brute force O ( ) jelas, menyebutkan semua kemungkinan hasil pertandingan dan melihat apakah ada yang cocok dengan kedudukan yang diajukan. Dan jika k bertambah kecil dan tidak menambah kerumitan - sangat mudah untuk memeriksa kedudukan liga dua orang terlepas dari apakah mereka bermain sepuluh pertandingan atau sepuluh miliar pertandingan. Selain itu saya belum membuat banyak kemajuan dalam menemukan metode yang lebih baik, dan ingin tahu apakah ada yang melihat masalah yang sama sebelumnya.$2^n$

Ini dapat dimodelkan sebagai masalah Max-Flow.

Sebagai langkah preprocessing, pastikan bahwa jumlah game sama dengan jumlah dari jumlah kemenangan (jika tidak, Anda tahu ada sesuatu yang salah).

Biarkan menjadi satu set simpul yang terkait dengan permainan yang dimainkan, dan satu set simpul yang sesuai dengan para pemain. Misalkan dan menunjukkan dua simpul tambahan (sumber dan wastafel).$G$$P$$s$$t$

Sekarang untuk setiap permainan dimainkan antara dan , tambahkan tepi dari ke dengan kapasitas dan tepi dari ke dan ke juga dengan kapasitas . Ini memodelkan fakta bahwa permainan dapat memberikan satu poin untuk salah satu pemain.$g\in G$$p1\in P$$p2\in P$$s$$g$$1$$g$$p1$$g$$p2$$1$

Kemudian untuk setiap pemain tambahkan keunggulan dari ke dengan kapasitas sama dengan jumlah kemenangan yang dilaporkan untuk pemain . Ini memodelkan fakta bahwa pemain ini harus menang paling banyak dalam jumlah pertandingan ini.$p\in P$$p$$t$$p$

Sangat mudah untuk melihat dari sini bahwa jika skor yang dilaporkan adalah mungkin, akan ada aliran jenuh dari ke dan secara timbal balik. Jadi yang perlu Anda periksa adalah apakah maksimum -flow dalam grafik ini sama dengan jumlah game yang dimainkan.$s$$t$$s,t$

Sebagai alternatif, Anda juga bisa memiliki grafik dengan satu titik per permainan dan sejumlah simpul untuk setiap pemain yang sesuai dengan jumlah kemenangan, sambungkan dengan cara yang sama seperti sebelumnya, dan lihat apakah jumlah tepi dalam pencocokan maksimum sama dengan jumlah gim (tapi ini hampir sama saja kok).