Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 15

Schon in jungen Jahren zeigte Vorli ihre soziale Ader, indem sie Kuscheltiere um sich versammelte.

Ungerichtete Graphen

Definition

Ein ungerichteter Graph auf einer Menge ${}V$ (die die Eckpunktmenge des Graphen heißt) besteht aus einer gewissen Auswahl an zweielementigen Teilmengen (die die Kantenmenge des Graphen heißt) von ${}V$ .

Man spricht auch von einem ungerichteten Graphen. Ein Graph ist nichts anderes als eine symmetrische Relation auf ${}V$ . Typischerweise ist die Grundmenge, zu der man auch Knotenmenge oder Punktmenge oder Vertexmenge sagt, endlich, und oft wählt man ${}V={\{1,\ldots ,n\}}$ . Eine typische Darstellung eines Graphen ist ein Diagramm aus ${}n$ Punkten, von denen manche miteinander durch eine Kante verbunden sind, manche nicht. Die Menge der Kanten bildet eine Teilmenge der Potenzmenge von ${}V$ , und zwar eine, wo sämtliche Teilmengen zweielementig sind. Im Sinne der obigen Definition darf ${}(v,v)$ keine Kante sein. Die Menge aller Kanten wird häufig mit ${}E$ bezeichnet und man schreibt ${}uv\in E$ für den Sachverhalt, dass ${}\{u,v\}$ eine Kante des Graphen ist. Ein Graph wird oft kurz in der Form ${}(V,E)$ angegeben. Wenn man zu einer Menge ${}V$ mit ${}{\mathfrak {P}}_{2}\,(V)$ die Menge aller zweielementigen Teilmengen von ${}V$ , bezeichnet, so kann man die Kantenmenge als ${}E\subseteq {\mathfrak {P}}_{2}\,(V)$ auffassen.

Es gibt noch weitere Konzepte von Graphen: gerichtete Graphen, mit denen man auch nicht symmetrische Relationen darstellen kann, Graphen mit Schleifen, wo ein Punkt mit sich selbst verbunden werden kann, Graphen mit Mehrfachkanten. Gelegentlich werden wir auch auf diese Konzepte eingehen, im Mittelpunkt stehen aber die ungerichteten, schleifenfreien, einfachen Graphen.

Definition

Zu einem Punkt ${}v\in V$ in einem Graphen ${}G=(V,E)$ nennt man

{}N(v)={\left\{u\in V\mid \{u,v\}\in E\right\}}\,

die Nachbarschaft von ${}v$ .

Wenn zwei Punkte benachbart sind, also durch eine Kante verbunden, so sagt man auch, dass sie adjazent sind. Ferner sagt man, dass eine Kante mit einem Knoten inzident ist, wenn der Knoten in der Kante vorkommt. Die Kante ${}\{u,v\}$ ist also inzident zu ${}u$ und zu ${}v$ und sonst zu keinem Punkt. Zwei Kanten nennen wir koinzident, wenn ihr Durchschnitt nicht leer ist, wenn sie also inzident zu einem gemeinsamen Punkt sind. Für eine Teilmenge ${}S\subseteq V$ setzt man ${}N(S)=\bigcup _{s\in S}N(s)$ und nennt dies die Nachbarschaftsmenge von ${}S$ .

Es gibt viele Situationen, die graphentheoretisch modelliert werden können und dazu führen, dass Graphen eine Vielzahl an Interpretationsmöglichkeiten besitzen. Es ist sinnvoll, eine Reihe von solchen Interpretationen präsent zu haben und sich bei jedem neuen graphentheoretischen Begriff zu fragen, was dieser in diesen Interpretationen jeweils bedeutet.

Beispiel

