Färbung isolierter Ecken < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Dies ist eigentlich schon die Lösung:Besteht G aus n isolierten Ecken,also ist er das Kompliment eines vollständigen Graphen,so gilt [mm] p(G;l)=l_hoch_n.
[/mm]
Wobei das p(G;l) für die Anzahl der l-Färbungen von G beschreibt. |
Hallo,
es ist bestimmt ganz leicht und ich habe eine denkblockade aber ich hätte gesagt das bei isolierten Ecken eher alle Ecken bei einer Färbung dieselbe Farbe bekommen da unverbunden.Also wäre mein Ergebnis p(G;l)=l.Kann mir sagen wo mein gedankenfehler liegt?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
ups,ich habe den ausdrück falsch verstanden.jetzt begreife ich wie es gemeint ist,es ist einfach nur der chromatische polynom
|
|
|
| |
|
Hallo neugierige26!
> Dies ist eigentlich schon die Lösung:Besteht G aus n
> isolierten Ecken,also ist er das Kompliment eines
> vollständigen Graphen,so gilt [mm]p(G;l)=l_hoch_n.[/mm]
> Wobei das p(G;l) für die Anzahl der l-Färbungen von G
> beschreibt.
> Hallo,
> es ist bestimmt ganz leicht und ich habe eine denkblockade
> aber ich hätte gesagt das bei isolierten Ecken eher alle
> Ecken bei einer Färbung dieselbe Farbe bekommen da
> unverbunden.Also wäre mein Ergebnis p(G;l)=l.Kann mir sagen
> wo mein gedankenfehler liegt?
l-Färbung soll wohl bedeuten, dass man den Graph mit l Farben färbt, oder? Wenn du dann einen Graphen hast, bei dem du jeden Knoten in jeder beliebigen Farbe färben darfst - unabhängig von allen anderen Knoten (weil du ja nur isolierte Knoten hast), dann hast du für jeden Knoten genau l viele Möglichkeiten, diesen Knoten zu färben. Und bei insgesamt l Knoten ergibt das [mm] l^n [/mm] Möglichkeiten.
Alles klar?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Danke Bastiane,
bin weniger kombinatorisch an die sache rangegangen,sondern folgendermassen gedacht:zuesrt kann ich sie alle grün färben,dann alle rot,dann... und zusammen sin es 1+1+..+1=l*1 Möglichkeiten.
|
|
|
|
