Referensi untuk algoritme pengujian grafik asiklisitas campuran?

16

Grafik campuran adalah grafik yang mungkin memiliki tepi terarah dan tidak berarah. Grafiknya yang tidak diarahkan mendasari diperoleh dengan melupakan orientasi dari tepi yang diarahkan, dan di arah lain orientasi dari grafik campuran diperoleh dengan menetapkan arah ke setiap tepi yang tidak diarahkan. Seperangkat tepi membentuk siklus dalam grafik campuran jika dapat berorientasi untuk membentuk siklus terarah. Grafik campuran asiklik jika dan hanya jika tidak memiliki siklus.

Ini semua standar dan ada banyak makalah yang diterbitkan menyebutkan grafik campuran asiklik. Jadi algoritma berikut untuk menguji acyclicity dari grafik campuran harus diketahui:

Ulangi langkah-langkah berikut:

  • Hapus semua titik yang tidak memiliki tepi terarah masuk dan tidak ada tepi tidak berarah, karena tidak dapat menjadi bagian dari siklus apa pun.
  • Jika ada titik yang tidak memiliki tepi diarahkan masuk tetapi memiliki tepat satu insiden tepi tidak terarah, maka setiap siklus menggunakan tepi tidak diarahkan harus masuk di tepi itu. Ganti tepi yang tidak terarah dengan tepi yang diarahkan masuk.

Berhentilah ketika tidak ada lagi langkah yang dapat dilakukan. Jika hasilnya adalah grafik kosong, maka grafik asli pastilah asiklik. Kalau tidak, mulai dari titik mana pun yang tersisa, seseorang dapat mundur melalui grafik, pada setiap langkah mengikuti mundur melalui tepi masuk atau mengikuti tepi tidak diarahkan yang bukan yang digunakan untuk mencapai puncak saat ini, sampai melihat simpul berulang. Urutan tepi yang diikuti antara pengulangan pertama dan kedua dari simpul ini (dalam urutan terbalik) membentuk siklus dalam grafik campuran.

Artikel Wikipedia tentang grafik campuran menyebutkan grafik campuran asiklik tetapi tidak menyebutkan cara mengujinya, jadi saya ingin menambahkan sesuatu tentang algoritma ini, tetapi untuk itu saya perlu referensi yang diterbitkan. Dapatkah seseorang memberi tahu saya di mana itu (atau algoritma lain untuk menguji asiklik) muncul dalam literatur?

ds.algorithms reference-request graph-theory graph-algorithms directed-acyclic-graph David Eppstein
sumber
apa yang terjadi ketika sebuah simpul memiliki dua insiden tepi yang tidak terarah, dan tidak ada tepi yang lain? Misalnya dalam segitiga tanpa arah. Maksud saya apakah aturan di atas mencakup kasus ini?
Mateus de Oliveira Oliveira
Anda tidak dapat melakukan apa pun tentang simpul tersebut hingga simpul yang berbeda menerapkan aturan yang mengarahkan salah satu ujungnya. Jika Anda terjebak dengan situasi di mana simpul tersebut ada, dan Anda tidak dapat menerapkan aturan lagi, maka grafik Anda berisi siklus.
David Eppstein
Mungkin akan lebih jelas untuk mempertimbangkan apa yang terjadi jika grafik Anda tidak diarahkan. Salah satu cara untuk menguji apakah itu hutan adalah menghilangkan daun (derajat satu simpul) dan simpul terisolasi sampai Anda mendapatkan grafik kosong (itu hutan) atau 2-core (sebuah subgraf di mana semua simpul memiliki derajat ≥ 2, yang tentu mengandung siklus). Algoritma mixed graph merosot ke hal ini dalam kasus yang tidak diarahkan (kecuali bahwa itu mengarahkan daun daripada segera menghapusnya), sama seperti itu merosot ke algoritma pengurutan topologi standar dalam kasus yang diarahkan.
David Eppstein
Tidak yakin apakah Anda pernah melihat: ada posting di cs.stackexchange yang menanyakan ref pertanyaan serupa . Penjawab memberikan algoritma untuk menemukan siklus dalam grafik campuran dengan mengorientasikan tepi yang tidak terarah, menolak grafik jika tidak ada. Ada juga kertas (s) tentang menentukan apakah grafik campuran adalah ref sangat berorientasi tetapi anehnya, tidak dapat menemukan apa-apa tentang menemukan komponen yang terhubung dalam grafik campuran.
Quanquan Liu
Terima kasih - tidak, saya belum melihat itu. Pertanyaan "temukan orientasi untuk membuat grafik berisi siklus terarah" pastinya sama, dan algoritme dalam jawabannya terlihat benar. Tapi tidak seperti yang saya jelaskan, ini bukan waktu linear.
David Eppstein

Jawaban:

1

