Introduction intuitive à la notion de graphe
Notions modélisées par des graphes
Il est intéressant d'utiliser des graphes chaque fois que l'on a :
- un ensemble d'objets (généralement homogènes) à considérer
et que l'on s'intéresse
- à des liens (orientés ou non) entre ces objets.
Exemple d'objets et de liens (orientés) entre les objets
Les liens peuvent simplement exister ou ne pas exister.
On peut aussi associer une liste de valeurs complémentaires qui qualifient le lien, pouvant représenter des distances, des coûts, des durées, des capacités, les notions "ami" ou "ennemi" ...
On dit dans ce cas que le graphe est valué.
Remarque :
Un débutant en théorie des graphes peut ignorer la fin de cette présentation informelle, qui donne des variantes de graphes et le vocabulaire associé. On utilisera toujours le terme général de graphe pour les graphes les plus simples sur lesquels portent ce module de base.
Notions de 1-graphe et de p-graphe
Le graphe ci-dessus est un 1-graphe car il existe au plus un lien orienté entre deux objets distincts.
C'est plus précisément un 1-graphe valué.
Lorsqu'il n'y a pas de flèche sur un lien, cela signifie que le lien existe dans les deux sens avec la même valeur sur le lien.
Le graphe ci-dessus est un p-graphe car il existe plusieurs liens entre deux objets distincts.
C'est plus précisément un p-graphe valué.
Il est à noter que si l'on accepte d'associer une liste de valeurs à un lien, alors le p-graphe redevient un 1-graphe.
Définition : Graphes simples et multigraphes
Considérons un graphe constitué d'objets et de liens où l'orientation des liens n'a pas d'importance (ou encore le lien existe toujours dans les deux sens).
Un graphe est dit simple s'il y a au plus un lien non orienté entre tout couple d'objets.
Un graphe est un multi-graphe s'il y a plus d'un lien non orienté entre certains couple d'objets.
Remarque :
Aussi bien dans ce module de base que dans le module "Algorithme sur les graphes", nous ne considérons que des 1-graphe lorsque les liens sont orientés et des graphes simples lorsque les graphes sont non orientés et nous les désignons par la notation simplifiée de graphe.
Il est à noter que nous remplaçons les p-graphes par des graphes simples en associant plusieurs valeurs aux liens.
