22

Geoinformatik (Fach) / Graphen & Netzwerke (Lektion)

Diese Lektion wurde von jakobdanel erstellt.

Lektion lernen

Diese Lektion ist leider nicht zum lernen freigegeben.

zurück  |  weiter 1 / 1

• 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
• Anzeige
• 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

zurück  |  weiter 1 / 1