Algoritma untuk menemukan semua orientasi asiklik suatu grafik

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

Diberikan terhubung grafik sederhana yang tidak terarah , bagaimana menemukan semua kemungkinan orientasi asiklik ? $G$ $G$
Berapa jumlah orientasi asiklik? Diketahui (dari sini ) adalah $(-1)^p\ \chi(G,-\lambda)$ untuk sebuah grafik $G$ dengan $p$ simpul mana $\chi$ adalah polinomial kromatik yang dievaluasi pada $-\lambda$ ; tetapi saya tidak berhasil memahami cara mengevaluasi $\chi$ pada nilai negatif ( $-\lambda$ ).

algorithms graph-theory counting seteropere
sumber

Re 2,

χ (G, \cdot)

$\chi(G,\cdot)$ hanyalah polinomial. Itu dapat dievaluasi pada setiap titik kompleks. Jumlah orientasi asiklik adalah

(- 1)^{p} χ (G, - 1)

$(-1)^p \chi(G,-1)$ dimana

p

$p$ adalah jumlah simpul. Sebagai contoh, polinomial kromatik dari sebuah segitiga adalah

t (t - 1) (t - 2)

$t(t-1)(t-2)$ , dan jumlah orientasi asiklik adalah

(- 1)^{3} (- 1) (- 2) (- 3) = 6

$(-1)^3(-1)(-2)(-3) = 6$ (semua

2^{3}

$2^3$ orientasi selain

2

$2$ orientasi siklik).

Yuval Filmus

@YuvalFilmus terima kasih banyak. jadi ini masalah mengevaluasi polinomial di

- λ

$-\lambda$ .

seteropere

Jawaban:

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 membutuhkan $O(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