Grafik isomorfisme dan kelompok automorfisme

Pendekatan umum untuk memutuskan apakah dua grafik yang diberikan adalah isomorfik adalah dengan menghitung apa yang disebut label kanonik (sebagai alternatif, grafik kanonik) dari masing-masing grafik dan untuk memeriksa apakah mereka cocok atau tidak.

Alat-alat seperti Nauty menghitung grafik kanonik melalui pohon pencarian yang dipangkas menggunakan beberapa ide pintar yang mengandalkan, antara lain, pada automorfisme grafik. Karena itu, Nauty memungkinkan seseorang untuk menghitung generator dari kelompok automorfisme grafik. Namun, sejauh yang saya mengerti ide di balik Nauty, perhitungan grafik kanonik tidak mengharuskan seseorang untuk menghitung generator dari kelompok automorfisme grafik secara umum.

Oleh karena itu pertanyaan saya adalah: adakah hubungan kompleksitas-teoretis formal antara GI dan perhitungan generator set dari kelompok automorfisme grafik?

Terimakasih banyak.

Seperti komentar menyarankan ada kebingungan tentang apa yang Anda sebut "GI". Tapi idenya di sini benar. Ini setara dengan waktu polinomial untuk menemukan generator dari kelompok automorfisme karena untuk menemukan isomorfisme antara dua kelompok. Idenya adalah "klasik" karena muncul dalam karya awal seperti Luks 'Group Isomorphism dalam valensi terbatas adalah dalam polinomial-waktu, dan bahkan di sana saya pikir ide itu dianggap "terkenal".

Klaim. Membiarkan$G$ dan $H$menjadi terhubung grafik. Kemudian$G\cong H$ jika, dan hanya jika, setiap genset $S$ dari $\mathrm{Aut}(G\sqcup H)$ mengandung elemen $g\in S$ seperti yang $G^g=H$.

Perhatian Penting di sini adalah bahwa setiap genset menukar grafik seperti jika tidak, terkadang Anda akan menghitung generator yang tidak menyelesaikan masalah. Jadi misalnya, isomorfisme dari dua kelompok tidak begitu mudah menyerah dengan cara ini. Itu karena tidak semua menghasilkan set$\mathrm{Aut}(G\times H)$ akan bertukar $G$ dan $H$ kapan $G\cong H$. alih-alih, mereka bisa pergi ke salinan diagonal. Situasi itu dapat diperbaiki, tetapi membutuhkan argumen yang lebih kuat. Jadi pendekatan di sini bukan yang berlaku di semua kategori.

Bukti. Untuk sebaliknya jika setiap (atau bahkan jika satu) menghasilkan set$\mathrm{Aut}(G\sqcup H)$ simpang susun $G$ dan $H$ kemudian $G\cong H$ oleh pembatasan fungsi itu untuk $G$. Jadi ini semua tentang arah ke depan. (Tapi saya sebutkan ini karena buktinya dengan kontrapositif sehingga bisa terlihat saya akan pergi ke arah yang sama.)

Seharusnya $\mathrm{Aut}(G\sqcup H)$ dihasilkan oleh satu set $S$ semua elemen yang dikirim $G$ untuk $G$, dan $H$ untuk $H$, (catat dengan asumsi konektivitas jika satu dhuwur $G$ dikirim ke satu titik dari $H$ lalu seluruh grafik $G$ dikirim ke $H$ dan dengan lubang merpati beberapa simpul di $H$ akan dikirim ke $G$ dan sebagainya $|G|=|H|$dan kami akan menukar kedua grafik). Sejak$S$ mengirim $G$ untuk $G$, lalu setiap komposisi fungsi dalam $S$ mengirim $G$ untuk $G$, dan begitu juga invers dari fungsi-fungsi ini. Jadi setiap kata masuk$S$ mengirim $G$ untuk $G$ (dan juga $H$ untuk $H$). Jadi tidak ada unsur$\mathrm{Aut}(G\sqcup H)$ simpang susun $G$ dan $H$.

Akhirnya jika $G\cong H$ kemudian sebuah isomorfisme $\phi:G\to H$ memberi automorfisme $\phi\sqcup \phi^{-1}$ dari $G\sqcup H$. Jadi tidak adanya elemen dalam$\mathrm{Aut}(G\sqcup H)$ untuk bertukar $G$ dan $H$ tersirat $G\not\cong H$. Hasilnya berikut.$\Box$

Tetapi sekarang poin yang harus jelas adalah bahwa pergi dari keputusan (Is $G\cong H$?) untuk mencari (Beri aku $\phi:G\to H$ atau sertifikat itu $G\not\cong H$) masih harus diperdebatkan (dan dapat). Juga dari satu isomorfisma ke generator automorfisme adalah argumen lain (individualkan grafik dan ulangi tes isomorfisme). Jadi semua memberi tahu Anda memiliki beberapa halaman argumen untuk membuat persamaan ini. Tidak ada yang akan menunjukkan label kanonik. Itu jauh lebih sulit (NP-keras jika saya ingat). Meskipun NAUTY dan Jejak menangani banyak contoh dengan cepat.