Knotenzahl

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Als Knotenzahl bezeichnet man in der Graphentheorie die Anzahl der Knoten eines Graphen.

Ist G der betrachtete Graph, so notiert man diese Zahl in der Regel mit n(G) (oder kurz n, falls klar ist, um welchen Graph es sich handelt). Alternativ schreibt man auch |G|. Ist die Menge/Zahl der Knoten endlich, spricht man von endlichen Graphen, ansonsten von unendlichen Graphen.

Die Graphentheorie unterscheidet zwischen Knoten (auch Ecken genannt) und Kanten. Dabei bezeichnen die Knoten in der Regel Ereignisse, während die sie verbindenden Kanten Vorgänge oder Aktivitäten darstellen. Wenn die Kanten statt durch Mengen durch Paare von Knoten angegeben sind, spricht man von gerichteten Graphen. In diesem Falle unterscheidet man zwischen der Kante (a,b) – als Kante von Knoten a zu Knoten b – und der Kante (b,a) – als Kante von Knoten b zu Knoten a.