Graphique dirigé vs non dirigé
Un graphe est une structure mathématique composée d'un ensemble de sommets et d'arêtes. Un graphe représente un ensemble d'objets (représentés par des sommets) qui sont connectés par des liens (représentés par des arêtes). En utilisant des notations mathématiques, un graphe peut être représenté par G, où G=(V, E) et V est l'ensemble des sommets et E est l'ensemble des arêtes. Dans un graphe non orienté, il n'y a pas de direction associée aux arêtes qui relient les sommets. Dans un graphe orienté, il existe une direction associée aux arêtes qui relient les sommets.
Graphique non orienté
Comme mentionné précédemment, un graphe non orienté est un graphe dans lequel il n'y a pas de direction dans les arêtes qui relient les sommets du graphe. La figure 1 représente un graphe non orienté avec un ensemble de sommets V={V1, V2, V3}. L'ensemble des arêtes dans le graphique ci-dessus peut être écrit comme V={(V1, V2), (V2, V3), (V1, V3)}. On peut également noter que rien n'empêche d'écrire l'ensemble des arêtes sous la forme V={(V2, V1), (V3, V2), (V3, V1)} puisque les arêtes n'ont pas de direction. Par conséquent, les arêtes d'un graphe non orienté ne sont pas des paires ordonnées. C'est la principale caractéristique d'un graphe non orienté. Les graphes non orientés peuvent être utilisés pour représenter des relations symétriques entre des objets représentés par des sommets. Par exemple, un réseau routier bidirectionnel qui relie un ensemble de villes peut être représenté à l'aide d'un graphe non orienté. Les villes peuvent être représentées par les sommets du graphique et les arêtes représentent les routes à double sens qui relient les villes.
Graphique orienté
Un graphe orienté est un graphe dans lequel les arêtes du graphe qui relient les sommets ont une direction. La figure 2 représente un graphe orienté avec un ensemble de sommets V={V1, V2, V3}. L'ensemble des arêtes dans le graphique ci-dessus peut être écrit comme V={(V1, V2), (V2, V3), (V1, V3)}. Les arêtes d'un graphe non orienté sont des paires ordonnées. Formellement, l'arête e dans un graphe orienté peut être représentée par la paire ordonnée e=(x, y) où x est le sommet appelé l'origine, la source ou le point initial de l'arête e, et le sommet y est appelé le terminus, sommet terminal ou point terminal. Par exemple, un réseau routier qui relie un ensemble de villes à l'aide de routes à sens unique peut être représenté à l'aide d'un graphe non orienté. Les villes peuvent être représentées par les sommets du graphique et les arêtes dirigées représentent les routes qui relient les villes en tenant compte de la direction dans laquelle le trafic circule sur la route.
Quelle est la différence entre un graphe orienté et un graphe non orienté ?
Dans un graphe orienté, une arête est une paire ordonnée, où la paire ordonnée représente la direction de l'arête qui relie les deux sommets. D'autre part, dans un graphe non orienté, une arête est une paire non ordonnée, puisqu'il n'y a pas de direction associée à une arête. Les graphes non orientés peuvent être utilisés pour représenter des relations symétriques entre des objets. Le degré d'entrée et le degré de sortie de chaque nœud dans un graphe non orienté sont égaux, mais ce n'est pas vrai pour un graphe orienté. Lorsque vous utilisez une matrice pour représenter un graphe non orienté, la matrice devient toujours un graphe symétrique, mais ce n'est pas vrai pour un graphe orienté. Un graphe non orienté peut être converti en un graphe orienté en remplaçant chaque arête par deux arêtes dirigées allant dans la direction opposée. Cependant, il n'est pas possible de convertir un graphe orienté en un graphe non orienté.
