Graphen

Bezeichnung: M$\choosek$ : = {M' | M' $\subseteq$ M $\wedge$ | M'| = k}.

beachte Analogie zur Binomialkoeffizienten: $\left\vert\vphantom{{M \choose k}}\right.$M$\choosek$$\left.\vphantom{{M \choose k}}\right\vert$ = | M|$\choosek$.

• Ein Graph G = (V, E) ist ein geordnetes Paar von
  • Knotenmenge V (vertex set)
  • und Kantenmenge E (edge set).
• Eine Kante ist eine Zweiermenge von Knoten: E $\subseteq$ V$\choose2$.

Beispiel: G = ({1, 2, 3},{{1, 2},{1, 3},{2, 3}}).

Vereinfachte Notation (Kante ohne Mengen-Klammern): G = ({1, 2, 3},{12, 13, 23}).

Das o. g. Modell heißt ungerichteter, einfacher Graph.

Es gibt Varianten (betrachten wir später):

• gerichtete Kanten,
• Schlingen,
• Mehrfachkanten

Beispiel: Automaten-Graphen