Einfuhrung in die Graphentheorie

Monika Konig

8. 11. 2011

1

Vorwort

Diese Seminararbeit basiert auf den Unterkapiteln 1.1 - 1.3 des Buches”Algebraic Graph

Theory“ von Chris Godsil und Gordon Royle (siehe [1]). Es werden grundlegende Defini-tionen eingefuhrt, Abbildungen zwischen Graphen besprochen und einzelne Familien vonGraphen naher vorgestellt. Um keine Verwirrung in den folgenden Seminarvortragen zustiften, werden die Definitionen analog zur Hauptquelle eingefuhrt. Als Ubersetzungshilfewurde eine Mitschrift von einer Vorlesung verwendet, siehe dazu [2].

Erste Definitionen und Begriffe

Ein Graph X besteht aus einer Knotenmenge V (X) (vertex set) und einer Kanten-menge E(X) (edge set), wobei eine Kante ein ungeordnetes Paar von zwei verschiedenenKnoten aus V (X) ist. Im Folgenden wird eine Kante zwischen den Knoten x und y alsxy bezeichnet, eine andere gangige Schreibweise ware {x, y}. Wenn xy eine Kante ist, sosagt man, dass die Knoten x und y adjazent oder auch benachbart sind. Man schreibt:x ∼ y. Ein Knoten heißt inzident mit einer Kante, wenn diese ihn enthalt, den Knotenalso beruhrt.

Graphen werden haufig verwendet, um eine binare Beziehung zwischen Objekten in einemgewissen Bereich zu modellieren. Zum Beispiel konnte die Knotenmenge die Computer ineinem Netzwerk reprasentieren und adjazente Knoten Computern entsprechen, die mittelsNetzwerkkabeln physikalisch verbunden sind. Ein weiteres klassisches Beispiel ist, dass dieKnoten Orte und die Kanten Straßen oder Wege zwischen den Orten darstellen.

Zwei Graphen X und Y sind genau dann gleich, wenn sie dieselbe Knotenmenge und die-selbe Kantenmenge besitzen. Diese Definition ist zwar durchaus sinnvoll, jedoch ist sie furdie Praxis meist zu eng gegriffen. Fur die meisten Anwendungen unterscheiden sich zumBeispiel zwei Graphen nicht, wenn man den einen durch Umbenennung der Knoten desanderen erzeugt. Das motiviert die folgende Definition:Zwei Graphen X und Y sind isomorph, wenn eine Bijektion ϕ von V (X) nach V (Y )existiert, sodass x adjazent zu y (x ∼ y) in X ist genau dann, wenn ϕ(x) adjazent zuϕ(y)(ϕ(x) ∼ ϕ(y)) in Y ist. ϕ heißt dann Isomorphismus von X nach Y . Da ϕ eine Bi-jektion ist, existiert auch seine Inverse, die eine Bijektion von Y nach X ist. Wenn X undY isomorph sind, schreibt man X ∼= Y . Im Normalfall ist es zulassig isomorphe Graphenso zu behandeln, als waren sie gleich.

Oft werden Graphen durch ein Bild veranschaulicht, weil es einfach besser fur das Verstandnisist. Man stellt dabei die Knoten durch Punkte beziehungsweise Kreise dar und die Kantendurch Linien. Streng genommen definiert aber ein Bild keinen Graphen, da die Knotenmen-ge im Bild nicht genau spezifiziert ist. Man kann jedoch den Knoten verschiedene Zahlenzuordnen und die Kanten dann dementsprechend benennen. So entspricht das Bild bis auf

2

Isomorphismus einem Graphen, was fast immer reicht. Wichtig ist, sich bewusst zu sein,dass in einem Bild eines Graphen die Positionen der Punkte und der Linien willkurlichsind. Das einzige, was wichtig ist, ist, welche Knoten mit einer Kante verbunden sind. Esist eine gute Ubung sich zu uberlegen, wieso die zwei Graphen in Abbildung 1 isomorphsind.

Abbildung 1: diese beiden Graphen sind isomorph

Ein Graph heißt vollstandig, wenn jedes Knotenpaar adjazent ist, das heißt, wenn zwi-schen je zwei verschiedenen Knoten eine Kante existiert. Der vollstandige Graph mit nKnoten wird mit Kn bezeichnet. Ein Graph mit leerer Kantenmenge, aber mit mindestenseinem Knoten, heißt leerer Graph. Manchmal wird der Graph mit leerer Knoten- undleerer Kantenmenge als Nullgraph bezeichnet.

Abbildung 2: Die vollstandigen Graphen K4 und K5

