Fiche de révision : Graphes abstraits

Caractérisation des graphes

• En sciences informatiques, le graphe est un type de structure de données relationnelles.
• La représentation graphique d'une structure de type graphe fait figurer des éléments reliés entre eux par des liaisons.
• Un graphe est défini par deux ensembles complémentaires :
• l'ensemble des sommets ;
• l'ensemble des arêtes reliant des sommets par paires.
• On distingue deux types de graphes selon leur orientation :
• les graphes non orientés ;
• les graphes orientés.

• Sur un graphe non orienté, les relations sont mutuelles : quand une arête relie deux sommets, il n'y a pas de notion de sens.
• Ces relations s'illustrent bien avec l’exemple du réseau social Facebook où les relations entre les membres peuvent être représentées par un graphe non orienté.

• Sur un graphe orienté, les sommets ne sont pas reliés par des arêtes mais par des arcs indiquant un sens à la relation.
• Quand ils sont reliés entre eux, les sommets d'un graphe orienté peuvent donc l'être par un ou deux arcs, selon qu'il y ait ou non réciprocité.
• Ces relations s'illustrent bien avec l’exemple des réseaux sociaux Twitter ou Instagram où les relations entre les membres peuvent être représentées par un graphe orienté.
• Les relations unilatérales, sur des graphes orientés, sont représentées par des arcs fléchés.
• Une éventuelle réciprocité de la relation est représentée par un arc complémentaire dans l'autre sens.
• Les graphes peuvent être ou non pondérés :
• les relations des graphes non pondérés ont toutes la même valeur, qui n'a donc pas à être précisée ;
• les relations des graphes pondérés pouvant varier, elles doivent être précisées.
• La valeur affectée à la relation est appelée pondération.
• Quand la pondération porte sur un graphe non orienté, elle est affectée à chaque arête.
• Quand la pondération porte sur un graphe orienté, une pondération est affectée à chaque arc.
• Un chemin ne repasse pas par la même arête et permet de relier deux sommets entre eux.
• Il peut exister plusieurs chemins reliant une même paire de sommets.
• Dans un graphe orienté, les chemins entre un sommet de départ et un sommet d'arrivée ne sont pas nécessairement symétriques.
• Cette capacité à distinguer les sens de cheminement entre deux sommets peut s'avérer utile dans différentes applications (cf. logiciel de navigation routière).
• Par exemple, quand les logiciels et applications de navigation routière et d'aide à la conduite calculent et proposent un itinéraire, ils doivent prendre en compte le fait que certains axes de circulation sont en sens unique, notamment en centre-ville.
• Des sommets sont dits adjacents s'ils sont reliés entre eux par une arête.

Parcours

• Le terme « parcours » est parfois employé comme synonyme de chemin ou de cheminement, mais l'expression « le parcours d'un graphe » désigne l'exploration de celui-ci afin de visiter tous ses sommets.
• Il existe plusieurs manières de parcourir les graphes dont les plus courantes que sont :
• le parcours en largeur ;
• et le parcours en profondeur.

• Le parcours en largeur d'un graphe consiste, à partir du sommet de départ, à considérer toutes les adjacences de ce sommet, puis les adjacences des sommets adjacents, et ainsi de suite.
• On garde la trace de chaque sommet visité pour ne pas les visiter plusieurs fois.
• Ce parcours s'apparente à une exploration par cercles concentriques depuis le sommet de départ dont on s'éloigne progressivement.
• On visite d'abord tous les voisins immédiats du sommet initial, puis tous les voisins des voisins initiaux qui n'ont pas déjà été visités, etc.
• La répétition de ce processus permet de découvrir l'intégralité des sommets présents sur le graphe.

• Contrairement au parcours en largeur, le parcours en profondeur ne considère pas d'emblée l'ensemble des voisins, mais un seul d'entre eux.
• À partir de ce sommet, il cherche à aller le plus loin possible, jusqu'à être entourés de sommets déjà visités.
• Quand cela se produit, on revient sur les sommets découverts mais non visités aux précédentes étapes.

Adjacence

• Les adjacences sont une propriété importante des graphes qui indiquent la proximité entre des sommets ou nœuds.
• Il existe plusieurs manières de représenter et d'implémenter ces adjacences :
• les matrices d'adjacence ;
• les listes d'adjacence.

• La représentation par matrice consiste à matérialiser chacune des adjacences, elles-mêmes matérialisées par l'existence d'une relation entre deux nœuds, elle-même matérialisée par une arête.
• Cela revient à remplir un tableau dont les entrées horizontales et verticales sont les nœuds.
• On note 1 en cas de liaison entre sommets, tandis que l'absence d'arête est notée 0.

• La représentation par listes d'adjacence consiste à lister, pour chaque sommet, l'ensemble des sommets qui y sont eux-mêmes reliés par une arête.
• L'implémentation des listes d'adjacence peut prendre la forme suivante :

adjacences = {

}

• On peut remplacer les listes d’adjacence par des sets et par des dictionnaires pour des graphes pondérés.
• Dans le cas de graphes orientés, la simple adjacence n'est pas suffisante pour renseigner les propriétés du graphe. Le caractère orienté des arcs se traduit par l'établissement de deux listes pour les différents sommets :
• listes de prédécesseurs ;
• listes de successeurs.

<<((100,50,auto,-10,auto))

• Le choix d'une représentation dépend du traitement algorithmique que l'on souhaite mettre en place et de la densité du graphe.
• Un graphe dont les sommets sont très largement reliés entre eux sera considéré comme dense.
• A contrario un graphe dont les sommets sont relativement peu reliés est dit creux.
• Les listes d'adjacence sont plus indiquées pour des graphes creux.
• Les matrices sont préférables pour des graphes denses.