Es sei eine Menge ${}P$ von Personen gegeben und wir interessieren uns für eine gewisse soziale Interaktion, die zwischen je zwei Personen bestehen kann oder nicht. Die Interaktion soll symmetrisch sein, also keine Richtung besitzen. Beispiele sind: kennen sich, sind befreundet, sind miteinander verwandt, waren schon mal zusammen im Kino, waren schon mal zusammen im Bett, waren schon mal miteinander verheiratet, haben ein gemeinsames Hobby, haben eine gemeinsame wissenschaftliche Arbeit publiziert. Wenn man einen solchen Sachverhalt mit einem ungerichteten Graphen ausdrücken möchte, so interpretiert man die Personenmenge als Punktmenge und erklärt die Kantenmenge dadurch, dass ${}x$ und ${}y$ aus ${}P$ genau dann durch eine Kante miteinander verbunden sind, wenn zwischen ${}x$ und ${}y$ die soziale Interaktion besteht. Fragestellung, die graphentheoretisch untersucht werden können, sind: Gibt es Personen, die mit besonders vielen Personen in der Interaktion stehen, mit wie vielen Personen steht durchschnittlich eine Person in Interaktion, gibt es Clusterbildungen (also Teilmengen von ${}P$ derart, dass innerhalb der Teilmenge viele Interaktionen stattfinden, aber wenige oder keine Interaktionen aus dieser Gruppe heraus), gibt es isolierte Personen ohne diese Interaktion, lässt sich die Personenmenge in Teilgruppen aufteilen, wo untereinander keine Interaktion stattfindet (heterosexuelles Verhalten, bipartiter Graph, Färbungsprobleme), über wie viele direkte Interaktionen stehen Personen in einer indirekten Beziehung zueinander (man kennt sich um ein paar Ecken, ist entfernt miteinander verwandt), wie ändert sich das soziale Gefüge, wenn man eine Person herausnimmt (wegzieht, die Firma verlässt, stirbt).

Beispiel

Die möglichen Springerzüge. Die mit einem Punkt markierten Felder sind diejenigen Felder, die der Springer (das Pferdchen) von seiner markierten Position aus mit einem Zug erreichen kann. Im zugehörigen Erreichbarkeitsgraphen muss also dieses Feld mit den acht angekreuzten Feldern durch eine Kante verbunden werden. Dies muss man für alle ${}64$ Felder machen.

Wir betrachten eine Ansammlung von mehr oder weniger geometrisch gegebenen Punkten, wo zugleich eine gewisse Bewegungsvorschrift oder Sprungvorschrift oder Zugvorschrift festgelegt ist, mit der man von einem Punkt aus zu gewissen anderen Punkten gelangen kann, indem man diese Bewegungsvorschrift ausführt. Die Bewegungsvorschrift soll symmetrisch sein, also umkehrbar, man kann die Bewegung rückgängig machen. Grundsätzlich kann die Bewegungsvorschrift willkürlich für jeden einzelnen Punkt festgelegt werden, interessantere Strukturen ergeben sich aber, wenn die Bewegungsvorschrift homogen unter Berücksichtigung der geometrischen Konfiguration festgelegt ist. Eine solche Situation wird durch einen Erreichbarkeitsgraphen beschrieben. Die Knotenpunkte sind die geometrischen Punkte und zwei Punkte sind miteinander durch eine Kante zu verbinden, wenn man durch einen einzigen direkten Sprung von dem einen Punkt zu dem anderen gelangen kann.

Im Unterschied zu Beispiel 10.13 ist hier die Erreichbarkeit nicht transitiv, der Graph drückt die direkte Erreichbarkeit aus. Die dadurch festgelegte indirekte Erreichbarkeit, die durch eine Hintereinanderausführung von direkten Erreichbarkeiten gegeben ist, führt aber auch zu interessanten Fragestellungen, beispielsweise zur Frage, mit wie vielen Sprüngen man minimal von einem Punkt zu einem anderen Punkt kommen kann.

Bei einem Brettspiel hängen beispielsweise die erlaubten Züge von den Figuren ab. Die Felder des Brettspiels sind die Knotenmenge und jede Figur legt einen Erreichbarkeitsgraphen fest, den wir Spielzuggraph nennen. Eine Schachfigur (nicht der Bauer, dessen Bewegungsvorschrift ist nicht symmetrisch, da er nicht zurückziehen darf) ist durch ihre Zugmöglichkeiten festgelegt. Der Läufer kann diagonal beliebig weit ziehen, der Turm horizontal und vertikal beliebig weit, der König immer nur um eine Position, die Einschränkungen durch die Gesamtstellung spielen hier keine Rolle. Eine solche Interpretation spiegelt natürlich nur einen einzelnen Aspekt des Spiels wider.

Ein Spezialfall eines solchen Erreichbarkeitsgraphen liegt in einem Verkehrsnetz.

Beispiel

