14
EA (Subject) / EA Foliensatz1 (Lesson)
EA Foliensatz1
This lesson was created by blumenkohl.
This lesson is not released for learning.
Advertisement
- Definition (Graph) Graph G = (V,E) besteht aus Menge V von Knoten (Multi-)menge E von Kanten (Paare von Knoten) Multimenge: Paar (v,w) kann mehrfach in E vorkommen -> Mehrfachkanten Schleife: Kante (v,v) -> self-loop
- Gerichtete Graphen Gerichteter Graph (Digraph): Paare in E sind geordnet Kanten: Gerichtete Kanten Maximale Kantenanzahl eines Digraphen ohne Schleifen und Mehrfachkanten: |E| <= |V| (|V|-1)
- Ungerichtete Graphen Paare in E sind ungeordnet. Maximale Kantenanzahl ohne Schleifen und Mehrfachkanten: |E| <= 1/2 |V| (|V|-1)
- Definition Nachbarn Sei e = (v,w) eine Kante in E, dann sagen wir: v und w sind adjazent v (bzw. w) und e sind inzident v und w sind Endpunkte von e v und w sind Nachbarn e ist eine ausgehende Kante von v und eine eingehende Kante von w (falls G Digraph)
- Definitionen für gerichte Graphen Gerichtete Graphen G = (V,A). Eingehene Nachbarmenge von v ∈ V: N⁻(v) := { u ∈ V | (u,v) ∈ A } Ausgehende Nachbarmenge von v ∈ V: N⁺(v) := {w ∈ V | (v,w) ∈ A} A⁻(v) := Menge der eingehenden Kanten von v. A⁺(v) := Menge der ausgehenden Kanten von v. A(v) := A⁻(v) ∪ A⁺(v) Eingangsgrad d⁻(v) = |A⁻(v)| Ausgangsgrad d⁺(v) = |A⁺(v)| Knotengrad d(v) := d⁻(v) + d⁺(v)
- Definitionen für ungerichtete Graphen Ungerichteter Graph (V,E). Nachbarmenge von v ∈ V: N(v) = { w ∈ V | (v,w) ∈ E } Menge der zu v inzidenten Kanten: E(v) = { (u,v) | (u,v) ∈ E } Knotengrad d(v) ist die Anzahl der zu v inzidenten Kanten, wobei eine Schleife doppelt gezählt wird.
- Lemma - gerade Knotengerade In einem ungerichteten Graphen G = (V,E) ist die Anzahl der Knoten mit ungeradem Knotengrad gerade. Summe von v ∈ V d(v) = 2 |E| (Rechte Seite gerade -> Linke Seite gerade -> also auch die Anzahl der ungeraden Summanden gerade)
- Definitionen - Wege Sei G = (V,E) gerichtet oder ungerichtet: Ein Kantenzug (walk) der Länge k ist eine nicht-leere Folge von abwechselnd Knoten und Kanten aus g. Ein Weg (path) ist ein Kantenzug in dem alle Knoten verschieden sind.
- Definitionen - Kreis Sei G = (V,E) gerichtet oder ungerichtet: Ist v0,e1,v1,e2,..., ek-1,vk-1 ein Weg mit k >= 3ek=(vk-1,v0) eine Kante aus G, dann ist v0,e1,v1,e2,...,ek-1,vk-1,ek,v0 ein Kreis der Länge k in G.
- Darstellung von Graphen im Rechner (statische Graphen) 1. Möglichkeit: Adjazenzlisten Speichere für jeden Knoten seine Nachbarmenge in einer Liste (z.B. Array für Knoten, LinkedList für Adjazenzliste) 2. Möglichkeit: Adjazenzmatrix Sei M = (mij) eine n x n - Matrix mit mij := 1 falls (vi,vj) ∈ E, sonst mij := 0; Bei Mehrfachkanten schreibe statt 1 die Anzahl der Kanten. Bei ungerichtetem Graph ist Adjazenzmatrix symmetrisch -> nur speicherung der oberen Hälfte
- Advertisement
- Laufzeiten/Speicherplatzverbrauch - Adjazenzlisten und Adjazenzmatrix Adjazenzliste: Speicherplatzverbrauch: linear, θ(|V|+|E|) Zeit für Aufbau: linear, θ(|V|+|E|) Abfrage, ob Kante (v,w) existiert: θ(d(v)) Iteration über alle Nachbarn von v: θ(d(v)) Adjazenzmatrix: Speicherplatzverbrauch: immer quadratisch, θ(|V|²) Zeit für Aufbau: immer quadratisch, θ(|V|²) Abfrage ob Kante (v,w) existiert: θ(1) Iteration über alle Nachbarn von v: θ(|V|)
- Definitionen - Dichte (Graphen) Die Dichte (density) eines Graphen G ist das Verhältnis |E|/|V|. G heißt dünn, falls seine Dichte O(1) ist. G heißt dicht, falls seine Dichte Ω(|V|) ist. Adjazenzlisten für dünne Graphen vorzuziehen.
- Darstellung von Graphen im Rechner (dynamische Graphen) Dynamisch unter den Opartionen: Hinzufügen neuer Knoten und Kanten Entfernen von Knoten und Kanten Idee für gerichtete Graphen: Inzidenzlisten: speichere ein- und ausgehende Knoten bei v Knoten in doppelt verketteter Liste (damit Entfernen in konstanter Zeit) Inzidenzlisten in doppelt verketteten Listen
- Laufzeiten/Speicherplatzverbrauch - dynamische Graphen Speicherplatzverbrauch: linear: Θ(|V|+|A|) Zeit für Aufbau: linear: Θ(|V|+|A|) Abfrage, ob Kante (v,w) existiert: Θ(d(v)) Iteration über alle Nachbarn von v ∈ V: Θ(d(v)) Iteration über alle ausg. Kanten von v ∈ V: Θ(d⁻(v)) Iteration über alle eing. Kanten von v ∈ V: Θ(d⁺(v)) Einfügen eines Knotens bzw. Kante: Θ(1) Entfernen einer Kante: Θ(1) Entfernen eines Knotens: Θ(d(v))