GraphColoring.tex 1.5 KB

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