Graphen, wie sie hier definiert wurden, werden auch als einfache Graphen bezeichnet. Esgibt noch viele andere Arten von Graphen, zum Beispiel gerichtete Graphen. Ein gerich-teter Graph besteht aus einer Knotenmenge V (X) und aus einer Menge von gerichtetenKanten A(X) (arc set), wobei eine gerichtete Kante (oder auch Bogen) ein geordnetesPaar von zwei verschiedenen Knoten ist. Man schreibt (x, y) fur eine Kante die von x nach ygeht. Oft wird die Menge der gerichteten Kanten statt mit A(X) auch mit E(X) analog zu

3

den ungerichteten Kanten bezeichnet. In einer Zeichnung eines gerichteten Graphen wirddie Richtung einer Kante mit einem Pfeil am Ende der Kante deutlich gemacht. In vielenAnwendungen kann ein einfacher Graph als gerichteter Graph gesehen werden, unter derBedingung, dass wenn (x, y) eine Kante ist, auch (y, x) eine Kante ist.

Abbildung 3: Beispiel fur einen gerichteten Graphen

Im weiteren wird explizit gesagt, wenn ein gerichteter Graph gemeint ist. Mit Graph istim Allgemeinen ein einfacher Graph gemeint. Zudem ließe unsere Definition eines Grapheneine unendliche Knotenmenge zu, wir werden auf diesen Fall aber nicht eingehen und imFolgenden immer von einer endlichen Knotenmenge ausgehen.

Teilgraphen

Ein Teilgraph (oder manchmal auch Subgraph) eines Graphen X ist ein Graph Y , furden gilt, dass

V (Y ) ⊆ V (X), E(Y ) ⊆ E(X).

Wegen der Forderung, dass Y ein Graph ist, konnen naturlich nur Kanten in E(Y ) sein,deren inzidente Knoten in V (Y ) enthalten sind. Wenn V (Y ) = V (X) (Y also alle Knotendes Ausgangsgraphen enthalt), so nennt man Y einen spannenden Teilgraph. Jedenspannenden Teilgraphen von X kann man einfach dadurch erhalten, dass man gewisseKanten aus X rauswirft. Die Anzahl aller moglichen spannenden Teilgraphen von X istgleich der Anzahl der Teilmengen von E(X).

4

Abbildung 4: Beispiel fur einen Teilgraphen und einen spannenden Teilgraphen

Ein Teilgraph Y von X heißt induzierter Teilgraph, wenn zwei Knoten aus V (Y ) immergenau dann in Y adjazent (also durch eine Kante verbunden) sind, wenn sie in X adjazentsind. Jeden induzierten Teilgraphen von X kann man dadurch generieren, dass man Knotenvon X weglasst und auch jene Kanten, die die weggelassenen Knoten enthalten. Deshalb istein induzierter Teilgraph durch seine Knotenmenge festgelegt. Man spricht deshalb auchvom Teilgraphen von X, der von seiner Knotenmenge (also die, des Teilgraphen) induziertwird. Die Anzahl der induzierten Teilgraphen von X ist gleich der Anzahl der Teilmengenvon V (X).

Abbildung 5: Beispiel fur einen induzierten Teilgraphen

Manche Typen von Teilgraphen sind so haufig, dass sie einer Erwahnung hier wert sind.Eine Clique ist ein Teilgraph, der vollstandig ist. Damit ist er notwendigerweise ein indu-zierter Teilgraph. Eine Menge von Knoten, die einen leeren Teilgraphen induziert, nenntman eine unabhangige Knotenmenge. Die Große der großten Clique (also die Anzahlder Knoten der großten Clique) wird mit ω(X) bezeichnet, die Große der großten un-abhangigen Knotenmenge mit α(X). Spater wird man sehen, dass sowohl ω(X) als auchα(X) wichtige Parameter eines Graphen sind. Im nachfolgenden Beispiel in Abbildung ??ist ω(X) = 4 und α(X) = 3.

5

Abbildung 6: Beispiel fur eine Clique und zwei unabhangige Knotenmengen

Ein Pfad oder Weg der Lange r von x nach y in einem Graphen ist eine Folge von r + 1verschiedenen Knoten, die bei x startet und bei y endet und wo alle aufeinanderfolgendenKnoten benachbart sind.

