Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 24

Übungsaufgaben

Aufgabe

Bestimme die chromatische Zahl eines Rundganges.

Aufgabe

Bestimme die chromatische Zahl des Schmetterlingsgraphen.

Aufgabe

Das Seminar zum Thema „Gezielter Einsatz von Vorlesungshunden in schwierigen Zeiten“ beginnt mit Gruppenarbeit. In der ersten Runde war die Gruppenaufteilung folgendermaßen. Gruppe A: Erika, Sven, Peter, Petra. Gruppe B: Lutz, Mats, Petsi, Gruppe C: Anna,Lena, Christian, Doro, Henning, Gruppe D: Marion, Markus, Martin, Martina, Marianne. Für die zweite Runde soll eine neue Gruppenaufteilung vorgenommen werden, bei der Leute, die sich schon (durch die Gruppenarbeit in der ersten Runde) kennen, nicht zusammen in eine Gruppe kommen.

1. Was ist die minimale Anzahl an Gruppen, die dafür benötigt wird?
2. Wie viele Möglichkeiten für die zweite Gruppenaufteilung gibt es, wenn jede Gruppe zumindest drei Teilnehmer haben soll.
3. Wie sieht es für die dritte Gruppenaufteilung aus?

Aufgabe

Es sei ${}V$ eine endliche Menge mit einer Äquivalenzrelation ${}\sim$ und dem zugehörigen Graphen ${}G$, wobei die Schleifen ignoriert werden. Zeige, dass die chromatische Zahl von ${}G$ gleich dem Maximum der Größe der Äquivalenzklassen ist.

Aufgabe

Wir betrachten die Ringe der olympischen Ringe als Knotenpunkte eines Graphen, wobei zwei Knotenpunkte miteinander benachbart sein sollen, wenn sich die zugehörigen Ringe treffen. Was ist die chromatische Zahl dieses Graphen?

Aufgabe

Zeige, dass die chromatische Zahl ${}\chi (G)$ eines Graphen ${}G=(V,E)$ die folgenden Eigenschaften erfüllt.

