# OLA, TD1 : Théorie des graphes

## Exercice 1 : _Degré des sommets d'un graphe_

1) S'il y a $m$ sommets, il y a $2m$ arètes. En effet chaque arètes est connectée à deux sommets et donc contribue 2 à la somme totale des degrés.
2) La somme des degré est $2m$, donc un sommet individuel ne peut avoir un dégré supérieur à la somme totale : $K<2m$. Une exemple ou cette borne est atteinte est un graphe "fleur" : un seul sommet et des boucles.
4) a. La borne est atteinte sur les cliques, en effet il y a au plus une arètes entre chaque paire de sommets distincts dans un graphe simple et il y a en exactement une dans une clique. La clique $K_n$ à $\sum_{i=1}^{n-1}i$ arètes, soit $\frac{n(n-1)}{2}$.
b. Dans un graphe simple une arète est de la forme $\{a, b\}$ avec $a \neq b$. S'il y a $n$ sommets le nombre de paires $\{a, b\}$ avec $a \neq b$ est exactement $n-1$. Comme il n'y a pas d'arètes multiples, $n-1$ est la borne recherchée. La borne est atteinte par exemple sur un graphe en étoile ou sur une clique.

## Exercice 2 : _Clique_
1) Cf dessin. 
2) Il y en a $\frac{n(n-1)}{2}$.
3) Si un couleur $c$ est utilisée sur un sommet, comme ce sommet est relié à tous les autres, aucun des autres ne peut être colorié de la couleur $c$. Il faut 1 couleur par sommet, il y a $n$ sommets, donc il faut $n$ couleurs.
4) $K_4$ est planaire, cf dessin.
5) D'après la question 3 il faut 4 couleurs pour colorer $K_5$ or d'après le théorème des 4 couleurs, si un graphe est planaire, il faut au plus 4 couleurs pour le colorer. Donc $K_5$ n'est pas planaire.

## Exercice 3 : _Coloration_
1) Les sommets sont les examens, les arètes sont les étudiants au sens où on met un arète entre deux examens si un étudiant doit assister aux deux, les couleurs sont les demi journées.
2)  Il faut au moins 3 couleurs car $K_3$ est un sous-graphe. Par ailleurs, il existe une 3-coloration, donc 3 suffisent.
4) On peut faire une 3-clique avec 3 cours et rajouter 2 arètes comme on veut (même preuve que à la question 2). On peut aussi faire un cycle dans ce cas la preuve est par disjonction de cas.

## Exercice 4 : _Coloration d'arètes_
1) Toutes les arètes de la même couleur sont des match joués à la même horaire. Un joueur ne peu jouer qu'un seul match à la même horaire, donc il faut que toutes les arètes incidentes à un sommet soient de couleur différentes.
2) Il faut au moins max(degrés des sommets) couleurs différentes, à cause de la condition de la question 1.
3) a. C'est une clique avec à nouveau $\frac{n(n-1)}{2}$ arètes.
b. On peut jouer au plus $\lfloor n/2 \rfloor$ match simultanément : chaque arrètes à au exactement 2 extrémités, donc si on joue $m$ matchs simultanément, ça implique $2m$ joueurs en train de jouer. Si le nombre de match en cours est strictement supérieur à $n/2$, il y a au moins un joueur qui joue dans deux match simultanément : c'est absurde. D'où la borne supérieure possible. Pour atteindre la borne, par exemple, le joueur $2k$ peut jouer avec le joueur $2k-1$. $\lfloor n/2 \rfloor$ est donc le maximum possible.
c. 

## Exercice 5 : _Un algorithme de coloration_
1) Une étoile convient.
2) La clique $K_4$ convient (preuve dans les exos précédents).
3) Initialisation : un graphe simple $G$ a 1 sommet n'a pas d'arètes donc $\Delta(G) = 0$ et on peut effectivement collorer $G$ avec $\Delta(G) + 1 = 1$ couleur (ce serait P(1)).
Initialisation alternative : c'est trivialement vrai pour le graphe à 0 sommets.
Récurrence : (HR) Supposons que tout graphe $G$ à $n$ sommet vérifie la propriété $\Delta(G)+1$-colorable (ce serait la propriété dépendant de n $P(n)$). On veut montrer que cela entraine que $P(n+1)$ est vraie.
Soit $G' = (V, E)$ un graphe à $n+1$ sommets et soit $s \in V$ un de ses sommets. On considère le sous-graphe induit par les sommets $V \setminus \{s\}$. Ce sous-graphe induit $H$ a $n$ sommets. On utilise l'hypothèse de récurrence pour choisir une coloration de ce sous-graphe avec $\Delta(H)+1$ couleurs. Comme $\Delta(G') \geq \Delta(H)$. Donc on a une coloration de $H$ avec au plus $\Delta(G')+1$ couleurs. Le sommet $s$ est connecté à au plus $\Delta(G')$ sommets de $H$. Donc il suffit de choisir un couleur parmi les $\Delta(G')+1$ couleurs à disposition qui ne soit pas la même qu'un des sommets connectés à $s$.
Conclusion : par le principe de récurrence, la propriété $P(n)$ est vraie quel que soit $n \geq 1$.

def coloration_recursive(G):
    if nombre de sommets de G = 1:
        colorer le sommet d'une couleur dans {1..Delta(G)+1}
    sinon :
        choisir un sommet s de G
        coloration_recursive(G privé de s)
        colorer s d'une couleur dans {1..Delta(G)+1} privé de {couleur de s' | s' adjacent à s}