Vorlesung 3 Flashcards
(79 cards)
Was ist ein Graph im mathematischen Sinn?
Was bedeutet es, wenn ein Graph als ‘planar’ bezeichnet wird?
Ein Graph ist planar, wenn er in der Ebene so gezeichnet werden kann, dass sich die Kanten nur in den Knoten treffen.
Was versteht man unter einem ‘vollständigen Graphen’?
Was bedeutet ‘zusammenhängend’ in Bezug auf Graphen?
Ein Graph heißt zusammenhängend, wenn man von jedem Knoten über die Kanten jeden anderen Knoten erreichen kann.
Was ist ein gerichteter Graph?
Was sind gerichtete Kanten und wie werden parallele Kanten definiert?
Was versteht man unter einem Pfad in einem gerichteten Graphen?
Ein Pfad in einem gerichteten Graphen ist eine durchgehende Folge von Kanten. Ein einfacher Pfad hat keine wiederholten Knoten, und seine Länge wird durch die Anzahl der enthaltenen Kanten bestimmt. Ein Zyklus entsteht, wenn ein Pfad vom Knoten v_i wieder zum gleichen Knoten zurückführt. Eine Schlinge ist ein Zyklus der Länge 1.
Was ist ein Baum in der Graphentheorie?
Ein Baum ist ein gerichteter Graph, bei dem von einem bestimmten Knoten (der Wurzel) zu jedem anderen Knoten genau ein einfacher Pfad existiert. Es gibt keine Zyklen, und alle Knoten sind über Kanten miteinander verbunden.
Wie unterscheiden sich Blätter, Wurzeln und innere Knoten in einem Baum?
Blätter sind Knoten am Ende der Pfade ohne Nachkommen, die Wurzel ist der Ursprungsknoten, von dem aus alle anderen Knoten erreichbar sind, und innere Knoten sind alle anderen Knoten, die weder Blätter noch die Wurzel sind.
Was besagt die Beziehung zwischen der Anzahl der Knoten und Kanten in einem Baum?
Ein Baum mit n Knoten hat immer n−1 Kanten.
Wie wird die Höhe eines Baumes definiert?
Die Höhe eines Baumes entspricht der Länge des längsten Pfades von der Wurzel zu einem Blatt.
Was ist ein binärer Baum?
Ein binärer Baum ist ein Baum, bei dem jeder Knoten entweder genau zwei oder keine gerichteten Kanten abgibt.
Was ist eine Adjazenzmatrix in der Graphentheorie?
Eine Adjazenzmatrix ist eine quadratische Matrix, die verwendet wird, um die Kantenbeziehungen in einem gerichteten Graphen darzustellen. Die Elemente der Matrix zeigen an, ob eine Kante von einem Knoten i zu einem Knoten j existiert (1 für existierend, 0 für nicht existierend).
Wie wird die Adjazenzmatrix für einen gerichteten Graphen definiert?
Was repräsentiert ein Diagonalelement a_ij in der Adjazenzmatrix eines gerichteten Graphen?
Was bedeutet das Transponieren der Adjazenzmatrix eines gerichteten Graphen?
Das Transponieren der Adjazenzmatrix eines gerichteten Graphen entspricht der Umkehrung aller Kantenrichtungen im Graphen.
Wie können parallele Kanten in der Adjazenzmatrix erkannt werden?
Parallele Kanten können in der Adjazenzmatrix nicht erkannt werden, da die Matrix nur die Information über die Existenz mindestens einer Kante zwischen zwei Knoten enthält, nicht jedoch die Anzahl der Kanten.
Beispiel einer Adjaszenz Matrix
Was besagt die Erreichbarkeit von Knoten in Bezug auf die Adjazenzmatrix?
Wie kann die Existenz von Zyklen mit der Adjazenzmatrix festgestellt werden?
2) Wie kann die Existenz von Zyklen mit der Adjazenzmatrix festgestellt werden?
Was ist ein Erreichbarkeitsbaum und wie wird er bestimmt?
Ein Erreichbarkeitsbaum ist eine Darstellung aller Knoten, die von einem Wurzelknoten aus erreichbar sind. Für einen gegebenen Graphen und einen ausgewählten Wurzelknoten zeigt der Erreichbarkeitsbaum alle Knoten, die vom Wurzelknoten aus über Pfade verschiedener Längen erreichbar sind.
Was bedeutet es, wenn zwei Knoten in einem Graphen “stark zusammenhängend” sind?
Was impliziert die Eigenschaft “stark zusammenhängend” für eine Relation auf der Knotenmenge eines Graphen?
Die Eigenschaft “stark zusammenhängend” impliziert, dass die Relation reflexiv, symmetrisch und transitiv ist, und somit eine Äquivalenzrelation darstellt.
