WikiDer > Graphentheorie

EIN Anzahl mit sechs Knöpfen.

Das Graphentheorie ist ein Teilbereich der Mathematik dass die Eigenschaften von Grafiken Studien.

Ein Graph besteht aus einer Menge Punkte, sogenannte Knoten, von denen einige durch verbunden sind Linien, die Seiten, Seiten, Äste oder Bögen. Je nach Anwendung können die Linien gerichtet sein, dann nennt man sie auch Pfeile, dann spricht man von einem gerichteten Graphen. Den Linien werden auch Gewichte durch Zahlen zugewiesen, die beispielsweise den Abstand zwischen zwei Punkten darstellen. Ein Graph mit Gewichten wird als gewichteter Graph bezeichnet.

Strukturen, die als Graphen dargestellt werden können, sind üblich. Grafiken werden beispielsweise verwendet, um endliche Automaten zu modellieren oder eine schematische Roadmap zwischen mehreren Orten und deren Entfernungen zu erstellen. Verschiedene Arten von Grafiken spielen in der Informatik eine Rolle, nicht nur in Form von Baumstrukturen, sondern auch um den Datenverkehr über Netzwerke anzuzeigen. Dort kann Algorithmen werden durchgeführt, um bestimmte Eigenschaften eines solchen Graphen zu berechnen und auf dieser Grundlage Vorhersagen oder Entscheidungen über das Optimum zu treffen Route Für ein Datenpaket; Dies ist daher ein wichtiges Fach in der Informatik.

Komplexe Netzwerke sind ein relativ junges Gebiet der Graphenforschung, das sich weniger auf das Studium kleiner Graphen und die Eigenschaften einzelner Knoten und Seiten in diesen Graphen konzentriert, sondern eher auf die statistischen Eigenschaften großräumiger Netzwerke.

Definition

Zur Definition von Graphen werden mehrere Definitionen verwendet. Hier sind die Definitionen, wie sie in dieser Enzyklopädie verwendet werden.

Ein Graph besteht aus a Sammlung Knoten oder Scheitelpunkte und eine Ansammlung von Seiten, Seiten, Bögen oder Ästen (Kanten) von Knotenpaaren. Formaler:

ein Graf ${Anzeigestil G=(V,E)}$ ist ein geordnetes Paar, in dem ${Anzeigestil V}$ ist eine beliebige Menge und wobei set ${Anzeigestil E}$ ist eine Sammlung bestehend aus Multi-Sets von zwei Elementen, die unterschiedlich sein können oder nicht ${Anzeigestil V}$. Die Elemente von ${Anzeigestil V}$ heißen Knoten (oder Punkte) des Graphen ${Anzeigestil G}$ und die Elemente von ${Anzeigestil E}$ heißen die Seiten (auch Seiten, Linien, Bögen oder Äste) von ${Anzeigestil G}$. Die Knoten, die eine Seite bilden, werden als Endpunkte der Seite bezeichnet.

Zur Verdeutlichung schreibt man auch

${displaystyle V_{G}{ ext{ or }}V(G)}$ für die Knöpfe von ${Anzeigestil G}$

${displaystyle E_{G}{ ext{ or }}E(G)}$ für die Seiten von ${Anzeigestil G}$

Normalerweise wird davon ausgegangen, dass eine Seite zwei verschiedene Knoten verbindet oder möglicherweise eine Schlaufe ist und zum selben Knoten zurückkehrt.

Ein weiter gefasster Graphenbegriff erlaubt es, zwei Knoten durch mehr als eine Seite zu verbinden: man spricht von a Multigraph. Die Seitensammlung ${Anzeigestil E}$ ist dann a Multi-Set von Teilmengen von ${Anzeigestil V}$ mit zwei Elementen. In der grafischen Darstellung wird statt jeder Seite einzeln die Anzahl der Seiten zwischen zwei Knoten manchmal als eine Seite mit einer Zahl daneben angezeigt, die die Anzahl der Seiten darstellt.

Terminologie und Notation

• Die Elemente von ${Displaystil V_{G}}$ heißen die Knoten oder Punkte des Grafen ${Anzeigestil G}$.
• Die Elemente von ${displaystyle E_{G}}$ heißen die Seiten, Linien, Seiten, Bögen oder Geäst des Grafen ${Anzeigestil G}$.
• Eine Anmerkung ${displaystyle v_{1}sim v_{2}}$ wie die zwei knoten ${displaystyle v_{1}}$ und ${displaystyle v_{2}}$ sind miteinander verbunden.
• Zwei Knoten werden zusammen genannt in Verbindung gebracht wenn es eine Seite dazwischen gibt.
• Wenn der Knoten ${Anzeigestil v}$ ist ein Start- oder Endpunkt der Seite ${displaystyle e}$, heiß ${Anzeigestil v}$in Verbindung gebracht mit ${displaystyle e}$.
• EIN Schleife ist eine Seite, die einen Knoten mit sich selbst verbindet.
• EIN gehen zwischen zwei verbundenen Knoten ${Anzeigestil a}$ und ${displaystyle b}$ ist eine Reihe zusammenhängender Knoten, von denen ${Anzeigestil a}$ der Anfang und ${displaystyle b}$ das ende ist. Die Reihe der Knöpfe ${displaystyle (v_{1},ldots ,v_{n})}$ ist also ein Spaziergang zwischen ${Anzeigestil a}$ und ${displaystyle b}$, wenn

${displaystyle a=v_{1}sim v_{2}sim ldots sim v_{n}=b}$

