Einfacher Graph - LinkFang.de





Einfacher Graph


Ein einfacher Graph (auch schlichter Graph) ist in der Graphentheorie ein ungerichteter Graph ohne Mehrfachkanten und ohne Schleifen.

Ein einfacher Graph ist also ein geordnetes Paar [math](V, E)[/math], wobei [math]V[/math] eine endliche Menge von Knoten und [math]E[/math] eine Menge von Kanten ist. Die Menge [math]E[/math] ist dabei Teilmenge der 2-elementigen Teilmengen von [math]V[/math], das heißt, jede Kante ist eine Menge von zwei Knoten.

Ein einfacher Graph mit [math]n[/math] Knoten kann demzufolge maximal [math]\textstyle {n \choose 2} = \frac{n (n-1)}{2} [/math] Kanten haben. Sind alle diese Kanten vorhanden, wird der Graph als vollständiger Graph [math]K_n[/math] bezeichnet.

Wenn die Kanten des Graphen zusätzlich mit Werten versehen sind (z.B. Entfernungen), spricht man von einer Gewichtung (auch Bewertung) der Kanten und dann von einem kantengewichteten Graphen.

Beispiel

Die Nachbarschaftsbeziehungen zwischen Deutschland und seinen Nachbarländern können als einfacher Graph modelliert werden. In diesem Beispiel umfasst die Menge [math]V[/math] die Länder und jede Kante steht dafür, dass zwei Länder benachbart sind. In der nebenstehenden Abbildung wird dieser Graph dargestellt, wobei die Knoten als Punkte und die Kanten als Verbindungslinien gezeichnet sind. Man beachte, dass der Graph nur die bestehenden Beziehungen umfasst, dagegen sind Position und Größe der Knoten und Kanten frei gewählt.

Betrachtet man die formale Definition des Graphen als Paar [math](V,E)[/math] dann ist die Knotenmenge [math]V[/math] also durch die Menge {Belgien, Dänemark, Deutschland, Frankreich, Luxemburg, Niederlande, Österreich, Polen, Schweiz, Tschechische Republik} gegeben. Beispiele für Kanten in der Menge [math]E[/math] sind {Belgien, Deutschland}, {Österreich, Schweiz} und {Deutschland, Polen}. Dabei bezeichnen {Belgien, Deutschland} und {Deutschland, Belgien} die gleiche Kante.

Literatur


Kategorien: Graphenklasse

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Einfacher Graph (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.