\section{Coupe dans un graphe (6 points)}

Pour tout graphe $G$, on dénote $V(G)$ l'ensemble des sommets et $E(G)$ l'ensemble des arêtes de $G$.
Par abus de notation, on dénote $uv$ ($=vu$) l'arête entre une paire de sommets distincts $u\in V(G)$, $v\in V(G)$, et $u\neq v$.
Une coupe $S\subseteq V(G)$ dans un graphe $G$ est un sous-ensemble de sommets de $G$ vérifiant $S\neq\emptyset$ et $S\neq V(G)$.
La valeur de la coupe $S$, notée $\texttt{score}(S)$, est le nombre d'arêtes ayant une extrémité à l'intérieur de $S$ et une extrémité à l'extérieur de $S$:
$$\texttt{score}(S)=|\{uv\in E(G):u\in S \land v\notin S\}|.$$

Dans la Figure~\ref{cdf}, la valeur de la coupe $\{\texttt{b},\texttt{a},\texttt{d}\}$ du graphe est $9$.
On appelle coupe maximum toute coupe du graphe ayant une valeur maximum.

\begin{figure}[h!]
\centerline{\includegraphics[width=0.6\textwidth]{bbx2/graphe.eps}}
\caption{\label{cdf} Un graphe.}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}[Echauffement]
\begin{questions}
  \begin{question}
    Peut on enlever un (et un seul) somment de la coupe $\{\texttt{a},\texttt{g},\texttt{i},\texttt{l},\texttt{e}\}$ afin d'augmenter la valeur de la coupe après l'enlèvement?
  \end{question}
  \begin{question}
    Peut on ajouter un (et un seul) somment dans la coupe $\{\texttt{a},\texttt{g},\texttt{i},\texttt{l},\texttt{e}\}$ afin d'augmenter la valeur de la coupe après l'ajout?
  \end{question}
  \begin{question}
  Mêmes questions avec la coupe $\{\texttt{f},\texttt{i},\texttt{c},\texttt{h},\texttt{e}\}$.
  \end{question}
\end{questions}
\end{exo}

\begin{exo}[Coupe maximum]
  Soient maintenant un graphe $G$, et une coupe $S\subseteq V(G)$ telle que $\texttt{score}(S\setminus\{v\})\leq\texttt{score}(S)$ pour tout $v\in S$ et
  telle que $\texttt{score}(S\cup\{v\})\leq\texttt{score}(S)$ pour tout $v\notin S$.
  On appelle degré d'un sommet le nombre de ses voisins:
  $$\texttt{degree}(v)=|\{uv\in E(G): u\in V(G)\}|\textrm{ pour tout }v\in V(G).$$
\begin{questions}
  \begin{question}
  Soit $s\in S$ et $t\notin S$ deux sommets (distincts) de $G$.
  Montrer que $|\{sv\in E(G):v\notin S\}|\geq\frac{1}{2}\texttt{degree}(s)$
  et que $|\{vt\in E(G):v\in S\}|\geq\frac{1}{2}\texttt{degree}(t)$.
  \end{question}
  \begin{question}
  Utiliser les résultats précédents pour montrer que $\texttt{score}(S)\geq\frac{m}{2}$, où $m=|E(G)|$ et $S$ est la coupe définie dans la question précédente.
  \end{question}
  \begin{question}
  On appelle $maxCut$ la valeur maximum d'une coupe de $G$. Montrer que $$maxCut\geq\texttt{score}(S)\geq \frac{1}{2}\times maxCut,$$
  où $S$ est la coupe définie dans les deux questions précédentes.
  \end{question}
\end{questions}
\end{exo}