• In einem ungewichteten Graphen ist der is Länge eines Spaziergangs die Anzahl der Seiten in der Wanderung (die Anzahl der Knoten minus 1).
• Eine Zählung heißt kohärent, wenn zwischen jedem Knotenpaar des Graphen ein Spaziergang möglich ist.
• EIN Pfad zwischen zwei verbundenen Knoten ${Anzeigestil a}$ und ${displaystyle b}$ ist ein Spaziergang dazwischen ${Anzeigestil a}$ und ${displaystyle b}$ bei denen kein Knoten mehr als einmal vorkommt.
• Das Entfernung${Anzeigestil d(a,b)}$ zwischen zwei Knoten ${Anzeigestil a}$ und ${displaystyle b}$ die Länge des kürzesten Weges zwischen ${Anzeigestil a}$ und ${displaystyle b}$. Wenn zwischendurch kein Spaziergang möglich ist ${Anzeigestil a}$ und ${Anzeigestil b,}$ ist der Abstand zwischen ${Anzeigestil a}$ und ${displaystyle b}$ nicht definiert.
• Das Durchmesser eines zusammenhängenden Graphen ${Anzeigestil G}$ ist das Maximum der Längen der kürzesten Wege zwischen zwei Knoten ${Anzeigestil G}$.
• EIN Zyklus in einem Graphen ist ein Weg mit einer Länge größer Null von einem Knoten zu sich selbst.
• Das Taille eines zusammenhängenden Graphen ist die Länge des kürzesten Zyklus im Graphen.
• Das Grad${displaystyle mathrm {deg} (v)}$ eines Knotens ${Anzeigestil v}$ ist die Anzahl der Seiten, mit denen ${Anzeigestil v}$ Ist verbunden.
• Wenn alle Knoten eines Graphen den gleichen Grad haben ${displaystyle g}$ haben, wird der Graf ${displaystyle g}$-regulär erwähnt. Eine Zählung heißt regulär wenn es eine Zahl gibt ${displaystyle g}$ ist, so dass die Zählung ${displaystyle g}$- ist regelmäßig.
• Zwei Grafiken ${Displaystil G_{1}}$ und ${Displaystil G_{2}}$ werden genannt isomorph, wenn ein Graph aus einem anderen entsteht, indem nur die Namen der Knoten geändert werden. Es gibt formelleres als a bijektion${Anzeigestil f:V(G_{1}) oder V(G_{2})}$ so dass ${Anzeigestil (u,v)in E(G_{1})}$ dann und nur dann, wenn ${Anzeigestil (f(u),f(v))in E(G_{2})}$.
• Die Zählung ${Displaystil G_{1}}$ heißt a Untergraph des Grafen ${Displaystil G_{2},}$ wie die Knoten und Seiten von ${Displaystil G_{1}}$ auch Knöpfe und Seiten von ${Displaystil G_{2}}$ sein, also wenn ${displaystyle V(G_{1})subsetq V(G_{2})}$ und ${displaystyle E(G_{1})subsetq E(G_{2})}$.
• EIN Partition eines Grafen ${Anzeigestil G}$ ist ein Partition aus der Knopfsammlung ${Displaystil V_{G}}$ von ${Anzeigestil G}$, also eine disjunkte Aufteilung der Knoten.

Einfaches Zählen

Das Singular Grafik ist die am häufigsten verwendete Grafikart. In einem einfachen Graphen gibt es keine Schleifen und es gibt nicht mehr als eine Seite zwischen zwei Knoten.

Der einfache Graph ist in der Mathematik und Informatik weit verbreitet. Über diese Graphen wurde eine Vielzahl von Aussagen gemacht bewährt.

Komponenten und verbundene Graphen

Ein Graph, der aus zwei Komponenten besteht.

Innerhalb eines einfachen ungerichteten Graphen ${Anzeigestil G}$ ist ein Komponente von ${Anzeigestil G}$ ein Untergraph ${Anzeigestil C=(V_{C},E_{C})}$ alle Knoten davon sind miteinander verbunden und mit keinem anderen Knoten verbunden. So:

${displaystyle V_{C}subsetq V_{G}}$

wenn ${displaystyle v,v'in V_{C}}$, als ${displaystyle vsim v'}$ und

für alle ${displaystyle vin V_{C},v'in V_{G}setminus V_{C}}$ gilt: ${displaystyle vot sim v'}$

Ein Graph, der nur eine Komponente hat und in dem es zwischen jedem Punktpaar einen Spaziergang gibt, ist also a verbunden Anzahl. Daraus folgt weiter, dass die Seiten eines Graphen nur zwischen Knoten derselben Komponente verlaufen, die Komponenten eines Graphen also insbesondere zusammenhängende Teilgraphen sind. Ein einfacher ungerichteter Graph zerfällt in voneinander getrennte Komponenten.

Matrixdarstellung eines Graphen

Wir können einen endlichen Graphen leicht in einer Matrix darstellen, de Bogenmatrix. Dies ist eine quadratische Matrix mit Dimensionen ${Anzeigestil n imes n}$, in welchem ${displaystyle n}$ ist die Anzahl der Knoten im Graphen. Das Element ${displaystyle a_{st}}$ in einer Reihe ${displaystyle s}$ und Spalte ${displaystyle t}$ in der Bogenmatrix ${Anzeigestil A}$ ist 1, wenn es eine Seite (Bogen) von gibt ${displaystyle s}$ zu ${displaystyle t}$ geht und 0 wenn nicht.

Beschriftete Anzahl	Bogenmatrix
	${displaystyle { egin{pmatrix}1&1&0&0&1&0/1&0&1&0&1&0/0&1&0&1&0&0/0&0&1&0&1&1/1&1&0&1&0&0/0&0&0&1&0&0/end{pmatrix}}}$

