L2 Info: Algorithmes de graphes

• L'algorithmique des graphes est étudiée en L2 Informatique.

Qu'est-ce qu'un graphe ?

• Un graphe est un objet mathématique et une structure de données qui modélise les éléments d'un ensemble en relation.
• Exemples d'éléments: Lieux, données, routeurs, instructions.
• Exemples de relations: "Il existe une route entre deux villes" ou "X est plus petit que Y".

Applications des graphes en informatique

• Les graphes sont utilisés dans de nombreuses disciplines en informatique, notamment:
• Bases de données
• Génie logiciel
• Réseaux et télécoms
• Cryptographie et sécurité
• Architecture informatique
• Les graphes ont également de nombreuses applications dans d'autres domaines :
• Transport/énergie
• Biologie/chimie
• Médecine et santé
• Réseaux sociaux
• Finance
• Sciences humaines et sociales

Concepts de base

• La base des graphes a été conceptualisée par Claude Berge.

Définitions (Graphes Orientés)

• Relation sur V : Une application A de VxV dans {Vrai, Faux}.
• Exemple sur V={a,b,c,d}: A={(a,a), (a,b), (b,c), (c,d), (d,c), (d,a)}.
• Représentation par une matrice d'adjacence ou un graphe de la relation.
• Un graphe orienté G est un couple (V,A) où:
• V est un ensemble d'éléments appelés sommets ou nœuds (vertex, vertices en anglais).
• A est une partie de VxV, chaque élément de A est un arc (arc en anglais).
• On étudie les degrés, distances, diamètre, chaînes, chemins, cycles, circuits, connexité, pondération et étiquetage d'un graphe.
• Pour un arc (v,w) d'un graphe orienté:
• w est un successeur de v.
• v est un prédécesseur de w.
• Deux arcs sont consécutifs si l'extrémité finale de l'un est l'extrémité initiale de l'autre ((u,v), (v,z)).
• Une boucle est un arc (u,u).
• Un arc est entrant (sortant) d'un sommet si ce sommet est son extrémité initiale (finale).
• Degrés d'un sommet:
• Le degré sortant de v, noté d⁺(v), est le nombre d'arcs dont v est l'origine.
• Le degré entrant de v, noté d¯(v), est le nombre d'arcs dont v est l'extrémité finale.
• Le degré entrant (sortant) d'un graphe est le degré entrant (sortant) maximum de ses sommets.
• Un graphe orienté G est complet si pour tout couple de sommets u et v, l'arc (u,v) existe ou l'arc (v,u) existe.
• Un graphe orienté G=(V,A) est orienté-symétrique si et seulement si (u,v) est un arc implique que (v,u) est un arc.

Définitions (Graphes Non-Orientés)

• Graphes: relation (application de V*V dans {Vrai, Faux})
• Une vision paresseuse du graphe orienté symétrique est le graphe non-orienté.
• Un graphe non orienté est un couple (V,E) où:
• V est un ensemble de sommets ou nœuds (vertex, vertices).
• E est une partie de l'ensemble des paires (non ordonnées) de sommets.
• Chaque élément de E est une arête (edge en anglais).
• [a,b]=[b,a], l'ordre n'importe pas.
• Une arête est incidente à un sommet si ce sommet est l'une de ses extrémités.
• Le degré d'un sommet v, noté d(v), est le nombre d'arêtes qui lui sont incidentes.
• Le degré d'un graphe est le degré maximum de ses sommets.

Figures Notables

• L.P. Euler (1707 – 1783)
• W.R. Hamilton (1805 – 1865)
• Claude Berge (1926 – 2002)

Définitions (Chaînes, Chemins, Cycles et Circuits)

• Un chemin est une suite de sommets v₀v₁...vn telle que chaque couple de sommets successifs est un arc.
• La longueur du chemin est n.
• Un circuit est un chemin tel que v₀=vn.
• Une chaîne est une suite de sommets v₀v₁...vn telle que chaque paire de sommets successifs vivi+1 est soit un arc (vivi+1), soit un arc (vi+1vi).
• La longueur de la chaîne est n.
• Un cycle est une chaîne telle que v₀=vn.
• Il existe des chaînes et des cycles dans les graphes orientés.
• Il existe des circuits et des chemins dans les graphes non-orientés (graphes orientés symétriques).

Exemples

• Chaîne: ACBECB (=BCEBCA) => les deux orientations d'une même chaîne.
• Chemin: AECAEBD (cas particulier de chaîne).
• Chemin élémentaire: AEBDFC
• Cycle: EBC(E)
• Circuit: CBDF(C)

Chaînes et Chemins Symétriques

• Chemin dans un graphe non orienté = orientation d'une chaîne
• {abcd, dcba}.
• Il y a des chaînes et des cycles dans les graphes orientés.
• Il y a des chemins et des circuits dans les graphes non-orier.

Définitions (Connexités dans les Graphes Orientés)

• Un chemin: une suite de sommets v₀v₁...vn telle que chaque couple de sommets successifs est un arc.
• La longueur du chemin est n (Un chemin est un cas particulier de chaînes)
• Un graphe orienté G est connexe si et seulement si, pour tout couple de sommets, il existe une chaîne entre ces deux sommets.
• Un graphe orienté est fortement connexe si et seulement si, pour tout couple de sommets, il existe un chemin entre ces deux sommets.
• Un graphe orienté G est connexe si et seulement si, pour tout couple de sommets, il existe une chaîne entre ces deux sommets dans le graphe non orienté obtenu en supprimant l'orientation des arcs de G.