Hitung semua grafik non-isomorfik dengan ukuran tertentu

30

Saya ingin menghitung semua grafik ukuran tidak diarahkan , tetapi saya hanya perlu satu instance dari setiap kelas isomorfisma . Dengan kata lain, saya ingin menghitung semua grafik non-isomorfik (tidak terarah) pada simpul. Bagaimana saya bisa melakukan ini? $n$ $n$

Lebih tepatnya, saya ingin algoritma yang akan menghasilkan urutan grafik tidak langsung , dengan properti berikut: untuk setiap grafik tidak diarahkan pada simpul, terdapat indeks sedemikian rupa sehingga isomorfik untuk . Saya ingin algoritma menjadi seefisien mungkin; dengan kata lain, metrik yang saya pedulikan adalah waktu berjalan untuk menghasilkan dan beralih melalui daftar grafik ini. Tujuan kedua adalah alangkah baiknya jika algoritme tidak terlalu rumit untuk diterapkan. $G_1,G_2,\dots,G_k$ $G$ $n$ $i$ $G$ $G_i$

Perhatikan bahwa saya perlu memiliki setidaknya satu grafik dari masing-masing kelas isomorfisma, tetapi tidak apa-apa jika algoritma menghasilkan lebih dari satu contoh. Secara khusus, tidak apa-apa jika urutan output mencakup dua grafik isomorfik, jika ini membantu membuatnya lebih mudah untuk menemukan algoritma seperti itu atau memungkinkan algoritma yang lebih efisien, selama itu mencakup semua grafik yang mungkin.

Aplikasi saya adalah sebagai berikut: Saya memiliki program yang ingin saya uji pada semua grafik ukuran . Saya tahu bahwa jika dua grafik isomorfis, program saya akan berperilaku sama pada keduanya (itu akan benar pada keduanya, atau salah pada keduanya), sehingga cukup untuk menyebutkan setidaknya satu perwakilan dari setiap kelas isomorfisme, dan kemudian menguji program pada input tersebut. Dalam aplikasi saya, cukup kecil. $n$ $n$

Beberapa kandidat algoritma yang saya pertimbangkan:

Saya bisa menghitung semua matriks adjacency yang mungkin, yaitu, semua matriks simetris 0-atau-1 yang memiliki semua 0 pada diagonal. Namun, ini membutuhkan enumerasi matriks . Banyak dari matriks tersebut akan mewakili grafik isomorfik, jadi ini sepertinya menghabiskan banyak usaha. $n\times n$ $2^{n(n-1)/2}$
Saya bisa menghitung semua matriks kedekatan yang mungkin, dan untuk masing-masing, menguji apakah isomorfik untuk salah satu grafik yang sebelumnya saya hasilkan; jika tidak isomorfik dengan output apa pun sebelumnya, output itu. Ini akan sangat mempersingkat daftar keluaran, tetapi masih membutuhkan setidaknya langkah-langkah perhitungan (bahkan jika kita mengasumsikan grafik cek isomorfisma super cepat), jadi tidak jauh lebih baik dengan metrik saya. $2^{n(n-1)/2}$
Dimungkinkan untuk menghitung subset dari matriks kedekatan. Secara khusus, jika adalah grafik pada simpul , tanpa kehilangan generalitas, saya dapat mengasumsikan bahwa simpul disusun sehingga . Dengan kata lain, setiap grafik isomorfik ke satu di mana simpul disusun dalam urutan derajat yang tidak menurun. Jadi, cukup untuk menghitung hanya matriks kedekatan yang memiliki properti ini. Saya tidak tahu persis berapa banyak matriks kedekatan seperti itu, tetapi jumlahnya jauh lebih sedikit dari , dan mereka dapat dihitung dengan jauh lebih sedikit dari $G$ $n$ $V=\{v_1,\dots,v_n\}$ $\deg v_1 \le \deg v_2 \le \cdots \le \deg v_n$ $2^{n(n-1)/2}$ $2^{n(n-1)/2}$ langkah-langkah perhitungan. Namun, ini masih menyisakan banyak redundansi: banyak kelas isomorfisme masih akan dibahas berulang kali, jadi saya ragu ini optimal.

Bisakah kita berbuat lebih baik? Jika saya mengerti dengan benar, ada sekitarkelas ekivalensi dari grafik non-isomorfik. Bisakah kita menemukan algoritma yang waktu operasinya lebih baik daripada algoritma di atas? Seberapa dekat kita denganbatas bawah? Saya terutama peduli tentang ketertelusuran untuk kecil (katakanlah, atau atau lebih; cukup kecil sehingga orang bisa menjalankan algoritma seperti itu sampai selesai), tidak begitu banyak tentang asimtotik untuk besar . $2^{n(n-1)/2}/n!$ $\sim 2^{n(n-1)/2}/n!$ $n$ $n=5$ $n=8$ $n$