Einmal eingerichtet, kann die Bogenmatrix verwendet werden, um zu lesen, wie viele Wege es von einem Knoten zum anderen gibt. Durch die Bogenmatrix ${Anzeigestil A}$ hoch ${displaystyle n}$ zu erheben, kann man in der Spalte ${displaystyle t}$ in einer Reihe ${displaystyle s}$ Lesen Sie, wie viele Spaziergänge es von Länge gibt ${displaystyle n}$ von knoten ${displaystyle s}$ knoten ${displaystyle t}$.

Im obigen Beispiel ist

${displaymath A ^ {2} = {Egin {pmatrix} 3 & 2 & 1 & 1 & 2 & sub0 ; / 2 & 3 & 0 , 2 & 1 & 0/1 & 0 , 2 & 0 , 2 & 1/1 & 2 & 0 & 3 & 0 0/2 & 1 & 2 & 0 & 3 & 1/0 0 1 0 1 & 1end {pmatrix {u}} } {MMATRIX {u}} } / 6 & 3 & 5 & 1 & 7 , 2/3 & 5 & 0 5 & 1 & 0/3 & 1 & 5 & 0 + 6 + {f {3}}/6&7&1&6&3&0/1&2&0&3&0&0Ende{pmatrix}}}$

So gibt es z.B. drei Spaziergänge der Länge drei von Knoten 4 zu Knoten 6, nämlich 4~3~4~6, 4~5~4~6 und 4~6~4~6.

Der Baum

Ein Baum mit 6 Knoten und 5 Leinen.

Ein zusammenhängender Graph ohne Zyklen heißt a Baum. Dies liegt daran, dass ein solches Diagramm oft einem Baum in einer Zeichnung ähnelt. Ein Baum hat eine Seite weniger als er Knoten hat.

Ein Baum mit einer Ansammlung von Knoten ${Displaystil V_{B}}$ hast ${Anzeigestil |V_{B}|-1}$ Seiten

Beweise

Der Beweis geht mit volle Einweisung nach der Anzahl der Knoten.

1. Mit nur einem Knoten gibt es keine Seiten und die Aussage ist wahr,
2. Angenommen, die Aussage gilt für einen größeren Baum.
3. An diesen Baum wird ein neuer Knoten über genau eine Seite angeschlossen, denn wenn der Knoten an zwei Seiten mit dem Baum verbunden ist, entsteht ein Kreislauf.
4. Für jeden neuen Knoten wird also eine neue Seite hinzugefügt.

Es ist bei Algorithmen auf Bäumen oft nützlich und auch üblich, um einen Knoten im Baum zu bezeichnen und ihm einen besonderen Status innerhalb des Baumes zu geben, oft wird dieser Knoten als 'Anfang' des Baumes angesehen. Dieser Knoten wird dann die Wurzel des Baumes genannt.

Bäume gehören zu den Grundstrukturen der Mathematik und Informatik. Bäume werden häufig verwendet (oder ausgewählt), um Sammlungen von Objekten zu modellieren, die eine inhärente Hierarchie aufweisen. Bäume finden sich in interessanten Bereichen wie:

• Erforschung von Sprache und Struktur der Mathematik, als Modell für die Konstruktion von Begriffen, Dokumenten und dergleichen
• Zusammenstellung, als Modell für die Struktur von formale Sprachen
• Dateisysteme, wenn das Modell auf einem Dateisystem basiert
• Codierungstheorien, wie z Huffman-Codierung

Die Vielfalt und Popularität von Bäumen bedeutet, dass viele Algorithmen für Bäume als solche definiert wurden. Beispiele dafür sind

• Breitenorientierte Suche
• Tiefensuche
• Minimaler Spannbaum

Der Cyclegraph

Der Cyclegraph ${Displaystil C_{6}}$

Der Zyklusgraph mit ${displaystyle n}$ Tasten, ${displaystyle C_{n}}$, ist der einfache zusammenhängende Graph mit ${displaystyle n}$ Knoten, bei denen jeder Knoten mit zwei anderen verbunden ist. Ein solcher Graph hat die Form eines Kreises und enthält so viele Knoten wie Seiten. Der Kreisgraph mit der geringsten Anzahl von Knoten und Seiten ist der Graph ${displaystyle K_{3}}$.

Zyklusgraphen sind in der Informatik bekannt als Netzwerkmodell. Es Token-Ring Darauf basiert das Netzwerk. Zyklusgraphen dienen auch oft als Modell für lokale Suchalgorithmen.

Die vollständige Zählung

Die volle Zählung mit ${displaystyle n}$ Tasten, ${displaystyle K_{n}}$, ist der Graph, in dem alle Knoten miteinander verbunden sind.

Die folgenden Grafiken sind Beispiele für vollständige Grafiken:

Die vollständigen Grafiken ${displaystyle K_{1}...K_{8}}$.

Die Anzahl der Seiten von ${displaystyle K_{n}}$ ist ${displaystyle { frac {1}{2}}n(n-1)}$, es ${Anzeigestil (n-1)}$-ste Dreieckszahl.

Beweise

Die Anzahl der Seiten ist gleich der Anzahl der möglichen Knotenpaare, also die Anzahl der Möglichkeiten, um ${displaystyle n}$ Objekte, um zwei zu wählen. Diese Zahl ist die Binomialkoeffizient${displaystyle { inom {n}{2}}={ frac {1}{2}}n(n-1)}$.

EIN Clique oder Clique ist eine Teilmenge von Knoten, in der jeder Knoten mit allen anderen Knoten in dieser Teilmenge verbunden ist. Zusammen mit den Seiten, mit denen sie verbunden sind, bilden sie einen vollständigen Graphen.

Euler und Hamilton

