Netzwerk: ist ein Graph, dessen Kanten eine Richtung und eine Bewertung haben.
Petrinetz: ist ein Graph, dessen Kanten eine Richtung haben und dessen Knoten zwei unterschiedliche Systemkategorien darstellen.
Knotenmenge: V
Kantenmenge: E
adjazente Knoten: zwei Knoten, die durch eine Kante verbunden sind. (benachbarte Knoten)
inzident: Wenn ein Knoten V Endknoten einer Kante E ist, dann heißt die Kante E mit dem Knoten V inzident und der Knoten V mit der Kante E ebenfalls.
adjazente Kanten: Zwei Kanten, die mit einem Knoten inzident sind, heißen adjazente Kanten.
Schlichter Graph: Ist ein Graph, der werden Schlingen, noch parallele Kanten besitzt.
Satz
der Graphentheorie: Für jeden Graphen G mit m Kanten und n
Knoten v1, v2, v3..., vn gilt:
Untergraph:
Ein Graph G1 = (V1, E1) heißt Untergraph eines Graphen G =
(V,E), wenn
und
ist.
Der Graph G heißt entsprechend Obergraph.
Echter Untergraph: wenn G1 eine echte Teilmenge von G ist, jedoch G1 ungleich G, dann heißt G1 echter Untergraph von G.
Ein spannender Untergraph/ Obergraph: hat außerdem die Eigenschaft, das V(G1) = V(G) ist, also die Anzahl der Knoten die selbe ist.
Unterliegender schlichter Graph: werden in einem Graphen G alle Schlingen und jede Ansammlung von parallelen Kanten entfernt (bis auf eine), so erhält man diesen Graphen.
Kantenfolge:
ist eine endliche Folge -
triviale Kantenfolge: enthält keine Kanten. D. h. für jeden Knoten v eines Graphen ist W=v, also nur der Knoten selbst, eine triviale Kantenfolge.
Kantenzug: Wenn alle Kanten e1,...,ek von W unterschiedlich sind, dann heißt W ein Kantenzug.
Weg: Wenn alle Knoten v1, ... vk von W unterschiedlich sind, dann heißt W ein Weg.
Trivialer Weg: besteht aus einem einzigen Knoten.
Komponente: eine Komponente eines Graphen G ist ein zusammenhängender Untergraph von G1, der in keinem anderen zusammenhängendem Untergraphen von G enthalten ist. _ Eine Komponente ist ein maximaler zusammenhängender Untergraph von G.
Kreis: ein nicht trivialer geschlossener Kantenzug heißt ein Kreis, wenn die Knoten alle verschieden sind.
Euler-Weg: Ein Kantenzug in G, der jede Kante von G genau einmal enthält.
Euler-Kreis: Ein geschlossener Kantenzug in G, der jede Kante von G genau einmal enthält.