(+212) 616 374 790 contact@developpement-informatique.com
| Connexion
MP, PSI et la TSI Les graphes

Les graphes : Chemins, cycles et connexité

14 Mar 2026 14 Mar 2026 254 vues ESSADDOUKI Mostafa 7 min de lecture
Complexité algorithmique
1 Introduction à l'analyse des algorithmes 2 Notations asymptotiques 3 Opérations élémentaires et modèles de coût 4 Complexité temporelle et spatiale 5 Méthode de comptage des pas 6 Méthode de comptage des pas pour les boucles
Diviser pour régner & algorithmes de tri
7 Rappel sur l'approche récursive 8 Diviser pour régner 9 la recherche dichotomique 10 Tri par fusion 11 Tri rapide 12 Analyse des fonctions récursives
Les arbres binaires
13 Introduction aux arbres binaires 14 Définitions récursives des arbres 15 Propriétés des arbres binaires 16 Types d'arbre binaire 17 Parcours en profondeur des arbres binaires 18 Parcours en largeur des arbres binaires 19 Exercices corrigés sur les arbres - TD 1 20 Exercices corrigés sur les arbres - TD 2 21 Exercices corrigés sur les arbres - TD 3 22 DS - Arbres binaires de recherche équilibrés (AVL) 23 DS - Codage de Huffman - Compression de données
Algorithmes gloutons
24 Introduction aux algorithmes gloutons 25 Problème de la sélection d'activités 26 Problème de séquencement des tâches 27 Problème du Sac à Dos fraction
Programmation dynamique
28 Introduction à la programmation dynamique 29 Le concept de sous-structure optimale 30 Le concept de sous-problèmes superposés 31 Méthodes de la programmation dynamique 32 Différence entre la programmation dynamique, l'approche diviser pour régner, et les algorithmes gloutons 33 Calculer les nombres de catalan en C++ et Python 34 Calculer le coefficient binomial 35 Le nombre de façons pour construire un mur de dimension 4*N 36 Défi de conversion de mots 37 Décomposition de phrases à partir d'un dictionnaire 38 La collection de pièces dans un labyrinthe 39 Nombre de façons de regrouper les étudiants 40 Compter tous les chemins possibles dans une grille MxN
Méta heuristique
41 Algorithmes heuristiques et métaheuristiques 42 Algorithme de Recuit simulé 43 Algorithme Colonies de fourmis
Théorie des graphes
44 Introduction et notions fondamentales 45 Chemins, cycles et connexité 46 Représentations des graphes 47 Parcours de graphes 48 Algorithme de Dijkstra 49 Algorithme A* 50 Algorithme de Bellman-Ford 51 Algorithme Floyd-Warshall 52 Coloration des graphes
Base de données et SQL
53 Introduction au langage SQL 54 Concepts de base de SGBDR 55 Syntaxes de différentes instructions SQL 56 Création et suppression d'une base de données 57 Opérateurs SQL 58 Les contraintes en SQL 59 Création et suppression des tables en SQL 60 Insertion et modifications des enregistrements 61 Extraction des données - SELECT 62 Filtrer les données - WHERE 63 Recherche de motifs - LIKE 64 Trier les données - ORDER BY 65 Les jointures en SQL - JOIN 66 Fonctions d'agrégation en SQL - SUM, COUNT, AVG, MIN et MAX 67 Organiser des données identiques en groupes - GROUP BY et HAVING 68 Les sous-requêtes en SQL 69 Les fonctions SQL de manipulation de date 70 DS - langage SQL 71 Exercices corrigés de langage SQL
Introduction à l'intelligence artificielle
Introduction à la théorie des jeux
Préparation aux concours
72 Réseau de distribution d'eau 73 Arbre d'expression arithmétique 74 Exploration d'une grotte souterraine

Chemins, cycles et connexité

Chemins et cycles

Chaîne et chemin

Définition - Chaîne Soit \(G = (S,A)\) un graphe. Une chaîne de longueur \(k\) est une suite de sommets : \[ (v_0, v_1, \dots, v_k) \] telle que, pour tout \(i\) : \[ (v_i, v_{i+1}) \in A \]
Définition - Chemin Un chemin est une chaîne sans répétition de sommets.
  • Chemin élémentaire : Aucun sommet n'est répété (implique qu'aucune arête n'est répétée).
  • Chemin simple : Aucune arête n'est répétée (mais on peut repasser par le même sommet).
