Pour commencer une petite vidéo : ici
"Un graphe est un objet abstrait très simple, composé d’éléments (les sommets) et de relations entre ces éléments (les arêtes).
Un graphe permet de représenter des liens d’amitié entre des gens, des lignes aériennes entre des villes, des câbles entre des ordinateurs, des références entre des pages web, etc.
Ce concept est utilisé dans l’industrie (informatique, recherche opérationnelle) mais il intéresse aussi les chercheurs (étude des réseaux sociaux, biologie, mathématiques…)" +
Voici les définitions et propriétés utiles pour commencer.
Pour construire des graphes afin d'illustrer ce cours on pourra utiliser ce site : ici
Définition :
On appelle graphe la donnée d’un ensemble de points appelés sommets et d’un ensemble de lignes appelées arêtes qui relient certains sommets entre eux.
Ordre d’un graphe :
L’ordre d’un graphe est le nombre de sommets du graphe.
Adjacents
Deux sommets sont dits adjacents s’ils sont reliés entre eux par une arête.
Degré d’un sommet
Le degré d’un sommet est le nombre d’arêtes issues de ce sommet.
Sommet isolé
Un sommet qui n’est adjacent à aucun autre sommet du graphe est dit isolé.
Graphe complet
Un graphe est dit complet si deux sommets quelconques distincts sont toujours adjacents.
Autrement dit, tous les sommets sont reliés deux à deux par une arête.
Un graphe peut être orienté ( chaque arête ne peut-être parcourue que dans un seul sens indiqué par une flèche ) ou non-orienté (chaque arête peut-être parcourue dans les deux sens).
Un graphe (orienté ou non-orienté) peut contenir des boucles c’est-à-dire une arête dont l’origine et l’extrémité correspondent au même sommet
Propriété :
Le nombre d’arêtes est égal à la moitié de la somme des degrés des sommets
Définition :
On appelle chaîne toute succession d’arêtes dont l’extrémité de l’une (sauf la dernière) est l’origine de la suivante.
Le nombre d’arêtes qui composent une chaîne est appelé longueur de la chaîne.
On appelle chaîne fermée toute chaîne dont l’origine et l’extrémité coïncident.
On appelle cycle toute chaîne fermée dont les arêtes sont toutes distinctes.
Définition :
Un graphe est dit connexe si deux de ses sommets quelconques sont toujours reliés par une chaîne.
Remarque :
Un graphe complet est donc nécessairement connexe mais la réciproque est fausse . Donner un contre exemple.
Définition :
On appelle chaîne eulérienne d’un graphe toute chaîne qui contient une fois et une seule toutes les arêtes du graphe.
On appelle cycle eulérien une chaîne eulérienne fermée.
Le théorème d’Euler:
Soit G un graphe connexe.
G admet un cycle eulérien si et seulement si tous les sommets de G sont de degré pair.
G admet une chaîne eulérienne (non fermée) si et seulement si le nombre de sommets de degré impair dans G est 2.
Si tel est le cas, les extrémités de la chaîne eulérienne sont les deux sommets de degré impair.
Un des objectifs des activitès suivantes sera de découvrir diffèrentes manières de de parcourir des graphes ou de calculer des chemins entre des paires de sommets, et d'implèmenter certaines de ces méthodes.