Direkt zum Inhalt

Lexikon der Mathematik: Graph

oder genauer ungerichteter Graph, ein Grundbegriff der Graphentheorie.

Ein Graph G besteht aus einer endlichen, nicht leeren Menge E(G) von Ecken und einer Menge K(G) von zweielementigen Teilmengen aus E(G). Man nennt E(G) Eckenmenge, |E(G)| Eckenzahl oder Ordnung, K(G) Kantenmenge und |K(G)| Kantenzahl des Graphen G.

Ein gerader bzw. ungerader Graph ist ein Graph gerader bzw. ungerader Ordnung. Ein Element k = {x, y} ∈ K(G) heißt Kante des Graphen G, und im allgemeinen wird die kurze und bequeme Schreibweise \begin{eqnarray}k=xy=yx\end{eqnarray} benutzt.

Zwei verschiedene Ecken x und y heißen adjazent, wenn es eine Kante k = xy gibt. Man sagt dann auch, die Kante k = xy inzidiert mit den Ecken x und y oder x und y sind durch die Kante k verbunden. Inzidieren zwei verschiedene Kanten mit einer gemeinsamen Ecke, so nennt man die Kanten inzident. Eine Ecke, die mit keiner Kante inzidiert, heißt isolierte Ecke. Im Fall K(G) = ∅ spricht man von einem leeren Graphen.

Falls ein Graph G nicht zu groß ist, so veranschaulicht man ihn sich am besten durch eine Skizze, indem man die Ecken als Punkte der Ebene und die Kanten als Verbindungslinien adjazenter Eckenpaare zeichnet. Die Abbildung zeigt einen Graphen H mit der Eckenmenge E(H) = {x1, x2, x3, x4, x5, x6, x7} und den 8 Kanten x2x3, x3x4, x4x5, x2x6, x3x6, x3x7, x4x7, x6x7.

Der skizzierte Graph H besitzt folgende Eigenschaften. Er hat sieben Ecken, also ist |E(H)| = 7. Die Ecken x2 und x3 sind adjazent, und die Ecken x2 und x7 sind nicht adjazent. Die Kanten x3x4 und x4x7 sind inzident, die Kanten x4x5 und x6x7 sind nicht inzident. Der Graph H ist ungerade, und er besitzt die isolierte Ecke x1.

Abbildung 1 zum Lexikonartikel Graph
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Graph H

Der Grad dG(x) einer Ecke x in einem Graphen G zählt die mit x inzidenten Kanten. Man nennt \begin{eqnarray}\delta(G)=\min \{{d}_{G}(x)|x\,\in \,E(G)\}\end{eqnarray}

Minimalgrad und \begin{eqnarray}\Delta (G)=\max \{{d}_{G}(x)|x\,\in \,E(G)\}\end{eqnarray}

Maximalgrad von G. Die Zahl \begin{eqnarray}d(G)=\left(\displaystyle \sum _{x\in E(G)}{d}_{G}(x)\right)\,/|E(G)|\end{eqnarray} heißt Durchschnittsgrad von G.

Addiert man in einem Graphen G die Grade aller Ecken, so zählt man dabei jede Kante xy genau zweimal, nämlich einmal von x und einmal von y aus. Damit gelangt man zu der einfachen aber fundamentalen Identität \begin{eqnarray}\displaystyle \sum _{x\in E(G)}{d}_{G}(x)=2|K(G)|\end{eqnarray} von Leonhard Euler aus dem Jahre 1736, die auch unter dem Namen „Handschlaglemma“ bekannt ist. Als wichtige Folgerung ergibt sich daraus die Tatsache, daß die Anzahl der Ecken ungeraden Grades in einem Graphen stets gerade ist.

Eine endliche Folge von inzidenten Kanten \begin{eqnarray}W={x}_{0}{k}_{1}{x}_{1}{k}_{2}{x}_{2}\,\ldots \,{x}_{p-1}{k}_{p}{x}_{p},\end{eqnarray} mit ki = xi−1xiK(G) für i = 1, 2,…,p heißt Kantenfolge von x0 nach xp der Länge p. Für W schreibt man auch kurz \begin{eqnarray}W={x}_{0}{x}_{1}\,\ldots \,{x}_{p}\,.\end{eqnarray}

Die Kantenfolge W ist geschlossen, wenn x0 = xp, und offen, wenn x0 ≠ xp gilt.

Sind in einer Kantenfolge alle Kanten paarweise verschieden, so spricht man von einem Kantenzug, und sind sogar alle Ecken paarweise verschieden, so liegt ein Weg vor. Jede offene Kantenfolge von x0 nach xp enthält einen Weg von x0 nach xp. Ein geschlossener Kantenzug C = x0k1x1xp−1kpx0, in dem die Ecken x0, x1,…,xp−1 paarweise verschieden sind, heißt Kreis.

In dem oben skizzierten Graphen H ist z. B. W = x3x2x6x3x4x7x3 ein geschlossener Kantenzug der Länge 6, aber kein Kreis. Dagegen ist C = x3x2x6x7x3 ein Kreis der Länge 4. Die Länge eines kürzesten Kreises in einem Graphen G ist die Taillenweite g(G) und die Länge eines längsten Kreises sein Umfang c(G). (Beide Werte seien ∞, wenn der Graph keinen Kreis besitzt.) Im skizzierten Graphen H gilt z. B. g(H) = 3 und c(H) = 5. Ist δ(G) ≥ 2, so hat G.A. Dirac 1952 gezeigt, daß G einen Kreis besitzt und c(G) ≥ δ(G) + 1 ist.

Haben alle Ecken eines Graphen G den gleichen Grad, so heißt G regulär. Ein regulärer Graph vom Grad 3 wird auch kubisch genannt. Da die Anzahl der Ecken ungeraden Grades stets gerade ist, muß ein kubischer Graph ein gerader Graph sein. Ein Graph der Ordnung n, in dem jedes Paar von Ecken adjazent ist, heißt vollständiger Graph, in Zeichen Kn. Ein vollständiger Graph Kn ist regulär, und er besitzt n(n−1)/2 Kanten. Der Komplementärgraph \(\bar{G}\) eines Graphen G besteht aus der Eckenmenge E(G), und in \(\bar{G}\) sind zwei Ecken genau dann adjazent, wenn sie es in G nicht sind.

Zur Darstellung von Graphen, z. B. in einem Computer, eignen sich besonders gut die sogenannten Adjazenz- und Inzidenzmatrizen. Es sei G ein Graph mit der Eckenmenge {x1, x2,…,xn} und der Kantenmenge {k1, k2,…,km}. Die quadratische (n × n)-Matrix AG = ((aij)) mit aij = 1, falls xixjK(G) und aij = 0, falls xi und xj nicht adjazent sind, heißt Adjazenzmatrix. Die (n×m)-Matrix IG = ((bij)) mit bij = 1, falls xi und kj inzident sind und bij = 0, falls xi und kj nicht inzident sind, wird Inzidenzmatrix oder Inzidenzliste genannt.

Numeriert man die Ecken eines Graphen G der Ordnung n mit den Zahlen {1, 2,…,n}, so spricht man von einem numerierten oder markierten Graphen der Ordnung n. Dabei werden zwei markierte Graphen mit der gleichen numerierten Eckenmenge {1, 2,…,n} genau dann als verschieden angesehen, wenn zwei Ecken ij existieren, die in dem einen Graphen adjazent, in dem anderen jedoch nicht adjazent sind. Man kann nun recht einfach zeigen, daß es genau 2n(n−1)/2 markierte Graphen der Ordnung n gibt.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos