Graphes

Regarder le Cours d'ASD

• Graphe : Un graphe non orienté est un couple \(G = (V, E)\) où \(V\) est un ensemble de sommets, et \(E \subset V \times V\) est un ensemble d'arêtes.
• Ordre : L'ordre d'un graphe est \(G = (V, E)\) est \(|V|\) .
• Adjacence : S'il existe une arête entre les sommets \(u\) et \(v\) de \(G\), alors ils sont adjacents. Deux sommets non adjacents sont indépendants.
• Voisinage : Soit \(G = (V, E)\) le voisinage d'un sommet \(u\) de \(G\) est l'ensemble de ses voisins.
• Graphe simple : \(G\) est un graphe simple si il ne contient ni boucles ni arêtes parallèles.
• Graphe complet: Un graphe est complet si chaque sommet du graphe est relié directement à tous les autres sommets. On note \(K_n\) le graphe complet à \(n\) sommets. On a \(\operatorname{taille}(K_n) = \frac{n(n-1)}{2}\).
• Chemin : Un chemin dans un graphe \(G = (V, E)\) est une séquence \(P = (u_0, u_1, \dots, u_{p-1})\) de sommets où \(\{u_i, u_{i+1}\} \in E\) pour \(0 \le i \le p-2\).
• Chemin simple : Un chemin est simple si chaque arête apparaît au plus une fois.
• Chemin élémentaire : Chaque sommet apparaît au plus une fois.
• Longueur d'un chemin : Le nombre d'arêtes du chemin.
• Cycle : un cycle dans un graphe \(G = (V, E)\) est une séquence \(C = (u_0, u_1, \dots, u_{p-1})\) de sommets où \(\{u_i, u_{p-1 \mod p}\} \in E\) pour \(0 \le i \le p-1\).
• Cycle simple, cycle élémentaire…
• La longueur du cycle est le nombre d'arêtes du cycle.
• Connexité : Un graphe \(G = (V, E)\) est connexe si pour toute paire de sommets \(u, v \in V^2\), il existe un chemin dans \(G\) dont les extrémités sont \(u\) et \(v\).
• Sous graphe : Un sous graphe d'un graphe \(G = (V, E)\) est un graphe \(H = (V', E')\) avec \(V' \subset V\) et \(E' \subset E\).
• Sous graphe induit: On dit qu'un sous graphe est induit par un ensemble \(U \subset V\) de sommets si toutes les arêtes de \(E\) reliant deux sommets de \(U\) dans \(G\) sont présents dans \(H\). On peut aussi induire un sous graphe par les arêtes.
• Composante connexe : Un composante connexe d'un graphe \(G = (V, E)\) est un sous-graphe connexe \(H = (V', E')\) de \(G\) qui est maximal, c'est-à-dire qu'il n'existe pas de sommet de \(G\) à la fois accessible à partir d'un élément de \(V'\) et hors de \(V'\)

Si jamais, revoir le cours d'IA

Il n'y a pas de racine, donc il faut choisir un nœud de départ. Contrairement à un arbre, "descendre" ne signifie plus grand chose.

Un arbre de parcours est couvrant s'il contient tous les sommets.

Un graphe pondéré est un graphe avec des poids "sur les arêtes". C'est \(G = (V, E, w)\), avec \(w : E \mapsto \mathbb{R}\) est une fonction de poids. Le poids d'un graphe est la somme les poids du graphe.

ACPM-GENERIQUE

Tant que A ne forme pas un arbre couvrant faire
trouver une arête {u, v} qui est sûre pour A
ajouter {u, v} à A
retourner A

Soit A un ensemble d'arêtes qui est un sous-ensemble d'un arbre couvrant. Une arête \(/{u, v/}\) est sûre pour A si \(A \cup \{u, v\}\) est un sous ensemble d'un arbre couvrant

Autrement, une arête sûre est :

• Valide au sens où elle ne crée pas de cycle
• De poids minimale parmi les valides possibles

Voir algo

La distance la plus courte entre \(u\) et \(v\) sera le poids du plus court chemin entre u et v, noté \(\delta(u, v)\)

• capacité : \(c(u, v)\)
• flot: \(f(u, v)\)
• Contrainte de capacité : \(c(u, v) \le f(u, v)\)
• Contraite de conservation : tout ce qui rentre dans un sommet doit sortir

• Une k-coloration d'un graphe est une application \(c : V \to S\) où \(S\) est un ensemble de \(k\) couleurs.
• Une coloration \(c\) est propre si toute arête a ses extrémités de couleurs différentes.
• Un graphe est $k$-colorable s'il admet une $k$-coloration propre.
• Ln plus petit \(k\) pour lequel un grahe \(G\) est $k$-colorable est son nombre chromatique, noté \(\xi (G)\). Si \(\xi(G) = k\), le graphe \(G\) est dit $k$-chromatique.