Ein Verkehrsnetz, beispielsweise ein ${}U$ -Bahnnetz, kann man in verschiedener Weise als einen Graphen interpretieren. Die Knotenmenge ist die Menge der Haltestellen. Man kann nun zwei Haltestellen miteinander durch eine Kante verbinden, wenn sie direkt durch eine Linie unmittelbar benachbart sind (wenn es eine direkte Tunnelverbindung ohne Zwischenstation gibt). Dies ist der Graph (Netzgraph), der üblicherweise als Netzplan aushängt (wenn verschiedene Linien eine Strecke lang parallel fahren, ist dies für den Graphen unerheblich, ist aber im Netzplan sichtbar). Man kann aber auch zwei Haltestellen miteinander durch eine Kante verbinden, wenn sie an einer gemeinsamen Linie liegen, also ohne Umsteigen erreichbar sind. Im eben erwähnten Netzplan ist dies durch die verschiedenen Farben der Linien einfach erkennbar. Würde man aber all diese Kanten hinmalen, ergäbe sich schnell eine unübersichtliche Darstellung der Netzsituation. Die volle Erreichbarkeit (also mit Umsteigen) wird typischerweise durch den vollständigen Graphen der Haltestellen dargestellt, es sei den, das Liniennetz zerfällt in zueinander disjunkte Teilnetze.

Beispiel

Oft drückt eine Kante in einem Graphen eine gewisse Verbundenheit zwischen den an der Kante beteiligten Knotenpunkten aus, es kann aber auch genau umgekehrt sein, dass man mit einem Graphen Ausschließungen ausdrücken möche. Man spricht dann von einem Ausschließungsgraphen. Beispielsweise kann es um eine Menge von Personen gehen, und die mit dem Graphen zu modellierende Relation ist etwas wie „sie gehen sich aus dem Weg“, „sie können nicht zusammen in einem Team arbeiten“, „sie vertragen sich nicht“. Die Knotenmenge kann aber auch eine Menge von Aussagen sein, die mit einer Kante zu verbinden sind, wenn die Aussagen sich widersprechen. Oder Klamotten, die nicht zueinander passen.

Wir besprechen die ersten strukturellen Eigenschaften, die ein Graph haben kann. Generell ist zu sagen, dass graphentheoretische Begriffe zumeist recht natürlich, naheliegend und intuitiv zugänglich sind. Es gibt Begriffe für einzelne Graphen und Klassen von Graphen und Begriffe und Invarianten für spezielle Eigenschaften. Man kann die Begriffe meistens direkt anhand von einfachen Graphen überprüfen und sich aneignen, was auch dadurch unterstützt wird, dass man kleine Graphen einfach skizzieren kann, und dabei die Skizzen wirklich die vollständige Information über den Graphen offen legen. Dennoch muss man auch in der Graphentheorie die genauen Definitionen und die gewählten Wörter lernen. Dieser vergleichsweise konkreten Bedeutung der graphentheoretischen Konzepte steht entgegen, dass die Komplexität eines Graphen mit seiner Knoten- und Kantenzahl sehr schnell wächst und dadurch die Theorie dann doch wieder, wie sich das für eine mathematische Theorie gehört, beliebig kompliziert wird, wovon tiefe Sätze wie der Vier-Farben-Satz und unbewiesene Vermutungen zeugen.

Definition

Ein Graph auf einer Menge ${}V$ heißt vollständig, wenn je zwei Punkte miteinander durch eine Kante verbunden sind.

Der vollständige Graph auf einer ${}n$ -elementigen Menge wird mit ${}K_{n}$ bezeichnet.

Definition

Ein Graph ${}G=(V,E)$ heißt kantenfrei, wenn die Kantenmenge ${}E$ leer ist.

Definition

Ein Graph ${}G=(V,E)$ heißt linear, wenn es eine Auflistung ${}v_{1},\ldots ,v_{n}$ aller Knoten derart gibt, dass die Kantenmenge gleich ${}\{v_{i},v_{i+1}\}$ , ${}i=1,2,\ldots ,n-1$ , ist.

Statt von einem linearen Graphen spricht man auch von einem Pfadgraphen.

Definition

Ein Graph ${}G=(V,E)$ heißt Sterngraph, wenn es in ihm einen Knoten (das Zentrum) gibt, der mit allen anderen Knoten verbunden ist und dies die einzigen Kanten des Graphen sind.

Beispiel

Der gleiche Graph, aber ohne Überkreuzungen gezeichnet.

Sei ${}d\in \mathbb {N}$ . Unter dem ${}d$ -dimensionalen Würfelgraphen versteht man die Knotenmenge bestehend aus den ${}d$ -Tupeln

(\pm ,\ldots ,\pm ),