Menemukan siklus campuran dalam grafik campuran sama dengan menemukan siklus arah elementer (dengan panjang> = 3) dalam grafik arah yang sesuai. Grafik berarah yang sesuai diperoleh dari grafik campuran dengan mengganti setiap tepi yang tidak terarah dengan dua tepi terarah yang menunjuk ke arah yang berlawanan. Bukti: (1) Setiap siklus berarah dasar (dengan panjang> = 3) dalam digraf berhubungan langsung dengan siklus campuran dalam grafik campuran. (2) Setiap siklus campuran dalam grafik campuran berisi siklus campuran elementer dari panjang> = 3, dan setiap siklus tersebut berhubungan langsung dengan siklus pengarahan elementer (dengan panjang> = 3) dalam grafik yang diarahkan. (1) dan (2) bersama-sama membuktikan kedua arah pernyataan itu, qed. Jadi kami mencari referensi bagaimana menghitung siklus SD (semua?) (Panjang> = 3) dalam grafik berarah.

Komentar menunjukkan bahwa cs.stackexchange berisi beberapa jawaban untuk pertanyaan ini, tetapi tidak jelas bagaimana mengatur hasilnya menjadi jawaban yang ringkas. Posting blog ini tampaknya meringkas referensi penting (paling?) Dengan baik:

Algoritma oleh R. Tarjan

Algoritma paling awal yang saya sertakan diterbitkan oleh R. Tarjan pada tahun 1973.

Enumeration of the elementary circuits of a directed graph
R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216
http://dx.doi.org/10.1137/0202017

Algoritma oleh DB Johnson

Algoritma oleh DB Johnson dari tahun 1975 meningkatkan algoritma Tarjan oleh kompleksitasnya.

Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
http://dx.doi.org/10.1137/0204007

Dalam kasus terburuk, algoritma Tarjan memiliki kompleksitas waktu O (n⋅e (c +1)) sedangkan algoritma Johnson diduga berhasil tetap dalam O ((n + e) ​​(c +1)) di mana n adalah jumlah simpul, e adalah jumlah tepi dan c adalah jumlah siklus dalam grafik.

Algoritma oleh KA Hawick dan HA James

Algoritma oleh KA Hawick dan HA James dari 2008 meningkatkan lebih lanjut pada algoritma Johnson dan menghilangkan keterbatasannya.

Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.
Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20
www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf
http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf

Berbeda dengan algoritma Johnson, algoritma oleh KA Hawick dan HA James mampu menangani grafik yang berisi tepi yang dimulai dan berakhir pada titik yang sama serta banyak sisi yang menghubungkan dua simpul yang sama.

Pengujian acyclicity itu sendiri tampaknya mudah: Hitung komponen grafik yang sangat terhubung . Setiap siklus (dasar) sepenuhnya terkandung dalam komponen yang sangat terhubung. Komponen yang terhubung kuat mengandung siklus dasar jika bukan pohon yang tidak diarahkan.

Algoritma yang diusulkan David Eppstein juga menghitung satu siklus dasar sebagai bukti, dan algoritma di atas menghitung semua siklus dasar. Setiap titik atau tepi yang tidak terkandung dalam siklus dasar dapat dihapus sebagai langkah preprocessing untuk meningkatkan kecepatan algoritma di atas. Algoritma David Eppstein dapat digunakan untuk tujuan itu, tetapi bahkan jika hanya digunakan pada komponen yang sangat terhubung, itu tidak akan menghapus setiap kemungkinan titik atau tepi yang dapat dihapus. Tetapi bahkan jika itu dapat diperluas untuk melakukannya (menghitung pohon blok-potong setidaknya memungkinkan untuk menghapus setiap titik yang mungkin dapat dihapus), tidak jelas apakah ini akan benar-benar meningkatkan kecepatan algoritma di atas.

Thomas Klimpel
sumber
Apakah ada referensi yang menyebutkan grafik campuran? Saya tahu tentang menemukan siklus dalam grafik terarah. Pertanyaan saya adalah tentang ekstensi dari algoritma tersebut ke grafik campuran.
David Eppstein
@DavidEppstein Menemukan siklus campuran dalam grafik campuran sama dengan menemukan siklus elementer (panjang> = 3) dalam grafik langsung yang sesuai. Menemukan referensi untuk pernyataan itu mungkin sulit, tetapi membuktikan pernyataan ini sangat mudah. Saya sekarang menambahkan pernyataan dan buktinya ke jawabannya. (Juga menambahkan komentar tanpa bukti bahwa menghitung pohon blok-potong memungkinkan untuk menghapus setiap kemungkinan simpul yang dapat dihapus tanpa mempengaruhi siklus dasar.)
Thomas Klimpel
Ok, tapi mereka juga masih belum linear.
David Eppstein
@ David Eppstein Pengujian acyclicity itu sendiri dilakukan dalam waktu linier. Tapi Anda benar, waktu salah satu dari algoritma tersebut perlu menemukan rangkaian dasar pertama (panjang> = 3) tidak linier (dalam kasus terburuk). Lebih buruk lagi, sebagian besar implementasi algoritma Johnson tampaknya menggunakan lebih dari waktu O ((n + e) ​​(c + 1)), ketika diterapkan pada satu lingkaran berarah tunggal (dengan n simpul, e = n tepi, dan c = 1 dasar siklus). Namun, ini dimaksudkan untuk menjadi jawaban yang benar, karena makalah Johnson tampaknya menjadi referensi yang paling banyak dikutip untuk "menemukan sirkuit dasar".
Thomas Klimpel