Wenn zwischen je zwei Knoten eines Graphen ein Pfad existiert, dann heißt der Graphzusammenhangend, sonst unzusammenhangend. Anders gesagt ist ein Graph dannunzusammenhangend, wenn man seine Knoten in zwei nichtleere Mengen, zum Beispiel dieMengen R und S, aufteilen kann, sodass kein Knoten aus R mit einem Knoten aus S be-nachbart ist. In diesem Fall sagt man dann, dass der GraphX eine disjunkte Vereinigungder zwei Teilgraphen, die von R und S induziert werden, ist. Einen zusammenhangenden,induzierten Teilgraphen von X, der maximal ist, nennt man eine Zusammenhangskom-ponente von X.

Ein Kreis oder Zyklus ist ein zusammenhangender Graph, in dem jeder Knoten genauzwei Nachbarn hat. Der kleinste solche Graph ist der vollstandige Graph K3. Einen Teilgra-phen von X, der ein Kreis ist, nennt man einen Kreis in einem Graphen. Es gibt nochandere Moglichkeiten einen Kreis zu definieren. Eine weitere ist zum Beispiel: ein Kreisist ein Pfad, dessen Anfangs- und Endknoten ident sind. Diese Definition ist um einigesanschaulicher, obwohl sie mit der hier verwendeten Definition von Pfad nicht korrekt ist,da die Knoten verschieden sein mussen.

6

Abbildung 7: Beispiel fur Kreise in einem Graphen

Der Beweis, dass ein Graph, in dem jeder Knoten mindestens zwei Nachbarn besitzt, min-destens einen Kreis enthalten muss, ist ein klassisches Beispiel am Anfang der Graphen-theorie. Ein kreisfreier oder azyklischer Graph ist ein Graph, der keinen Kreis enthalt.Es gibt auch noch weitere, bildlichere Bezeichnungen fur azyklische Graphen: einen zusam-menhangenden, kreisfreien Graphen nennt man einen Baum und einen kreisfreien Graphennennt man deshalb auch einen Wald, da ja jede Zusammenhangskomponente Baum ge-nannt wird. Ein spannender Teilgraph, der keine Kreise besitzt, heißt spannender Baumoder auch Spannbaum. Man kann zeigen, dass ein Graph genau dann einen spannendenBaum besitzt, wenn er zusammenhangend ist. Ein maximaler spannender Wald inX ist ein spannender Teilgraph, in dem jede Zusammenhangskomponente ein spannenderBaum ist.

Abbildung 8: Beispiel fur einen Wald mit zwei Baumen

Automorphismen

Ein Isomorphismus von einem Graphen X auf sich selbst nennt man einen Automor-phismus von X (von gr. αυτoς = selbst und µoρϕη = die Gestalt). Anders gesagt: ein

7

Automorphismus eines Graphen X ist eine bijektive Abbildung ϕ : V (X)→ V (X), sodass

{x, y} ∈ E(X)⇔ {ϕ(x), ϕ(y)} ∈ E(X) fur alle x, y ∈ V (X).

Ein Automorphismus ist deshalb eine Permutation der Knoten von X, die Kanten zuKanten und Nichtkanten zu Nichtkanten abbildet. Wir betrachten nun die Menge allerAutomorphismen des Graphen X. Naturlich ist die Identitat, welche wir mit e bezeichnen,ein Automorphismus. Wenn g ein Automorphismus von X ist, dann auch seine Inverseund wenn h ein zweiter Automorphismus von X ist, dann ist auch das Produkt (also dieHintereinanderausfuhrung) gh ein Automorphismus. Aufgrund dessen bilden die Automor-phismen von X ein Gruppe, die die Gruppe der Automorphismen von X genannt wirdund mit Aut(X) abgekurzt wird.

Die symmetrische Gruppe Sym(V ) ist die Gruppe aller Permutationen einer MengeV . Daher ist die Gruppe der Automorphismen von X eine Untergruppe von Sym(V (X)).Wenn der Graph X n Knoten besitzt, werden wir einfach Sym(n) fur Sym(V (X)) schrei-ben.

Im Allgemeinen ist es nicht trivial zu entscheiden, ob zwei Graphen isomorph sind oderob ein gegebener Graph einen Automorphismus besitzt, der nicht gleich der Identitat ist.Trotzdem gibt es Falle, wo dies ganz einfach moglich ist. Zum Beispiel ist jede Permuta-tion der Knoten des vollstandigen Graphen Kn ein Automorphismus, also ist Aut(Kn) ∼=Sym(n).

Das Bild eines Knotens v ∈ V unter der Permutation g ∈ Sym(V ) wird bezeichnet mit vg.Wenn g ∈ Aut(X) und Y ein Teilgraph von X ist, dann sei Y g der Graph mit

