Kembalinya Grafik (dan Kuis Menyenangkan) – Beragampengetahuan

Oleh: Blog Bogumił Kamiński

Repost dari:

Minggu ini saya kembali dengan grafik. Alasannya adalah saya bergabung
dalam Lokakarya inspirasional tentang Jejaring Sosial & Sistem Kompleks.

Selama lokakarya ini, Paweł Prałat menanyakan kuis berikut:

Anda diberi delapan baterai, empat di antaranya bagus dan empat bagus
habis, tetapi di permukaan mereka tidak berbeda.
Anda memiliki senter yang membutuhkan dua baterai yang bagus untuk bekerja.
Anda ingin senter Anda berfungsi. Berapa kali minimal?
Anda perlu memasukkan dua baterai ke dalam senter untuk memastikannya berfungsi
dalam kasus terburuk.

Pada postingan kali ini saya ingin membahas bagaimana cara mengatasinya.
Kami akan mulai dengan solusi analitik dan kemudian memberikan perhitungan
satu. Anda bisa menilai sendiri mana yang lebih sulit.

Posting itu ditulis di bawah Julia 1.9.
Kombinasi v1.0.2, DataFrames v1.5.0,
SimpleGraphs v0.8.4 dan SimpleGraphAlgorithms v0.4.21.

Sebelum kita mulai, kita perlu melakukan observasi. Jika saya mengatakan saya ingin menggunakan
sejumlah tes dalam kasus terburuk yang bisa saya berikan kepada mereka terlebih dahulu (sebelumnya
melakukan tes apapun). Alasannya adalah jika saya memasukkan beberapa baterai ke dalam a
senter itu akan berfungsi (dan kemudian kita selesai) atau tidak (dan kita harus melanjutkan).
Jadi situasinya lebih sederhana daripada di banyak teka-teki lain saat Anda menginginkannya
sesuaikan strategi Anda secara kondisional berdasarkan jawaban yang Anda lihat pada pertanyaan Anda sebelumnya.

Yang ingin kami tunjukkan adalah bahwa kami membutuhkan 7 tes. Mulailah dengan tampilan
7 tes sudah cukup. Untuk melihat pesan ini kami memiliki 4 baterai yang bagus.
Oleh karena itu, jika kita membagi 8 baterai menjadi tiga kelompok, akan ada a
kelompok dengan dua baterai (menurut prinsip lubang merpati).
Apa yang perlu kita lakukan adalah menunjukkan bahwa menggunakan 7
bandingkan kita dapat menemukan sepasang baterai yang bagus di salah satunya
tiga kelompok.

Inilah cara Anda melakukannya.
Katakanlah kita memberi nomor pin dari 1 sampai 8. Bagilah menjadi tiga kelompok:
{1, 2, 3}, {4, 5, 6}Dan {7, 8}. Sekarang kita berasumsi bahwa kita membuat semua
komparatif kelompok. Kita bisa melihatnya di dua kelompok pertama
bisa ada tiga perbandingan dan pada kelompok terakhir hanya satu perbandingan. tujuh
Total. Ini menyimpulkan bukti bahwa 7 perbandingan sudah cukup.
Kami dapat memvisualisasikan solusi ini sebagai berikut (garis menunjukkan perbandingan
kami buat):

  1      4    7
 / \    / \   |
2---3  5---6  8

Kami dibiarkan menunjukkan bahwa 6 perbandingan tidak cukup. Lihat
ini perhatikan berikut ini. Dalam grafik di atas kita memiliki grafik pada 8 node
dan memiliki 7 sisi. Kami dapat mengklaim bahwa kami memiliki solusi karena di
setiap subset empat elemen dari simpulnya memiliki setidaknya dua koneksi
oleh tepi (dalam kelompok).

Jadi, untuk menunjukkan bahwa 6 perbandingan saja tidak cukup, kita harus menunjukkan bahwa terlepas dari
cara kami membuatnya akan selalu memiliki 4 tombol berbeda
Menghubung. Kita akan membuktikannya dengan kontradiksi. Misalkan kita memiliki beberapa tugas
tepi di mana hingga tiga node tidak terhubung. tidak ada kerugian
secara umum menganggap bahwa nomor mereka adalah 1, 2 dan 3. Tetapi ini berarti masing-masing
node 4, 5, 6, 7 dan 8 harus terhubung ke salah satu node 1, 2 atau 3
sama dengan setidaknya satu sisi. Jadi kita harus menggunakan semua 5 sisi untuk membuat koneksi ini.
Kita hanya memiliki satu sisi (ingat bahwa kita mengasumsikan bahwa kita dapat menggunakan total 6 sisi).
Jika ujung terakhir ini dihubungkan ke simpul 1, 2 atau 3. Maka simpul 4, 5, 6, 7 dan 8
tidak terhubung langsung dan kami baru saja menemukan kumpulan 5 elemen yang tidak terhubung oleh sebuah sisi.
Jadi misalkan edge ini menghubungkan sepasang node dari himpunan {4, 5, 6, 7, 8}.
Namun, karena kami hanya memiliki satu sisi, kami masih memiliki 4 node yang tidak terhubung.
Misalnya jika 4 dan 5 dihubungkan maka himpunan simpulnya {4, 6, 7, 8} Tidak terhubung,
jadi kami memiliki satu set 4 elemen node yang tidak terhubung. Kontradiksi dengan asumsi
bahwa ada hingga tiga node yang tidak terhubung. Singkatnya – 6 perbandingan
tidak memadai.

