18
PI (Subject) / Graphen: Grundlagen und Begriffe (Lesson)
Graphen: Grundlagen und Begriffe
This lesson was created by blace.
This lesson is not released for learning.
Advertisement
- Was ist ein gerichteter Graph und welche Eigenschaften hat er? Eingerichteter Graph ist ein Graph mit gerichteten Kanten, also Kanten die nur in einer Richtung Durchlaufen werden können und oft als pfeile Dargestellt werden. Ein gerichteter Graph G= (V, E) hat eine Knotenmenge V = {1,2,3,...,|V|} Eine Kantenmenge E ⊆ VxV mit e =(v,v´)∈ E Kanten von v nach v´ Die Kante von v nach v´hat den Anfangsknoten v den Endknoten v´ v und v´sind adjazent v ist mit e inzident v´ist mit e inzident e inzident mit v, v´ Zwischen Knoten gibt es nur maximal eine Kante und es gibt keine Parallelen Kanten.
- Was ist ein ungerichteter Graph? Ein ungerichteter Graph ist ein Graph dessen Kanten ungeordnete Knotenpaare {v,w} sind, welche in beide Richtungen Durchlaufen werden können.
- Erläutere die Begriffe adjazent und inzident. Zwei Knoten sind adjazent, wenn sie durch eine Kante miteinander verbunden sind. ein Knoten ist inzident zu einer Kante, wenn der Knoten Eckpunkt dieser Kante ist.
- Was ist der Eingangs- was der Ausgangsgrad eines Knotens? Der Eingansgrad eines Knoten ist die Anzahl der einmündenden Kanten in den Knoten indeg(v) = |{v´∈V:(v´,v)∈E}| Bsp: drei gehen zu 1 indeg(1) = 3 Der Ausgangsgrad eines Knoten ist die Anzahl der ausgehenden kannten outdeg(v) = |{v´∈V:(v´,v)∈E}| Bsp 5 gehen von 4 aus outdeg(4) = 5
- Wie ist Teilgraph eines Graphen definiert? Ein Teilgraph ist ein Teilgraph, wenn er ein Graph ist und alle Kanten und Knoten dieses Graphes Teilmengen des eigentlichen Graphes sind G= (V,E) G´Teilgraph von G falls G´Graph V´⊆ V E´⊆ E
- Wie ist ein Weg in einem Graphen definiert? Ein Weg, oder Pfad von v nach v´ist eine Folge von (Kanten die zwei Knoten miteinander verbinden)Knoten (v0, v1,....,vk), vi∈V k > 0 mit v0= v vk = v´und (vi, vi+1)∈E, i∈{0,.....,k-1} mit der Weglänge k ( Anzahl von Kanten) p1= (2,3,4,1) k = 3
- Wie ist die Länge eines Weges in einem Graphen definiert Die Länge eines Weges Weglänge k ist definiert durch die Anzahl der Kannten in diesem Weg. geht man also von einem Knoten zum anderen mittels 3 Kanten so ist die Weglänge k = 3.
- Wie ist Zyklus in einem gerichteten Graphen definiert? Gib ein Beispiel an. Ein Zyklus ist ein geschlossener Weg, der zu seinem Startknoten zurückführt und eine Länge von k >= 3 hat. Also ein Weg mit v0 = vk Ein zyklenfreier (azyklischer) Graph hat keine Zyklen ein einfacher zyklus hat einen Weg mit v0 = vk und einen Teilweg von v0 -> vk-1 Bsp. 1 ----> 2 <--- 3<------- 4
- Wann ist ein ungerichteter Graph zyklenfrei? Wenn der Weg nicht die Länge von mindestens 3 hat. Wenn es keine 3 Kanten gibt, die 3 Knoten verbinden
- Was ist ein gerichteter Wald? Gib ein Beispiel und ein Gegenbeispiel an. Ein gerichteter Wald ist ein Zyklenfreier Graph G mit indeg(v) >= 1 für alle v∈V Die Wurzeln dieses Waldes sind {v∈V| indeg(v) = 0} Bsp: 4 Knoten mit Gerichteten Kanten, welche keinen Zyklus bilden und jeweils nur eine Kannte eingehend haben Gegenbeispiel: Ein Graph mit einem möglichen Zyklus
- Advertisement
- Was ist ein gerichteter Baum? Gib ein Beispiel und ein Gegenbeispiel an. Ein gerichteter Baum ist ein gerichteter Wald mit genau einer Wurzel w sodass für Alle Knoten v != W gilt es gibt einen Weg p(w,v). Wurzel = 2 mit zwei ausgehenden kanten zu 1 und 3 3 hat eine ausgehende zu4 4 hat eine ausgehende zu 1 Gegenbeispiel_ Graph mit einem Zyklus
- Was ist ein spannender Wald? Erläutere an einem geeigneten Beispiel. Ein Spannender Wald von G=(V, E) ist ein gerichteter Wald W´=(V,F) mit F⊆E. Ein spannender Wald ist also ein gerichteter Wald, dessen knoten Teilmenge der Knoten des Graphen sind. 5 mit einer auf sich selber Zeigenden Kante wäre ein Spannender Wald des Graphen.
- Was ist ein spannender Baum? Erläutere an einem geeigneten Beispiel. ein spannender Baum ist ein spannender Wald, wenn der gerichtete Wald ein gerichteter Baum ist. Bsp vom gerichteten Baum
- Was ist ein bewerteter Graph? Ein bewerteter Graph ist ein Graph, bei welchem jeder Kante ein Gewicht zugeordent ist. Bei diesen graphen ist die Weglänge k = die Summe der Kanten Gewichte Bewertungsfunktion c: E -> Relle c(e) ist Bewertung der Kante e (Länge Gewicht Kosten) Gesamtlänge c(G) von G ist die Summe der Bewertungen aller Kanten von G
- Was ist ein Distanzgraph? Ein Distanzgraph zu einem graphen G = (V, E) ist der vollständige kantengewichtete Graph auf der Knotenmenge V, welcher jeder Kante als Kantengewicht den Abstand zwischen den zwei verbundenen Knoten in G zuordnet. Vollständig heißt, dass je zei Knoten durch eine Kante verbunden sind, oder evtl bei einem gerichteten Graph in beide Richtungen, solange keine Schleifen entstehen. c: E -> Relle mit c >= 0 da die Kantenlänge niemals negativ ist
- Wie ist ein kürzester Weg zwischen zwei Knoten in einem Graphen definiert? Der kürzeste Weg zwischen zwei Knoten ist al der Weg mit minimaler Länge definiert, also mit minimaler Distanz. Länge c(p) von p=(v0,....vk) ist k-1Summei=0 c((v1,v1+1)) Distanz von v zu v`ist d(v,v`) = min({c(p)| p=(v,...,v`)}) kürzester Weg ist der Weg p von v nach v´mit c(p= = d(v, v´)
- Wie ist die Distanz von zwei Knoten in einem Graphen definiert? Die DIstanz von zwei Knoten ist die Länge/ der Abstand zwischen zwei Knoten in einem gewichteten graphen
- Wie ist ein minimal aufspannender Baum definiert? Ein minimaler Spannbaum ist der Spannbaum in einem gewichteten/gewerteten Graphen, welche die kleinst mögliche Distanz geht um die Punkte zu verbinden. MST von G ist ein Spannbaum von G mit minimaler Gesamtlänge