Wie berechnet man die Möglichkeiten, die Knoten eines Baums mit m Farben zu malen, so dass die Enden jeder Kante unterschiedliche Farben haben?Wie berechnet man die Möglichkeiten, einen Baum zu malen?
Jede polynomiale Lösung ist willkommen.
Wie berechnet man die Möglichkeiten, die Knoten eines Baums mit m Farben zu malen, so dass die Enden jeder Kante unterschiedliche Farben haben?Wie berechnet man die Möglichkeiten, einen Baum zu malen?
Jede polynomiale Lösung ist willkommen.
Sie haben eine Auswahl für die Wurzel. Wenn Sie von der Wurzel ausgehend malen, haben Sie m-1 Auswahlmöglichkeiten für jeden weiteren Knoten. Wenn die Anzahl der Knoten n ist, ist die Anzahl der Möglichkeiten, den Baum zu malen, m * (m-1)^(n-1).
Was ist mit n = 1 und m = 1 in Ihrer Lösung? – v78
@ dd2 setze 'n = 1' und 'm = 1' in die gegebene Formel und du wirst die richtige Antwort erhalten, wie ich im Kommentar zu deiner Antwort erwähnt habe. –
@ dd2 0^0 = 1. Es ist eine Konvention, und nicht eine, die allgemein gelehrt wird. https://www.quora.com/What-is-0-0-the-zeroth-power-of-zero-1 – Dave
Ja, ich suche nach Wegen. – newbie
Muss es alle m Farben verwenden? – Bergi
Sie brauchen keinen Algorithmus, Sie müssen lediglich eine 'O (1)' Formel anwenden (vorausgesetzt, Sie müssen die Knoten nicht zuerst zählen): https://en.wikipedia.org/wiki/Chromatic_polynomial#Examples – Bergi