Graphentheorie - Grundlagen

Graphen bestehen aus Ecken (Punkten, Knoten) und Kanten (Linien).

Eine Kante endet immer in einer Ecke - es können sogar beide Enden der Kante in der selben Ecke enden (Schlinge). Sobald also mindestens eine Kante im Graph vorhanden ist muss also auch mindestens eine Ecke vorhanden sein.

Kanten können Geradenstücke oder Kurven sein, und zwischen zwei Ecken können mehrere Kanten parallel verlaufen (Mehrfachkanten). Kanten können sich auch überkreuzen ohne im Schnittpunkt eine neue Ecke zu bilden.

Einfache Graphen haben keine Schlingen und keine Mehrfachkanten. Graphen mit Mehrfachkanten nennt man auch Multigraphen.

Isolierte Ecken sind mit keiner Kante verbunden.1)

In einem zusammenhängenden Graph kann man von jedem Punkt über die Kanten irgendwie zu jedem anderen Punkt kommen (die Verbindung muss also nicht über eine gemeinsame Kante erfolgen).

In einem nicht zusammenhängendem Graph sind Ecken oder Kanten isoliert, sind also nicht mit den anderen verbunden. Die einzelnen Teile solcher Graphen nennt man Komponenten.

Den Grad einer Ecke ermittelt man, indem man die in der Ecke endenden Kanten zählt.

Eine isolierte Ecke hat demnach den Grad 0, eine Ecke am Anfang einer Strecke den Grad 1, eine Ecke die nur mit einer Kante in Form einer Schlinge verbunden ist, hat dann den Grad 2, genau wie eine Ecke die z.B. die Spitze eines Dreiecks bildet. Der Eckengrad kann beliebig groß werden.

Beispiele

Ein klassisches Beispiel für einen Graphen ist das „Haus des Nikolaus“.

Nikolaus

Isomorphe Graphen

Wenn man verschiedene Graphen gezeichnet hat, ist es sinnvoll, zu überprüfen, ob verschieden aussehende Graphen eigentlich ein und derselbe Graph sind. Damit Graphen isomorph2) sein können, müssen mehrere Bedingungen erfüllt sein:

  1. gleiche Anzahl Ecken und Kanten
  2. gleiche Anzahl Ecken eines bestimmten Eckengrades
  3. die Graphen müssen durch Verschieben von Ecken und Kanten ineinander umwandelbar sein3)

Graphen mit geraden Kanten könnte man jetzt mit einer dynamischen Geometriesoftware nachzeichnen und dann verändern - auf dem Papier ist es etwas schwieriger. Hier kann man sich jedoch einfach behelfen:

  • man färbt gleichartige Kanten gleich ein oder
  • man benennt die Kanten gleichartig oder
  • man benennt die Ecken gleichartig

Wenn man sich drei Beispielgraphen genau anschaut, stellt man fest, dass sie isomorph sind, denn

  1. sie bestehen jeweils aus 5 Ecken und 8 Kanten
  2. in allen drei Graphen hat eine Ecke den Grad 2 (E), jeweils zwei Ecken haben den Grad 3 (A, B) bzw. den Grad 4 (C, D)
  3. sie lassen sich ineinander umwandeln, weil die Ecke A jeweils mit den Ecken B, C und D verbunden ist, die Ecke B jeweils mit den Ecken A, C und D, und die Ecke E jeweils mit den Ecken C und D, C mit A, B, D, E und D mit A, B, C, E.

Verknüpfungstabellen

Eine Verknüpfungstabelle, in der die Anzahl der Kanten zwischen zwei Ecken eingetragen ist (bei der also, wie im Beispiel, die Bezeichnung der Ecken sowohl in der Spaltenüberschrift als auch in der Zeilenbezeichnung auftaucht) heißt Adjazenzmatrix.

ABCDE
A01110
B10110
C11011
D11101
E00110

Für alle drei Graphen aus dem Beispiel ergibt sich also

(wenn man die Bezeichnungen, wie oben, gleichartig zugeordnet hat)

dieselbe Verknüpfungstabelle (s. links).

Eigenschaften

  • Symmetrisch zur Diagonale von links oben nach rechts unten
  • Die Summe der Zahlen in einer Spalte bzw. der entsprechenden Reihe ergibt den Grad der jeweiligen Ecke (bei Graphen ohne Schlinge)
  • Einfache Graphen zeigen in den Verknüpfungstabellen nur 0 und 1
  • Schlingen erkennt man an Einträgen auf der Diagonale - für den Eckengrad muss man diese Zahlen verdoppeln
  • Isomorphe Graphen haben identische Verknüpfungstabellen - manchmal sieht man das aber erst, wenn man die Tabellen geeignet umgeformt hat.
    Näheres dazu steht hier.

Wege in Graphen

Moderne Navigationsgeräte wären ohne die Wegfindungsalgorithmen der Graphentheorie sicher nicht so leistungsfähig.

Sucht man Wege in Graphen, kann man zwei Herangehensweisen unterscheiden:

  1. Wege über alle Knoten (Eulersche Graphen)
  2. Wege über alle Kanten (Hamiltonsche Graphen)

Weitere Themen aus Sicht der Graphentheorie

1) Der kleinstmögliche Graph ist also genau eine isolierte Ecke
2) iso = gleich, morphus = Gestalt
3) Beim Umwandeln kann man sich die Kanten wie Gummibänder vorstellen - man darf sie aber nicht zerschneiden. Und Ecken dürfen nicht aufeinander fallen.
mint/graphen/einstieg.txt · Zuletzt geändert: 2012/01/08 17:59 von ahrens
CC Attribution-Noncommercial-Share Alike 3.0 Unported
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0