GraphesIntroduction
Dans le cours sur les réseaux, nous avions représenter les routeurs par des cercles et les connexions entre eux par des traits. Quand nous utilisions cette représentation, nous utilisions déjà les graphes. Il existe de nombreuses autres applications aux graphes, par exemple pour représenter les réseaux, Internet, les réseaux urbains, les circuits électroniques et même les liaisons moléculaires. Ils sont même utiliser pour représenter les réseaux sociaux entre amis et familles.
Route
Relations sociales
Internet
Les graphes aux B.O.
Structure de données
| Contenu | Capacités attendues | Commentaires |
|---|---|---|
| Graphes : structures relationnelles. Sommets, arcs, arêtes, graphes orientés ou non orientés. | Modéliser des situations sous forme de graphes. Écrire les implémentations correspondantes d’un graphe : matrice d’adjacence, liste de successeurs/de prédécesseurs. Passer d’une représentation à une autre. | On fait le lien avec la rubrique « algorithmique ». On s’appuie sur des exemples comme le réseau routier, le réseau électrique, Internet, les réseaux sociaux. Le choix de la représentation dépend du traitement qu’on veut mettre en place : on fait le lien avec la rubrique « algorithmique ». |
Algorithme
| Contenu | Capacités attendues | Commentaires |
|---|---|---|
| Algorithme sur les graphes | Parcourir un graphe en profondeur d’abord, en largeur d’abord. Repérer la présence d’un cycle dans un graphe. Chercher un chemin dans un graphe. | Le parcours d’un labyrinthe et le routage dans Internet sont des exemples d’algorithme sur les graphes. L’exemple des graphes permet d’illustrer l’utilisation des classes en programmation. |
Premières définitions
Les
Nous pouvons représenter des graphes simples à l’aide de cercles et de lignes. La position des sommets et la longueur des bords n'a pas d'importance – nous nous soucions uniquement de la manière dont ils sont connectés les uns aux autres. Les arêtes peuvent même se croiser et n’ont pas besoin d’être droites
Graphe orienté et arc
Dans certains graphes, les arêtes ont un sens, elles sont modélisées par des flèches. On les appelle des
Exercice
Abel, Brieuc, Corentin, David et Ewen postent des messages sur un réseau social. Un message peut-être « aimé » par n’importe quel utilisateur, y compris son créateur. On regarde, sur une période de deux semaines, qui a aimé les messages de qui. Voici les résultats :
- Abel a aimé des messages de Corentin et David ;
- Brieuc a aimé ses messages et ceux de Corentin ;
- Corentin a aimé les messages de David ;
- David a aimé ses propres messages ;
- Ewen a aimé les messages d’Abel.
Le relation "aimer" est-elle symétrique ?
Ewen va donc être relier a
Sur votre copie, construire le graphe représentant la situation
Graphe pondéré
Dans certains graphes (comme ceux représentant les réseaux), les arêtes portent un nombre. Ces graphes sont appelés
Nous avons déjà vu ce type de graphe quand nous travaillons sur les réseaux.
D'autre type de graphe
Certains graphes sont constitués de plusieurs groupes de sommets qui ne sont pas connectés les uns aux autres. Ces graphes sont non connexes.
D'autres graphiques peuvent contenir plusieurs arêtes entre les mêmes paires de sommets, ou sommets qui sont connectés à eux-mêmes par des boucles.
Chaine, chemin, cycle et circuit
Chaine
Dans un graphe non orienté, une chaîne est une suite finie d'arêtes consécutives reliant deux sommets.
B-D-C-E-D est une chaine.
Chemin
Dans un graphe orienté, on appelle cette notion un chemin.
Chaine élémentaire
Une chaîne élémentaire est une chaîne ne passant pas deux fois par un même sommet, c'est-à-dire dont tous les sommets sont distincts.
A-B-D-C-E est une chaine élémentaire.
Chaine simple
Une chaîne simple est une chaîne ne passant pas deux fois par une même arête, c'est-à-dire dont toutes les arêtes sont distinctes.
B-D-C-E-D est une chaine simple mais pas une chaine élémentaire.
Cycle
Dans un graphe non orienté, un
A - H - D - B - A est un cycle.
Circuit
Dans les graphes orientés, la notion équivalente est celle de
Munis de ces nouvelles définitions, explorons certaines des propriétés et applications fascinantes des graphiques.