bei der zwei Punkte genau dann durch eine Kante verbunden werden, wenn sie sich in genau einer Komponente unterscheiden. Statt Würfelgraph sagt man auch Hyperwürfel.

Beispiel

Wir betrachten in der Ebene eine endliche Familie von Geraden, ein solches Gebilde nennen wir eine Geradenkonfiguration. Zwei Geraden schneiden sich entweder in genau einem Punkt oder sie sind parallel zueinander. Einer solchen Geradenkonfiguration ordnen wir in folgender Weise einen Graphen zu. Als Knotenmenge nehmen wir die Menge der Geraden der Geradenkonfiguration, und wir verbinden zwei Knoten genau dann, wenn sich die zugrunde liegenden Geraden in der Konfiguration schneiden. Die „generische“ Geradenkonfiguration, bei der sich je zwei Geraden schneiden (also keine Parallelität vorliegt), ergibt den vollständigen Graphen, eine Geradenkonfiguration, die aus einer parallelen Geradenschar besteht, ergibt einen kantenfreien Graphen.

Beispiel

Es sei ${}M$ eine (endliche) Menge und ${}V={\mathfrak {P}}\,(M)$ die zugehörige Potenzmenge, die wir als Knotenmenge eines Graphen nehmen. Wir verbinden zwei Knoten, also zwei (verschiedene, um Schleifen zu vermeiden) Teilmengen ${}S,T\subseteq M$ genau dann durch eine Kante, wenn ${}S\cap T\neq \emptyset$ ist, wenn also die beiden Teilmengen nicht zueinander disjunkt sind. Man spricht vom Potenzmengengraphen.

Beispiel

Es sei ${}V$ eine Menge von natürlichen Zahlen. Wir verbinden zwei Zahlen durch eine Kante, wenn diese beiden Zahlen teilerfremd sind. Durch diese Vorschrift entsteht der Teilerfremdheitsgraph. Die ${}1$ ist zu jeder Zahl teilerfremd (auch zu sich selbst, das wird aber hier nicht berücksichtigt, da wir ohne Schleifen arbeiten) und damit mit jeder Zahl durch eine Kante verbunden (wenn die ${}1$ zu ${}V$ gehört), die ${}0$ ist nur zur ${}1$ teilerfremd. Im Komplementärgraph sind zwei Zahlen genau dann miteinander verbunden, wenn sie einen gemeinsamen Teiler ${}\geq 2$ haben.

Der Knotengrad

Definition

Zu einem Punkt ${}v\in V$ in einem Graphen nennt man die Anzahl der Kanten, die an ${}v$ anliegen, den Grad von ${}v$ . Er wird mit ${}d(v)$ bezeichnet.

Es ist also ${}d(v)={\#\left(N(v)\right)}$ .

Die folgende Aussage (bzw. das darauf folgende Korollar) heißt auch Handschlaglemma. Man überlege sich eine Handschlaginterpretation für diese Aussagen.

Lemma

Es sei ${}(V,E)$ ein Graph.

Dann gilt

${}\sum _{v\in V}d(v)=2\cdot {\#\left(E\right)}\,.$

Beweis

Das kann man beispielsweise durch Induktion über die Anzahl der Kanten bei gegebener Knotenmenge beweisen. Beim einem kantenlosen Graphen steht links und rechts beidseitig ${}0$ . Wenn man zu einem Graphen eine Kante hinzutut, sagen wir die Kante, die die beiden Punkte ${}u$ und ${}v$ verbindet, so erhöht sich der Grad von ${}u$ und der Grad von ${}v$ jeweils um ${}1$ und die anderen Grade bleiben unverändert. Somit erhöhen sich beide Seiten um ${}2$ .

\Box

Korollar

Es sei ${}(V,E)$ ein Graph.

Dann ist die Anzahl der Knoten, die einen ungeraden Grad besitzen, gerade.

Beweis

Es sei ${}V_{g}$ die Knoten mit einem geraden Grad und ${}V_{u}$ die Knoten mit einem ungeraden Grad. Nach Lemma 15.16 gilt

{}\sum _{v\in V_{g}}d(v)+\sum _{v\in V_{u}}d(v)=2\cdot {\#\left(E\right)}\,,

diese Zahl ist also gerade. Der linke Summand ist als Summe von geraden Zahlen ebenfalls gerade. Somit muss auch der rechte Summand gerade sein. Dies kann nur sein, wenn die Anzahl von ${}V_{u}$ gerade ist.