Saya ingin bertanya apakah ada hasil yang sudah dipublikasikan tentang itu:
Kami mengambil semua kemungkinan jalur yang berbeda antara setiap pasangan node dari dua grafik reguler yang terhubung (dengan derajat katakanlah, dan jumlah node n ) dan tulis panjangnya. Tentu saja jumlah jalur yang berbeda ini eksponensial. Pertanyaan saya adalah, jika kita mengurutkan panjang dan membandingkannya (daftar diperoleh oleh dua grafik) dan mereka persis sama, dapatkah kita mengatakan bahwa kedua grafik itu isomorfis?
Tentu saja, bahkan jika ini adalah hasil, kita tidak dapat menggunakannya untuk membalas Grafik Isomorfisme, karena jumlah jalur yang berbeda bersifat eksponensial, seperti yang dikatakan
Dengan jalur yang berbeda , saya merujuk ke jalur yang memiliki setidaknya satu simpul berbeda, jelas.
Terima kasih atas bantuan Anda.
Jawaban:
Saya percaya jawaban untuk pertanyaan Anda adalah "tidak" karena kondisi yang setara akan menyiratkan solusi waktu polinomial untuk GI.
Untuk , matriks kedekatan dari grafik G , perhatikan bahwa jumlah lintasan dari i ke j dengan panjang k adalah ( A k ) i , j (dengan pengulangan simpul dan tepi diizinkan). Untuk dua grafik G 1 dan G 2 (dengan matriks kedekatan A 1 dan A 2 ) dan k ≥ 1 , jika Anda mengurutkan elemen A k 1 dan A k 2 maka untukSEBUAH G i j k (Ak)i,j G1 G2 A1 A2 k≥1 Ak1 Ak2 menjadi isomorfik terhadap G 2 , adalah kondisi yang diperlukan bahwa daftar identik untuk semua k .G1 G2 k
Saya yakin dugaan Anda setara dengan:
Jika daftar elemen yang diurutkan dari dan A d 2 identik untuk k = 1 hingga n - 1 (upperbound pada lintasan terpanjang dengan simpul yang tidak berulang) maka G 1 dan G 2 adalah isomorfik.Ak1 Ad2 k=1 n−1 G1 G2
Jadi untuk memecahkan GI, satu-satunya harus melakukan perkalian dari n × n matriks (dan sedikit waktu ekstra untuk mengurutkan dan membandingkan n 2 elemen). Ini akan memakan waktu kurang dari n 4 kali.n−1 n×n n2 n4
Saya mengakui dua kemungkinan kelemahan dalam argumen saya. Pertama, sangat mungkin bahwa GI memiliki algoritma waktu polinomial dan kami baru saja menemukannya bersama, baru saja (hore, kami terkenal!). Saya menemukan ini sangat tidak mungkin. Kedua (dan lebih mungkin), apa yang saya usulkan sebenarnya tidak sama dengan dugaan Anda.
Pemikiran terakhir. Sudahkah Anda mencoba ini untuk semua, katakanlah, grafik 3-reguler untuk ukuran 8 atau lebih? Saya akan berpikir bahwa jika dugaan Anda salah, bahwa harus ada contoh counter dalam grafik 3-reguler berukuran cukup kecil.
sumber
Karena Anda hanya membandingkan panjang jalur (dan sementara itu melupakan pasangan node yang sesuai dengan jika saya memahami Anda dengan baik), saya pikir grafik yang sangat mirip harus memberikan contoh tandingan: pada akhirnya Anda hanya menghitung jumlah jalur dengan panjang tetap dan tidak tergantung pada simpul yang dihubungkan. Misalnya saya pikir grafik ini adalah contoh tandingan: http://www.mathe2.uni-bayreuth.de/markus/REGGRAPHS/GIF/06_3_3-2.gif dan http://www.mathe2.uni-bayreuth.de/ markus / REGGRAPHS / GIF / 06_3_3-1.gif
Jika saya tidak salah (menghitung jalur itu membosankan), keduanya memiliki 9 jalur panjang 1, 18 jalur panjang 2, 48 jalur panjang 3, 30 jalur panjang 4 dan 36 jalur panjang 5
sumber
sumber