Chromatisches Polynom

Aufrufe: 269     Aktiv: 26.07.2024 um 15:38
Jetzt Frage stellen
0
Hallo,

ich habe probleme das chromatische Polynom zu verstehen und bekomme auch leider keine Hilfe von meinem Dozenten/Tutorium.

Für einen vollständigen Graphen habe ich es verstanden, aber für "zusammengesetzte" Graphen leider nicht.

Gibt es hier jemanden, der das anschaulich erklären kann und nicht zu "mathematisch".

Vielen Dank

EDIT vom 21.07.2024 um 19:01:

Hierzu steht die Formel: M_G (Lambda) = M_G' (Lambda) + M_G'' (Lambda) Da verstehe ich nicht, wie die untere Rechnung zustande kommt. Also die Schritte dahin.
Diese Frage melden
gefragt

Punkte: 21

 
Was hat denn Dein Dozent/Tutor Dir geantwortet, und was daran hast Du nicht verstanden? Es gibt zig Erklärungen/Beispiele/Erläuterungen im Netz, was daran reicht Dir nicht? Suche eine dieser vielen Erklärungen, nenn uns die Quelle und dazu Deine konkrete(!) Frage, dann können wir helfen.   ─   mikn 20.07.2024 um 12:29
Zu erst einmal würde ich gerne wissen, was ein "zusammengesetzer" Graph ist? Ich habe eine Vermutung, aber ich will es von dir hören. Vielleicht kann @mikn das auch sagen, was gemeint ist.   ─   crystalmath 20.07.2024 um 13:05
Mit einem zusammengesetzten Graph ist wohl ein Graph wie das Haus vom Nikolaus gemeint, also ein K_4 der an einem K_3 angesetzt ist und sich zwei Knoten überlappen.

Es gibt eine Rechnung, die ich nicht verstehe, in der eine Kante erst in dem Graphen hinzugefügt wird und in einem späteren Schritt dann auch zwei Knoten zusammengefasst werden um das chromatische Polynom zu berechnen. Die beiden Graphen G' und G'' werden dann addiert in der Rechnung.

Nen Großteil habe ich jetzt nach und nach verstanden, Aber da verstehe ich die Zusammenhänge und die Rechnung einfach nicht. Leider sind die meisten Quellen auch auf Englisch :(   ─   ich123 21.07.2024 um 10:53
Es gibt eine Formel, mit der man diese chromatischen Polynome zu jedem Graphen ausrechnen kann.
Man findet sie z.B. in der Wikipedia: https://de.wikipedia.org/wiki/Chromatisches_Polynom
Dort steht: \( \kappa(G,\lambda) \;=\; \kappa(G\setminus\{e\},\lambda) \;-\; \kappa(G/\{e\},\lambda)\),
wobei e eine beliebige Kante von G ist,
und \(G\setminus\{e\}\) der Graph G ohne die Kante G ist,
und \(G/\{e\}\) ist der Graph G, der durch "Kantenkontraktion" von entsteht.

Meinst Du diese Formel?
   ─   m.simon.539 21.07.2024 um 12:32
Lade die erwähnte Rechnung hoch (oben "Frage bearbeiten"), und dazu lass uns genau die Stellen wissen, an denen Du Probleme hast, und was genau(!) das Problem ist. Lass uns hier nicht raten.   ─   mikn 21.07.2024 um 12:35
Entschuldigen Sie bitte die Umstände, mir werden leider die Antworten nicht angezeigt.   ─   ich123 21.07.2024 um 19:03
Zu Ihrer Eingangsfrage, wir haben eine Quelle bekommen die wir selber bearbeiten müssen. Leider auf englisch :(. Mein Tutor hatte gesagt: "das müssen ja nicht so viele machen, daher behandeln wir es nicht". Die Rechnung müssen nur eine Handvoll Leute machen.   ─   ich123 21.07.2024 um 19:07
Ja, wir kommentieren ja bisher nur, und Kommentare werden Dir nicht angezeigt. Wir haben ja bisher nichts gehabt, worauf wir antworten können. Jetzt sind wir schonmal weiter. Ich persönlich weiß aber nicht, was $M_G(\lambda)$ sein soll. Du bekommst wesentlich schneller Hilfe, wenn Du nicht häppchenweise Deine Frage ergänzt, sondern unaufgefordert vollständige Info lieferst.   ─   mikn 21.07.2024 um 19:22
Ich vermute, \(M_G\) ist das chromatische Polynoms des Graphen G.
G' ist der Graph, der aus G durch Hinzufügen einer beliebigen Kante e hervorgeht.
G'' ist der Graph, der durch Kontrahieren dieser Kante e aus G' hervorgeht.
Dann gilt in der Tat die Formel \(M_G = M_{G'} + M_{G''}\).
Diese Formel ist äquivalent zur von mir o.g. Wikipedia-Formel.
Diese Formel wird immer wieder, bei jeden Gleichheitszeichen in Deiner Rechnung, angewandt - außer beim letzten.
Immer wieder wird eine Kante hinzugefügt, und die wird dann wieder kontrahiert.
Das macht man so lange, bis nur noch vollständige Graphen dastehen.

Beim letzten Gleichheitszeichen wird verwendet, dass das chromatische Polynom eines vollständigen Graphen mit n Knoten = \(\lambda^{(n)}\) ist.
Dabei ist \(\lambda^{(n)} = \lambda (\lambda-1) \cdot \ldots \cdot (\lambda-n+1)\).

   ─   m.simon.539 26.07.2024 um 01:46
@m.simon So richtig groß scheint das Interesses des Fragys nicht zu sein. Aber schreib Deinen Kommentar doch als Antwort (denn das ist es ja), dann wird ja benachrichtigt.   ─   mikn 26.07.2024 um 09:56
Sorry, ich war verhindert. Erstmal vielen Dank für die Antworten.   ─   ich123 26.07.2024 um 15:32
Kommentar schreiben
1 Antwort
0
Ich vermute, \(M_G\) ist das chromatische Polynoms des Graphen G.
G' ist der Graph, der aus G durch Hinzufügen einer beliebigen Kante e hervorgeht.
G'' ist der Graph, der durch Kontrahieren dieser Kante e aus G' hervorgeht.
Dann gilt in der Tat die Formel \(M_G = M_{G'} + M_{G''}\).
Diese Formel ist äquivalent zur von mir o.g. Wikipedia-Formel.
Diese Formel wird immer wieder, bei jeden Gleichheitszeichen in Deiner Rechnung, angewandt - außer beim letzten.
Immer wieder wird eine Kante hinzugefügt, und die wird dann wieder kontrahiert.
Das macht man so lange, bis nur noch vollständige Graphen dastehen.

Beim letzten Gleichheitszeichen wird verwendet, dass das chromatische Polynom eines vollständigen Graphen mit n Knoten = \(\lambda^{(n)}\) ist.
Dabei ist \(\lambda^{(n)} = \lambda (\lambda-1) \cdot \ldots \cdot (\lambda-n+1)\).
Diese Antwort melden
geantwortet

Punkte: 2.52K

 
Vielen Dank.
Aber wirklich verstehen tue ich es dennoch nicht. Das Lambda steht ja für die chromatische Zahl, also die Anzahl Farben, die mindestens gebraucht werden um den Graph zu Färben, ohne das benachbarte Knoten die selbe Farbe haben.

Was muss ich den hier, bezogen auf das Beispiel wirklich rechnen?
M_G = M_G′ + M_G′′
   ─   ich123 26.07.2024 um 15:38

Kommentar schreiben

Jetzt Antwort schreiben