Graphen beschreiben

Hier ist eine Möglichkeit, ein soziales Netzwerk zu darzustellen:

Eine Linie zwischen den Namen zweier Personen bedeutet, dass sie sich kennen. Wenn es keine Linie zwischen zwei Namen gibt, dann kennen sich die betreffenden Personen nicht. Die Beziehung "einander kennen" ist bilateral. Zum Beispiel, wenn Audrey Gayle kennt, dann kennt Gayle auch Audrey.

Dieses soziale Netzwerk ist ein Graph . Die Namen sind in den Knoten des Graphen. Jede Linie ist eine Kante , die zwei Knoten verbindet. Wir bezeichnen eine Kante, die die Koten $u$u und $v$v verbindet durch das Paar $(u, v)$left parenthesis, u, comma, v, right parenthesis. Weil das "kennen sich" -Verhältnis in zwei Richtungen arbeitet, ist dieser Graph ungerichtet . Eine ungerichtete Kante $(u, v)$left parenthesis, u, comma, v, right parenthesis ist identisch zur Kante $(v, u)$left parenthesis, v, comma, u, right parenthesis. Später werden wir gerichtete Graphen kennenlernen, in denen die Beziehungen zwischen Knoten nicht unbedingt bilateral ist. In einem ungerichteten Graphen bezeichnet man eine Kante zwischen zwei Knoten, wie z.B. die Kante zwischen Audrey und Gayle, als inzident zu den beiden Knoten, und wir sagen, dass die Knoten, die durch eine Kante verbunden sind, benachbart oder Nachbarn sind. Die Anzahl der Knoten bestimmt die Ordnung und die Anzahl der Kanten die Größe eines Graphen.

Audrey und Frank kennen sich nicht. Angenommen, Frank möchte Audrey vorgestellt werden. Wie könnte er eine Referenz bekommen? Nun, er kennt Emily, die Bill kennt, der Audrey kennt. Es gibt also einen Weg von drei Kanten zwischen Frank und Audrey. In der Tat ist das der direkteste Weg für Frank, Audrey zu treffen; Es gibt keinen Weg zwischen ihnen mit weniger als drei Kanten. Wir nennen einen Weg zwischen zwei Knoten mit den wenigsten Kanten den kürzesten Weg . Wir haben diesen kürzesten Weg unten hervorgehoben:

Wenn ein Weg von einem bestimmten Knoten zurück zu sich selbst geht, ist das ein Zyklus oder Kreis. Das soziale Netzwerk enthält viele Zyklen: Einer von ihnen geht von Audrey zu Bill zu Emily zu Jeff zu Harry zu Ilana und zurück zu Audrey. Es gibt einen kürzeren Zyklus mit Audrey, wie unten gezeigt: Audrey zu Bill zu Gayle und zurück zu Audrey. Welche anderen Zyklen kannst Du finden?

Manchmal weisen wir den Kanten numerische Werte zu. Zum Beispiel können wir im sozialen Netzwerk Werte verwenden, um anzuzeigen, wie gut sich zwei Menschen gegenseitig kennen. Oder, um ein anderes Beispiel zu bemühen, stellen wir eine Straßenkarte als Graphen dar. Angenommen, es gibt keine Einbahnstraßen, dann ist eine Straßenkarte ein ungerichteter Graph, mit Städten als Knoten und Straßen als Kanten. Die Werte an den Kanten geben den Abstand zwischen den Städten an. Hier ist eine nicht maßstabsgetreue Straßenkarte von einigen Autobahnen in den nordöstlichen Vereinigten Staaten:

Der allgemeine Begriff, den wir für eine Zahl verwenden, die wir einer Kante zuweisen, ist ihr Gewicht , und ein Graph, dessen Kanten Gewichte haben, ist ein gewichteter Graph . Wenn wir also die kürzeste Entfernung zwischen zwei Standorten finden wollen, suchen wir einen Weg zwischen zwei Knoten mit der minimalen Summe der Kantengewichte über alle Wege zwischen den beiden Knoten. Wie bei ungewichteten Graphen nennen wir einen solchen Weg einen kürzesten Weg . Zum Beispiel führt in diesem Graph der kürzeste Weg von New York nach Concord von New York über New Haven über Hartford über Sturbridge über Weston über Reading nach Concord - insgesamt 289 Meilen.