V (Y g) = {xg : x ∈ V (Y )}

undE(Y g) = {{xg, yg} : {x, y} ∈ E(Y ).}

Man kann sofort sehen, dass Y g zu Y isomorph ist und auch ein Teilgraph von X ist.

Der Grad oder manchmal auch Valenz eines Knotens x ist die Anzahl seiner Nachbarnund der maximale beziehungsweise minimale Grad eines Graphen X ist der maximale be-ziehungsweise minimale Wert, wenn man die Grade aller Knoten von X betrachtet. InAbbildung 9 wurde zu jedem Knoten des Beispielgraphen der entsprechende Grad dazuge-schrieben.

8

Abbildung 9: Graph, in dem bei jedem Knoten sein Grad steht

Lemma 1. Sei x ein Knoten des Graphen X und g ein Automorphismus von X. Dannhat der Knoten y = xg den gleichen Grad wie der Knoten x.

Beweis. Sei N(x) der Teilgraph von X, der von den Nachbarn von x in X induziert wird.Dann gilt

N(x)g = N(xg) = N(y)

und deshalb sind N(x) und N(y) isomorphe Teilgraphen von X. Daraus folgt, dass sie diegleiche Anzahl von Knoten haben und somit haben x und y den gleichen Grad.

Das zeigt, dass die Gruppe der Automorphismen eines Graphen immer die Knoten mitgleichem Grad (unter sich selbst) permutiert. Ein Graph, in dem jeder Knoten den Grad khat, heißt regular vom Grad k oder k - regular. Einen 3 - regularen Graph nennt manauch kubisch und ein 4-regularer Graph wird manchmal auch quartisch genannt.

Der Abstand dX(x, y) zwischen zwei Knoten x und y in einem Graphen X ist die Langedes kurzesten Pfades von x nach y. Wenn aus dem Zusammenhang heraus klar ist, welcherGraph gemeint ist, kann man auch d(x, y) schreiben.

Lemma 2. Seien x und y Knoten von X und g ∈ Aut(X). Dann gilt d(x, y) = d(xg, yg).

Beweis. Wenn man den Teilgraphen von X betrachtet, der durch alle Pfade (bzw. derenKnoten) von x nach y induziert wird, dann folgt aus dem vorigen Lemma, dass der Teilgraphunter dem Automorphismus erhalten bleibt.

Der komplementare Graph X eines Graphen X hat dieselbe Knotenmenge wie X undx und y sind genau dann benachbart, wenn sie in X nicht benachbart sind.

9

Abbildung 10: ein Graph und sein komplementarer Graph

Lemma 3. Die Gruppe der Automorphismen eines Graphen ist gleich der Gruppe derAutomorphismen seines Komplements.

Beweis. Dies folgt aus der Definition eines komplementaren Graphen, da ja ein Automor-phismus Kanten auf Kanten und Nichtkanten auf Nichtkanten abbildet.

Wenn X ein gerichteter Graph ist, dann ist ein Automorphismus eine Permutation der Kno-ten, die gerichtete Kanten auf gerichtete Kanten abbildet, das heißt, dass die Richtungender Kanten erhalten werden.

10

Anhang

Englisch Deutschacyclic azyklisch, kreisfreiadjacent adjazentarc gerichtete Kante, Bogenautomorphism Automorphismusautomorphism group Gruppe der Automorphismenclique Cliquecomplete vollstandigconnected zusammenhangend(connected) component Zusammenhangskomponentecubic kubischcycle Kreis, Zyklusdirected edge gerichtete Kantedirected graph gerichteter Graphdisconnected unzusammenhangenddisjoint union disjunkte Vereinigungdistance Abstandedge set Kantenmengeempty leerforest Waldgraph Graphincident inzidentindependent set unabhangige Knotenmengeinduced subgraph induzierter Teilgraphisomorphic isomorphneighbour of Nachbar von, benachbartnull graph Nullgraphpath Pfad, Wegquartic quartischregular of valency k regular vom Grad ksimple graph einfacher Graphspanning forest Spannwald, spannender Waldspanning subgraph spannender Teilgraphspanning tree spannender Baum, Spannbaumsubgraph Teilgraph, Subgraphsymmetric group symmetrische Gruppetree Baumvalency Grad, Valenzvertex set Knotenmenge

11

Literatur

[1] Godsil Chris, Royle Gordon: Algebraic Graph Theory. Springer, 2001.

[2] Frei Christopher: Skriptum zur Vorlesung Diskrete Mathematik, nachden Vorlesungsunterlagen von Sophie Frisch. SS 2007.

12