\[ v_0 \neq v_1 \neq \dots \neq v_k \]

  Exemple

Dans cet exemple :

  • une chaîne est : \((G, B, C, A, B, G)\).
  • un chemin est : \(G \rightarrow B \rightarrow A \rightarrow C \rightarrow E \rightarrow F\). C'est un itinéraire direct sans aucun doublon.

Cycle et circuit

Définition - Cycle (non-orienté) Un cycleest un chemin simple : \[ (v_0, v_1, \dots, v_{k-1}, v_0) \] avec :
  • \(k \ge 3\)
  • seuls le premier et le dernier sommet coïncident

  Exemple

Un cycle est : \((C, D, F, E, C)\). On part de \(C\) et on y revient sans jamais croiser deux fois le même sommet entre-temps.

Définition - Circuit (orienté) Un circuit est une chaîne fermée, sans répétition d'arcs, mais les sommets peuvent être répétés.

  Exemple

Dans ce graphe orienté, nous avons plusieurs circuits possibles :

  • Un circuit de longueur 3 : \(A \rightarrow B \rightarrow E \rightarrow A\).
  • Un circuit de longueur 6 : \(A \rightarrow B \rightarrow D \rightarrow C \rightarrow B \rightarrow E \rightarrow A\).

Graphe acyclique

Définition Un graphe est acyclique s'il ne contient aucun cycle.

  Exemple de graphe acyclique

Ce graphe est acyclique car tous ses arcs convergent vers les sommets \(B\) ou \(E\) sans jamais permettre de retour vers les sommets sources \(A\) ou \(D\).

Remarque
  • Les arbres sont des graphes acycliques connexes.
  • En orienté, on parle de DAG (Directed Acyclic Graph), structures fondamentales pour représenter des dépendances ou des ordonnancements.

Connexité

La connexité mesure la capacité à circuler entre les différentes parties d'un graphe.

Graphe connexe

Définition - Graphe connexe Un graphe non orienté est connexe si : \[ \forall u,v \in S,\ \exists \text{ un chemin reliant } u \text{ à } v \] On peut aller de n'importe quel sommet à n'importe quel autre.

Dans un graphe orienté, le sens des flèches change tout. On distingue deux niveaux :
  • Connexité faible : Le graphe est connexe si l'on ignore le sens des arcs (on remplace les arcs par des arêtes).
  • Forte connexité : Pour tout couple \((u,v)\), il existe un chemin de \(u\) vers \(v\) ET un chemin de \(v\) vers \(u\).
\[ \forall u,v \in S,\ \exists \text{ un chemin de } u \text{ vers } v \] et \[ \exists \text{ un chemin de } v \text{ vers } u \]

  Exemples

  • Le graphe orienté avec circuit est connexe (faiblement).
  • Le graphe acyclique est techniquement connexe (faiblement) car tous les sommets sont reliés entre eux, mais il n'est pas fortement connexe car aucun arc ne sort du sommet \(E\), rendant impossible le retour vers les autres sommets.

Composantes connexes

Définition - Composantes connexes Une composante connexeest :
  • un sous-graphe connexe maximal
Propriété
  • Les composantes forment une partition de \(S\).
  • Un graphe est connexe \(\Longleftrightarrow\) il a une seule composante.

Distance et Diamètre

Définition
  • Distance \(d(u,v)\) : Longueur du plus court chemin entre \(u\) et \(v\).
  • Diamètre: La plus grande distance entre deux sommets du graphe : \[ \max_{u, v \in S} d(u,v) \]
    • Dans \(K_n\), le diamètre est 1.
    • Dans un cycle \(C_n\), le diamètre est \(\lfloor n/2 \rfloor\).

  Exemple

  • La distance entre \(C\) et \(F\) est de \(2\) (le plus court chemin est par exemple \(C \rightarrow D \rightarrow F\) ou \(C \rightarrow E \rightarrow F\)).
  • Le diamètre du graphe est de 4, car la distance maximale entre deux sommets quelconques (comme entre G et F) n'excède jamais 4.

Points d'articulation et Ponts

