Algoritmo para encontrar todas as orientações acíclicas de um gráfico

Estou trabalhando em orientações acíclicas de gráficos não direcionados e tenho as seguintes perguntas:

Dado o gráfico simples não direcionado conectado , como encontrar todas as orientações acíclicas possíveis de ? $G$ $G$
Qual é o número de orientações acíclicas? Sabe-se ( daqui ) ser para um gráfico com vértices onde é o polinômio cromático avaliado em ; mas não consegui entender como avaliar com um valor negativo ( ). $(-1)^p\ \chi(G,-\lambda)$ $G$ $p$ $\chi$ $-\lambda$ $\chi$ $-\lambda$

algorithms graph-theory counting seteropere
fonte

Re 2, é apenas um polinômio. Pode ser avaliado em qualquer ponto complexo. O número de orientações acíclicas é , onde é o número de vértices. Por exemplo, o polinômio cromático de um triângulo é e, portanto, o número de orientações acíclicas é (todas as orientações, exceto as orientações 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 muito obrigado. então é uma questão de avaliar o polinômio em .

- λ

$-\lambda$

Seteropere

Respostas:

Como Yuval observou, você pode contar o número de orientações acíclicas avaliando o polinômio cromático de um gráfico na unidade negativa. Para computação de polinômios cromáticos, existem algoritmos eficientes conhecidos para algumas classes de gráficos .

Existe também um algoritmo recursivo para gerar todas as orientações acíclicas de um gráfico fornecido por Squire [1]. O algoritmo requer $O(n)$ tempo por orientação acíclica gerada. Cerca de 20 anos atrás, esse foi o algoritmo mais rápido conhecido; é possível que um mais rápido seja conhecido agora ou que você possa melhorar o algoritmo do Squire por técnicas conhecidas.

[1] Squire, MB (1998). Gerando as orientações acíclicas de um gráfico. Journal of Algorithms, 26 (2), 275-290.

Juho
fonte