Ausarbeitung.

Graphentheorie
Gatschelhofer Doris, 0713319
Seminar - Diskrete Mathematik und Algorithmentheorie
SS2015
1
Inhaltsverzeichnis
0 Vorwort
3
1 Grundlagen
4
1.1
Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2
Klassen von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2 Das Königsberger Brückenproblem
8
2.1
Das Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2
Die Lösung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.2.1
Die Übersetzung der Karte in einen Graphen . . . . . . . . . . . . .
9
2.2.2
Die Übersetzung des Problems . . . . . . . . . . . . . . . . . . . . .
9
2.3
Durchlaufbarkeit von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Planare Graphen
12
3.1
Ecken- und Kantenordnung . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2
Hinführung zur Eulerschen Polyederformel . . . . . . . . . . . . . . . . . . . 13
3.3
Planarität und Plättbarkeit von Graphen . . . . . . . . . . . . . . . . . . . 18
2
0 Vorwort
Die Graphentheorie hat sich zu einem zentralen Thema der diskreten Mathematik entwickelt. Eine große Anzahl an modernen Entwicklungen und Problemstellungen benötigen zur optimalen Lösung Methoden aus diesem Gebiet. Graphen dienen als Analysemodell zum Beispiel bei Computernetzwerken, Verkehrsnetzen, Versorgungsnetzen und in der
Wirtschaft.
Als Quellen für die vorliegende Arbeit dienten die Werke Diskrete Mathematik für
Einsteiger (Albrecht Beutelspacher, Marc-A. Zschiegner) und Leitfaden Geometrie
(Susanne Müller-Philipp, Hans-Joachim Gorski).
3
1 Grundlagen
1.1 Einführung
Graphen besitzen Ecken und Kanten1 , wobei eine Kante genau zwei Ecken verbindet. Zwei
Ecken können also durch keine, eine oder mehr Kanten verbunden sein.
Aus Gründen der Übersichtlichkeit werden im folgenden Text Graphen mit G, die Eckenmenge mit E und die Kantenmenge mit K abgekürzt. Sofern keine Missverständnisse zu
befürchten sind, wird das Tripel G = (G, K, f ) mit G = (G, K) abgekürzt.
Abbildung 1: Zwei Graphen
Definition 1.1.1. Es seien E und K disjunkte Mengen, die Elemente E1 , E2 , ..., En aus
E Ecken und die Elemente k1 , k2 , k3 , ..., km aus K Kanten. Ebenfalls sei E 6= ∅ und f eine
Abbildung K → E E = {Ei ; Ej ∈ E}2 , das heißt jeder Kante werden genau zwei Ecken
zugeordnet, die nicht notwendig verschieden sein müssen. Das Tripel G = (G, K, f ) heißt
Graph.
1
2
Je nach Literatur spricht man von Knoten statt Ecken und Bögen statt Kanten.
E E definitert das ungeordnete Produnkt von E, also die Menge der undgeordneten Paare.
4
1.2 Klassen von Graphen
Definition 1.2.1. Ein Graph heißt vollständig, wenn jede Ecke mit jeder anderen Ecke
genau durch eine Kante verbunden ist. Der vollständige Graph mit n Ecken wird mit Kn
bezeichnet.
Abbildung 2: Vollständige Graphen K1 , ..., K5
Definition 1.2.2. Ein Graph heißt bipartit, wenn man seine Ecken in zwei Klassen einteilen kann, so dass jede Kante von einer Klasse zur anderen führt.
Abbildung 3: Bipartite Graphen
Definition 1.2.3. Ein bipartiter Graph mit Bipartition {E1 ,E2 } heißt vollständig bipartit,
wenn jede Ecke von E1 mit jeder Ecke von E2 durch genau eine Kante verbunden ist.
Abbildung 4: Vollständig bipartite Graphen K2,2 , K2,3 und K3,3
Definition 1.2.4. Ein Kantenzug k1 , k2 , k3 , ..., km ist ein n-Tupel von Ecken, bei dem
der Endpunkt der Kante ki mit dem Anfangspunkt der Kante ki+1 indiziert.
Es gilt: i ∈ {1, 2, 3, ..., m − 1}, (m ∈ N)
5
Definition 1.2.5. Ein Kantenzug heißt geschlossen, wenn e0 = es ist.
Ein Kantenzug heißt Weg, falls alle Kanten verschieden sind.
Ein geschlossener Kantenzug heißt Kreis, falls seine Kanten alle verschieden sind. Die Länge eines Kreises ist die Anzahl seiner Kanten/Ecken.
Abbildung 5: Kantenzug, geschlossener Kantenzug, Weg, Kreis
Definition 1.2.6. Ein Graph heißt zusammenhängend, wenn je zwei Ecken durch einen
Kantenzug verbunden werden können.
Mit einfachen Worten ausgedrückt, könnten man sagen, dass diese Graphen nicht in mehrere Teile zerfallen.
Definition 1.2.7. Es sei v ∈ E eine Ecke eines Graphen G. Die Ordnung der Ecke v ∈ E
ist die Anzahl der Kanten, die in einer Ecke zusammentreffen. Kanten, die zur selben Ecke
zurückführen (Schlinge), werden zweimal gezählt. Die Summe der Ordnung aller Ecken
wird mit ord(E), die Ordnung einer Ecke wird mit ord(v), v ∈ E, bezeichnet.
Abbildung 6: Ecken mit der Ordnung 0, 1, 2 bzw. 3
6
Beispiel.
Abbildung 7: Beispielgraph
Abb.7 verdeutlicht einige Besonderheiten:
1. Die Ecken A und B werden durch die Kanten k1 und k2 verbunden. Man spricht
hierbei von Mehrfachkanten.
2. Bei der Kante k5 fallen beide Ecken zusammen. Eine solche Kante nennt man Schlinge.
3. Man spricht von einer isolierten Ecke, wenn die Ordnung der Ecke gleich 0 ist.
7
2 Das Königsberger Brückenproblem
Das Königsberger Brückenproblem gehört zu den Klassikern in der Mathematik. Leonard
Euler (1707-1783) löste nicht nur das Königsberger Brückenproblem an sich, sondern entwickelte gleichzeitig Methoden, welche zu den Grundsteinen der modernen Graphentheorie
gehören.
2.1 Das Problem
Durch Königsberg fließt die Pregel, welche sich an einer Stelle so teilt, dass sie anschließend zwei Inseln umfließt. Diese zwei Inseln sind durch Brücken untereinander und mit
den Ufern verbunden.
Abbildung 8: Stadtplan von Königsberg
Die Einwohner der Stadt stellten sich folgende Frage:
"Kann man durch Königsberg spazieren und dabei jede Brücke nur einmal überqueren?"
Dieses Problem erschien aber als solch ein Großes, dass einer der größten Mathematiker,
nämlich Leonard Euler, herangezogen wurde, um die Lösung zu finden.
8
2.2 Die Lösung
2.2.1 Die Übersetzung der Karte in einen Graphen
Abbildung 9: Übersetzung der Landkarte Königsberg in einen Graphen
2.2.2 Die Übersetzung des Problems
Definition 2.2.2.1. Sei G ein Graph.
Ein Weg, der jede Kante von G genau einmal enthält, heißt eulerscher Weg von G.
Ein Kreis von G heißt eulerscher Kreis 3 , wenn in ihm jede Kante genau einmal vorkommt.
Ein Graph heißt eulersch, wenn er einen eulerschen Kreis enthält.
Satz 2.2.2.1. (Euler 1736) Wenn ein Graph G eulersch ist, dann hat jede Ecke von
G eine gerade Ordnung. Wenn G eine Ecke ungerader Ordnung hat, dann ist G nicht
eulersch.
Beweis.
Man betrachte eine beliebige Ecke v ∈ E.
Zeige: Die Anzahl der Kanten, die an v ∈ E angrenzt, ist gerade. Die Ordnung kann bei
verschiedenen Ecken unterschiedlich sein; es ist also nur zu zeigen, dass die Ordnung jeder
Ecke eine gerade Zahl ist.
Überlegung: Der eulersche Kreis durchquert die Ecke v ∈ E einige Mal, wie oft wissen wir
nicht genau, aber wir definieren eine Anzahl von a Mal, mit a ∈ N. Die Zahl a definiert
somit die Anzahl an Durchgängen des eulerschen Kreises durch die Ecke v ∈ E.
Behauptung: ord(v) = 2a mit v ∈ E und a ∈ N
Resultat: Der eulersche Kreis verbraucht bei jedem Durchgang durch v ∈ E zwei Kanten;
in a Durchgängen (a ∈ N) werden 2a Kanten erfasst. Da per Definition keine Kante zwei
3
Je nach Literatur wird der eulersche Kreis auch geschlossener eulerscher Weg genannt.
9
Mal benutzt werden darf, ist die Ordnung der Ecke v ∈ E mindestens 2a, also ord(v)≥ 2a.
Die Ordnung der Ecke kann aber auch nicht größer sein, da jede Kante, im eulerschen
Kreis insbesondere jede Kante die an v ∈ E grenzt, mindestens einmal vorkommen muss.
Somit ord(v)= 2a.
Zurückgreifend auf das Problem des Spazierganges durch Königsberg bedeutet dies nun,
dass der Spaziergang einem eulerschen Kreis entspricht, wenn man dabei jede Brücke genau einmal überquert und schlussendlich wieder am Ausgangspunkt ankommt.
Nun also die Frage: Ist der Graph des Königsberger Brückenproblems eulersch?
Durch das Anwenden des Satzes von Euler können wir sagen, dass der Graph des Königsberger Brückenproblems nicht eulersch ist. Die Ecken im Graphen sind von der Ordnung
3, 3, 3, 5 und somit nicht eulersch. Ein Spaziergang wie erwünscht, ist also nicht möglich.
2.3 Durchlaufbarkeit von Graphen
Satz 2.3.1. Wenn ein Graph einen offenen eulerschen Weg4 besitzt, dann hat er genau
zwei Ecken ungerader Ordnung.5
Beweis. Sei G ein Graph, der einen offenen eulerschen Weg besitzt. Dieser beginnt an
einer Ecke v1 ∈ E und endet an einer anderen Ecke vn ∈ E.
Trick: Man fügt zusätzlich und nur für kurze Zeit eine Kante k ∗ ∈ K ein, die v1 und vn
verbindet. Der neu erhaltene Graph wird G∗ genannt und unterscheidet sich von G nur
durch die Kante k ∗ . Hängt man an den offenen eulerschen Weg die Kante k ∗ , erhält man
einen neuen eulerschen Kreis von G∗ . Durch den Satz von Euler wissen wir, dass jede Ecke
von G∗ eine gerade Ordnung hat.
Daraus können wir schließen, dass jede Ecke vi ∈ E, die keine Ecke von k ∗ ist, auch eine
gerade Ordnung besitzt. Außerdem folgt daraus, dass die Ecken v1 ∈ E und vn ∈ E eine
ungerade Ordnung haben, da sie in G∗ eine gerade Ordnung hatten und die Kante k ∗
wieder entfernt wurde.
Also sind v1 ∈ E und vn ∈ E die einzigen Ecken mit ungerader Ordnung in G.
Die Aussage des Beweises ist durch "das Unterkellern des Hauses vom Nikolaus", wie in
Abb.11 ersichtlich, sehr einfach und anschaulich erklärbar:
4
5
Je nach Literatur wird der offene eulersche Weg auch als offene eulersche Linie bezeichnet.
Es gilt auch die Umkehrung.
10
Abbildung 10: Haus vom Nikolaus
Abbildung 11: Haus vom Nikolaus mit
Keller
Bemerkung. Graphen können in einem Zuge gezeichnet werden, wenn sie einen eulerschen Kreis oder einen offenen eulersche Weg enthalten.
Beispiele.
Abbildung 12: Der Fisch
Die Graphen der Abb. 10 und Abb. 12 enthalten einen offenen eulerschen Weg. Der offene
eulersche Weg beginnt beim Haus des Nikolaus in der unteren Ecke und endet bei der
anderen, unteren Ecke. Auch beim Fisch kann der Start- und Zielpunkt nicht frei gewählt
werden.
Der Graph in Abb.11 enthält einen eulerschen Kreis und ist somit eulersch. Solche Graphen
lassen sich in einem Zug, also ohne Absetzen, zeichnen und man gelangt schlussendlich
wieder zum Ausgangspunkt.
Aus dem Satz 2.3.1., sowie den Abb. 10 und Abb. 12 kann schließlich folgende Tatsache
entnommen werden:
Korollar 2.3.1. In der Situation aus Satz 2.3.1. beginnt jeder offene, eulersche Weg an
einer Ecke ungerader Ordnung und endet an der anderen.
11
3 Planare Graphen
3.1 Ecken- und Kantenordnung
Wiederholung. Es sei v ∈ E eine Ecke eines Graphen G. Die Ordnung der Ecke v ∈ E ist
die Anzahl der Kanten, die in einer Ecke zusammentreffen. Kanten, die zur selben Ecke
zurückführen (Schlinge), werden zweimal gezählt. Die Summe der Ordnung aller Ecken
wird mit ord(E), die Ordnung einer Ecke wird mit ord(v), v ∈ E, bezeichnet.
Satz 3.1.1. In einem vollständigen Graphen Kn hat jede Ecke die Ordnung n − 1.
Abbildung 13: Vollständige Graphen K1 , ..., K6
Beweis. Da in einem vollständigen Graphen Kn (n ∈ N) jede der n Ecken mit jeder der
anderen n − 1 Ecken verbunden ist, gilt für jede Ecke v ∈ E im vollständigen Graphen:
ord(v) = n − 1, (v ∈ E)
Abbildung 14: Dodekaedergraph
12
Abbildung 15: Würfelgraph
Lemma 3.1.1. Sei G = (E, K) ein Graph. Die Summe der Ordnungen aller Ecken entspricht der doppelten Kantenzahl, also
P
ord(E) = 2|K|.
Beweis. Man betrachte einen schlingenfreien Graphen G.
Nach der Definition „Graph“ sind jeder Kante k des Graphen genau zwei Ecken zugeordnet. Jede Kante erhöht die Summe aller Eckenordnungen des Graphen also genau um 2.
Daher ist die Summe aller Eckenordnungen doppelt so groß wie die Anzahl der vorhandenen Kanten, die keine Schlingen sind. (*)
Da laut Definition festgelegt wurde, dass Schlingen bei der Bestimmung der Eckenordnung
doppelt gezählt werden, erhöht daher auch jede Schlinge die Summe der Eckenordnungen
um 2. (**)
Aus (*) und (**) folgt schlussendlich: Die Summe aller Eckenordnungen ist gleich dem
Doppelten der Kantenzahl, also
P
ord(E) = 2|K|.
Definition 3.1.1. Jeder planare Graph zerlegt die Ebene in Gebiete. Die Anzahl der Gebiete wird mit g bezeichnet. Es gibt stets mindestens ein Gebiet, das äußere Gebiet und
somit gilt stets g > 1.
3.2 Hinführung zur Eulerschen Polyederformel
Definition 3.2.1. Polyeder sind Körper, die von Polygonen, also von Vielecken wie Dreiecken, Vierecken, usw. begrenzt sind.
Definition 3.2.2. Ein Polyeder heißt konvex, wenn für je zwei Punkte des Polyeders die
Verbindungsstrecke zwischen diesen Punkten vollständig im Polyeder liegt.
13
Lemma 3.2.1. Konvexe Polyeder können stets auf einen planaren Graphen projiziert
werden.
Die Eulersche Polyederformel ist auf den Zusammenhang von konvexen Polyedern und
planaren Graphen zurückzuführen. Platonische Körper6 sind Beispiele von konvexen Polyedern. Sie können also durch zusammenhängende, planare Graphen dargestellt werden.
Bei Betrachtung der folgenden Tabelle weisen all diese Körper eine Gemeinsamkeit auf:
Tabelle 1: Platonische Körper
Körper
Eckenzahl e
Kantenzahl k
Anzahl Gebiete g
e−k+g
Tetraeder
4
6
4
2
Würfel
8
12
6
2
Oktaeder
6
12
8
2
Dodekaeder
20
30
12
2
Ikosaeder
12
30
20
2
Man betrachte nun folgende planare, zusammenhängende Graphen:
Hier wird schnell deutlich, dass die Beobachtung aus Tabelle 1, (e − k + g = 2), auch für
planare, zusammenhängende Graphen gilt.
Abbildung 16: Graph 1
6
Abbildung 17: Graph 2
Platonische Körper sind reguläre Polyeder; es gibt genau fünf Platonische Körper (Tetraeder, Würfel,
Dodekaeder, Oktaeder, Ikosaeder).
14
Tabelle 2: Graphen 1,2
Körper
Eckenzahl e
Kantenzahl k
Anzahl Gebiete g
e−k+g
Graph 1
5
8
5
2
Graph 2
5
8
5
2
Mit der nun erlangten Erkenntnis lässt sich folgendes definieren:
Die Eulersche Polyederformel. Sei G ein zusammenhängender, planarer Graph mit e
Ecken, k Kanten und g Gebieten. Dann gilt: e − k + g = 2.
Beweis.
Idee: Zuerst ist zu zeigen, dass die Behauptung für einen planaren zusammenhängenden
Graphen mit null Kanten gilt. Danach werden wir den Graphen kantenweise aufbauen und
beobachten dabei die Zahl e − k + g.
Wir zeigen die Behauptung durch vollständige Induktion über der Kantenzahl.
Es gilt:
Besteht der Graph aus einer einzelnen Ecke ohne Kante, so haben wir eine Ecke, keine
Kante und eine Fläche, also 1 − 0 + 1 = 2.7
Abbildung 18: Einzelne Ecke ohne Kante
Induktionsanfang:
Zu zeigen: Die Behauptung gilt für einen Graphen mit einer Kante.
Wir fügen eine Kante zum Graphen aus Abb.18 hinzu. Wenn diese Kante eine Schlinge
ist, dann bleibt die Eckenzahl unverändert, während sich die Kantenzahl und die Anzahl
der Gebiete um jeweils 1 erhöhen, was e − k + g unverändert lässt.
7
Der Fall k gleich 0 und e größer gleich 2 erzeugt einen nicht zusammenhängenden Graphen.
15
Abbildung 19: Einzelne Ecke mit einer Kante (Schlinge)
Wenn diese Kante keine Schlinge ist, dann hat sie eine zweite Ecke. Dadurch erhöhen sich
e und k um jeweils 1, die Zahl der Gebiete bleibt aber unverändert. Dies ändert also auch
nichts an e − k + g = 2.
Abbildung 20: Zwei Ecken mit einer Kante
Induktionsschritt:
Zu zeigen: Wenn die Behauptung für einen Graphen mit n Kanten gilt, dann gilt sie auch
für einen Graphen mit (n + 1)-Kanten.
Wir setzen also voraus, dass die Behauptung für einen planaren zusammenhängenden
Graphen mit n Kanten gilt.
Wenn wir den Graphen schon aus n Kanten (n ∈ N) aufgebaut haben und anschließend
eine (n + 1)-te Kante unter Beibehaltung der Planarität hinzufügen, eröffnen sich drei
mögliche Fälle:
1. Fall: Die neue gestrichelte Kante ist eine Schlinge. Dann bleibt e gleich, k und g erhöhen
sich um 1 und e − k + g bleibt unverändert.
Abbildung 21: Graphenaufbau 1.Fall
16
2. Fall: Die neue gestrichelte Kante verbindet zwei schon vorhandene Ecken. Dann bleibt
e gleich, k und g erhöhen sich um 1. Auch hier bleibt e − k + g unverändert.
Abbildung 22: Graphenaufbau 2.Fall
3. Fall: Die neue gestrichelte Kante hat als zweite Ecke eine neue gestrichelte Ecke. e
wächst dann um 1, ebenso k, aber die Anzahl der Gebiete g bleibt unverändert. Also
bleibt auch e − k + g in diesem Fall unverändert.
Abbildung 23: Graphenaufbau 3.Fall
Da der Graph zusammenhängend8 ist, erhalten wir schließlich den ganzen Graphen, wobei
sich bei keinem Schritt die Zahl e − k + g verändert.
Korollar 3.2.1. Sei G ein zusammenhängender planarer Graph, in dem je zwei Ecken
durch höchstens eine Kante verbunden sind. Dann gilt
(a) Falls G mindestens drei Ecken hat, dann gilt k ≤ 3e − 6. Das heißt: Ein planarer Graph
hat relativ wenige Kanten.
(b) Es gibt mindestens eine Ecke der Ordnung ≤ 5.
Beweis.
(a) Für ein Gebiet L sei k(L) die Anzahl der Kanten des Gebietes.
8
Diese Eigenschaft ist zusammen mit der Planarität der Grund, dass beim Einfügen der (n + 1)-ten Kante
nur die drei oben gezeigten Fälle möglich sind.
17
Da jedes Gebiet mindestens drei Kanten hat, gilt
P
k(L) ≥ 3g.
Nun zählt man folgende Paare (k, L) mit k ∈ K, L Gebiet und k sei ein Teil der Grenze
von L:
P
k(L) ≤ 2k.
Zusammengefasst:
2k ≥ 3g
Schließlich setzt man dieses Ergebnis in die Eulersche Polyederformel und es folgt:
e − k + 32 k ≥ e − k + g = 2, also k ≤ 3e − 6.
(b) Die Behauptung gilt für e = 1 oder e = 2. Für e ≥ 3 wendet man (a) an und erhält:
δ∗e≤
ord(v) = 2k ≤ 6e − 12,
P
wobei v ∈ E, δ die kleinste Ordnung von G ist. Daraus folgt: δ ∗ e < 6e, also δ < 6.
3.3 Planarität und Plättbarkeit von Graphen
Definition 3.3.1. Man nennt einen Graph planar, falls er ohne Überschneidungen in der
Ebene gezeichnet ist, also so, dass sich zwei Kanten höchstens in einer Ecke schneiden.
Definition 3.3.2. Ein Graph ist plättbar, wenn er überschneidungsfrei in die Ebene gezeichnet werden kann.
Abbildung 24: Planare Darstellung eines Würfels
18
Abbildung 25: Planare Darstellung Haus des Nikolaus
Korollar 3.3.1. Der vollständige Graph9 K5 ist nicht plättbar. Das heißt, dass er nicht
überschneidungsfrei in die Ebene gezeichnet werden kann.
Abbildung 26: Plättbarkeitsversuch K5
Beweis.
Annahme: K5 sei plättbar.
Dann hätte K5 nach Korollar 3.2.1. höchstens 3n − 6 = 9 Kanten. K5 hat aber genau
5
2
9
=
5!
(5−2)!∗2!
=
5∗4
2
= 10 Kanten. Dieser Widerspruch zeigt die Behauptung.
Ein Graph heißt vollständig, wenn jede Ecke mit jeder anderen Ecke genau durch eine Kante verbunden
ist.
19
Korollar 3.3.2. Der vollständig bipartite Graph K3,3 ist nicht plättbar.
Abbildung 27: K3,3
Beweis. Angenommen K3,3 könnte als planarer Graph dargestellt werden. Dann hätte
dieser e = 6 Ecken, k = 9 Kanten und nach der Eulerschen Polyederformel
2 = e − k + g = 6 − 9 + g, also g = 5 Gebiete.
Betrachtet man ebenfalls die Überlegung aus Korollar 3.2.1.(a), so folgt daraus, dass jedes
Gebiet mindestens 4 Ecken und also auch mindestens 4 Kanten haben muss. Daher gilt
(L) ≥ 4g, und daher 2k ≥ 4g.
P
In diesem Beispiel bedeutet dies 18 = 2k ≥ 4g = 20. Dieser Widerspruch zeigt, dass K3,3
nicht plättbar ist.
Abbildung 28: Plättungsversuch des K3,3
Die Graphen K5 und K3,3 besitzen eine spezielle Eigenschaft. Dies wird durch folgenden
Satz deutlich:
Definition 3.3.3. Ein Graph G0 = (E0 , K0 ) ist ein Teilgraph von G = (E, K), wenn E0 ⊆ E
und K0 ⊆ K.
20
Satz 3.3.1. (Satz von Kuratowsi) Ein zusammenhängender Graph ist genau dann
nicht plättbar, wenn er den vollständigen Graphen K5 oder K3,3 oder eine Unterteilung10
einer dieser Graphen als Teilgraph enthält.
10
Von einer Unterteilung der Graphen K5 oder K3,3 spricht man, wenn auf einer oder auf mehreren Kanten
dieser Graphen neue Ecken ausgezeichnet sind.
21

Download Report