Eine besondere Art von Objekten wird in fast jedem Abschnitt dieses Online-Skriptums Verwendung finden: Graphen. Die Welt der Graphen ist bunt und reichhaltig. Da gibt es Wege, Bäume, Wurzeln, Blätter, Farben, Gewichte und vieles mehr. Auch abstraktere Begriffe wie Ecke, Kante, Weg, Länge und Kreis treten auf und erhalten neue Bedeutungen. Trotz - oder vielleicht gerade wegen - der Einfachheit der ihr zu Grunde liegenden Idee beherbergt sie eine Vielfalt komplexer Strukturen. Insbesondere in Zusammenarbeit mit anderen Teilgebieten der Mathematik ergibt sich eine Fülle von Anwendungen. Graphen dienen dazu, Beziehungsstrukturen, Abläufe und Verzweigungen übersichtlich darzustellen, sind manchmal unentbehrliche Hilfsmittel, um Probleme zu lösen und treten bisweilen sogar als die zentralen Objekte des Interesses auf. Die Graphentheorie ist ein schnell wachsendes Gebiet der modernen Mathematik. Aber auch in ästhetischer Hinsicht ist die Welt der Graphen nicht ohne Reize, stellt sie doch ein schönes Beispiel für einen "diskreten" Blick auf die Welt dar. Wir wollen hier
keine Einführung in die Graphentheorie geben, sondern nur einige
der grundlegenden Eigenschaften von Graphen besprechen, um ein bisschen
Sicherheit im Umgang mit ihnen zu gewinnen und um uns ein kleines Vokabular
für die folgenden Anwendungen zurecht zu legen. Wenden wir uns
also der Frage zu, was ein Graph ist.
Ein Graph (nicht zu verwechseln mit dem Begriff des Funktionsgraphen) ist ein Objekt, das in dieser Form veranschaulicht werden kann: Es besteht aus Ecken (schwarze Punkte, auch Knoten genannt, englisch vertices) und Kanten (rote Linien, auch Bögen genannt, englisch edges). Jede Kante verbindet genau zwei (voneinander verschiedene) Ecken. Dabei kommt es nicht auf die präzise Lage und Form der Ecken und Kanten an: Wichtig ist lediglich, welche Ecken durch wieviele Kanten miteinander verbunden sind. So wollen wir beispielsweise zwischen dem obigen Graph und diesem nicht unterscheiden. (Es ist ja lediglich eine Ecke nach oben gerutscht, und das Ganze wurde ein bisschen deformiert). Demgegenüber stellt diese Zeichnung einen davon echt
verschiedenen Graphen dar. Ein Graph drückt also in gewisser
Weise eine "Beziehungsstruktur" aus, wobei es auf die Art
der Beziehungen zwischen zwei Ecken nicht ankommt, sondern lediglich
auf ihre Anzahl.
Um zu präzisieren, worauf es beim Begriff des Graphen ankommt und worauf nicht, benötigen wir eine genaue Definition. Es gibt verschiedene (äquivalente) Methoden, den Begriff des Graphen formal zu fassen. Eine ist diese: Definition: Ein Graph ist gegeben durch
Überlegen wir kurz, was das bedeutet: Jede 2-elementige Teilmenge von E ist von der Form {x, y}, wobei x und y zwei (verschiedene) Elemente von E (d.h. zwei verschiedene Ecken) sind. (Man spricht auch von einem ungeordneten Paar). Die Funktion f ordnet jedem Element k Î K (d.h. jeder Kante) ein solches ungeordnetes Paar von Ecken zu. Die beiden Ecken dieses Paares bezeichnen wir als "durch die Kante k verbunden". Ist x Î E und k Î K, so sagen wir, dass "die Ecke x auf der Kante k liegt", wenn x Î f (k) ist. Durch diese Sprachregelungen entsteht die intuitive Vorstellung eines Graphen nach Art der obigen Zeichnungen. In der graphentheoretischen Literatur, die formal rigoroser vorgeht, als wir es in der Folge tun werden, wird ein Graph G als Tripel (E, K, f ) betrachtet, manchmal auch einfach als Paar (E, K) oder in der Form G(E, K) angeschrieben. Die Ecken- und Kantenmenge eines gegebenen Graphen G schreibt man auch in der Form E(G) und K(G). Beispiel für eine formale Charakterisierung eines Graphen:
Das ist genau der zu Beginn dieses Abschnitts angegebene Graph. (Übungsaufgabe: Fügen Sie die entsprechenden Ecken- und Kantenbezeichnungen in die erste der obigen Zeichnungen ein!) Genau genommen kommt es nicht einmal darauf an, welcher Art die Elemente der Mengen E und K sind, sondern nur auf deren Mächtigkeit. Wir bezeichnen zwei durch die Tripel (E, K, f ) und (E', K', f ' ) gegebenen Graphen als isomorph, wenn sie durch bloße Umbenennung von Ecken und Kanten auseinander hervorgehen. Formal ausgedrückt ist das dann der Fall, wenn es zwei bijektive Abbildungen h : E ® E' und j : K ® K' gibt, für die f ' = h o f o j-1 gilt, wobei die Wirkung von h auf 2-elementige Teilmengen von E durch h({x, y}) = {h(x), h(y)} definiert ist. Isomorphe Graphen werden vom graphentheoretischen Standpunkt nicht voneinander unterschieden.
Nun sollte klar sein, was an einem in der Ebene gezeichneten Schaubild eines Graphen relevant ist und was nicht. Von der formalen Strenge der obigen Betrachtungen werden wir in den folgenden Abschnitten kaum Gebrauch machen, sie sollte aber im Hinterkiopf immer mitschwingen. Im Allgemeinen kommt man mit einem intuitiven Bild des Graphen und einer korrekten Verwendung der Begriffe "Ecke" und "Kante" recht weit. Vor diesem Hintergrund bildet natürlich auch die Zeichnung eine legitime (und schulgerechte) Methode, Graphen anzugeben. Übungsaufgabe:
Begründen
Sie Ihre Antwort!
Wir werden im Folgenden zwei weitere Definitionen benötigen:
Der oben definierte Begriff des Graphen kann in vielerlei Hinsicht erweitert werden:
Von den daran anknüpfenden Begrifflichkeiten gibt die Seite http://de.wikipedia.org/wiki/Graph_(Graphentheorie) einen kleinen Geschmack. |
¬ Vorbemerkungen | Übersicht | Spaziergänge und Buslinien ® |