Différence entre les graphes dirigés et les graphes non dirigés
Un graphique 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) relié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 bords qui connectent les sommets. Dans un graphe orienté, il y a une direction associée aux bords qui relient les sommets.
Graphe 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 contours qui lient 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 graphe ci-dessus peut être écrit comme V = {(V1, V2), (V2, V3), (V1, V3)}. On notera également qu'il n'y a rien qui empêche d'écrire l'ensemble des arêtes comme 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 caractéristique principale 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 graphique 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.
Un graphe orienté est un graphe dans lequel les bords 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 graphe ci-dessus peut être écrit comme V = {(V1, V2), (V2, V3), (V1, V3)}. Les bords d'un graphe non orienté sont des paires ordonnées. Formellement, le bord e dans un graphe orienté peut être représenté par la paire ordonnée e = (x, y) où x est le sommet appelé origine, source ou le point initial du bord e, et le sommet y est appelé terminus, terminant le sommet ou le 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 graphique non orienté. Les villes peuvent être représentées par les sommets dans le graphique et les bords dirigés représentent les routes qui relient les villes en considérant la direction que le trafic circule dans la route.
Dans un graphe orienté, un bord est une paire ordonnée, où la paire ordonnée représente la direction du bord qui relie les deux sommets. D'autre part, dans un graphe non orienté, un bord est une paire non ordonnée, puisqu'il n'y a pas de direction associée à un bord.Les graphes non orientés peuvent être utilisés pour représenter des relations symétriques entre des objets. Le degré et le degré hors degré de chaque nœud dans un graphe non orienté sont égaux mais ceci 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 le cas pour un graphe orienté. Un graphe non orienté peut être converti en un graphe orienté en remplaçant chaque bord par deux bords dirigés allant dans la direction opposée. Cependant, il n'est pas possible de convertir un graphe orienté en un graphe non orienté.
