Transcript
ETH Zürich Institut für Theoretische Informatik Prof. Dr. Emo Welzl Dr. Johannes Lengler
HS 2014 Lösungsvorschlag zu Übungsblatt 5
Diskrete Mathematik (D-ITET)
Aufgabe 1 (a) Sei G = (A ] B, E) ein k-regulärer bipartiter Graph. Wir zählen die Kanten des Graphen G, indem wir entweder die Grade aller Knoten in A aufsummieren, oder indem wir die Grade aller Knoten in B aufsummieren (doppeltes Abzählen). Wir erhalten |E| = k|A| = k|B| und damit |A| = |B|. Nach Satz 2.51 aus dem Skript (Satz von Hall) gibt es in G ein Matching der Kardinalität |A| (das wegen |A| = |B| ein perfektes Matching ist), falls für jede Menge A0 ⊆ A folgende Bedingung gilt: |Γ(A0 )| ≥ |A0 |. Sei A0 ⊆ A. Wir betrachten den bipartiten GraphenP G0 , der von A0 ∪ Γ(A0 ) induziert wird. Doppeltes Abzählen der Kanten von G0 ergibt 0 k|A | = v∈Γ(A0 ) degG0 (v) ≤ |Γ(A0 )|k, da der Grad eines jeden Knotens in G0 nicht grösser ist als der Grad in G. Division durch k liefert die gewünschte Ungleichung. Der Satz von Hall liefert uns also zunächst ein perfektes Matching in G. Entfernen wir dieses, so verbleibt ein (k − 1)-regulärer Graph, auf den wir das obige Vorgehen wiederholt anwenden können. Insgesamt erhalten wir also eine Partition der Kantenmenge von G in k disjunkte perfekte Matchings. (4 Punkte) (b) Bob hat recht. Um dies einzusehen, betrachten wir den Sachverhalt graphentheoretisch: Wir wählen einen bipartiten Graphen mit den Knotenklassen {l1 , l2 , . . . , l8 } für die acht Länder und {1, 2, 5, 10, 20, 50, 100, 200} für die Werte der Münzen in Cent, und wir fügen eine Kante {l, w} ein, genau dann wenn Alice eine Münze aus dem Land l vom Wert w mitgebracht hat. Aus der Aufgabenstellung folgt, dass der so konstruierte Graph 5-regulär ist. Das Ergebnis von Teilaufgabe (a) liefert uns unmittelbar die Existenz eines perfekten Matchings in diesem Graphen, d.h. eine Menge von acht Münzen aus acht verschiedenen Ländern und von allen acht Münzwerten. Diese Münzen (im Gesamtwert von 3,88 Euro) kann Alice an ein Kind verteilen. Entfernen wir die Kanten des entsprechenden perfekten Matchings aus dem Graphen, so ist der verbleibende bipartite Graph 4-regulär, und wir finden leicht ein weiteres perfektes Matching. Wenden wir dieses Argument wiederholt an, so ist die Verteilung aller Münzen an die Kinder auf die geforderte Weise offenbar kein Problem. Man beachte, dass der so konstruierte Graph gemäss Aufgabenstellung keine Mehrfachkanten besitzt (mehrere Münzen vom selben Wert aus demselben Land). Satz 2.51 und Satz 2.53 gelten jedoch unverändert auch für Graphen mit Mehrfachkanten, sodass diese Bedingung eigentlich überflüssig ist. (4 Punkte) (c) Sei ein lateinisches r × n-Rechteck gegeben, so konstruieren wir daraus einen bipartiten Graphen G = (S ] {1, . . . , n}, E), wobei S := {s1 , . . . , sn } die Menge der Spalten ist, und eine Spalte si mit genau denjenigen Zahlen aus der Menge {1, . . . , n} durch eine Kante verbunden ist, die in dieser Spalte nicht vorkommen. Wir zeigen im Folgenden, dass alle Knoten in G genau Grad n − r besitzen; dann können wir mit den Ergebnissen aus Teilaufgabe (a) ebensoviele disjunkte perfekte Matchings in G finden. Jedes dieser Matchings gibt an, wie eine weitere Zeile des Ausgangsrechtecks ohne Widersprüche ausgefüllt werden kann (so dass am Ende ein lateinisches n × n-Quadrat entsteht). Zunächst einmal gilt in G sicherlich deg(si ) = n − r. Weiterhin kommt jede der Zahlen 1, . . . , n in den ersten r Zeilen des Ausgangsrechtecks genau einmal vor, insgesamt also in genau r Spalten (und in genau n − r Spalten nicht). Damit gilt also auch deg(i) = n − r für alle i = 1, . . . , n, und G ist tatsächlich (n − r)-regulär. (4 Punkte) 1
Aufgabe 2 (a) Wir bezeichnen mit V , E und R die Menge der Knoten, Kanten bzw. Gebiete einer gegebenen Triangulierung. Wir betrachten die Zahl N := |{(e, r) | e ∈ E, r ∈ R, e begrenzt r}|. Da jedes Gebiet von genau drei Kanten begrenzt wird, ist N = 3|R|. Da andererseits jede Kante genau zwei Gebiete begrenzt, ist auch N = 2|E|. Zusammen folgt, dass 3|R| = 2|E| ist, oder äquivalent dazu |R| = 32 |E|. Nach der Eulerschen Polyederformel gilt aber |R| = |E| − |V | + 2 für alle zusammenhängenden Graphen mit |V | ≥ 3. Setzen wir obige Beziehung für |R| ein und lösen nach |E| auf, so erhalten wir 1 |E| = |V | − 2. 3 Multiplikation mit 3 liefert wie gewünscht, dass die Zahl der Kanten 3|V | − 6 ist. Ist umgekehrt G planar, aber keine Triangulierung, so wird mindestens ein Gebiet von mindestens vier Kanten begrenzt. Daher ist N > 3|R|, aber immer noch N = 2|E|. Zusammen folgt 3|R| < N = 2|E|. Dieselbe Umformung wie oben zeigt mit Hilfe der Eulerschen Polyederformel, dass |E| < 3n − 6 ist. Wir haben also gezeigt, dass für jeden planaren Graphen mit mindestens drei Knoten, der keine Triangulierung ist, |E| 6= 3n − 6 gilt. Aufgrund des Kontrapositionsprinzips ist daher jeder planare Graph mit mindestens drei Knoten, für den |E| = 3n − 6 gilt, schon eine Triangulierung. (4 Punkte) (b) Hat G = (V, E) jeder Knoten höchstens Grad 5, so gilt |E| = P in einer Triangulierung 1 5 deg(v) ≤ |V |. v∈V 2 2 Nach Teil (a) ist aber |E| = 3|V | − 6, und daher 3|V | − 6 ⇔
|V |
5 |V | 2 ≤ 12. ≤
Also kann eine solche Triangulierung höchstens 12 Knoten haben. Anmerkung: Die errechnete Schranke ist scharf, da es einen 5-regulären planaren Graphen mit 12 Knoten gibt. Ein Beispiel ist der Kantengraph des Ikosaeder (Abbildung im Skript auf Seite 41). (2 Punkte)
Aufgabe 3 (a)
(2 Punkte)
(b) Sei G = (V, E) ein Graph mit sechs Knoten und 13 Kanten. Dann gilt |E| = 13 > 12 = 3 · 6 − 6 = 3|V | − 6 und somit folgt aus Satz 2.57, dass der Graph nicht planar ist. (1 Punkt) (c) Sei G =P (V, E) ein planarer Graph, in dem jeder Knoten mindestens Grad 4 hat. Dann gilt |E| = 12 v∈V deg(v) ≥ 12 4|V | = 2|V |. Setzen wir dies in die eulersche Polyederformel ein, so erhalten wir für die Anzahl der Gebiete |E| − |V | + 2 ≥ 2|V | − |V | + 2 = |V | + 2. (2 Punkte)
2
(d) Der erste Graph ist nicht planar, denn er enthält eine Unterteilung des K3,3 als Untergraphen. Der zweite Graph ist planar, denn man kann ihn überschneidungsfrei in der Ebene zeichnen. (3 Punkte)
Aufgabe 4 (a) Die fehlenden Werte des Flusses ergeben sich aus der Flusserhaltung der Reihe nach wie folgt: f (a, b) = 5,
f (c, b) = 4,
f (c, d) = 1,
f (c, e) = 6,
f (e, t) = 7.
Der Wert des Flusses lässt sich als vorzeichenbehaftete Summe der aus s herausfliessenden Ströme berechnen: val(f ) = f (s, a) + f (s, c) + f (s, d) = 8 + 8 + 0 = 16, oder auch als vorzeichenbehaftete Summe der in t hineinfliessenden Ströme: val(f ) = f (b, t) + f (e, t) = 9 + 7 = 16.
(2 Punkte)
(b) Ein augmentierender Pfad ist (s, d, e, c, a, b, t). Entlang dieses Pfades kann man den Fluss maximal um den Wert 3 erhöhen, da der Fluss entlang der Kante (a, c) maximal um 3 vermindert werden kann. Kapazität von 3 hat. Der Wert des erhöhten Flusses f˜ beträgt 16 + 3 = 19. (Bemerkung: ein anderer möglicher augmentierender Pfad ist z.B. (s, d, c, a, b, t).) Nun beweisen wir die Maximalität des neuen Flusses. Der s-t-Schnitt (S, T ) mit S = {s, c, d, e} und T = {a, b, t} hat die Kapazität c(s, a) + c(c, b) + c(e, t) = 8 + 4 + 7 = 19. Da val(f˜) = 19 = cap(S, T ) ist nach Satz 2.66 (Maxflow-Mincut-Theorem) der Schnitt (S, T ) minimal und der Fluss f˜ maximal. (4 Punkte)
3
