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.
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.
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).
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
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