Partie I – Coloration de graphes
L’objectif de cette partie est de proposer une implémentation en Python d’une solution au problème de coloration d’un graphe.
I.1 – Définitions et propriétés
Soit {G=(S,A)} un graphe fini non orienté avec S son ensemble de sommets et A son ensemble d’arêtes. On suppose que le graphe est simple c’est-à-dire qu’il ne comporte pas de boucles et que chaque paire de sommets est reliée par au plus une arête. On note n, le cardinal de l’ensemble S .
Les sommets sont numérotés de 0 à {n-1}. Étant donné un entier naturel k, une k-coloration des sommets de G est une application {c:S\to\{0,1,\ldots,k-1\}} telle que pour chaque arête {x,y} d’extrémités x et y, {c(x)\ne c(y)}. Si {c(x)=i}, on considèrera que la couleur i est affectée au sommet x.
Si G admet une k-coloration, il est k-coloriable. On définit le nombre chromatique {\chi(G)} d’un graphe G fini par {\chi(G)=\min\{k\in\mathbb N,\ G\text{ est }k\text{-coloriable}\}}. Une clique est un sous-ensemble de sommets du graphe, adjacents 2 à 2. On dit qu’un graphe est complet si il est une clique. On notera {K_p} le graphe complet à p sommets.
On pose {\omega(G)=\max\{p\in\mathbb N\mid K_p\text{ est une clique de }G\}} , avec N l’ensemble des entiers naturels.

- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres