Home
Writing
ETH

Quiz on AuD Proofs and Theory

Wenn $G$ einen geschlossenen Eulerschen Weg hat und wir die Kanten eines Kreises $F$ entfernen, hat der verbleibende zusammenhängende Graph $H$ auch einen geschlossenen Eulerschen Weg.

True False

Ein Eulerscher Graph hat nur gerade Grade. Das Entfernen eines Kreises reduziert den Grad jedes betroffenen Knotens um genau 2. Gerade – 2 = Gerade. Wenn $H$ zusammenhängend ist, ist es immer noch Eulersch.

Es gilt $n! \le 2^{n(n+1)}$ für $n \ge 1$.

True False

Basisfall: $1! = 1 \le 4 = 2^2$. Induktionsschritt: $(k+1)! \le (k+1) \cdot 2^{k(k+1)}$. Da $(k+1) \le 2^{2k+2}$ für $k \ge 1$, folgt $(k+1)! \le 2^{(k+1)(k+2)}$.

Der Kondensationsgraph $H$ eines gerichteten Graphen $G$ (Knoten von $H$ sind die SCCs von $G$) ist ein DAG.

True False

Wenn $H$ einen Zyklus hätte, wären alle Knoten in diesen SCCs gegenseitig erreichbar, was bedeutet, sie sollten eine einzige größere SCC sein – Widerspruch zur Maximalität.

Ein Graph mit $n$ Knoten und mehr als $n-1$ Kanten enthält mindestens einen Zyklus.

True False

Ein zusammenhängender azyklischer Graph (Baum) hat genau $n-1$ Kanten. Mehr Kanten bedeuten entweder einen Zyklus oder mehrere Komponenten – aber selbst dann würde eine Komponente einen Zyklus haben müssen.

Wenn ein Turniergraph (gerichtet, jedes Knotenpaar genau einmal verbunden) ein DAG ist, hat er eine eindeutige topologische Sortierung.

True False

In einem Turnier-DAG gibt es einen Hamiltonpfad $v_1 \to v_2 \to \dots \to v_n$. Dieser Pfad legt die eindeutige topologische Ordnung fest.

Quiz on AuD Proofs and Theory

Recent posts

Lecture Notes

Quizzes

New Siri needs that Steve Jobs touch

Conversations don’t flow linearly, so LLM interfaces shouldn’t either

LaTeX Collection