AA Flashcards Materoids

q aosr/vp6q3
Was ist ein Unabhängigkeitssystem (Independence System)?
? aosr/vp6q3/m/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 aosr/408vc
Was ist eine Basis in einem Unabhängigkeitssystem?
? aosr/408vc/m/479c

q aosr/6kde6
Was ist ein Matroid?
? aosr/6kde6/m/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 aosr/53h4p
Wann funktioniert ein greedy Algorithmus optimal?
? aosr/53h4p/m/6f2s
Ein greedy Algorithmus liefert eine optimale Lösung genau dann, wenn das zugrunde liegende Optimierungsproblem durch ein Matroid beschrieben werden kann.

q aosr/39rem
Warum ist ein MST ein independence system?
? aosr/39rem/m/632g

q aosr/7b0ut
Warum ist ein Maximum Matching ein independence system?
? aosr/7b0ut/m/32s0

q aosr/6to2q
Warum ist das Knapsack Problem ein independence system?
? aosr/6to2q/m/3luk

q aosr/13lq7
Was ist ein Uniformes Matroid?
? aosr/13lq7/m/7dk1

q aosr/5442v
Was ist ein Partition-Matroid?
? aosr/5442v/m/6bug

q aosr/7bjmh
Was ist ein Lineares Matroid?
? aosr/7bjmh/m/6tho

q aosr/42ntu
Was ist ein Grafisches Matroid?
? aosr/42ntu/m/4ukf

q aosr/f8od0
Warum ist das MST-Problem ein Matroid-Optimierungsproblem?
? aosr/f8od0/m/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 aosr/4dbgi
Was ist ein Matching-Matroid?
? aosr/4dbgi/m/r0ch

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

q aosr/6u36m
Was ist die Rangfunktion eines Matroids?
? aosr/6u36m/m/7qog

q aosr/dlruh
Wie kann man einen Matroid characterisieren (erkennen)?
? aosr/dlruh/m/5f0e

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