Mathématiques 2: Géométrie
Les graphes
Termes et définitions
Algorithmes

I. TERMES ET DÉFINITIONS

1. Le graphe

• Arc : Trait ou courbe avec une flèche (orienté) reliant deux sommets.

• Arête : Trait ou courbe (non-orienté) reliant deux sommets.

• Degré d’un sommet : Nombre d'arêtes (ou un arcs) sur un sommet.

• Graphe : Représentation géométrique d'un ensemble contenant des sommets reliés par des arêtes ou des arcs.

• Ordre d'un graphe: Nombre de sommets qu'il contient.

• Graphe orienté : Graphe utilisant des arcs au lieu des arêtes.

• Graphe valué : Graphe construit avec des arêtes contenant des valeurs.

• Sommet :Point relié par des arcs ou des arêtes.

2. Propriétés des graphes

1. Graphe non-orienté

• Chaîne : Ensemble de sommets reliés par des arêtes entre eux de façon continue.

• Chaîne Simple : Une chaîne qui n'utilise jamais deux fois la même arête.

• Chaîne Eulérienne : Chaîne simple qui passe par toutes les arêtes d'un graphe. Le graphe doit contenir exactement deux sommets de degré impair.

• Chaîne Hamiltonienne : Chaîne simple qui passe par tous les sommets d'un graphe une et une seule fois.

• Cycle : Un cycle est une chaîne qui revient à son point de départ.

• Cycle simple : C’est un cycle dont toutes les arêtes du cycle sont utilisées une et une seule fois.

• Cycle Eulérien : Cycle simple qui passe par toutes les arêtes d'un graphe. Tous les sommets du graphe doivent être de degré pair.

• Cycle Hamiltonien : Cycle simple qui passe par tous les sommets du graphe une et une seule fois.

2. Graphe orienté

• Chemin : Les sommets sont reliés par des arcs de façon continue.

• Circuit : Un circuit est un chemin qui revient à son point de départ.

II. ALGORITHMES

1. Algorithme de chemin le plus court

• On choisit un point de départ. Par exemple le point O,
• On considère TOUS les sommets adjacents,
• On retient la valeur le plus petite de l'arête,
ce qui donne alors le premier point intermédiaire,
• On élimine les arêtes adjacentes à ce point qui forment le trajet le plus long vers ce point,
• On évalue les trajets qui restent jusqu'au point d'arrivée,
• Le trajet le plus court est la solution finale.

2. Algorithme du chemin critique

• On assigne à chaque sommet une lettre et à chaque arête ou arc un nombre ou une valeur,
• Le premier nombre retenu est la plus grande somme des valeurs pour se rendre du point de départ au premier sommet d'intersection,
• Le deuxième nombre retenu est la plus grande somme des valeurs pour se rendre du point de départ au deuxième sommet d'intersection,
• On continue le même processus jusqu'à la fin,
• La chaîne la plus longue est le chemin critique.

3. Algorithme du nombre chromatique

• Représenter la situation à l'aide d'un graphe dans lequel les sommets représentent les éléments et les arêtes représentent les incompatibilités ou les conflits,
• Énumérer tous les sommets du graphe et les placer en ordre décroissant de degré. Pour deux sommets ayant le même degré, l'ordre n'a pas d'importance,
• Attribuer une première couleur au sommet ayant le plus grand degré,
• Appliquer cette même couleur à tous les sommets de degré inférieur qui ne sont pas reliés à ce sommet et qui ne sont pas reliés entre eux,
• Répéter les étape 3 et 4 avec de nouvelles couleurs jusqu'à ce que tous les sommets soient colorés,
• Le nombre chromatique du graphe est égal au nombre de couleurs utilisées,
• Conclure sur ce partage en groupes.

4. Heuristque du voisin le plus proche

• Choisir un sommet de départ X,
• Tant que tous les sommets ne sont pas encore visités faire l’opération suivante se rendre au sommet le plus proche pas encore visité.

Autrement dit :

• On fixe un sommet de départ,
• À partir de ce sommet, on joint un autre sommet via une arête de plus petite valeur, en considérant toutes les arêtes qui touchent ce sommet,
• On s'assure à la fin qu'on passé, une seule fois, par tous les sommets du cycle simple obtenu.

5. Heuristque d'arête croissante

• Trier les arêtes par longueur croissante (ou decroissante selon le contexte),
• Parcourir la liste triée des arêtes en sélectionnant les arêtes de manière à : Ne pas fermer le cycle pendant cette séléction (créer un court-circuit), et de Ne pas considérer les sommets de degré 3 (créeer une fouche)
• Continuer, en considérant tous les sommets, jusqu'à ce qu'on puisse revenir au sommet de départ pour compléter un cycle. C,est donc un cycle hamiltonien.

Autrement dit :

• Trier les arêtes par longueur croissante (ou decroissante),
• Tant que la tournée n'est pas complète,
Prendre la première arête non considérée de la liste Si elle ne crée ni cycle, ni fourche avec les arêtes précédemment sélectionnées, la retenir.