AA Flashcards Materoids

Q vp6q3
Was ist ein Unabhängigkeitssystem (Independence System)?
? 186m
Ein Unabhängigkeitssystem ist ein Paar $(E,\mathcal{I})$, wobei $E$ eine Grundmenge ist und $\mathcal{I}\subseteq 2^E$ die unabhängigen Mengen beschreibt. Es gelten:

1. $\varnothing \in \mathcal{I}$
2. Wenn $A\in \mathcal{I}$ und $B\subseteq A$, dann ist auch $B\in \mathcal{I}$.

Q 408vc
Was ist eine Basis in einem Unabhängigkeitssystem?
? 479c

Q 6kde6
Was ist ein Matroid?
? 2cg0
An independence system $(E,\mathcal{I})$ is called a matroid if:

1. $\varnothing \in \mathcal{I}$

2. for all $A\in \mathcal{L}$ and $B\subseteq A$, we have $B\in \mathcal{I}$

3. for all $A,B\in \mathcal{L}$ with $|A|<|B|$, there exists an element $b\in B\backslash A$ such that $A\cup \{b\}\in \mathcal{I}$

Q 53h4p
Wann funktioniert ein greedy Algorithmus optimal?
? 6f2s
Ein greedy Algorithmus liefert eine optimale Lösung genau dann, wenn das zugrunde liegende Optimierungsproblem durch ein Matroid beschrieben werden kann.

Q 39rem
Warum ist ein MST ein independence system?
? 632g

Q 7b0ut
Warum ist ein Maximum Matching ein independence system?
? 32s0

Q 6to2q
Warum ist das Knapsack Problem ein independence system?
? 3luk

Q 13lq7
Was ist ein Uniformes Matroid?
? 7dk1

Q 5442v
Was ist ein Partition-Matroid?
? 6bug

Q 7bjmh
Was ist ein Lineares Matroid?
? 6tho

Q 42ntu
Was ist ein Grafisches Matroid?
? 4ukf

Q f8od0
Warum ist das MST-Problem ein Matroid-Optimierungsproblem?
? 9k9h
Weil die Menge der kreisfreien Teilmengen der Kanten eines Graphen ein grafisches Matroid bildet, und der gierige Algorithmus (z. B. Kruskal) auf Matroiden optimal ist.

Q 4dbgi
Was ist ein Matching-Matroid?
? r0ch

Q 5sb90
Was ist nicht notwendigerweise ein Matroid, obwohl es auf Matchings basiert?
? 4rnl
Das System $(E,\mathcal{I})$ mit $E=$ Kanten und $\mathcal{I}=$ Menge aller Matchings in einem Graphen ist kein Matroid.

Q 6u36m
Was ist die Rangfunktion eines Matroids?
? 7qog

Q dlruh
Wie kann man einen Matroid characterisieren (erkennen)?
? 5f0e

Q j28lu
Was ist ein Greedy Algorithmus?
? 2pmc
Sie wählen schrittweise den Folgezustand, der zum Zeitpunkt der Wahl den größten Gewinn gibt.