imported>Wfstb: Links willkürlich

2025-03-24T11:16:02Z

Links willkürlich

Neue Seite

Ein '''einfacher Graph''' (auch '''schlichter Graph''') ist in der [[Graphentheorie]] ein [[ungerichteter Graph]] ohne [[Mehrfachkante]]n und ohne [[Schleife (Graphentheorie)|Schleifen]].

Ein einfacher Graph ist also ein geordnetes Paar <math>(V, E)</math>, wobei <math>V</math> eine Menge von [[Knoten (Graphentheorie)|Knoten]] und <math>E</math> eine Menge von [[Kante (Graphentheorie)|Kanten]] ist. Die Menge <math>E</math> ist dabei eine Menge von 2-elementigen Teilmengen von <math>V</math>.

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 [[Kantengewichteter Graph|kantengewichteten Graphen]].

== Beispiel ==
[[Datei:Graph-BRD-Nachbarn-1.png|mini|Beispielgraph: Deutschland und Nachbarländer]]

Die Nachbarschaftsbeziehungen zwischen [[Deutschland]] und seinen Nachbarländern können als einfacher Graph [[Modell|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} dieselbe Kante.

== Literatur ==
* {{Literatur
|Autor=[[Dieter Jungnickel]]
|Titel=Graphen, Netzwerke und Algorithmen
|Auflage=3
|Verlag=BI Wissenschaftsverlag
|Datum=1994
|ISBN=3-411-14263-4}}

* {{MathWorld |title=Simple Graph |id=SimpleGraph}}

[[Kategorie:Graphenklasse]]

[[en:Graph (discrete mathematics)#Simple graph]]

Einfacher Graph - Versionsgeschichte

imported>Wfstb: Links willkürlich