Algoritmo para encontrar todas las orientaciones acíclicas de un gráfico

Estoy trabajando en orientaciones acíclicas de gráficos no dirigidos y tengo las siguientes preguntas:

Dado el gráfico simple no dirigido conectado , ¿cómo encontrar todas las orientaciones acíclicas posibles de ? $G$ $G$
¿Cuál es el número de orientaciones acíclicas? Se sabe (de aquí ) que es para un gráfico con vértices donde es el polinomio cromático evaluado en ; pero no tuve éxito en comprender cómo evaluar en un valor negativo ( ). $(-1)^p\ \chi(G,-\lambda)$ $G$ $p$ $\chi$ $-\lambda$ $\chi$ $-\lambda$

algorithms graph-theory counting seteropere
fuente

Re 2, es solo un polinomio. Se puede evaluar en cualquier punto complejo. El número de orientaciones acíclicas es , donde es el número de vértices. Por ejemplo, el polinomio cromático de un triángulo es , por lo que el número de orientaciones acíclicas es (todas las orientaciones distintas de las orientaciones cíclicas).

χ (G, \cdot)

$\chi(G,\cdot)$

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

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

p

$p$

t (t - 1) (t - 2)

$t(t-1)(t-2)$

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

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

2^{3}

$2^3$

2

$2$

Yuval Filmus

@YuvalFilmus muchas gracias. entonces es cuestión de evaluar el polinomio en .

- λ

$-\lambda$

seteropere

Respuestas:

Como señaló Yuval, puede contar el número de orientaciones acíclicas evaluando el polinomio cromático de un gráfico en la unidad negativa. Para calcular polinomios cromáticos, existen algoritmos eficientes conocidos para algunas clases de gráficos .

También hay un algoritmo recursivo para generar todas las orientaciones acíclicas de un gráfico dado por Squire [1]. El algoritmo requiere tiempo por orientación acíclica generada. Hace aproximadamente 20 años, este era el algoritmo más rápido conocido; es posible que ahora se conozca uno más rápido o que pueda mejorar el algoritmo de Squire mediante técnicas conocidas. $O(n)$

[1] Squire, MB (1998). Generando las orientaciones acíclicas de un gráfico. Diario de Algoritmos, 26 (2), 275-290.

Juho
fuente