Der Euler-Graphen ist eine spezielle Art von Graphen, die von den MathematikerLeonhard Euler als er sich mit dem Problem der sieben Brücken von Koningsbergen. Dieses Problem läuft auf die Frage hinaus, ob es in einem zusammenhängenden Graphen möglich ist, einen Walk zu haben, bei dem alle Seiten des Graphen genau einmal vorkommen, einen Euler Walk oder sogar einen solchen Walk, dass er im selben Knoten beginnt und endet , ein eulercycle.

Im 1736 Euler hat dieses Problem gelöst:

Ein einfacher zusammenhängender Graph enthält genau dann einen Euler-Zyklus, wenn der Grad aller Knoten gerade ist.

Beweise

${displaystyle Pfeil nach rechts }$

Jedes Mal, wenn ein Euler-Zyklus einen Knoten passiert, gibt es eine Seite, auf der der Zyklus ankommt und eine, auf der der Zyklus abfährt.

${Anzeigestil Pfeil nach links}$

Angenommen, es gibt zwei geschlossene Wege, also Zyklen, beide ohne Seiten zweimal verwendet, die keine Seite, sondern einen Knoten haben ${displaystyle k}$ verbreitet. Diese Zyklen können zu einem neuen Spaziergang zusammengeklebt werden: Starten Sie den ersten Spaziergang in ${Anzeigestil k.}$ Beende es und gehe dann zum nächsten über, das in . endet ${Anzeigestil k.}$ Angenommen, in einem einfachen zusammenhängenden Graphen haben alle Knoten einen geraden Grad. In diesem Diagramm kann ein Zyklus ohne Doppelseiten erstellt werden: Wählen Sie einen Knoten aus und beginnen Sie, über die Seiten zu gehen, bis er stoppt. Der Endpunkt ist gleich dem Startpunkt (alle Knoten haben geraden Grad, daher ist der einzige Knoten, der während des Spaziergangs einen unbenutzten Eingang und keine Ausgänge hat, der Knoten, an dem er begonnen hat). Entfernen Sie nun die Seiten, die im Zyklus verwendet wurden. Wiederholen Sie diesen Vorgang, bis alle Seiten fertig sind. Jetzt gibt es eine Reihe von losen geschlossenen Wegen, die keine Seiten haben, aber eine Reihe von Punkten gemeinsam haben. Fügen Sie nun alle Spaziergänge in der Weise des allgemeinen Kommentars oben zusammen, und das Diagramm, mit dem Sie begonnen haben, ist zurück mit dem darin erstellten Eulerzyklus.

${Displaystil K_{3}, K_{5}}$ und die "sieben brücken"

die Gräber ${displaystyle K_{3}}$ und ${displaystyle K_{5}}$ enthalten beide Euler-Zyklen. Der Graph, der das Problem der sieben Brücken darstellt, enthält keinen Euler-Zyklus.

Die Bedingung für einen Euler-Spaziergang ist etwas weniger streng.

Ein einfacher zusammenhängender Graph enthält genau dann eine Euler-Wanderung, wenn der Grad aller Knoten, möglicherweise außer zwei, gerade ist.

Beweise

${displaystyle Pfeil nach rechts }$

Wenn die Euler-Wanderung im selben Knoten beginnt und endet, handelt es sich um einen Euler-Zyklus und alle Knoten haben einen geraden Grad. Ansonsten ist ein Euler-Walk im Grunde ein Euler-Zyklus mit einer fehlenden Seite. Nehmen Sie nun den Euler-Weg im Graphen und legen Sie eine fiktive Seite zwischen Start- und Endknoten, dann liegt ein Euler-Zyklus vor, dessen Grad also aller Knoten gerade ist. Wird nun die fiktive Seite entfernt, wird vom Grad des Start- und Endknotens eins abgezogen. Ihre Grade werden dann ungerade, die Grade der restlichen Knoten bleiben gleich.

${Anzeigestil Pfeil nach links}$

Finden Sie die beiden Knoten ungeraden Grades, falls vorhanden, und zeichnen Sie eine fiktive Seite dazwischen. Jetzt sind die Grade aller Knoten gerade, es gibt also einen Euler-Zyklus. Entfernen Sie die fiktive Seite wieder, ein Euler-Zyklus minus einer Seite ist ein Euler-Weg.

Neben den Euler-Zyklen und Spaziergängen gibt es noch eine weitere Variante: den Zyklus und den Spaziergang, bei dem jeder Knoten einmal vorkommt. Dies sind der Hamilton-Zyklus und Hamilton Spaziergang. Diese Variante wurde erstellt von William Hamilton. Es gibt keine Eigenschaft von Graphen, die einen Hamilton-Kreis enthalten. der Mathematiker Øystein-Erz bewies den folgenden Satz: Die Zählung ${Anzeigestil G}$ enthält einen Hamilton-Zyklus, wenn die Summe der Grade eines beliebigen Paares nicht verbundener Knoten zusammen größer ist als die Anzahl der Knoten des Graphen.

Im Allgemeinen ist das Auffinden eines Hamilton-Zyklus in einem Graphen a NP-vollständig Problem; dies steht im Gegensatz zur Suche nach einem Euler-Zyklus, der dank der obigen Regeln in polynomieller Zeit gelöst werden kann. Ein Hamilton-Zyklus ist ein einfacher Fall von Probleme mit dem Handelsreisenden. Bei diesem Problem werden auch Distanzen zu den Verbindungen zwischen den Knoten oder Orten hinzugefügt und die Aufgabe besteht darin, den kürzesten Rundweg zu bestimmen.

Andere Grafiken

Der planare Graph

Planare oder planare Graphen sind Graphen, die auf einer flachen Ebene gezeichnet werden können, ohne dass sich die Seiten des Graphen schneiden.

