Jumlah mincuts grafik tanpa menggunakan algoritma Karger

Kita tahu bahwa algoritma mincut Krier dapat digunakan untuk membuktikan (dengan cara yang tidak konstruktif) bahwa jumlah maksimum dari mincuts yang mungkin dimiliki oleh sebuah grafik adalah .$n \choose 2$

Saya bertanya-tanya apakah kita bisa membuktikan identitas ini dengan memberikan bukti bijective (agak suntik) dari set mincuts ke set kardinalitas lain $n \choose 2$ . Tidak ada alasan khusus, hanya rasa ingin tahu. Saya mencoba melakukannya sendiri tetapi sejauh ini belum berhasil. Saya tidak ingin ada yang menyia-nyiakan waktu untuk hal ini dan jadi jika pertanyaannya tidak ada artinya saya akan meminta moderator untuk mengambil tindakan yang sesuai.

-Akash terbaik

The $\binom{n}{2}$ terikat Saya pikir awalnya dibuktikan dengan Dinitz, Karzanov dan Lomonosov pada tahun 1976, di "Struktur untuk sistem semua pemotongan minimal grafik". Mungkin Anda dapat menemukan apa yang Anda cari di makalah ini, tetapi saya tidak yakin apakah itu daring.

Secara informal, orang dapat berargumen bahwa untuk mendapatkan jumlah minimum pemotongan minimum, semua simpul dalam grafik harus memiliki derajat yang sama.

Biarkan potongan membagi grafik menjadi dua set node dan sehingga . Biarkan jumlah potongan minimum dalam grafik dilambangkan sebagai .$G$$C$$\bar C$$C \cap \bar C=\emptyset$$mc(G)$

Pertimbangkan grafik terhubung dengan simpul di mana setiap simpul memiliki derajat dua. Ini harus menjadi grafik siklus dan potongan minimum adalah dua sisi. Jelas bahwa memotong dua sisi akan menghasilkan potongan dan potongan tersebut adalah potongan minimum. Karena ada pasang tepi yang berbeda, maka ada potongan minimum.$n$$n(n-1)/2$$n(n-1)/2$

Buat grafik baru dengan menghapus tepi dari grafik siklus. Pemotongan minimum grafik baru adalah satu sisi dan memotong setiap sisi akan cukup: ada potongan yang dapat dibuat.$n-1$

Buat grafik baru dengan menambahkan tepi ke grafik siklus. Sekarang dua node memiliki derajat tiga dan node memiliki derajat dua. Tingkat tiga node harus baik milik atau keduanya milik . Perhatikan bahwa dalam kasus grafik siklus, tidak ada node dibatasi untuk tampil bersama dalam atau . Implikasinya adalah bahwa menambahkan tepi menambah kendala, yang mengurangi jumlah pemotongan minimum.$n-2$$C$$\bar C$$C$$\bar C$

Mempromosikan lebih banyak node ke tingkat tiga menambah kendala tambahan sampai titik di mana hanya ada satu pemotongan minimal derajat dua.

Hal tersebut di atas menunjukkan bahwa grafik siklus adalah (setidaknya) maksimum lokal .$mc$

Pertimbangkan set grafik di mana setiap node adalah derajat tiga. Menghapus sebuah tepi menghasilkan grafik dengan potongan minimal dua. Menambahkan edge, seperti di atas, menghasilkan dua node yang paling banyak muncul di sisi yang sama dengan cut.

Ini menunjukkan bahwa grafik di mana setiap node adalah derajat adalah maksimum lokal . Memperhatikan bahwa grafik lengkap memiliki potongan ukuran menunjukkan bahwa ini adalah fungsi yang menurun.$k$$mc$$mc=n$$n-1$

Saya belum terlalu memikirkan apakah mungkin untuk memformalkan hal di atas, tetapi ini merupakan pendekatan yang memungkinkan.

Juga, saya pikir makalah Bixby Jelani Nelson menyebutkan dalam komentar untuk jawabannya berjudul "Jumlah Minimum Tepi Dan Verteks dalam Grafik Dengan Konektivitas Tepi dan ikatan-N" ( tautan )