\newcommand{\img}{\operatorname{img}}

\begin{slide}{Registervergabe und Graphenfärbung}

Gegeben Programm (das Let innerhalb einer Abstraktion),
konstruiere Graph $G=(V,E)$
\begin{itemize}
\item Knoten $V$:  die lokal gebundenen Namen
\item Kanten $E$: falls $x$ und $y$
  gleichzeitig benötigt, dann $xy\in E$.
\end{itemize}
gesucht ist konfliktfreie Färbung
mit geringer Farbzahl:
\begin{itemize}
\item Farben $C$: (virtuelle) Register
\item Färbung: Abbildung $f: V\to C$
\item konfliktfrei: $\forall xy\in E: f(x)\neq f(y)$
\end{itemize}

\end{slide}

\begin{slide}{Algorithmen zur Färbung}
Das Entscheidungsproblem COL
\begin{itemize}
\item Eingabe: $(G,k)$
\item Frage: existiert konfliktfreie Färbung $f$ 
für $G$ mit $|\img f| \le k$
\end{itemize}
\dots ist NP-vollständig

$\Rightarrow$  kein effizienter Algorithmus bekannt

\bigskip

Näherungsverfahren (für Farben $\{1,2,\ldots\}$):
\begin{itemize}
\item färbe der Reihe nach jeden Punkt
  mit der kleinsten freien Farbe ($=$ die
  nicht unter seinen Nachbarn vorkommt)
\end{itemize}

Heuristik für gute Reihenfolge?

\end{slide}

\begin{slide}{Graphenparameter}

  \begin{itemize}\itemsep 2pt
  \item Maximalgrad $\Delta(G)$
  \item chromatische Zahl $\chi(G)$

    kleinstes $k$, für das $G$ eine konfliktfreie
    $k$-Färbung besitzt
  \item
    Cliquenzahl $\omega(G)$: 
    maximale Knotenzahl einer Clique 

    ($=$ vollständig verbundener Teilgraph)
  \end{itemize}
Anwendungen:
\begin{itemize}\itemsep 2pt
\item 
  Folgerung aus Algorithmus: $\chi(G)\le\Delta (G) +1 $.

  Für welche Graphen gilt Gleichheit?
\item 
  größter Fehler des heuristischen Algorithmus?
\item
  trivial $\omega(G)\le\chi(G)$. Möglicher Abstand?
\end{itemize}



\end{slide}
