22
Geoinformatik (Subject) / Graphen & Netzwerke (Lesson)
Advertisement
- Graph ★ Def.: Triple (N, E, g) mitN = {n1, ... nm} Menge der KnotenE = {e1, ... ek} Menge Kanteng = E↦N×N Abb. Kanten auf Knotenpaare★ Kanten auch als Knotenpaareei = (nr,ns) beschreibbar
- ungerichter Graph e(a,b)=e(b,a)
- gerichteter Graph e(a,b)!=e(b,a)
- Inzidenz Def. Beziehung zwischen Knoten undKanten in ungerichtetem Graph:Knoten inzident mit Kante, wenn vondieser Kante berührt (in ihr enthalten)★ incident(n,e): g(e)=(n1,n2)∧(n=n1∨n=n2)★ gerichteter Graph:es gibt positive undnegative Inzidenz
- Adjazenz Def. Beziehung zwischen Knoten inungerichtetem Graph; zwei Knoten sindadjazent (benachbart) wenn direktdurch eine Kante verbunden★ adjacent(n1,n2):∃e∈E: incident(n1,e)∧incident(n2,e)★ gerichteter Graph:n1 adjazent zu n2, wennKante von n1 nach n2
- Weg Folge von Knoten,sequentiell adjazentW={n1,...np} mit∀i<p-1: adjacent(ni,ni+1)
- Pfad Weg, bei demalle Knoten paarweiseverschieden sind
- Zyklus Pfad von min.drei Knoten, bei dem derletzte und erste Knotenadjazent sind
- Valenz/Grad Def. Grad eines Knoten = Anzahl mitKnoten inzidenter Kanten★ degree(n)=|{ei∈E:incident(n,ei)}|
- vollständiger Graph jeder Knoten hat Kantenzu allen anderen Knoten
- Advertisement
- Gewichtete Graphen ★ Def. Graphen, bei denen jeder Kanteein Gewicht zugeordnet wird:★ l:E↦W, ∀e∈E: l(e)=w (w∈R)★ von großerpraktischerBedeutung,u.a. in GIS
- Baum zusammenhängenderGraph ohne Zkylus(azyklischer Graph)
- Blätter Knoten inBaum mit Grad 1
- Wurzel(Baum) Knoten imBaum mit Eingangsgrad 0
- Bipartite Graphen Def. Graph ist bipartit, wenn er sich inzwei Mengen von Knoten teilen lässt,die jeweils nur mit Knoten aus deranderen Menge verbunden sind
- Adjazenzmatrix Matrix M, die alle Knoten beinhaltet undAdjazenz zu allen anderen Knoten★ wenn Kante von A nach B existiert,dann Eintrag gleich eins, sonst null ★ wenn Graph gerichtet, dann kannAdjazenzmatrix asymmetrisch sein★ Elemente in Adjazenzmatrix könnenauch Anzahl Verbindungen angeben
- Inzidenzmatrix n×m Matrix für Graph mit n Knoten(Zeilen) und m Kanten (Spalten)★ Element eij ist eins, falls Knoten iinzident zu Kante j ist★ bei gerichteten Graphen unterscheidetman, ob die Kante j im Knoten i beginnt(eij =1) oder endet (eij =-1)
- Kürzester Pfad Def. Pfad zwischen zwei Knoten ineinem Graph mit minimaler Länge (bzw.minimalen Kosten)★ wenn Graph ungewichtet ist, dannkürzester Pfad äquivalent zu Pfad mitwenigsten Knoten
- Dijkstra-Algorithmus Algorithmus zum finden des kürzesten Weges
- Netzwerkfluss Gewicht von Kanten in gewichtetem(und gerichtetem) Graph wird als Kapazitätbezeichnet★ Fluss: Funktion, die jeder Kante einen nichtnegativen Flusswert zuordnet★ immer gilt:Flusswert ≤ Kapazität★ in jeden Knoten mussgleich viel hinein- wiehinausfließen
- Ford-Fulkerson ★ Grundidee:★ solange es Pfad mit freier Kapazitätgibt von Quelle zu Senke, sende(maximal möglichen) Fluss entlangdieses Pfades -> Augmentierungspfad★ fahre damit fort, bis kein Pfad mehrmit freier Kapazität vorhanden
- Residualgraph ★ hat selben Knoten wie Ursprungsgraph★ Kanten unterschiedlich:★ Rückkanten zu jeder Kante mit Teilfluss★ Kanten mit noch freier Kapazität