Jak obliczyć sposoby malowania drzewa?

Jak obliczyć sposoby malowania węzłów drzewa za pomocą m kolorów, aby końce każdej krawędzi miały różne kolory?Jak obliczyć sposoby malowania drzewa?

Każde rozwiązanie wielomianowe jest mile widziane.

Źródło

2016-09-20 newbie

Tak, szukam wielu sposobów. – newbie

Czy musi używać wszystkich m kolorów? – Bergi

Nie potrzebujesz żadnego algorytmu, wystarczy zastosować formułę 'O (1)' (zakładając, że nie musisz najpierw liczyć węzłów): https://en.wikipedia.org/wiki/Chromatic_polynomial#Examples – Bergi

Masz m wyborów dla root. Jeśli malujesz schodząc z katalogu głównego, masz wybór m-1 dla każdego dodatkowego węzła. Jeśli liczba węzłów wynosi n, to liczba sposobów malowania drzewa to m * (m-1)^(n-1).

Źródło

2016-09-20 11:55:32 Dave

co z n = 1 i m = 1 w twoim rozwiązaniu? – v78

@ dd2 wpisz 'n = 1' i' m = 1' w podanej formule, a otrzymasz poprawną odpowiedź, jak wspomniałem w komentarzu do twojej odpowiedzi. –

@ dd2 0^0 = 1. Jest to konwencja, a nie taka, której powszechnie się uczy. https://www.quora.com/What-is-0-0-the-zeroth-power-of-zero-1 – Dave

Jak obliczyć sposoby malowania drzewa?

Odpowiedz

Powiązane problemy