Graphentheorie (Fach) / Elementares in 40 Schritten (Lektion)
In dieser Lektion befinden sich 7 Karteikarten
Lektionen zum Fach Graphentheorie. Definitionen und Grundsätzliche Konzepte zum besseren Verständnis.
Diese Lektion wurde von hannemac erstellt.
- Definition: Graph Ein Tupel G = (V, E) heißt (ungerichteter) Graph, falls E Teilmenge von [V]2. Elemente v aus V heißen Knoten bzw. Ecken (engl. nodes bzw. vertices),Elemente e aus E heißen Kanten (engl. edges bzw. arcs). Ist G gegeben, so bezeichnet V (G) die Knoten und E(G) die Kantenmenge von G. Falls E = [V]2, so heißt G vollständig,
- Definition: Diagramm Symbolisiert man zu G = (V,E) jedes v aus V durch einen Punkt, und jedes e = (v1, v2) aus E durch eine Verbindungslinie zwischen v1 und v2, so erhält man ein Diagramm/Zeichnung von G in der Ebene.
- Definition: Bipartiter Graph Ein einfacher Graph G = (V,E) (V Menge der Knoten, E Menge der Kanten) heißt in der Graphentheorie bipartit (auch paar), falls sich seine Knoten in zwei disjunkte Teilmengen A und B aufteilen lassen, sodass zwischen den Knoten innerhalb beider Teilmengen keine Kanten verlaufen.
- Definition: Weg Ein Weg (oder auch Pfad) Pk in G besteht aus einer Folge v1, ..., vk verschiedener Knoten, so daß (vi, vi+1) aus E(G) für i = 1, ..., k - 1.Die Länge des Weges ist die Anzahl k - 1 der Kanten (vi, vi+1). Für einen Weg von v1 nach v2 der Länge k schreibt man auch P(v1, v2, k).
- Definition: Kreis Ein Kreis Ck ist eine Folge verschiedener Knoten v1, ..., vk aus V (G) mit (vi, vi+1) aus E(G) für i = 1, ..., k - 1 und (vk, v1) aus E(G). Die Länge von Ck ist die Anzahl seiner Kanten.
- Definition: Isomorph Zwei Graphen G, G' heißen isomorph, bezeichnet, durch G ≈ G', falls es eine bijektive Abbildung ø : V (G) → V (G') mit (v1, v2) aus E(G) ↔ (ø(v1), ø(v2)) aus E(G') gibt. Isomorphie drückt Strukturgleichheit aus.
- Definition: Adjazent, Inzident Sei G = (V,E) Graph. v1, v2 aus V heißen benachbart bzw. adjazent, falls (v1, v2) aus E. Es heißen v aus V, e aus E inzident, falls v aus e. Man nennt e1, e2 aus E inzident, falls e1 ∩ e2 ≠ ø, also einen gemeinsamen Knoten haben. Die Menge der Nachbarn zu v aus V sind alle zu v benachbarte Knoten: N(v) = {u aus V | Existiert ein e = (u, v) aus E}. Man nennt d(v) = | N(v)| den Grad von v. Die Ecke v heißt isoliert, falls d(v) = 0. Allgemein heißt jV j Ordnung und jEj Gr¨oße von G.