${displaystyle K_{3}}$ ist eben, ${displaystyle K_{5}}$ ist nicht planar

Solche Graphen sind wichtig bei der Modellierung von Dingen wie Rohrleitungen und Leiterplatten für die Elektronik, bei denen die Verbindungen keinen Kontakt haben dürfen. In Bezug auf erstere sind planare Graphen der breiten Öffentlichkeit in Form von Rätseln bekannt wie "Versuchen Sie, drei Häuser an die Gas-, Wasser- und Stromquellen anzuschließen, ohne dass sich die Rohre kreuzen". Dies ist in der Tat die Frage, ob ${displaystyle K_{3,3}}$ ist eben.

Leonhard Euler dachte auch über planare Graphen nach und fand den Satz von Euler. Dieser Satz basiert auf der Anzahl der Knoten, Seiten und Flächen eines Graphen. Ein Bereich eines Graphen ist ein Teil des Graphen, der vollständig von Seiten oder äußeren Knoten des Graphen umgeben ist. Eine Fläche kann man sich als einen Teil des Papiers vorstellen, auf dem die Grafik gezeichnet wird. Die Anzahl der Bereiche hängt davon ab, wie genau der Graph gezeichnet wird, aber es stellt sich heraus, dass ein bestimmter Graph immer mit einer Anzahl von Bereichen gezeichnet werden kann, die sich nicht ändert, egal wie genau der Graph gezeichnet wird, es sei denn, der Graph wird gezeichnet nicht-planar.

Satz von Euler

Sie ${Anzeigestil G}$ ein zusammenhängender, planarer Graph mit ${Anzeigestil v}$ Tasten, ${displaystyle e}$ Seiten und ${displaystyle f}$ Bereiche. Dann gilt

${Anzeigestil v-e f=2}$

Beweise

Der Beweis geht per Induktion zu ${displaystyle e-v}$. weil ${Anzeigestil G}$ ist stimmig, gilt immer ${displaystyle e-vgeq -1}$.

Paar ${displaystyle e-v=-1}$, die Zählung ist dann ein Baum. Schon seit ${Anzeigestil G}$ enthält keine Zyklen, die Anzahl der Regionen ist 1. So

${Anzeigestil v-e f=1 1=2}$