Die Beziehung zwischen Kanten geht nicht immer in beide Richtungen. In einer Straßenkarte könnte es zum Beispiel Einbahnstraßen geben. Hier ist eine Grafik, die zeigt in welcher Reihenfolge ein Eishockey Torwart seine Ausrüstung anziehen könnte:

Nun sind Kanten, die als Pfeile dargestellt sind, gerichtet . Damit erhalten wir einen gerichteten Graph . Hier zeigen die Pfeile an in welcher Reihenfolge die Ausrüstungsteile angelegt werden müssen. Zum Beispiel bedeutet die Kante vom Schulterschutz (chest pad) zum Trikot (sweater), dass der Schulterschutz vor dem Trikot angezogen wird. Die Zahlen neben den Eckpunkten zeigen einen der vielen möglichen Reihenfolgen, in denen man die Ausrüstung anziehen kann, so dass die Unterhosen (undershorts) zuerst angezogen werden, dann die Socken (socks), dann die Hosen (compression shorts) und so weiter, bis zuletzt der Blocker. Du hast vielleicht bemerkt, dass dieser gerichtete Graph keine Zyklen hat. Wir nennen einen solchen Graph einen gerichteten azyklischen Graph oder gag . Natürlich können wir auch gewichtete gerichtete Graphen haben, wie z.B. Straßenkarten mit Einbahnstraßen und Entfernungen.

Wir verwenden unterschiedliche Terminologie für gerichteten Kanten. Wir sagen, dass eine gerichtete Kante einen Knoten verläßt und in einen anderen eintritt. Zum Beispiel verlässt eine gerichtete Kante den Knoten für chest pad und tritt in den Knoten für sweater ein. Wenn eine gerichtete Kante den Knoten $u$u verlässt und in den Knoten $v$v eintritt, bezeichnen wir sie mit dem Tupel $(u, v)$left parenthesis, u, comma, v, right parenthesis, wobei dabei die Reihenfolge der Knoten wichtig ist. Die Anzahl der Kanten, die einen Knoten verlassen, ist sein Ausgangsgrad , und die Anzahl der eingehenden Kanten ist der Eingangsgrad .

Wie man sich vorstellen kann, haben Graphen - sowohl gerichtet als auch ungerichtet - viele Anwendungen für die Modellierung von Beziehungen in der realen Welt.

Wenn wir mit Graphen arbeiten, ist es hilfreich, über die Menge von Knoten und die Menge von Kanten zu reden. Wir bezeichnen normalerweise die Knotenmenge, mit $V$V und die Kantenmenge mit $E$E. Wenn wir einen Graphen darstellen oder einen Algorithmus auf einem Graphen ausführen, wollen wir oft die Größen der Knoten- und Kantenmengen in asymptotischer Notation verwenden. Angenommen, wir wollen über eine Laufzeit sprechen, die linear zur Anzahl der Ecken ist. Streng genommen sollten wir sagen, dass sie $\Theta (| V |)$\Theta, left parenthesis, vertical bar, V, vertical bar, right parenthesis ist, mit der Notation $| \cdot |$vertical bar, dot, vertical bar, Um den Betrag einer Menge zu bezeichnen. Aber die Verwendung dieser Mengenbetragsnotation in asymptotischer Notation ist umständlich, und so nehmen wir die Konvention an, daß in asymptotische Notation und nur in asymptotischer Notation die Mengenbetragsnotation fallengelassen wir mit dem Verständnis, dass wir über Mengenbeträge sprechen, Also, anstelle von $\Theta (| V |)$\Theta, left parenthesis, vertical bar, V, vertical bar, right parenthesis, schreiben wir nur $\Theta (V)$\Theta, left parenthesis, V, right parenthesis. Ähnlich, anstelle von $\Theta (\lg | E |)$\Theta, left parenthesis, \lg, vertical bar, E, vertical bar, right parenthesis, schreiben wir $\Theta (\lg E)$\Theta, left parenthesis, \lg, E, right parenthesis.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.