Terkait: Membangun matriks biner yang tidak seimbang (meskipun sayangnya seseorang sepertinya tidak menerima jawaban yang valid).

1

Afaik, bahkan jumlah grafik ukuran hingga isomorfisme tidak diketahui, jadi saya pikir tidak mungkin ada algoritma (non-brute-force). Mengenai algoritme kandidat Anda, ingatlah bahwa kami tidak tahu algoritma waktu polinomial untuk memeriksa grafik isomorfisme (afaik), jadi setiap algoritme yang seharusnya dijalankan di harus menghindari keharusan periksa isomorfisma (sering / bodoh). (Juga, .)

n

$n$

O (| output |)

$O(|\text{output}|)$

| output | = Ω (n \cdot | classes |)

$|\text{output}| = \Omega(n \cdot |\text{classes}|)$

Raphael

@ Raphael, (1) Saya tahu kita tidak tahu jumlah pasti dari grafik ukuran hingga isomorfisma, tetapi masalah ini tidak selalu membutuhkan mengetahui hal itu (misalnya, karena fakta saya OK dengan pengulangan). Saya tidak tahu mengapa itu menyiratkan tidak mungkin ada algoritma yang lebih baik daripada yang saya berikan. (2) Ya, saya tahu tidak ada algoritma waktu polinomial yang dikenal untuk grafik isomorfisme, tetapi kita akan berbicara tentang nilai-nilai seperti sini, jadi algoritma yang ada mungkin akan cepat - dan lagi pula, saya hanya menyebutkan algoritma kandidat untuk menolaknya, jadi tetap bisa diperdebatkan.

n

$n$

n

$n$

n = 6

$n=6$

DW

Untuk paling banyak 6, saya percaya bahwa setelah memilih jumlah simpul dan jumlah tepi, dan memesan label verteks secara non-menurun berdasarkan derajat seperti yang Anda sarankan, maka akan ada sangat sedikit kemungkinan kelas isomorfisma. Pada titik ini mungkin menjadi layak untuk menyortir kasing yang tersisa dengan uji isomorfisme brute-force menggunakan mis. NAUTY atau BLISS.

n

$n$

Simon

19

Mungkin cara termudah untuk menghitung semua grafik non-isomorfik untuk jumlah titik kecil adalah dengan mengunduhnya dari koleksi Brendan McKay . Algoritma enumerasi dijelaskan dalam makalah McKay [1] dan bekerja dengan memperluas non-isomorf dengan ukuran n-1 dengan semua cara yang mungkin dan memeriksa untuk melihat apakah verteks baru itu kanonik. Ini diimplementasikan seperti gengpada pemeriksa isomorfisma grafik McKay nauty.

[1]: BD McKay, Penerapan teknik enumerasi berlabel , Congressus Numerantium, 40 (1983) 207-221.

David Eisenstat
sumber

Saya punya masalah. Saya mengambil grafik ukuran n-1dan memperluasnya dengan simpul dalam semua cara yang mungkin, seperti yang Anda katakan. Lalu saya memeriksa apakah vertex memiliki label kanonik, katakanlah 1(kanonikal vertex ?!). Namun, bagaimana jika grafiknya hanya isomorfik dari bentuk kanonik dan simpulnya memiliki label yang berbeda? Saya telah mencoba memeriksa automorfisma untuk melihat apakah vertex dengan label 1berada di orbit yang sama, tetapi kemudian saya berakhir dengan grafik dua kali dalam daftar saya. Makalah itu tidak benar-benar membantu saya. Juga, kode sumber geng tidak dapat dibaca karena semua optimasi biner dan hampir tidak ada komentar.

Alex

1

@Alex Anda pasti ingin versi cek yang menentukan apakah simpul baru berada di orbit yang sama dengan 1. Bisakah Anda memberikan contoh di mana ini menghasilkan dua grafik isomorfik? Mungkin ini akan lebih baik sebagai pertanyaan baru.

David Eisenstat

Oke, terima kasih banyak! Saya kira dalam kasus itu "memperluas dengan segala cara yang mungkin" perlu entah bagaimana mempertimbangkan automorfisme grafik dengan n-1simpul? misal n = 3 dan grafik saya sebelumnya adalah P2. Kemudian dua kasus di mana saya bergabung dengan simpul ketiga ke salah satu simpul sebelumnya tentu saja akan menghasilkan grafik P3 yang sama. Bisakah Anda dengan cepat menjelaskan bagaimana cara "memperluas dalam semua cara yang mungkin" dengan benar atau haruskah saya mengajukan ini sebagai pertanyaan lain? (Juga, kadang-kadang saya bingung tentang apa yang terjadi, karena program saya perlu menemukan non-isomorfisme dari jenis grafik khusus, yang membuat segalanya sedikit lebih rumit)

