Mathematik Graphentheorie – Graphenfärbung
Karteikarten zum Thema „Mathematik“ · 15 Karten · von atrio. Beispiele: Was ist eine korrekte Knotenfärbung eines Graphen? · Wie ist die chromatische Zahl χ(…
Karten
15 KartenWas ist eine korrekte Knotenfärbung eines Graphen?
Rückseite
Eine Zuordnung von Farben zu Knoten, sodass benachbarte Knoten stets unterschiedliche Farben erhalten.
Wie ist die chromatische Zahl χ(G) definiert?
Rückseite
Die minimale Anzahl Farben, die für eine korrekte Knotenfärbung des Graphen G notwendig sind.
Welche chromatische Zahl hat der vollständige Graph Kₙ?
Rückseite
χ(Kₙ) = n, da jeder Knoten mit allen anderen adjazent ist und daher eine eigene Farbe benötigt.
Wann ist ein Graph bipartit im Hinblick auf die chromatische Zahl?
Rückseite
Ein Graph ist bipartit genau dann, wenn χ(G) ≤ 2 gilt, also mit höchstens zwei Farben färbbar ist.
Was besagt der Satz von Brooks für zusammenhängende Graphen?
Rückseite
Für zusammenhängende G ≠ Kₙ, C₂ₖ₊₁ gilt χ(G) ≤ Δ(G), wobei Δ der maximale Knotengrad ist.
Wie lautet die obere Schranke nach dem gierigen Färbalgorithmus?
Rückseite
Der gierige Algorithmus liefert eine Färbung mit höchstens Δ(G) + 1 Farben für beliebige Knotenreihenfolgen.
Was besagt der Vier-Farben-Satz für planare Graphen?
Rückseite
Jeder planare Graph lässt sich mit maximal vier Farben korrekt knotenfärben: χ(G) ≤ 4.
Welche chromatische Zahl haben ungerade Zyklen C₂ₖ₊₁?
Rückseite
χ(C₂ₖ₊₁) = 3, da sie nicht bipartit sind, aber drei Farben stets ausreichen.
Was ist der Unterschied zwischen Knoten- und Kantfärbung?
Rückseite
Bei der Kantenfärbung erhalten inzidente Kanten unterschiedliche Farben; die Kantchromatische Zahl χ'(G) beschreibt die minimale Anzahl.
Was besagt der Satz von Vizing zur Kantchromatischen Zahl?
Rückseite
Für jeden Graphen gilt Δ(G) ≤ χ'(G) ≤ Δ(G) + 1; Graphen werden in Klasse 1 (χ' = Δ) und Klasse 2 (χ' = Δ + 1) eingeteilt.
Wie verhält sich χ(G) zum Kliquen-Zahl ω(G)?
Rückseite
Immer gilt ω(G) ≤ χ(G), da alle Knoten einer Klique paarweise adjazent sind und verschiedene Farben brauchen.
Was sind perfekte Graphen?
Rückseite
Graphen, für die χ(H) = ω(H) für alle induzierten Teilgraphen H gilt – etwa bipartite Graphen, Intervallgraphen, Komplementäre perfekter Graphen.
Wie bestimmt man χ(G) für Bäume?
Rückseite
Bäume sind bipartit, daher χ(T) = 2 für alle Bäume mit mindestens einer Kante; isolierte Knoten haben χ = 1.
Was ist eine kritische Graphenfärbung?
Rückseite
Ein Graph ist k-kritisch, wenn χ(G) = k gilt, aber χ(H) < k für alle echten Teilgraphen H ⊂ G.
Welche Rolle spielt Graphenfärbung bei Registerallokation?
Rückseite
Variablen werden als Knoten modelliert, Kanten zeigen gleichzeitige Lebensdauern; χ(G) entspricht der minimalen Registeranzahl ohne Spilling.