(Jika ingin melihat pembuktian alternatif menggunakan metode probabilitas
Anda dapat menghubungi Paweł Prałat yang menunjukkan kepada saya.)

Sekarang mari beralih ke kalkulus dan kekerasan (dan dalam prosesnya, semoga mempelajari beberapa trik Julia).

Pertama unduh paket yang diperlukan dan lakukan beberapa pengaturan:

julia > gunakan Combinatorics julia > gunakan DataFrames julia > gunakan SimpleGraphs julia > gunakan SimpleGraphAlgorithms julia > use_Cbc()
[ Info: Solver Cbc verbose is set to false

As we saw in the analytical solution we can represent our queries as graphs on 8 nodes
and some edges.

The problem is that there are potentially many such graphs. Therefore we will want to limit
our search to the graphs that are not isomorphic. Two graphs are isomorphic if you can
get one from the other by re-labelling the nodes. Clearly such two graphs are undistinguishable
for our purposes.

What we want to show is that all graphs on 8 nodes and 6 edges contain at least 4 nodes that
are not connected by an edge. And that there exist graphs on 8 nodes and 7 edges in which
the maximum number of unconnected nodes is 3.

So how do we create a list of all non-isomorphic graphs having 6 and 7 edges respectively?

Let us start with a simpler case of graphs on 8 nodes and 3 edges and list non-isomorphic graphs:

julia> function create_graph(es)
           g = IntGraph(8)
           for e in es
               add!(g, e...)
           end
           return g
       end
create_graph (generic function with 1 method)

julia> g3 = map(create_graph, combinations([(i, j) for i in 1:7 for j in i+1:8], 3));  julia > hg3 = uhash.(g3);  julia> g3df = DataFrame(hg=hg3, g=g3);  julia> g3gdf = groupby(g3df, :hg);  julia> redirect_stdout(devnull) membuat sdf di g3gdf untuk saya di 2:nrow(sdf) @assert is_iso(sdf.g[1]sdf.g[i]) akhir akhir julia > noniso3 = gabungkan(g3gdf, pertama).g;  julia> elist.(noniso3) vektor 5 elemen{Vektor{Tuple{Int64, Int64}}}:
 [(1, 2), (1, 3), (1, 4)]
 [(1, 2), (1, 3), (2, 3)]
 [(1, 2), (1, 3), (2, 4)]
 [(1, 2), (1, 3), (4, 5)]
 [(1, 2), (3, 4), (5, 6)]

Mari kita jelaskan apa yang kita lakukan langkah demi langkah. Itu g3 objek berisi semua
grafik pada tiga sisi. Mari kita periksa berapa banyak dari mereka yang kita miliki:

Ada banyak grafik. Tetapi kebanyakan dari mereka adalah isomorfik. Bagaimana kita memangkasnya?
Menggunakan uhash fungsi kami menghitung hash dari setiap grafik.
uhash meyakinkan kita bahwa grafik dengan fungsi hash lainnya tidak isomorfik.
Itu g3gdf Apakah satu GroupedDataFrame pertahankan agar grafik ini dikelompokkan berdasarkan
Nilai hash. Kami memiliki 5 grup yang dapat didaftarkan:

Namun, ada kemungkinan bahwa ini adalah kasus di mana kita memiliki graf non-isomorfik
memiliki nilai hash yang sama (yang tidak mungkin tetapi mungkin). Kami mengujinya dengan
itu is_iso fungsi. Jika mereka tidak isomorfik @assert akan kesalahan.
Karena itu bukan kita yang baik. Perhatikan bahwa saya menggunakan redirect_stdout(devnull)
tip untuk menghindari mencetak keluaran apa pun is_iso pembuatan. Alasan
adalah bahwa ia memanggil pemecah CBC untuk mencetak layar statusnya (dan karena
kami melakukan lebih dari 3000 panggilan, layar akan meluap karena keluarannya tidak terlalu berguna).

dengan elist.(noniso3) kita bisa melihat apa tepi lima tidak isomorfik
Grafik ada di 3 tepi.
(Dan karena kami hanya memiliki 5 grafik, Anda dapat meyakinkan diri sendiri menggunakan pena
dan kertas tempat kami menemukan semua opsi yang memungkinkan.)

Bagaimana kita melakukan proses ini untuk jumlah edge yang lebih banyak.
Pendekatan yang sama akan berhasil, tetapi akan memakan waktu lebih lama (ya
lebih dari 1 juta grafik pada 7 sisi). Jadi kami menggunakan trik berikut, kami ambil
Graf non-isomorfik memiliki 3 sisi dan menambahkan sisi padanya. Sekarang kita mendapatkan grafiknya
di 4 sisi. Beberapa di antaranya isomorfik. Tapi kita sudah tahu cara memangkasnya
yang tersisa hanya yang tidak isomorfik.

Prosedur untuk mengulang tugas ini hingga 7 sisi adalah sebagai berikut:

julia> function add_possible_edges(g::T) where T
           res = T[]
           for i in 1:7, j in i+1:8
               if !has(g, i, j)
                   newg = deepcopy(g)
                   add!(newg, i, j)
                   @assert NE(newg) == NE(g) + 1
                   push!(res, newg)
               end
                   end
           return res
       end
add_possible_edges (generic function with 1 method)

julia> function grow_graphs(noniso)
           g = reduce(vcat, add_possible_edges.(noniso))
           hg = uhash.(g)
           gdf = DataFrame(; hg, g)
           ggdf = groupby(gdf, :hg)
           redirect_stdout(devnull) do
               for sdf in ggdf
                   for i in 2:nrow(sdf)
                       @assert is_iso(sdf.g[1], sdf.g[i])
                   end
               end
           end
           return combine(ggdf, first).g
       end
grow_graphs (generic function with 1 method)

julia> noniso4 = grow_graphs(noniso3)
11-element Vector{UndirectedGraph{Int64}}:
 UndirectedGraph{Int64} (n=8, m=4)
 ⋮
 UndirectedGraph{Int64} (n=8, m=4)

julia> noniso5 = grow_graphs(noniso4)
24-element Vector{UndirectedGraph{Int64}}:
 UndirectedGraph{Int64} (n=8, m=5)
 ⋮
 UndirectedGraph{Int64} (n=8, m=5)

julia> noniso6 = grow_graphs(noniso5)
56-element Vector{UndirectedGraph{Int64}}:
 UndirectedGraph{Int64} (n=8, m=6)
 ⋮
 UndirectedGraph{Int64} (n=8, m=6)

julia> noniso7 = grow_graphs(noniso6)
115-element Vector{UndirectedGraph{Int64}}:
 UndirectedGraph{Int64} (n=8, m=7)
 ⋮
 UndirectedGraph{Int64} (n=8, m=7)

Selama proses tersebut, kita mengetahui bahwa terdapat 11 graf non-isomorfik dengan 4 sisi,
dan 24 untuk 5 sisi, masing-masing 56 untuk 6 sisi dan 115 untuk 7 sisi.

Sekarang untuk masing-masing grafik ini, mari kita cari jumlah simpul maksimum yang bisa ada
memutuskan. Ini dapat dilakukan dengan menggunakan max_indep_set fungsi.
Sekali lagi kami menggunakan devnull tips untuk menghindari hasil cetak:

julia> mis6 = redirect_stdout(devnull) do
           return max_indep_set.(noniso6)
       end
56-element Vector{Set{Int64}}:
 Set([5, 4, 6, 7, 2, 8, 3])
 ⋮
 Set([4, 7, 8, 3])

julia> minimum(length.(mis6))
4

Jadi pertama-tama kita melihat bahwa untuk grafik lebih dari 6 tepi, kita sebenarnya memiliki setidaknya 4 node
himpunan mandiri.

Sekarang mari kita periksa kasus 7 node:

julia> mis7 = redirect_stdout(devnull) do
           return max_indep_set.(noniso7)
       end
115-element Vector{Set{Int64}}:
 Set([5, 4, 6, 7, 2, 8, 3])
 ⋮
 Set([7, 2, 8, 3])

julia> minimum(length.(mis7))
3

julia> elist.(noniso7[length.(mis7) .== 3])
1-element Vector{Vector{Tuple{Int64, Int64}}}:
 [(1, 2), (1, 3), (2, 3), (4, 5), (4, 6), (5, 6), (7, 8)]

Di sini kita melihat bahwa hanya ada satu graf (hingga isomorfisme)
memiliki properti yang paling banyak tiga node independen.
Dan melihat ujungnya, sepertinya grafik yang kita gambar
dalam solusi analitik kami.

Jadi apakah solusi analitik atau komputasi lebih menarik?
Bagi saya keduanya memiliki kelebihan dan keduanya menyenangkan.

Jika Anda menyukai kuis semacam itu dan rencanakan ke depan, harap pertimbangkan untuk berpartisipasi
kami tahun depan. Dari 3 hingga 7 Juni 2024, kami akan mengadakan
WAW2024: Lokakarya ke-19 tentang Pemodelan dan Penambangan Jaringan
di Sekolah Ekonomi SGH Warsawa. Kami mengundang semua penggemar grafik:
baik teori maupun praktisi.

Terkait