Graphentheorie: Knotenfärbung

24.04.2021, 11:33	Der_Apfel	Auf diesen Beitrag antworten »
Graphentheorie: Knotenfärbung Ich soll in einer Übung zeigen, dass ein einfacher Knotenfärbealgorithmus mit $\begin{eqnarray} ceil\{\sqrt{2\|E\|}\} \end{eqnarray}$ Farben auskommt. Dieser Algorithmus geht die nummerierten Knoten von $\begin{eqnarray} \{1,...,n\} \end{eqnarray}$ durch und vergibt die kleinst mögliche Farbe, die noch kein benachbarter Knoten hat. Im Übungsblatt wurde dabei die Rekursion definiert: $\begin{eqnarray} f(1) = 2 \end{eqnarray}$ $\begin{eqnarray} f(m) \leq f(m - k) + 1 \end{eqnarray}$ mit $\begin{eqnarray} k = \sum_{u\in U_1} deg(u) \end{eqnarray}$ , $\begin{eqnarray} m = \|E\| \end{eqnarray}$ und $\begin{eqnarray} f(m) \end{eqnarray}$ die maximale Anzahl an Farben, die vom Algorithmus für einen Graph mit $\begin{eqnarray} m \end{eqnarray}$ Kanten vergeben werden. Also k wäre die Summe der Knotengrade aller Knoten, die die Farbe "1" erhalten haben (so verstehe ich das)? Wenn ich nun z.B. einen Graphen wie diesen habe (siehe Anhang). Dann wäre doch $\begin{eqnarray} f(3) \leq f(3 - 3) + 1 \Leftrightarrow f(3) \leq f(0) + 1 \Leftrightarrow f(3) \leq 1 \end{eqnarray}$ ? Weil der Knotengrad vom Knoten mit der Farbe 1 ist 3. Aber das Ergebnis stimmt doch nicht? Bei dem gezeigten Graph brauch ich doch mindestens 4 Farben und nicht $\begin{eqnarray} \leq 1 \end{eqnarray}$ ? Hat jemand einen Tipp für mich?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »