Select your language

Suggested languages for you:
Log In Anmelden

Lernmaterialien für Algorithmen & Wahrscheinlichkeiten an der ETHZ - ETH Zurich

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Algorithmen & Wahrscheinlichkeiten Kurs an der ETHZ - ETH Zurich zu.

TESTE DEIN WISSEN

Wer braucht zusätzlich diese Bedingung: |V| ≥ k+1?

Lösung anzeigen
TESTE DEIN WISSEN

k-zusammenhängend

Lösung ausblenden
TESTE DEIN WISSEN

Um wie viel vergrößert sich das Matching bei M' = M ⊕ P?

Lösung anzeigen
TESTE DEIN WISSEN

um eins

Lösung ausblenden
TESTE DEIN WISSEN

Was ist richtig?

Lösung anzeigen
TESTE DEIN WISSEN

(Knoten-)Zusammenhang ≤ Kanten-Zusammenhang ≤ minimaler Grad

Lösung ausblenden
TESTE DEIN WISSEN

Wie ist low[v] definiert?

Lösung anzeigen
TESTE DEIN WISSEN

kleinste dfs-Nummer, die man von v aus durch einen gerichteten Pfad aus (beliebig vielen) Baumkanten und maximal einer Restkante erreichen kann

Lösung ausblenden
TESTE DEIN WISSEN

In welcher Zeit können alle Low-Werte berechnet werden?

Lösung anzeigen
TESTE DEIN WISSEN

O(|V|+|E|)

Lösung ausblenden
TESTE DEIN WISSEN

Wann ist v ein Artikulationsknoten?

Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
TESTE DEIN WISSEN

Was ist eine Eulertour?

Lösung anzeigen
TESTE DEIN WISSEN

Ein geschlossener Weg in G, der jede Kante genau einmal enthält.

Lösung ausblenden
TESTE DEIN WISSEN

Was ist ein Hamiltonkreis?

Lösung anzeigen
TESTE DEIN WISSEN

Ein Kreis in G, der jeden Knoten genau einmal enthält.

Lösung ausblenden
TESTE DEIN WISSEN

Wann enthält ein zusammenhängender Graph eine Eulertour?

Lösung anzeigen
TESTE DEIN WISSEN

Ein zusammenhängender Graph G = (V, E) enthält eine Eulertour <=> der Grad jedes Knotens gerade ist

Lösung ausblenden
TESTE DEIN WISSEN

Wann enthält ein n x m-Gitter einen Hamiltonkreis?

Lösung anzeigen
TESTE DEIN WISSEN

Genau dann wenn n*m gerade ist.

Lösung ausblenden
TESTE DEIN WISSEN

Was besagt der Satz von Dirac?

Lösung anzeigen
TESTE DEIN WISSEN

Jeder Graph G = (V, E) mit |V| ≥ 3 und Minimalgrad δ(G) ≥ |V|/2 enthält einen Hamiltonkreis.

Lösung ausblenden
TESTE DEIN WISSEN

Äquivalenzklassen mit nur einer Kante entsprechen den Brücken, Blöcke bestehen aus Knoten, Knoten in zwei Äquivalenzklassen sind die Artikulationsknoten

Lösung anzeigen
TESTE DEIN WISSEN

Wahr, Falsch, Wahr

Lösung ausblenden
  • 81335 Karteikarten
  • 1534 Studierende
  • 94 Lernmaterialien

Beispielhafte Karteikarten für deinen Algorithmen & Wahrscheinlichkeiten Kurs an der ETHZ - ETH Zurich - von Kommilitonen auf StudySmarter erstellt!

Q:

Wer braucht zusätzlich diese Bedingung: |V| ≥ k+1?

A:

k-zusammenhängend

Q:

Um wie viel vergrößert sich das Matching bei M' = M ⊕ P?

A:

um eins

Q:

Was ist richtig?

A:

(Knoten-)Zusammenhang ≤ Kanten-Zusammenhang ≤ minimaler Grad

Q:

Wie ist low[v] definiert?

A:

kleinste dfs-Nummer, die man von v aus durch einen gerichteten Pfad aus (beliebig vielen) Baumkanten und maximal einer Restkante erreichen kann

Q:

In welcher Zeit können alle Low-Werte berechnet werden?

A:

O(|V|+|E|)

Mehr Karteikarten anzeigen
Q:

Wann ist v ein Artikulationsknoten?

A:

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.

Q:

Was ist eine Eulertour?

A:

Ein geschlossener Weg in G, der jede Kante genau einmal enthält.

Q:

Was ist ein Hamiltonkreis?

A:

Ein Kreis in G, der jeden Knoten genau einmal enthält.

Q:

Wann enthält ein zusammenhängender Graph eine Eulertour?

A:

Ein zusammenhängender Graph G = (V, E) enthält eine Eulertour <=> der Grad jedes Knotens gerade ist

Q:

Wann enthält ein n x m-Gitter einen Hamiltonkreis?

A:

Genau dann wenn n*m gerade ist.

Q:

Was besagt der Satz von Dirac?

A:

Jeder Graph G = (V, E) mit |V| ≥ 3 und Minimalgrad δ(G) ≥ |V|/2 enthält einen Hamiltonkreis.

Q:

Äquivalenzklassen mit nur einer Kante entsprechen den Brücken, Blöcke bestehen aus Knoten, Knoten in zwei Äquivalenzklassen sind die Artikulationsknoten

A:

Wahr, Falsch, Wahr

Algorithmen & Wahrscheinlichkeiten

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten Algorithmen & Wahrscheinlichkeiten Kurse im gesamten StudySmarter Universum

E-Lehre Wahrscheinlichkeitsrechnung

RWTH Aachen

Zum Kurs
Statistik & Wahrscheinlichkeit ETH

ETHZ - ETH Zurich

Zum Kurs
Wahrscheinlichkeit und Risiko

Universität Tübingen

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Algorithmen & Wahrscheinlichkeiten
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Algorithmen & Wahrscheinlichkeiten