Diskrete Mathematik
Hussmann TU Dortmund
Hussmann TU Dortmund
-
- 1 / 21
-
Cartes-fiches
Was ist ein aufspannender Baum?
Ein kreisfreier, zusammenhängender Teilgraph eines Graphen, der alle Knoten erreicht.
Was ist ein Kreis?
Ein geschlossener Kantenzug, der jeden seiner Knoten (außer Start und Ziel) nur einmal durchläuft.
Was ist ein zusammenhängender Graph?
Wenn jeder Knoten jeden anderen durch einen Kantenzug erreicht.
Was bedeutet isomorph?
Wenn man die Knoten beider Graphen so umbenennen kann, dass die Adjazenzmatrix beider Graphen gleich ist: -Knoten, - Kanten, -Knotengrade, -Nachbarschaft,
Satz: Verbindungen im Baum
In einem Baum sind je zwei Knoten durch genau einen Weg verbunden.
Satz: Aufbau Baum
Ein Baum ist minimal zusammenhängend und maximal kreisfrei
Satz: Knoten und Kanten im Baum
Ein Baum mit n Knoten hat n-1 Kanten
Satz: Blätter im Baum
Jeder Baum (mit mindestens 2 Knoten) besitzt mindestens 2 Blätter
Was ist ein minimal aufspannender Baum? (Gewichtung)
Ein aufspannender Baum mit einer minimalen Summe an kantengewichten
Was ist eine Brücke?
Eine Kante in einem Graphen, bei deren Wegnahme er in zwei Komponenten zerfallen würde.
Satz: Summe der Kanten = Summe der Knotengrade
Die Summe aller Knotengrade ist gleich der doppelten Anzahl der Kanten.
Satz: Anzahl Knoten mit ungeradem Grad.
In jedem Graphen ist die Anzahl der Knoten mit ungeradem Grad gerade
Was ist ein bipartiter Graph?
Wenn sich seine Knotenmenge in zwei disjunkte Teilmengen (V1 V2) zerlegen lassen und jede Kante ein Ende in V1 und V2 hat.
Was ist ein matching?
Es verbindet in einem bipartiten Graphen je einen Knoten der einen menge mit einem Knoten der anderen Mange mit höchstens einer Kante.
Was ist ein maximales matching?
Die maximale Anzahl an Knoten beider Knotenmengen ist verbunden.
Welche Nachbarschaftsbedingungen gibt es?
Jede Teilmengen von V1 ist nicht größer als ihre jeweilige Nachbarschaftsmenge
Die chromatische Zahl eines planeren Graphen ist nicht größer als 4
Die chromatische Zahl eines planeren Graphen ist nicht größer als 4
Eulerformel
E-K plus F = 2 F ist größer/= k x2 / 3 (bei bipartiten Graphen /4)
Zeifarbensatz
Ist ein Graph bipartiten, ist seine chromatische Zahl 2
Plättbrett/ planere Graphen
Können in der Ebene gezeichnet werden, also ohne Überkreuzug(en).