Définition
  • Point d'articulation : Un sommet dont la suppression augmente le nombre de composantes connexes.
  • Pont : Une arête dont la suppression déconnecte le graphe.

  Exemple

  • Le sommet \(C\) est un point d'articulation car sa suppression divise le graphe en deux composantes isolées : \(\{G,A,B\}\) d'un côté et \(\{D,E,F\}\) de l'autre.
  • L'arête \((G, B)\) est un pont car c'est l'unique lien qui relie le sommet \(G\) au reste du graphe ; sa suppression rend \(G\) isolé.
Propriété Une arête est un pont si et seulement si elle n'appartient à aucun cycle.

Graphes particuliers

Dans l'étude des graphes, certaines familles de graphes jouent un rôle central car elles apparaissent fréquemment :

  • comme modèles extrêmes (très denses ou très structurés),
  • comme contre-exemples,
  • ou comme structures fondamentales en algorithmique.

Graphes complets

Définition - Graphe complet Le graphe complet à \(n\) sommets, noté \(K_n\), est le graphe non orienté tel que : \[ \forall u \neq v,\quad \{u,v\} \in A \] Autrement dit, toute paire de sommets distincts est reliée par une arête.

Exemple de graphe complet \(K_4\)

PropriétésSoit \(K_n = (S,A)\) avec \(|S| = n\).
  1. Nombre d'arêtes : \[ |A| = \binom{n}{2} = \frac{n(n-1)}{2} \]
  2. Degré des sommets : \[ \forall v \in S,\quad \deg(v) = n-1 \]
  3. Connexité :
    • \(K_n\) est connexe pour tout \(n \ge 2\)
    • Le diamètre de \(K_n\) est égal à 1
  4. Cycles : Pour \(n \ge 3\), \(K_n\) contient de nombreux cycles

Graphes bipartis

Définition - Graphe biparti Un graphe \(G = (S,A)\) est biparti si l'ensemble des sommets peut être partitionné en deux ensembles disjoints : \[ S = X \cup Y,\quad X \cap Y = \varnothing \] tels que : \[ \forall \{u,v\} \in A,\quad u \in X \text{ et } v \in Y \] Aucune arête ne relie deux sommets d'un même ensemble.

Exemple de graphe biparti

Propriété fondamentale Un graphe est biparti \(\iff\) il ne contient aucun cycle impair.

Dans un graphe biparti, on alterne forcément : \[ X \to Y \to X \to Y \to \cdots \] Pour revenir au sommet de départ, le cycle doit avoir une longueur paire.

Arbres

Définition - ArbreUn arbre est un graphe qui est simultanément :
  • non orienté
  • connexe
  • acyclique

Exemple d'arbre

PropriétésSoit \(T = (S,A)\) un arbre.
  1. Nombre d'arêtes : \[ |A| = |S| - 1 \]
  2. Entre deux sommets quelconques, il existe un et un seul chemin simple.
  3. Supprimer une arête \(\rightarrow\) graphe non connexe.
  4. Ajouter une arête \(\rightarrow\) apparition d'un cycle.
  5. Tout arbre est biparti (car il ne contient aucun cycle, donc aucun cycle impair).

Tableau récapitulatif des graphes particuliers

Type de grapheNotationNombre d'arêtesPropriété caractéristique
Complet\(K_n\)\(\frac{n(n-1)}{2}\)Tous les sommets sont adjacents
Biparti\(K_{p,q}\)\(p \times q\)Pas de cycle impair
Arbre\(-\)\(n-1\)Connexe et acyclique
Formules à retenir
  • Graphe complet \(K_n\) : \(|A| = \frac{n(n-1)}{2}\), \(\deg(v) = n-1\)
  • Arbre à \(n\) sommets : \(|A| = n-1\)
  • Théorème de la poignée de main : \(\sum \deg(v) = 2|A|\)
  • Condition de biparti : absence de cycle impair

Sortie
// La sortie apparaîtra ici…
Prêt · Ctrl+Entrée pour exécuter
arbres arbres binaires graphe orienté graphe non orienté plus cours chemin dans un graphe algorithmes sur les graphes graphe pondéré Chaîne Chemin Circuit Forte connexité Composante connexe Diamètre Point d'articulation Graphe biparti

Discussion (0)

Soyez le premier à laisser un commentaire !

Laisser un commentaire

Votre commentaire sera visible après modération.