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

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

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

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

Isolierte Knoten sind mit keiner Kante verbunden.¹⁾

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

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

Den Grad eines Knoten ermittelt man, indem man die in dem Knoten endenden Kanten zählt.

Ein isolierter Knoten hat demnach den Grad 0, ein Knoten am Anfang einer Strecke den Grad 1, ein Knoten, der nur mit einer Kante in Form einer Schlinge verbunden ist, hat dann den Grad 2, genau wie ein Knoten, der z.B. die Spitze eines Dreiecks bildet. Der Knotengrad kann beliebig groß werden.

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

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

1. gleiche Anzahl Knoten und Kanten
2. gleiche Anzahl Knoten eines bestimmten Knotengrades
3. die Graphen müssen durch Verschieben von Knoten und Kanten ineinander umwandelbar sein³⁾

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 Knoten gleichartig

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

1. sie bestehen jeweils aus fünf Knoten und acht Kanten
2. in allen drei Graphen hat ein Knoten den Grad 2 (E), jeweils zwei Knoten haben den Grad 3 (A, B) bzw. den Grad 4 (C, D)
3. sie lassen sich ineinander umwandeln, weil der Knoten A jeweils mit den Knoten B, C und D verbunden ist, der Knoten B jeweils mit den Knoten A, C und D, und der Knoten E jeweils mit den Knoten C und D, C mit A, B, D, E und D mit A, B, C, E.

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

• Symmetrisch zur Diagonale von links oben nach rechts unten
• Die Summe der Zahlen in einer Spalte bzw. der entsprechenden Reihe ergibt den Grad des jeweiligen Knoten (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 Knotengrad 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.

Moderne Navigationsgeräte wären ohne die Wegfindungsalgorithmen der Graphentheorie, vor allem der Dijkstra-Algorithmus, sicher nicht so leistungsfähig.

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

1. Touren über alle Kanten (Eulersche Graphen)
2. Kreise durch alle Knoten (Hamiltonsche Graphen)
   1. optimiert, mit Kantengewicht: Travelling Salesman Problem

1. kürzester Weg von einem Startknoten zu allen anderen Knoten
   1. ohne Kantengewicht: Breitensuche
   2. mit Kantengewicht: Dijkstra-Algorithmus

• Platonische Körper

Manfred Nitzsche: Graphen für Einsteiger (Rund um das Haus des Nikolaus), Vieweg (2005)