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

Les graphes : Introduction et notions fondamentales

14 Mar 2026 14 Mar 2026 204 vues ESSADDOUKI Mostafa 8 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

Introduction et notions fondamentales

De nombreux problèmes rencontrés en mathématiques, en informatique et en ingénierie ont une caractéristique commune : ils mettent en jeu des objets entre lesquels existent des relations.

Or, ces relations ne sont pas toujours :

  • numériques,
  • ordonnées,
  • ni naturellement décrites par des fonctions ou des équations.

La théorie des graphes fournit alors un cadre mathématique simple et puissant pour :

  • représenter ces relations,
  • raisonner sur leur structure,
  • et concevoir des algorithmes efficaces.
Astuce Un graphe ne cherche pas à modéliser la nature des objets, mais la manière dont ils sont reliés.

  Exemple : Réseau de communication

  • Objets : ordinateurs, routeurs, villes, centres de données
  • Relation : possibilité de communication directe
Question naturelle :
  • Peut-on envoyer un message d'un point à un autre en passant par des relais intermédiaires ?

Exemple : Réseau de routes

  • Objets : villes
  • Relation : existence d'une route directe
Problèmes typiques :
  • existe-t-il un chemin entre deux villes ?
  • quel est le chemin le plus court ?
  • que se passe-t-il si une route est coupée ?

Exemple : Dépendances entre tâches

  • Objets : tâches d'un projet
  • Relation : "la tâche A doit être terminée avant la tâche B"
Problèmes typiques :
  • dans quel ordre exécuter les tâches ?
  • existe-t-il une contradiction (cycle de dépendances) ?

Ces situations, bien que très différentes, partagent une structure commune : des éléments et des liaisons.

C'est précisément ce que formalise un graphe.

Définition d'un graphe

Définition - GrapheUn graphe est un couple : \[ G = (S, A) \] où :
  • \(S = \{s_1, s_2, \dots, s_n\}\) est un ensemble fini de sommets,
  • \(A = \{a_1, a_2, \dots, a_n\} \subseteq S \times S\) est un ensemble d'arêtes, représentant les relations entre sommets.
Définition - Boucle Une boucle est une arête reliant un sommet à lui-même, de la forme : \[ \{u, u\} \]

  Exemple de graphe

Considérons le graphe \(G = (S, A)\) où :

  • \(S = \{A, B, C, D\}\)
  • \(A = \{(A, B), (A, A), (B, C), (A, C), (B, D), (A, D), (C, D)\}\)

Note : La boucle sur A n'est pas représentable en ASCII

RemarqueUn graphe est un objet abstrait :
  • le dessin d'un graphe n'est qu'une représentation,
  • deux dessins différents peuvent représenter le même graphe.

Types de graphes

Définition - Graphe simple Un graphe est dit simple s'il ne contient ni boucles, ni arêtes multiples (plusieurs arêtes reliant la même paire de sommets).

  Exemple de graphe simple

Définition - Graphe non orienté Un graphe non orienté \(G = (S, A)\) est constitué d'un ensemble de sommets \(S\) et d'un ensemble d'arêtes \(A\), où chaque arête est un ensemble non ordonné de deux sommets distincts : \(\{u, v\}\) avec \(u, v \in S\) et \(u \neq v\). \[ \{u, v\} = \{v, u\} \]

  Exemple de graphe non orienté

Définition - Graphe orienté Un graphe orienté \(G = (S, A)\) est constitué d'un ensemble de sommets \(S\) et d'un ensemble d'arcs \(A\), où chaque arc est un couple ordonné \((u, v)\) avec \(u, v \in S\). \[ (u, v) \neq (v, u) \text{ (sauf si les deux arcs existent explicitement).} \] L'arc \((u, v)\) indique une direction de \(u\) (origine) vers \(v\) (extrémité).

  Exemple de graphe orienté

Définition - Graphe pondéré Un graphe pondéré est un couple \(G = (S, A)\) auquel on ajoute une fonction de pondération \(w\).

Cette fonction \(w\) associe un nombre réel à chaque arête \(e \in A\). Ce nombre est appelé le poids de l'arête.

Dans un graphe non pondéré, toutes les arêtes sont considérées comme égales (poids de 1). Dans un graphe pondéré, ces valeurs permettent de hiérarchiser l'importance ou le coût des connexions.

  Exemple de graphe pondéré

Pour chaque liaison \(e\) du graphe, la valeur \(w(e)\) indique :

  • Le coût associé (comme une distance, une durée ou un prix).
  • L'intensité de la relation entre les deux sommets reliés.

Vocabulaire fondamental

Ordre d'un graphe

Définition - Ordre d'un graphe L'ordre d'un graphe correspond au nombre total de ses sommets, noté \(|S|\).

