1234567891011121314151617181920212223242526272829303132333435363738 |
- \section{Färbung von Graphen}
- \subsection{}
- \begin{frame}{Färbung von Graphen}{Graph coloring}
- \begin{block}{Problem COLOR}
- Gegeben sei ein Graph $G = (V, E)$ und ein Parameter $K \in \mathbb{N}$.
- Frage: Gibt es eine Knotenfärbung von $G$ mit höchstens $K$ Farben,
- so dass je zwei adjazente Knoten verschiedene Farben besitzen?
- \end{block}
- \begin{itemize}
- \item Ist für 2 Farben entscheidbar (bipartite Graphen)
- \item Für 3 Farben schon $\mathcal{NP}$-vollständig \\
- (Sogar $\mathcal{NP}$-schwer einen 3-färbbaren Graphen mit 4 Farben zu färben)
- \item Für 4 Farben für planare Graphen bewiesenermaßen immer möglich
- \end{itemize}
- \end{frame}
- \begin{frame}{2-COLOR}{Bipartite Graphen}
- Problem: Gegeben Graph $G=(V, E)$. Ist dieser eine Ja-Instanz von 2-COLOR?
- Lösungsansatz:
- \begin{itemize}
- \item Tiefensuche
- \item Wechsle Farbe nach jedem Knoten
- \item Bei Konflikten breche ab und antworte "Nein"
- \end{itemize}
- Läuft die Tiefensuche ohne abzubrechen durch, ist der Graph bipartit. Aus dem Algorithmus folgt bereits eine gültige Färbung.
- \end{frame}
- \begin{frame}{3-COLOR}
- Auch hier: Ist Graph $G = (V,E)$ mit 3 Farben färbbar? \\
- Achtung: Problem ist $\mathcal{NP}$-Vollständig.
- \\
- Das heißt es ist kein effizienter Algorithmus bekannt, Laufzeit zur Lösung steigt i.A. exponentiell. \\
- Brute-force für kleine Instanzen des Problems praktikabel. \\
- Für größere Instanzen bietet sich Transformation zu $\mathcal{SAT}$ und Lösung per SAT-Solver an.
- \end{frame}
|