Wald mit c Bäume: Knoten färben

Aufrufe: 75     Aktiv: 27.06.2021 um 16:46

0





Hallo!

kann mir hier jemand weiterhelfen? Ich bin mir recht unsicher mit meiner Lösung.

 

Also ich habe folgendes:

 

Ein Wald ist ja ein ungerichteter Graph, dass bedeutet die Anzahl der Knoten |V| beträgt höchstens (n^2 - 1) / 2

Wir haben k >= 2 Farben zur Verfügung. 

 

Das heißt wir müssen uns zuerst klar machen, wieviele "Färb"-Varianten bzw. Möglichkeiten es gibt, das wäre dann k^( (n^2 - 1) / 2 )

Nachdem, dem es sich hier aber um einen Wald mit c Bäume handelt, müssen wir das ganze noch mit c multiplizieren d.h. das Resultat lautet dann: 

 

=> c * [k^( (n^2 - 1) / 2 )]

 

 

 

Diese Frage melden
gefragt

Punkte: 36

 
Kommentar schreiben
1 Antwort
0
Hat a) jeder Baum $n$ Knoten oder haben b) alle $c$ Bäume insgesamt $n$ Knoten? Ich verstehe die Aufgabe wie b), dann ist aber auf jeden Fall $|V|=n$.
Diese Antwort melden
geantwortet

Punkte: 690

 

Kommentar schreiben