Induktionsschritt: Nehmen Sie an, dass für alle planaren Graphen mit ${displaystyle -1leq e-v$ zählt das ${Anzeigestil v-e f=2}$.

Wir müssen beweisen, dass für einen beliebigen planaren Graphen mit ${displaystyle e-v=n}$ das Eigentum hält auch.

Der Graph enthält nun einen Zyklus. Dieser Zyklus trennt einen separaten Bereich. Wenn wir nun eine Seite aus dem Kreis entfernen, haben wir einen Graphen mit einer Seite und einer Fläche weniger. Wenn wir die Anzahl der Knoten, Seiten und Flächen in diesem Graphen messen ${displaystyle v',,e'}$ und ${displaystyle f'}$ anrufen, gilt

${Anzeigestil e'-v'=(e-1)-v=(e-v)-1=n-1}$,

und so wegen der Induktionshypothese:

${displaystyle v'-e' f'=2}$

Daraus können wir ableiten

${Anzeigestil v-e f=v'-(e' 1) (f' 1)=v'-e' f'=2}$,

Genau das mussten wir beweisen.

Der Satz von Euler zeigt, dass ein zusammenhängender Graph nur dann planar sein kann, wenn er nicht zu viele Seiten hat.

Sie ${Anzeigestil G}$ ein zusammenhängender, planarer Graph mit ${displaystyle vgeq 3}$ Knöpfe und ${displaystyle e}$ Seiten. Dann gilt

${displaystyle eleq 3v-6}$

Beweise

Die Idee hinter dem Theorem ist, dass es eine Beziehung zwischen der Anzahl der Seiten in gibt ${displaystyle K_{n}}$ und die Art der Bereiche, in denen ${Anzeigestil G}$ teilt die Ebene. Bei einer ebenen Wand fungiert jede Seite als „Innenwand“ und als „Außenwand“ einer (umschlossenen) Fläche – die „Außenseite“ des Graphen zählt als eine große Fläche. Zählen wir alle Innen- und Außenwände, dann kommen wir an ${Anzeigestil 2.}$ (jede Seite wird doppelt gezählt). Darüber hinaus hat jeder durch den Graphen getrennte Bereich eine bestimmte Form: Dreieck, Viereck, Fünfeck usw. Every ${displaystyle n}$-Winkel hat dann ${displaystyle n}$ Innenwände. Nennen wir die Anzahl der Dreiecksflächen ${displaystyle f_{3}}$, die Zahl der viereckigen ${displaystyle f_{4}}$, die Zahl der fünfeckigen ${displaystyle f_{5}}$, usw., dann können wir die Anzahl der Wände auch anders zählen:

${Anzeigestilsumme _{i=3}^{n}ncdot f_{n}}$,

so dass

${displaystyle 2e=3f_{3} 4f_{4} 5f_{5} ldots }$

Also das wissen wir auch

${displaystyle 2egeq 3f_{3} 3f_{4} 3f_{5} ldots =3f}$

Das bedeutet

${displaystyle v-e {frac {2e}{3}}geq 2}$

woraus folgt:

${displaystyle 3v-egeq 6}$

Anhand dieser Informationen können wir beispielsweise berechnen, ${displaystyle K_{5}}$ ist nicht eben.

Ähnlich wie oben können wir auch für zusammenhängende ebene Graphen ohne Dreiecke (also die "kleinste" Fläche ist ein Viereck) beweisen, dass ${displaystyle eleq 2v-4}$. Damit ist auch das Rätsel gelöst: ${displaystyle K_{3,3}}$ ist nicht eben.

Eine bemerkenswerte und nützliche Aussage ist die von Kuratowski: ein Graph ist genau dann planar, wenn er es nicht ist ${displaystyle K_{5}}$ oder ${displaystyle K_{3,3}}$ enthält. Mit anderen Worten, nur diese beiden Graphen sind tatsächlich nichtplanar.

Die zweigeteilte Zählung

Ein Beispiel für einen bipartiten Graphen

Eine zweigeteilte Zählung ${Anzeigestil G}$ ist ein Graph, dessen Knoten über eine Partition verteilt sind ${Displaystil V_{1},V_{2}}$ mit der Eigenschaft, dass ein Knoten in einem Teil nur mit einem Knoten im anderen Teil verbunden ist. Formal:

${displaystyle V_{G}=V_{1}cup V_{2}}$

${displaystyle V_{1}cap V_{2}=varnothing }$

${displaystyle v_{1}in V_{1}{ ext{ und }}v_{1}sim v_{2}}$, als ${displaystyle v_{2}in V_{2}}$

Es ist auch erlaubt, dass eine der beiden Mengen leer ist oder sogar beide, so dass ein Graph am 0- oder 1-Knoten auch zweiteilig ist.

Es ist auch klar, dass ${Displaystil C_{3}}$ ist der kleinste nicht bipartite Graph. Mit dieser Einsicht ist auch leicht zu erkennen, dass ein Graph nicht bipartit ist, wenn er einen Kreis ungerader Länge enthält. Gilt insbesondere für alle Grafiken ${Displaystil C_{2n 1}}$ dass diese tatsächlich nicht zweiteilig sind:

ein Graf ${Anzeigestil G}$ ist zweigeteilt ${displaystyleLeftrightarrow }$${Anzeigestil G}$ enthält keine ungeraden Zyklen

Beweise

${displaystyle Pfeil nach rechts }$

Paar ${Anzeigestil G}$ ist eine zweigeteilte Zählung. Alle Seiten von ${Anzeigestil G}$ also die Teilungsgrenze überschreiten. Wenn es nun einen Zyklus ungerader Länge gibt, gibt es einen Knoten des Zyklus mehr in einer Teilmenge als in der anderen – sozusagen befinden sich der "erste" und "letzte" Knoten des Zyklus in derselben Teilmenge. Diese beiden Knoten können jedoch nicht verbunden werden, um den Kreislauf zu schließen: Wenn dies der Fall ist, ist der Graph nicht zweiteilig.

${Anzeigestil Pfeil nach links}$

Paar ${Anzeigestil G}$ enthält keine ungeraden Zyklen. Das heißt, für jeden Zyklus in ${Anzeigestil G}$ der nicht mit einem anderen zusammenhängt Ich kann einen Knoten wählen, der in ${Displaystil V_{1}}$ Plätze, die nächste in ${Displaystil V_{2}}$, zurück im nächsten ${Displaystil V_{1}}$, und so weiter, und der letzte in ${Displaystil V_{2}}$ und dann überschreiten alle Seiten im Zyklus die Teilungsgrenze. Für alle anderen Knoten (Zyklen dagegen) ist deren Verteilung auf die Partitionen fest, sobald die Verteilung der oben genannten Zyklen gewählt wurde (und beachten Sie: auch für Zyklen in dieser Situation können sie perfekt verteilt werden , weil sie die gleiche Länge haben). Dadurch wird die Zählung zweiteilig.

Es gibt auch ${displaystyle k}$-partite Graphen, bei denen der Graph aufgeteilt ist in ${displaystyle k}$ Partitionen, für die es wiederum keine Linien zwischen Punkten in derselben Partition gibt. Vor dem ${Anzeigestil k=2}$ hast du die zweigeteilte Zählung wieder.

Die Petersengraaf

Petersengraaf.

Der nächste Graph ist als Petersen-Graph bekannt, definiert durch die dänischMathematiker Petersen.

An sich ist nichts Besonderes daran; Der Petersen-Graph kommt jedoch häufig in der Graphentheorie vor, als Beispiel für Beweise oder als Gegenbeispiel zur Widerlegung von Theoremen. Der Petersen-Graphen wird dann oft als Untergraph eines anderen, komplexeren Graphen verwendet.

Übrigens ist der Petersen-Graphen auch ein Beispiel für einen Graphen, der ${displaystyle K_{5}}$ enthält: wenn wir den äußeren "Knotenring" und den inneren "Ring" zusammenziehen, finden wir den ${displaystyle K_{5}}$-Grab. Wir können deutlich sehen, dass der Petersen-Graphen nicht planar ist.

Aushubarbeiten, die 2 Zähl- und induzierten Graphen

Der rechte Graph ist ein induzierter Untergraph auf der linken Seite.

Angenommen ein Diagramm ${Anzeigestil G}$ (oder eine Reihe verschiedener Graphen) können wir durch alle Arten von Operationen andere Graphen erstellen.

Für den Anfang gibt es die op ${Anzeigestil G}$induzierte Zählung${Anzeigestil G'.}$ Dieser Graph ist definiert durch:

${Anzeigestil G'=(V',E')}$

mit

${displaystyle V'subseteq V_{G}}$

und damit für alle Tasten ${displaystyle v_{1},v_{2}in V'}$ gilt

${displaystyle {v_{1},v_{2}}in E_{G}Pfeil nach rechts {v_{1},v_{2}}in E'}$

Die Tür ${Anzeigestil G}$ induzierte Zählung ${Anzeigestil G'}$ ist der Graph, der aus einer Anzahl von Knoten von besteht ${Anzeigestil G}$ und die entsprechenden Seiten von ${Anzeigestil G}$.

Zähle mit seinem Komplementgraphen.

Außerdem gibt es die Komplement-Grafik (oder komplementäre Grafik) ${displaystyle {overline {G}}}$ von ${Anzeigestil G,}$ definiert von:

${displaystyle {overline {G}}=(V_{overline {G}},E_{overline {G}})}$

mit

${Displaystil V_{overline {G}}=V_{G}}$

und damit für alle Tasten ${displaystyle v_{1},v_{2}in V', v_{1}eq v_{2}}$ gilt

${displaystyle {v_{1},v_{2}}nicht in E_{G}Pfeil nach rechts {v_{1},v_{2}}in E_{overline {G}}}$

Der Komplementgraph ${displaystyle {overline {G}}}$ von ${Anzeigestil G}$ hat die gleichen Knoten wie ${Anzeigestil G}$, aber alle möglichen Seiten, die nicht in sind ${Anzeigestil G}$ sitzen.

Zählen Sie mit dem entsprechenden Liniendiagramm.

Es gibt auch die Liniendiagramm${Anzeigestil L(G)=(V_{L},E_{L})}$ von ${Anzeigestil G}$, zeigt die Seiten von ${Anzeigestil G}$ als Knöpfe. Die Knöpfe von ${Anzeigestil L(G)}$ durch eine Seite verbunden sind, wenn die Originalseiten von ${Anzeigestil G}$ - Biene ${displaystyle {overline {G}}}$ Knoten - haben einen Knoten gemeinsam.

Dieser Graph ist definiert durch:

${Anzeigestil V_{L}=E(G)}$

${displaystyle {{v_{1},v_{2}},{v_{1}',v_{2}'}}in E_{L}}$ wenn

${displaystyle v_{1}=v_{1}'{ ext{ or }}v_{1}=v_{2}'{ ext{ or }}v_{2}=v_{1}'{ ext{ or }} v_{2}=v_{2}'}$

Die Vereinigung zweier disjunkter Graphen.

Für zwei Grafiken ${Anzeigestil G}$ die keine Knöpfe oder Schnürsenkel gemeinsam haben, die Verband und der kartesisches Produkt definiert sein. Der Verein von ${Anzeigestil G}$ und ${Anzeigestil H}$ ist die Zählung ${Anzeigestil Gcup H}$ mit

${Anzeigestil V(Gcup H)=V(G)cup V(H)}$

${Anzeigestil E(Gcup H)=E(G)cup E(H)}$

Das kartesische Produkt zweier Graphen.

Das kartesische Produkt von ${Anzeigestil G}$ und ${Anzeigestil H}$ ist die Zählung ${displaystyle-Gimes H}$ mit als Knoten die Knotenpaare von ${Anzeigestil G}$ und ${Anzeigestil H}$ und zwei solcher Knoten sind durch eine Seite verbunden, wenn einer der Knoten in den beiden Paaren gleich ist und die anderen verbunden waren. Der Verein ist somit definiert durch:

${Anzeigestil V(G imes H)=V(G) imes V(H)}$

${Anzeigestil {(g,h),(g',h')}in E(G imes H)}$ wenn

${displaystyle (g=g'{ ext{ und }}hsim h'){ ext{ or }}(gsim g'{ ext{ und }}h=h')}$

Von links nach rechts: ${Displaystil K_{2}^{0}, K_{2}^{1}, K_{2}^{2}}$ und ${displaystyle K_{2}^{3}}$.

Ein bekanntes Beispiel für die Graphenmultiplikation ist die Folge der "Potenzen" des 2-Graphen (d.h. ${displaystyle K_{2}}$): Dies sind die ${displaystyle n}$-dimensionale Würfel genau hier.

Gerichtete Grafiken

Eine Art von Graph, der häufig neben dem einfachen Graphen auftritt, ist der gerichteter Graph. Formal ist ein gerichteter Graph ein Graph ${Anzeigestil G=(V,E)}$ mit

${displaystyle Essubseteq {(v_{1},v_{2})mid v_{1},v_{2}in V,v_{1}ot =v_{2}}}$

Der Unterschied zum einfachen Graphen besteht darin, dass die Seiten keine ungeordneten Paare mehr sind, sondern geordnete Paare (die Seiten haben intuitiv eine Richtung). Beachten Sie, dass in der obigen Definition eine Seite ein geordnetes Paar und keine Menge ist. Dies bedeutet, dass die Seide ${Anzeigestil (a,b)}$ ist nicht gleich Seide ${Anzeigestil (b,a)}$.

Wegen der Richtung ist es normal, die Seiten in einem gerichteten Graphen als Pfeile zu zeichnen.

Viele der für einfache Graphen definierten Konzepte existieren auch für gerichtete Graphen. Es gibt Bäume, vollständige Graphen, Som-Graphen und Produkt-Graphen. Nur die Wirkung ist manchmal anders, denn die Richtung spielt jetzt eine Rolle. In einfachen Graphen gibt es zum Beispiel für jeden Knoten die Seite ${displaystyle k}$ nur ein Pfad ist von der Wurzel zu ${displaystyle k}$; in einem gerichteten Graphen kann es mehrere geben, ohne dass dies einen Kreis ergibt.

Richtungsgraphen werden häufig bei der Modellierung von Problemen verwendet, bei denen es keinen Sinn macht, Pfade in mehr als einer Richtung zu durchlaufen. Wenn Sie beispielsweise den Bau eines Hauses mit einem Diagramm planen, ist es nur sinnvoll, das Fundament für den Bau der Wände zu legen und umgekehrt.

Einige Unterschiede zu einfachen Grafiken

Es gibt einige typische Dinge, die sich in gerichteten Graphen von singulären Graphen unterscheiden. Grad hat zum Beispiel eine andere Bedeutung. Der Grad eines Knotens in einem einfachen Graphen ist die Anzahl der Seiten, mit denen der Knoten verbunden ist; in einem gerichteten Graphen ist die Definition etwas anders:

• Grad eines Knotens ${displaystyle k}$: die Anzahl der Seiten ${Anzeigestil (m,k)in E}$
• Grad eines Knotens ${displaystyle k}$: die Anzahl der Seiten ${Anzeigestil (k, n) in E}$

Ein gerichteter Graph enthält genau dann eine Euler-Wanderung, wenn die Ein- und Auswärtsgrade für alle Knoten im Graphen gleich sind. Der Beweis dafür ist derselbe wie für den einfachen Euler-Graphen.

Ein gerichteter Graph heißt zusammenhängend, wenn es ${displaystyle V=V_{1}cup V_{2}}$ eine Seite läuft von ${Displaystil V_{1}}$ zu ${Displaystil V_{2}}$ oder umgekehrt. Läuft eine solche Seite immer in beide Richtungen, d.h. gibt es zwischen jeweils zwei Knoten einen Spaziergang in beide Richtungen, dann heißt der Graph stark zusammenhängend.

Beschriftete und gewichtete Grafiken

Eine weitere gängige Erweiterung des einfachen Graphen ist die Beschriftung. In diesem Fall ist der Graph ${Anzeigestil G}$ um eine oder zwei Funktionen erweitert ${displaystyle f}$ und ${Displaystil g:}$

${Anzeigestil f:E(G) oder A}$

${Anzeigestil g:V(G) oder B}$

Die Funktionen ${displaystyle f}$ fügt zu jeder Seite hinzu, und die Funktion ${displaystyle g}$ zu jedem Knoten ein Element aus einer Reihe von Symbolen. Das Beschriften der Seiten ist häufiger als das Beschriften der Knoten.

Wenn die Symbole Zahlen sind (${displaystyle mathbb {N} ,mathbb {Z} ,mathbb {Q} ,mathbb {R} ,mathbb {C} }$, etc.), heet we de labeling een weging. De graaf heet dan een gewogen graaf. Een gewogen, gerichte graaf wordt ook wel een netwerk genoemd.

Labeling en met name weging worden gebruikt om aan een graaf speciale betekenissen toe te kennen. Wordt een graaf gebruikt als model voor een wegennet bij routeplanning, dan kan bij een weging bijvoorbeeld gedacht worden aan de lengte van de weg, of de drukte. Optimaliseringsproblemen op grafen gebruiken meestal weging als criterium aan de hand waarvan wordt geoptimaliseerd.

Het aantal gelabelde bomen op ${displaystyle v}$ knopen is ${displaystyle v^{v-2}}$

Bewijs

Het bewijs volgt uit de codering van Prüfer van knoop-gelabelde bomen. Deze constructie werkt als volgt:

• Van knoopgelabelde boom met ${displaystyle v}$ knopen naar prüferrij ter lengte ${displaystyle v-2:}$ kies het blad (knoop met graad 1) van de boom met het laagste label. Verwijder deze knoop en noteer het label van zijn buur. Ga zo door totdat er maar twee knopen over zijn en verwijder deze gewoon. Nu is er een prüferrij ter lengte ${displaystyle v-2}$, door steeds bladeren te verwijderen naar volgorde van grootte.

• Van de prüferrij ter lengte ${displaystyle v-2}$ naar knoopgelabelde boom met ${displaystyle v}$' knopen: Merk om te beginnen op dat een element van de prüferrij een buur is van een andere knoop in de boom. Alleen labels van bladeren in de nog op te bouwen (deel)boom staan dus niet in de rij. Schrijf nu alle getallen ${displaystyle 1,2,ldots ,v}$ op. Kies uit dit rijtje het laagste element dat niet in de prüferrij staat. Verbindt dit element met het eerste element van de prüferrij en streep beide weg. Herhaal dit totdat de Prüferrij leeg is. Er staan nu nog twee getallen in de rij – verbindt deze twee in de boom. Nu heb je een boom opgebouwd met ${displaystyle v}$' knopen, door steeds bladeren toe te voegen naar volgorde van grootte.

• Iedere boom op ${displaystyle v}$ knopen kan dus eenduidig gecodeerd worden als een rij van lengte ${displaystyle v-2}$. Ieder van deze elementen kan een van de getallen ${displaystyle 1,2,ldots ,v}$ zijn. Dat zijn dus ${displaystyle v^{v-2}}$ mogelijke combinaties.

Hypergrafen

Hypergrafen zijn een veralgemening van grafen, in zoverre dat in een hypergraaf een hyperkant een willekeurig aantal knopen kan verbinden, gaande van 1 tot het aantal knopen in de graaf.

Problemen op grafen

• Kleuren van grafen: de vierkleurenstelling
• De fundamenten van identificatie en systematisering van de grafen grafs (pdf)
• Routeproblemen:
  • Zeven bruggen van Koningsbergen
  • Minimaal opspannende boom
  • Kortstepadprobleem
  • Chinees postbodeprobleem
  • Handelsreizigersprobleem
• Stromen:
  • Max-flow-min-cut-stelling

Belangrijke algoritmes op grafen

• Dijkstra's algoritme
• Kruskals algoritme
• Prims algoritme
• Hongaarse methode
• Algoritme van Bellman-Ford

Gerelateerde wiskundige gebieden

• Ramsey-theorie
• Combinatoriek
• Complexe netwerken

Zie de categorie Graph theory van Wikimedia Commons voor mediabestanden over dit onderwerp.