Graphes
Les graphes servent à modéliser des réseaux et à lire leurs relations.
1
Définir un graphe
Vocabulaire minimal
Un graphe est un ensemble de sommets reliés par des arêtes.
- Sommet = point du réseau.
- Arête = liaison entre deux sommets.
- Poids = valeur portée par une arête.
Repères essentiels
- Un graphe peut être orienté ou non orienté.
- Une arête orientée a un sens de parcours.
2
Degré, chaînes et cycles
Lecture sur un schéma
Chaîne
- Suite de sommets reliés.
- Le départ et l’arrivée peuvent être différents.
- La longueur compte les arêtes parcourues.
Cycle
- Chaîne fermée.
- Le départ et l’arrivée coïncident.
- Le parcours revient au sommet initial.
À retenir
Pense au métro : les stations sont des sommets, les trajets sont des arêtes.
Définitions utiles
- Le degré d’un sommet est le nombre d’arêtes incidentes.
- Dans un graphe orienté, on distingue entrée et sortie.
3
Coder les connexions
Matrice d’adjacence
| Sommet i | Sommet j | Coefficient |
|---|---|---|
| i | j | 1 si i et j sont adjacents |
| i | j | 0 sinon |
| i | j | Le sens compte dans un graphe orienté. |
4
Passer du graphe à la matrice
Procédure
- 1
Choisir un ordre fixe des sommets.
- 2
Compléter la ligne du sommet de départ.
- 3
Mettre
1aux voisinages repérés.
Pièges fréquents
- !!Inverser lignes et colonnes casse la lecture.
- !!Oublier le sens d’une arête orientée fausse la matrice.
5
Graphes pondérés et algorithmes
Pondération et calcul
Idée clé
- Un poids peut représenter une distance, un temps ou un prix.
- Un algorithme suit des étapes précises.
6
S’entraîner
Questions rapides
- Définis sommet, arête et poids.
- Comment reconnaître un cycle ?
- Que représente une matrice d’adjacence ?
Bilan
- Un graphe se lit par ses sommets et ses arêtes.
- Le degré, les chaînes et les cycles décrivent sa structure.