Graphenfärbung n Knoten mit k Farben färben

11.11.2018, 16:01

CrazyGhosty

Graphenfärbung n Knoten mit k Farben färben

Meine Frage:
Hallo,

ich hänge aktuell an einer Aufgabe zur Graphenfärbungskombinatorik. Ich habe mehrere Ideen an einem Beispiel ausprobiert, jedoch bekomme ich nicht die richtigen Werte raus.

1. Wie viele Möglichkeiten gibt es, n Knoten mit k Farben zu färben?
2. Wenn es n Farbaufkleber, und zwar $\begin{eqnarray*} n_{1} \end{eqnarray*}$ Stück der Farbe $\begin{eqnarray*} f_{1}, n_{2} \end{eqnarray*}$ Stück der Farbe $\begin{eqnarray*} f_{2}, ..., n_{k} \end{eqnarray*}$ viele der Farbe $\begin{eqnarray*} f_{k} \end{eqnarray*}$ gibt, wie viele Möglichkeiten gibt es dann, die n Knoten eines Graphen damit zu färben ?

Da 2. eine Variation von 1. ist komme ich da natürlich auch nicht weiter.

Meine Ideen:
Ich habe mir überlegt, dass man erstmal für jede Farbe einen Knoten färbt. Das wäre dann $\begin{eqnarray*} \frac{n!}{(n-k)!} \end{eqnarray*}$ richtig?
Dannach komme ich dann leider nicht weiter.

Vielleicht kann ja jemand mir helfen smile

11.11.2018, 16:25

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von CrazyGhosty
Ich habe mir überlegt, dass man erstmal für jede Farbe einen Knoten färbt. Das wäre dann $\begin{eqnarray*} \frac{n!}{(n-k)!} \end{eqnarray*}$ richtig?

Das wäre die richtige Antwort zu 1. für den Fall "ohne Wiederholung", d.h., wenn keine Farbe mehrfach verwendet werden darf. Das enstpricht dem Spezialfall $\begin{eqnarray*} n_1=n_2=\ldots=n_k=1 \end{eqnarray*}$ von 2.
(Ok, es ist doch nicht ganz 2., denn dort lautet ja noch die Gesamtbedingung, dass genau $\begin{eqnarray*} n \end{eqnarray*}$ Aufkleber verfügbar sind - das stimmt bei dieser Zuordnung nicht).

11.11.2018, 16:34

CrazyGhosty

Auf diesen Beitrag antworten »

Aber mir würde dann ja noch bei 1. der andere Teil Fehlen, also dass ich auf die restlichen verbliebenen Plätze beliebige Farben verteilen darf. Ich habe ein kleines Programm geschrieben, dass mir für n=4 und k=3 nur die Kombinationen ausgibt, bei denen jede Farbe mindestens einmal verwendet wurde. Das Ergebnis wäre 36. Aber für diese Werte kommt $\begin{eqnarray*} \frac{4!}{(4-3)!} = 4*3*2 = 20 \end{eqnarray*}$ raus.

12.11.2018, 09:04

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von CrazyGhosty
Aber mir würde dann ja noch bei 1. der andere Teil Fehlen, also dass ich auf die restlichen verbliebenen Plätze beliebige Farben verteilen darf.

Was meinst du mit "restliche" Plätze? Es gibt die Variante "mit Wiederholung", d.h., jeder Knoten darf mit jeder Farbe gefärbt werden, ohne Rücksicht darauf, wie oft diese Farbe anderswo schon Verwendung findet.

Dann ist die Färbungsanzahl gemäß "Variationen mit Wiederholung" gleich $\begin{eqnarray*} k^n \end{eqnarray*}$ .

Und beim ersten Fall "Variationen ohne Wiederholung", also keine Farbe kommt mehrfach vor, habe ich deinen Beitrag leider nur oberflächlich gelesen: In diesem Fall ist die Färbungsanzahl $\begin{eqnarray*} \frac{k!}{(k-n)!} \end{eqnarray*}$ , d.h., die Rollen von $\begin{eqnarray*} n \end{eqnarray*}$ und $\begin{eqnarray*} k \end{eqnarray*}$ sind gegenüber deiner Formel oben vertauscht! Und das ganze macht natürlich nur Sinn, wenn es mindestens soviel Farben wie Knoten gibt, also $\begin{eqnarray*} k\geq n \end{eqnarray*}$ .

Zitat:

Original von CrazyGhosty
Ich habe ein kleines Programm geschrieben, dass mir für n=4 und k=3 nur die Kombinationen ausgibt, bei denen jede Farbe mindestens einmal verwendet wurde.

Was hat das mit Aufgabenstellung 1. zu tun? Von einer Bedingung, dass jede Farbe mindestens einmal verwendet werden soll, lese ich da nichts. unglücklich

"Mit $\begin{eqnarray*} k \end{eqnarray*}$ Farben" färben bedeutet gewöhnlich, dass $\begin{eqnarray*} k \end{eqnarray*}$ Farben zur Verfügung stehen - aber nicht, dass man auch wirklich alle $\begin{eqnarray*} k \end{eqnarray*}$ Farben zur Färbung der $\begin{eqnarray*} n \end{eqnarray*}$ Knoten verwenden muss. Wenn dies der Fall sein soll, dann muss man dies extra deutlich machen!

Kommen wir zu 2.: Dort sind anscheinend genauso viele Farbaufkleber vorhanden, wie es Knoten gibt, d.h. es ist $\begin{eqnarray*} n_1+\ldots+n_k=n \end{eqnarray*}$ . Die Anzahöl möglicher Färbungen ergibt sich gemäß Permutationen mit Wiederholung als $\begin{eqnarray*} \frac{n!}{n_1!\cdot n_2!\cdot \ldots\cdot n_k!} \end{eqnarray*}$ .

12.11.2018, 09:41

CrazyGhosty

Auf diesen Beitrag antworten »

Naja ganz einfach, weil die Aufgabenstellung so ungenau ist, will ich das lieber noch dazu schreiben. Grade weil da steht, dass man den Graphen eben mit diesen k Farben färben soll. Naja auf jeden Fall habe ich das mittlerweile. Trotzdem danke für deine Hilfe smile

12.11.2018, 09:52

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von CrazyGhosty
Naja auf jeden Fall habe ich das mittlerweile.

Hast du was? Die komplette Aufgabenstellung, d.h., mit Bereinigung obiger Unklarheiten? verwirrt

Wenn die Fragestellung abweichend zu oben

Zitat:

1. Wie viele Möglichkeiten gibt es, $\begin{eqnarray*} n \end{eqnarray*}$ Knoten mit $\begin{eqnarray*} k \end{eqnarray*}$ Farben zu färben, so dass jede Farbe mindestens einmal verwendet wird?

lautet, dann ist die Antwort eben nicht mehr $\begin{eqnarray*} k^n \end{eqnarray*}$ , sondern deutlich komplizierter $\begin{eqnarray*} \sum_{j=0}^k (-1)^j \binom{k}{j} (k-j)^n \end{eqnarray*}$ , entwickelt per Siebformel.

Im Fall $\begin{eqnarray*} n=4,k=3 \end{eqnarray*}$ ergibt das tatsächlich $\begin{eqnarray*} 3^4-3\cdot 2^4+3\cdot 1^4 = 81-48+3=36 \end{eqnarray*}$ , also den von dir auch ermittelten Wert.

Neue Frage »

Antworten »

Graphenfärbung n Knoten mit k Farben färben

Verwandte Themen