Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Algorithmen & Wahrscheinlichkeiten Kurs an der ETHZ - ETH Zurich zu.
81335
Karteikarten
1534
Studierende
94
Lernmaterialien
Wer braucht zusätzlich diese Bedingung: |V| ≥ k+1?
k-zusammenhängend
Um wie viel vergrößert sich das Matching bei M' = M ⊕ P?
um eins
Was ist richtig?
(Knoten-)Zusammenhang ≤ Kanten-Zusammenhang ≤ minimaler Grad
Wie ist low[v] definiert?
kleinste dfs-Nummer, die man von v aus durch einen gerichteten Pfad aus (beliebig vielen) Baumkanten und maximal einer Restkante erreichen kann
In welcher Zeit können alle Low-Werte berechnet werden?
O(|V|+|E|)
Wann ist v ein Artikulationsknoten?
Wenn entweder v ≠ root, und v hat ein Kind u im DFS-Baum mit low[u] ≥ dfs[v] oder v = root, und v hat mindestens zwei Kinder im DFS-Baum.
Was ist eine Eulertour?
Ein geschlossener Weg in G, der jede Kante genau einmal enthält.
Was ist ein Hamiltonkreis?
Ein Kreis in G, der jeden Knoten genau einmal enthält.
Wann enthält ein zusammenhängender Graph eine Eulertour?
Ein zusammenhängender Graph G = (V, E) enthält eine Eulertour <=> der Grad jedes Knotens gerade ist
Wann enthält ein n x m-Gitter einen Hamiltonkreis?
Genau dann wenn n*m gerade ist.
Was besagt der Satz von Dirac?
Jeder Graph G = (V, E) mit |V| ≥ 3 und Minimalgrad δ(G) ≥ |V|/2 enthält einen Hamiltonkreis.
Äquivalenzklassen mit nur einer Kante entsprechen den Brücken, Blöcke bestehen aus Knoten, Knoten in zwei Äquivalenzklassen sind die Artikulationsknoten
Wahr, Falsch, Wahr
Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.
Jetzt loslegen
