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