Alex

@ Alex Ya, tampaknya ekstensi itu sendiri harus kanonik. Mungkin bernilai pertanyaan baru, karena saya tidak ingat bagaimana ini bekerja di atas kepala saya.

David Eisenstat

1

Nauty halaman rumah

Guy Coder

4

Saya mengusulkan peningkatan pada ide ketiga Anda: Isi baris matriks adjacency baris demi baris, catat simpul-simpul yang ekuivalen dengan derajat dan adjacency mereka dengan simpul yang sebelumnya terisi. Jadi awalnya kelas ekivalensi akan terdiri dari semua node dengan derajat yang sama.
Ketika vertex yang baru diisi berdekatan dengan hanya beberapa node yang setara, setiap pilihan mengarah ke representan dari kelas isomrphism yang sama. Jadi kami hanya mempertimbangkan penugasan, di mana simpul yang saat ini diisi berdekatan dengan simpul setara dengan jumlah tertinggi (dan membagi kelas ekivalensi menjadi dua untuk proses yang tersisa).

$n<6$
$(1,2)$ $(3,4)$ $n=6$

Implementasi naif dari algoritma ini akan menemui jalan buntu, di mana ternyata bahwa matriks adjacency tidak dapat diisi sesuai dengan set derajat yang diberikan dan tugas sebelumnya. Mungkin perlu upaya untuk mendeteksi / memfilter ini lebih awal. Beberapa ide:

Jika jumlah derajatnya ganjil, mereka tidak akan pernah membentuk grafik
Isi entri untuk simpul yang perlu terhubung dengan semua / tidak ada simpul yang tersisa segera.

FrankW
sumber

3

Makalah ini mungkin menarik.

"Tentang penggambaran grafik yang ringkas", Gyorgy Turan, Matematika Terapan Diskret, Volume 8, Edisi 3, Juli 1984, hlm. 289-294 http://www.sciencedirect.com/science/article/pii/0166218X84901264

"Representasi ringkas dari grafik tidak berlabel umum", Moni Naor, Matematika Terapan Diskrit, Volume 28, Edisi 3, September 1990, hlm. 303-307 http://www.sciencedirect.com/science/article/pii/0166218X9090011Z

Mereka menyajikan fungsi encoding dan decoding untuk pengkodean grafik berlabel titik sehingga dua grafik tersebut memetakan ke codeword yang sama jika dan hanya jika satu hasil dari permutasi label vertex yang lain.

Selain itu terbukti bahwa fungsi encoding dan decoding efisien.

Makalah pertama berkaitan dengan grafik planar. Dalam makalah kedua, pembatasan planaritas dihapus.

EDIT: Makalah ini mungkin juga relevan:

Grafik Isomorfisme dalam Waktu Kuasi-Polinomial, Laszlo Babai, Universitas Chicago, Pracetak pada arXiv, 9 Desember 2015 http://arxiv.org/pdf/1512.03547v1.pdf

Pengumuman Babai tentang hasilnya membuat berita: https://www.sciencenews.org/article/new-algorithm-cracks-graph-problem

Tapi mungkin saya salah mengacaukan pertanyaan OP dengan tiga makalah ini? OP ingin menghitung grafik non-isomorfik, tetapi mungkin masih bermanfaat untuk memiliki metode yang efisien untuk menentukan kapan dua grafik itu isomorfik?

Simon
sumber

Saya menghargai pemikiran itu, tetapi saya khawatir saya tidak bertanya bagaimana menentukan apakah dua grafik itu isomorfik. Saya benar-benar bertanya bagaimana cara menghitung grafik non-isomorfik. Menjelaskan algoritme untuk menguji apakah dua grafik isomorfik tidak benar-benar membantu saya, saya khawatir - terima kasih sudah mencoba!

DW

Turan dan Naor (dalam makalah yang saya sebutkan di atas) membangun fungsi dari tipe yang Anda gambarkan, yaitu memetakan grafik menjadi perwakilan kanonik dari kelas ekivalensi dimana grafik tersebut berada. Jika Anda dapat menyebutkan perwakilan kanonik tersebut, maka itu tampaknya akan menyelesaikan masalah Anda.

Simon

Babai mencabut klaim runtime quasipolynomial . Ternyata ada kesalahan dalam analisis.

Raphael

1

Ada sebuah makalah dari awal tahun sembilan puluhan yang menangani persis pertanyaan ini:

Algoritma yang efisien untuk daftar grafik tidak berlabel oleh Leslie Goldberg.

Pendekatan ini menjamin bahwa tepat satu perwakilan dari setiap kelas isomorfisma dihitung dan bahwa hanya ada penundaan polinom antara generasi dua grafik berikutnya.

$n$

Pascal Welke
sumber

Hitung semua grafik non-isomorfik dengan ukuran tertentu

Jawaban: