Algoritma untuk menemukan semua orientasi asiklik suatu grafik

8

Saya sedang mengerjakan orientasi asiklik pada grafik yang tidak diarahkan dan memiliki pertanyaan-pertanyaan berikut:

  1. Diberikan terhubung grafik sederhana yang tidak terarah , bagaimana menemukan semua kemungkinan orientasi asiklik ?GG
  2. Berapa jumlah orientasi asiklik? Diketahui (dari sini ) adalah(1)p χ(G,λ) untuk sebuah grafikG dengan p simpul mana χ adalah polinomial kromatik yang dievaluasi pada λ; tetapi saya tidak berhasil memahami cara mengevaluasiχ pada nilai negatif (λ).
seteropere
sumber
3
Re 2, χ(G,)hanyalah polinomial. Itu dapat dievaluasi pada setiap titik kompleks. Jumlah orientasi asiklik adalah(1)pχ(G,1)dimana padalah jumlah simpul. Sebagai contoh, polinomial kromatik dari sebuah segitiga adalaht(t1)(t2), dan jumlah orientasi asiklik adalah (1)3(1)(2)(3)=6 (semua 23 orientasi selain 2orientasi siklik).
Yuval Filmus
@YuvalFilmus terima kasih banyak. jadi ini masalah mengevaluasi polinomial di-λ.
seteropere

Jawaban:

5

Seperti yang dicatat Yuval, Anda dapat menghitung jumlah orientasi asiklik dengan mengevaluasi polinomial kromatik grafik pada kesatuan negatif. Untuk menghitung polinomial kromatik, ada algoritma efisien yang dikenal untuk beberapa kelas grafik .

Ada juga algoritma rekursif untuk menghasilkan semua orientasi asiklik dari grafik yang diberikan oleh Squire [1]. Algoritma membutuhkanHAI(n)waktu per orientasi asiklik yang dihasilkan. Sekitar 20 tahun yang lalu ini adalah algoritma tercepat yang diketahui; mungkin yang lebih cepat diketahui sekarang, atau Anda dapat meningkatkan algoritma Squire dengan teknik yang dikenal.


[1] Squire, MB (1998). Menghasilkan orientasi asiklik pada grafik. Jurnal Algoritma, 26 (2), 275-290.

Juho
sumber