1. Ein Graph ist genau dann nicht leer, wenn seine chromatische Zahl ${}\geq 1$ ist.
2. Ein nichtleerer Graph besitzt genau dann die chromatische Zahl ${}1$, wenn er keine Kanten besitzt.
3. Ein Graph ist genau dann bipartit, wenn seine chromatische Zahl ${}\leq 2$ ist.
4. Es ist

   ${}\chi (G)\leq {\#\left(V\right)}\,.$

5. Der vollständige Graph ${}K_{n}$ besitzt die chromatische Zahl ${}n$.

Aufgabe *

Bestimme sämtliche zulässigen Färbungen für den abgebildete Graphen mit den Farben rot, blau und grün.

Aufgabe

Es sei ${}f\colon G\rightarrow B$ eine zulässige Färbung auf einem Graphen ${}G$. Es sei ${}\theta \colon B\rightarrow B'$ injektiv. Zeige, dass auch ${}\theta \circ f$ eine zulässige Färbung auf ${}G$ ist.

Aufgabe

Es sei ${}\varphi \colon G\rightarrow H$ ein Graphhomomorphismus und ${}f\colon H\rightarrow B$ eine zulässige Färbung von ${}H$. Zeige, dass ${}f\circ \varphi$ eine zulässige Färbung von ${}G$ ist.

Zeige, dass diese Aussage nicht gilt, wenn ${}\varphi$ ein schwacher Graphhomomorphismus ist.

Aufgabe

Es sei ${}G$ ein Graph und ${}B$ eine Menge. Zeige, dass eine zulässige Färbung ${}f\colon G\rightarrow B$ dasselbe ist wie ein Graphhomomorphismus ${}f\colon G\rightarrow (B,{\mathfrak {P}}_{2}\,(B))$.

Kommentar:

Eine zulässige Färbung ${}f\colon G\rightarrow B$ ist nichts anderes als eine Abbildung, sodass ${}f(u)\neq f(v)$ ist, wenn ${}u$ und ${}v$ benachbart sind. Dies bedeutet, dass ${}\{f(u),f(v)\}$ eine Kante des vollständigen Graphen ${}(B,{\mathfrak {P}}_{2}\,(B))$ ist, wenn ${}\{u,v\}$ eine Kante von ${}G$ ist, d.h. ${}f\colon G\rightarrow (B,{\mathfrak {P}}_{2}\,(B))$ ist ein Graphhomomorphismus.

Diese Aufgabe besagt, dass man stattdessen Graphhomomorphismen untersuchen kann, um zulässige Färbungen von Graphen zu untersuchen. Siehe dazu Aufgabe 24.16. und Aufgabe 24.17..

 

Aufgabe

Zeige, dass das chromatische Polynom eines Baumes mit ${}n$ Knoten gleich ${}X(X-1)^{n-1}$ ist.

Aufgabe

Bestimme das chromatische Polynom eines Sterngraphen.

Aufgabe

Es sei ${}b$ ein Blatt eines Graphen ${}G$ und sei ${}H$ der Untergraph, bei dem ${}b$ und die zugehörige Kante entfernt wurde. Zeige, dass zwischen den chromatischen Polynomen die Beziehung

${}P_{G}=(X-1)P_{H}\,$

besteht.

Aufgabe *

Zeige durch Induktion über ${}n$, dass das chromatische Polynom eines Rundganges mit ${}n$ Knoten gleich ${}(X-1)^{n}+(-1)^{n}(X-1)$ ist.

Aufgabe *

Bestimme das chromatische Polynom zum vollständigen bipartiten Graphen ${}K_{2,s}$.

In den beiden folgenden Aufgaben bezeichnen wir mit ${}\operatorname {Hom} (G,H)$ die Menge der Graphhomomorphismen von ${}G$ nach ${}H$.

Aufgabe

Es sei ${}H$ ein fixierter Graph. Zeige, dass es zu einer Kante ${}e$ eines Graphen ${}G$ stets eine natürliche Identifizierung

${}\operatorname {Hom} (G\setminus \{e\},H)=\operatorname {Hom} (G,H)\uplus \operatorname {Hom} (G/e,H)\,$

gibt.

Kommentar:

Aufgrund von Aufgabe 24.10. handelt es sich bei dieser Aufgabe um eine Verallgemeinerung von Lemma 24.12  (1), die dem Fall entspricht, dass ${}H$ ein vollständiger Graph ist. Hier kann man ähnlich wie bei Lemma 24.12  (1) argumentieren. Sei ${}e=\{u,v\}$ und ${}f\in \operatorname {Hom} (G\setminus \{e\},H)$. Ist ${}f(u)\neq f(v)$, dann ist ${}f\in \operatorname {Hom} (G,H)$. Wenn andererseits ${}f(u)=f(v)$ ist, dann entspricht ${}f$ einem Element von ${}\operatorname {Hom} (G/e,H)$.

 

Aufgabe

Es sei ${}H$ ein Graph und sei ${}G=G_{1}\uplus G_{2}$ die disjunkte Vereinigung von Graphen ${}G_{1}$ und ${}G_{2}$. Zeige, dass es eine natürliche Identifizierung

${}\operatorname {Hom} (G,H)=\operatorname {Hom} (G_{1},H)\times \operatorname {Hom} (G_{2},H)\,$

gibt.

Zu einem Graphen ${}G=(V,E)$ und einem kommutativen Ring ${}R$ nennt man den Restklassenring

${}R[G]=R[X_{v},\,v\in V]/{\left(X_{u}X_{v}:\{u,v\}{\text{ ist keine Kante von }}G,\,X_{u}X_{v}X_{w},u,v,w{\text{ verschieden}}\right)}\,$

den Stanley-Reisner-Ring zu ${}G$ (über ${}R$).

Ein Stanley-Reisner-Ring ist eine Möglichkeit, einen ungerichteten Graphen in ein algebraisches Objekt zu übersetzen. In einem solchen Restklassenring werden also alle Monome mit zumindest drei verschiedenen Variablen zu ${}0$ gemacht und ein Monom mit zwei verschiedenen Variablen wird genau dann zu ${}0$ gemacht, wenn das zugehörige Knotenpaar keine Kante ist. Mit dem sogenannten Hilbertpolynom wird einem jeden ${}\mathbb {N}$- graduierten Ring ein Polynom zugeordnet. Im Falle eines Stanley-Reisner-Ringes zu einem ungerichteten Graphen ist dies besonders einfach.

Aufgabe

Es sei ${}G$ ein Graph mit ${}n$ Knoten und ${}m$ Kanten, sei ${}K$ ein Körper und ${}K[G]$ der Stanley-Reisner-Ring zu ${}G$ über ${}K$. Zeige, dass die ${}K$- Vektorraumdimension der ${}d$-ten Stufe ${}K[G]_{d}$ für ${}d\geq 1$ durch das lineare Polynom

${}P(d)=m(d-1)+n\,$

beschrieben wird.

Aufgaben zum Abgeben

Aufgabe (4 Punkte)

Zeige mit Lemma 24.12  (1), dass die chromatische Funktion ein normiertes Polynom ist.

Aufgabe (5 Punkte)

Bestimme das chromatische Polynom zum vollständigen bipartiten Graphen ${}K_{3,s}$.