-
Cours :
- Bases de données 1
- Bases de données 2
- Bases de données 3
- Bases de données 4
- Bases de données 5
- Programmation orientée objet
- cours 6
transparents : pdf, html - planche de TD/TP 6 (pdf)
- cours 6
- Programmation évènementielle
- Structures de données : listes, piles, files
- cours 8
transparents : pdf, html - planche de TD/TP 8 (pdf)
- cours 8
- Structures de données : arbres et ABR
- cours 9
transparents : pdf, html - planche de TD/TP 9 (pdf)
- cours 9
- Structures de données : graphes
- cours 10
transparents : pdf, html - planche de TD/TP 10 (pdf)
- cours 10
Structures de données : graphes
Exemples d’utilisation des graphes
Réseau routier
Réseau routier : avec sens interdits
Internet
Réseaux sociaux
Jeux : graphe des configurations
Graphe de dépendances
Graphe de prérequis
Définition d’un graphe
Graphe orienté
Un graphe orienté est la donnée :
d’un ensemble S de sommets
et d’un ensemble A d’arcs, chaque arc étant un couple (u, v) de deux sommets (possiblement les deux mêmes), parfois noté u → v : u est la source de l’arc et v sa destination
Un chemin est une suite de sommets u0, u1, …, uk (avec k ≥ 0) reliés par des arcs, c’est-à-dire telle que ui → ui + 1 pour tout i ∈ {0, …, k − 1}.
Relation
Un graphe orienté permet de représenter une relation entre des éléments d’un ensemble fini :
- relation de parenté
- relation d’amitié (pas forcément réciproque)
- relation d’ordre sur l’âge…
Graphe non orienté
Si les flèches ne sont pas importantes pour modéliser le problème, on utilise plutôt un graphe non orienté :
- il est composé d’un ensemble A d’arêtes, chaque arête étant une paire {u, v} de deux sommets distincts.
On parle alors de chaîne plutôt que de chemin.
Représentation d’un graphe
Matrice d’adjacence
Liste de successeurs : dictionnaire Python
Il existe aussi une représentation par liste de prédécesseurs: il faut choisir la meilleure des représentations selon le problème à résoudre sur les graphes…
Arbre comme sous-graphe
Connexité
- Une composante connexe d’un graphe non orienté est un ensemble maximal de sommets tous reliés les uns aux autres par un chemin.
- Un graphe peut se décomposer de manière unique en un ensemble de composantes connexes.
- Un graphe est dit connexe s’il ne possède qu’une unique composante connexe.
Une notion similaire existe pour les graphes orientés : la forte connexité
Acyclicité
- Un circuit dans un graphe non orienté est une chaîne partant et arrivant dans le même sommet. On parle de cycle dans un graphe orienté.
- Un graphe est dit acyclique s’il ne possède aucun circuit/cycle.
Caractérisation des arbres
Tout graphe connexe et acyclique est un arbre…
… au sens où on peut choisir n’importe quel sommet comme racine et obtenir un arbre d’arité non borné en considérant ses voisins, puis les voisins de ses voisins, etc.