Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 16/kontrolle
- Untergraphen
Ein Graph heißt Untergraph eines Graphen , wenn , und die Kanten aus nur Bezug auf Punkte aus nehmen.
Einen Untergraphen kann man auch durch die beiden Eigenschaften und
charakterisieren. Zu einem Graphen und einer Teilmenge gibt es eine Vielzahl an Untergraphstrukturen, abhängig davon, welche Kanten aus , deren beide Endpunkte zu gehören, in übernommen werden und welche nicht. Jede Teilmenge ist mit der leeren Kantenmenge ein Untergraph. Für jeden Graphen gilt .
Zum Sprachgebrauch der folgenden Definition vergleiche auch Definition 7.15.
Ein Untergraph heißt voll, wenn jede Kante aus , die Punkte aus verbindet, auch eine Kante in ist.
Bei einem vollen Untergraphen werden also alle Kanten aus übernommen, die Bezug auf die Teilmenge nehmen. Statt von einem vollen Untergraphen spricht man auch von einem induzierten Untergraphen.
- Homomorphismen von Graphen
Es seien und Graphen. Eine Abbildung mit der Eigenschaft, dass aus stets folgt, heißt Graphhomomorphismus.
Ein Homomorphismus von Graphen ist einfach eine relationserhaltende Abbildung, er führt adjazente Knotenpunkte in adjazente Knotenpunkte über. Er wird kurz als notiert. Ein Untergraph ist im Wesentlichen dasselbe wie ein injektiver Graphhomomorphismus.
Eine Hintereinanderschaltung von Graphhomomorphismen ist wieder ein Graphhomomorphismus.
Beweis
Es seien und Graphen. Ein Graphhomomorphismus heißt Isomorphismus, wenn es einen Graphhomomorphismus
derart gibt, dass
und
gilt.
Zwei Graphen und heißen isomorph, wenn es einen Graphisomorphismus gibt.
Isomorphe Graphen sind hinsichtlich sämtlicher graphentheoretischen Eigenschaften als gleich anzusehen.
Gelegentlich braucht man die folgende Variante eines Graphhomomorphismus, insbesondere, wenn durch eine Kante verbundene Knotenpunkte auf einen Punkt abgebildet werden sollen.
Es seien und Graphen. Eine Abbildung mit der Eigenschaft, dass aus entweder oder aber folgt, heißt schwacher Graphhomomorphismus.
- Konstruktionen für Graphen
Zu einem Graphen nennt man den Graphen den komplementären Graphen (oder Komplementärgraph). Er wird mit bezeichnet.
Es wird also die Knotenmenge übernommen und eine zweielementige Teilmenge ist genau dann eine Kante des komplementären Graphen, wenn sie keine Kante des Ausgangsgraphen ist. Dabei entsprechen sich der vollständige Graph und der kantenfreie Graph. Wenn Punkte und Kanten besitzt, so besitzt gerade Kanten. Der komplementäre Graph des komplementären Graphes ist wieder der Ausgangsgraph, also .
Zu einem Graphen und einer Teilmenge der Kantenmenge versteht man unter denjenigen Graphen, dessen Punktemenge ist und dessen Kantenmenge aus besteht.
Für schreibt man abkürzend für .
Es sei ein Graph. Man nennt denjenigen Graphen, dessen Knotenmenge die Kantenmenge von ist und bei dem zwei Knoten und (also Kanten aus ) genau dann durch eine Kante verbunden werden, wenn und einen gemeinsamen Punkt in besitzen, den Kantengraphen zu .
Der Kantengraph zu einem Sterngraph mit Punkten, also einem Zentrum mit daran anliegenden Blättern, ist ein vollständiger Graph mit Punkten.
Es sei ein Graph und der zugehörige Kantengraph. Dann gelten folgende Aussagen.
- Die Anzahl der Punkte von ist gleich der Anzahl der Kanten von .
- Der
Grad
eines Punktes von
(also einer Kante von ) ist
- Die Anzahl der Kanten von ist
- Dies folgt unmittelbar aus der Definition des Kantengraphen.
- Es sei eine Kante von , aufgefasst als Punkt im Kantengraph . Dieser Punkt ist mit einem anderen Punkt des Kantengraphen, also einer Kante des Ausgangsgraphen, genau dann verbunden, wenn diese Kante an oder an anliegt, wobei nur eines der Fall sein kann. Die Anzahl der an anliegenden Kanten ist , allerdings dürfen wir die Kante nicht mitzählen.
- Nach
Lemma 15.16
ist die gesuchte Anzahl der Kanten in unter Verwendung von Teil (2) gleich
da in der mittleren Summe der Term so oft vorkommt, wie es angibt.
- Äquivalenzrelationen und Quotientengraphen
Man beachte, dass dabei jede Kante nur einfach genommen wird, auch wenn sie im Urbild durch mehrere Kanten repräsentiert sein sollte.
Es sei ein Graph, eine Menge und eine Abbildung. Es werde mit der Struktur des Bildgraphen versehen.
Dann ist ein schwacher Homomorphismus von Graphen.
Beweis
Wir betrachten den durch eine U-Bahn in einer Stadt gegebenen Graphen, der aus der Menge der Haltestellen gegeben ist, und bei dem zwei Haltestellen durch eine Kante verbunden werden, wenn sie ohne Umsteigen verbunden sind, also an einer Linie liegen (siehe Beispiel 15.5). Es ist nicht zu erwarten, dass jede Haltestelle mit jeder anderen Haltestelle durch eine direkte Linie verbunden ist. Die Steuereinnahmen sprudeln kräftig und so möchte man wissen, ob zumindest jeder Stadtteil mit jedem Stadtteil ohne Umsteigen erreichbar ist. Dazu stellt man einen neuen Graphen auf, bei dem die Knotenpunkte die Stadtteile repräsentieren und bei dem zwei Stadtteile genau dann miteinander durch eine Kante zu verbinden sind, wenn es eine Haltestelle im einen und eine Haltestelle im andern Stadtteil gibt, die durch eine U-Bahnlinie verbunden sind.
In einer Firma arbeiten verschiedene Personen , und manche Personenpaare arbeiten gemeinsam an gewissen Aufgaben, was durch einen Kooperationsgraphen ausgedrückt wird. Es steht ein Stellenabbau an, bei dem die Aufgaben von mehreren Personen in Zukunft von einer einzigen (alten oder neuen) Person übernommen werden soll. Dabei sollen sämtliche Kooperationen übernommen werden, das heißt, dass jede Kooperation zwischen zwei (alten) Personen in eine Kooperation der diese Personen ersetzenden (neuen) Personen übertragen werden soll. Der einfachste nichttriviale Spezialfall hiervon ist, dass zwei Personen durch eine Person ersetzt werden und die bisherigen Kooperationen auf diese neue Person übergehen.
Die beiden vorstehenden Beispiele werden durch das folgende Konzept erfasst. Die Äquivalenzrelation ist im ersten Beispiel durch „liegt im gleichen Stadtteil“ und im zweiten durch „werden durch eine Person ersetzt“ gegeben.
Es sei ein Graph und sei eine Äquivalenzrelation auf . Dann nennt man die Quotientenmenge , versehen mit der Bildgraphstruktur zur kanonischen Abbildung
den Quotientengraphen zu . Er wird mit bezeichnet.
Es sei ein Graph und eine Kante, die die Knotenpunkte und verbindet. Man nennt denjenigen Graphen mit der Knotenmenge , bei der und miteinander identifiziert werden, und bei dem die Kantenmenge aus den Bildkanten zur Kontraktionsabbildung besteht, den Kontraktionsgraphen zu . Er wird mit bezeichnet.
Der Kontraktionsgraph ist einfach der Quotientengraph zur Äquivalenzrelation, bei der und (zusammen eine Kante bilden und) zueinander und ansonsten jeder Punkt nur zu sich selbst äquivalent ist. Eine rekursive Argumentation unter Bezug auf Kontraktionsgraphen werden wir in Lemma 18.12 und in Lemma 24.12 verwenden.
Es sei ein schwacher Homomorphismus zwischen den Graphen und .
Dann gibt es eine Faktorisierung von als
wobei die Quotientenabbildung zu einer Äquivalenzrelation auf ist, ein Isomorphismus ist, einen knotenidentischen Untergraphen und einen vollen Untergraphen beschreibt.
Wir definieren die Äquivalenzrelation auf durch , wenn . Es gibt dann nach Lemma 11.13 eine Abbildung
wodurch faktorisiert. Dabei ist injektiv und ebenfalls nach der Definition der Kanten auf ein Graphhomomorphismus. Der Bildgraph zu (der auch der Bildgraph von ist), ist ein Untergraph von , der zu isomorph ist. Wenn man durch die Kanten aus auffüllt, die zwischen Punkten aus verlaufen, so erhält man einen knotenpunktgleichen vollen Untergraphen von .
- Konstruktionen aus mehreren Graphen
Es gibt eine Vielzahl an Möglichkeiten, aus zwei Graphen einen neuen Graphen zusammenzusetzen.
Zu zwei Graphen und mit disjunkten Knotenmengen und nennt man den Graphen mit der Knotenmenge und der Kantenmenge die disjunkte Vereinigung der Graphen.
Zu zwei Graphen und nennt man den Graphen mit Knotenmenge , wobei zwischen zwei Knoten und genau dann eine Kante besteht, wenn entweder und oder und gilt, das kartesische Produkt der Graphen.
Beispielsweise ist das kartesische Produkt von zwei linearen Graphen ein rechteckiger Gittergraph, es gibt dort nur horizontale und vertikale Kanten.
- Die Automorphismengruppe eines Graphen
Es sei ein Graph. Ein Isomorphismus heißt Automorphismus.
Zu einem Graphen nennt man die Gruppe aller Automorphismen
die Automorphismengruppe von . Sie wird mit bezeichnet.
Statt von der Automorphismengruppe spricht man auch von Symmetriegruppe des Graphen.
Die Automorphismengruppe eines Sterngraphen mit einem Zentrum und Blättern ist die volle Permutationsgruppe , da man die Blätter beliebig ineinander überführen kann und das Zentrum auf sich selbst abgebildet werden muss.
Wir wollen die Automorphismengruppe des chemischen Elementes Butan (bzw. der zugehörigen Darstellung als Graph ) bestimmen. Zunächst halten wir fest, dass die Benennung von einigen Knotenpunkten mit und mit (was natürlich eine chemische Bedeutung hat) keine eigenständige graphentheoretische Information dartellt, da sie ja aus dem Graphen direkt rekonstruierbar ist: Die Punkte mit dem Grad werden mit und die Punkte mit dem Grad , also die Blätter, werden mit bezeichnet. In den folgenden Überlegungen werden wir zwecks Vereinfachung die chemischen Benennungen verwenden. Ein Automorphismus des Graphen führt -Atome in -Atome und -Atome in -Atome über, da der Grad bei einem Isomorphismus erhalten bleibt. Dies führt insbesondere zu einem Gruppenhomomorphismus
wobei die Gruppe der Permutationen auf den vier -Atomen und die Einschränkung eines Automorphismus bezeichnet. Bei einem Automorphismus des Moleküls wird also geschaut, was dieser mit den -Atomen macht. Diese Gesamtzuordnung ist ein Gruppenhomomorphismus. Die vier -Atome haben zwar alle den Grad , sie sind aber nicht gleichberechtigt, die beiden äußeren sind mit drei Blättern und die beiden inneren sind mit zwei Blättern verbunden. Wenn man die beiden inneren vertauscht, so muss man auch die beiden äußeren vertauschen, da ja bei einem Automorphismus Kanten erhalten bleiben. Deshalb ist das Bild von die zyklische Gruppe
(in der Tat ist die Spiegelung an der vertikalen Achse ein Automorphismus). Wir haben also einen surjektiven Gruppenhomomorphismus
Dies erleichtert die Bestimmung der Automorphismengruppe, da man diese aufspalten kann nach solchen Automorphismen, die auf den -Atomen identisch wirken, und solchen, die die -Atome spiegeln. Aufgrund von gruppentheoretischen Gesetzmäßigkeiten gibt es von beiden Sorten gleich viele. Deshalb betrachten wir nur noch den Kern von . Es sei also ein Automorphismus, der auf den -Atomen identisch wirkt. Dann wird jedes -Atom unter auf ein -Atom abgebildet, das mit dem selben -Atom verbunden ist. Was unter mit den an einem -Atom hängenden -Atomen passiert, ist unabhängig voneinander. Der Kern ist deshalb gleich
und besitzt Elemente, die gesamte Automorphismengruppe besitzt Elemente.
Ein homogener Graph sieht in jedem Punkt gleich aus, keine zwei Punkte sind durch graphentheoretische Eigenschaften unterscheidbar. Ein vollständiger Graph und ein leerer Graph sind homogen.
Ein Graph heißt starr, wenn die Automorphismengruppe von trivial ist.
Bei einem starren Graphen sind je zwei Knotenpunkte graphentheoretisch unterscheidbar. Statt starr sagt man auch asymmetrisch oder rigide.
Der abgebildete Graph ist starr. Bei einem solchen Nachweis geht man am besten sukzessive vor, man zeigt für einen Automorphismus unter Bezug auf graphentheoretische Eigenschaften, dass er alle Knoten auf sich selbst abbildet, wobei man mit besonders einfachen Knotenpunkten anfängt und dann weitere Knotenpunkte betrachtet und dabei verwendet, dass andere Knotenpunkte auf sich selbst abgebildet werden. Es sei also ein Automorphismus von . Der Graph verfügt nur über ein einziges Blatt (links oben), diese muss auf sich selbst abgebildet werden. Damit muss auch der an das Blatt anliegende Knotenpunkt auf sich selbst abgebildet werden. Die an anliegenden Knotenpunkte (außer ) haben die Grade , sie müssen also jeweils auf sich selbst abgebildet werden. Dann muss auch der verbleibende Punkt auf sich selbst abgebildet werden.