L'ordre du graphe de l'exemple précédent est 4.

Sommets adjacents

Définition - Sommets adjacents Deux sommets \(u\) et \(v\) sont dits adjacents s'ils sont reliés par une arête. \[ u \sim v \quad \Longleftrightarrow \quad \{u, v\} \in A \]
Remarque
  • L'adjacence est une relation symétrique dans un graphe non orienté.
  • Dans un graphe orienté, on distingue :
    • \(u\) est prédécesseur de \(v\),
    • \(v\) est successeur de \(u\).

  Exemple

Dans un graphe simple, le sommet A est adjacent à B et C.

Arête incidente

Définition - Arête incidente Une arête est dite incidente à chacun de ses sommets extrémités. \[ \text{l'arête } \{u, v\} \text{ est incidente à } u \text{ et à } v. \]

Degré d'un sommet

Définition - Degré d'un sommet Dans un graphe non orienté, le degré d'un sommet \(v \in S\), noté \(\deg(v)\), est le nombre d'arêtes incidentes à \(v\). \[ \deg(v) = \text{nombre d'arêtes ayant } v \text{ comme extrémité} \]
Dans un graphe orienté, chaque arête possède un sens, ce qui conduit à distinguer deux types de degrés.

Pour un sommet \(v\), on définit :
  • degré entrant : \(d^{-}(v) = \text{nombre d'arcs arrivant en } v\)
  • degré sortant : \(d^{+}(v) = \text{nombre d'arcs partant de } v\)
\[ \deg(v) = d^{-}(v) + d^{+}(v) \]
Remarque
  • Une boucle \(\{v, v\}\) contribue pour 2 au degré de \(v\).
  • Dans un graphe simple, le degré d'un sommet est compris entre : \[ 0 \le \deg(v) \le |S| - 1 \]
Théorème - Poignée de main Dans tout graphe non orienté fini \(G = (S, A)\), on a : \[ \sum_{v \in S} \deg(v) = 2|A| \]
Preuve Considérons la relation d'incidence \(S\) définie sur \(V \times E\) telle que : \[ (v, e) \in S \Longleftrightarrow \text{le sommet } v \text{ est une extrémité de l'arête } e \]
Comptons le nombre d'éléments de l'ensemble \(S\) de deux manières différentes :
  • Par les sommets : Chaque sommet \(v\) appartient à exactement \(\deg(v)\) couples de \(S\) (un couple pour chaque arête incidente). La somme totale est donc \(\sum_{v \in S} \deg(v)\).
  • Par les arêtes : Chaque arête \(e \in A\) possède exactement deux extrémités. Elle apparaît donc dans exactement deux couples de \(S\). Le nombre total de couples est donc \(2 \times |A|\).
Par transitivité de l'égalité, nous en déduisons : \[ \sum_{v \in S} \deg(v) = 2 \times |A| \]
Corollaire Le nombre de sommets de degré impair est pair.
Preuve Soient \(S_1\) et \(S_2\) respectivement l'ensemble des sommets de degré pair et l'ensemble des sommets de degré impair dans un graphe non orienté \(G = (S, A)\) avec \(m\) arêtes. Alors : \[ 2m = \sum_{v \in S} \deg(v) = \sum_{v \in S_1} \deg(v) + \sum_{v \in S_2} \deg(v) \]
Puisque \(\deg(v)\) est pair pour \(v \in S_1\), le premier terme du membre de droite de la dernière égalité est pair. De plus, la somme des deux termes du membre de droite de la dernière égalité est paire, car cette somme est égale à \(2m\).

Par conséquent, le second terme de la somme est également pair. Comme tous les termes de cette somme sont impairs, il doit y avoir un nombre pair de tels termes. Ainsi, il existe un nombre pair de sommets de degré impair.

Récapitulatif des concepts clés

ConceptDéfinitionNotation
GrapheCouple (sommets, arêtes)\(G = (S, A)\)
OrdreNombre de sommets\(|S|\)
BoucleArête reliant un sommet à lui-même\(\{u, u\}\)
AdjacenceRelation entre deux sommets reliés\(u \sim v\)
Degré (non orienté)Nombre d'arêtes incidentes\(\deg(v)\)
Degré entrant (orienté)Nombre d'arcs arrivant\(d^{-}(v)\)
Degré sortant (orienté)Nombre d'arcs partant\(d^{+}(v)\)

Sortie
// La sortie apparaîtra ici…
Prêt · Ctrl+Entrée pour exécuter
graphe orienté graphe non orienté algorithmes sur les graphes graphe pondéré théorème de la poignée de main

Discussion (0)

Soyez le premier à laisser un commentaire !

Laisser un commentaire

Votre commentaire sera visible après modération.