Graphe orienté

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes un graphe orienté G=(V,A) est défini par la donnée d'un ensemble de sommets V et d'un ensemble d'arcs A, chaque arc étant un couple de sommets (par exemple, si x et y sont des sommets, les couples (x,y) et (y,x) - notés respectivement xy et yx - peuvent être des arcs du graphe G).

Remarquons que dans un graphe non orienté G=(V,E), les arêtes remplacent les arcs et sont des paires de sommets (par exemple, si x et y sont des sommets, la paire {x, y}, notée xy, peut être une arête du graphe G).

Les graphes étudiés en théorie des graphes sont en général des graphes simples, sans arêtes/arcs multiples (par opposition aux multigraphes) et généralement sans boucles.

Articles connexes[modifier | modifier le code]