Ungerichtete Graphen/Typische Interpretationen/Einführung/Textabschnitt

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 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 (das gilt zur Zeit in Berlin).

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.