Différence entre le graphique dirigé et non dirigé

Graphique dirigé ou non dirigé

Un graphique est une structure mathématique constituée d'un ensemble de sommets et d'arêtes. Un graphique 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 représente l’ensemble des sommets et E l’ensemble des arêtes. Dans un graphe non dirigé, aucune direction n'est associée aux arêtes reliant les sommets. Dans un graphe orienté, une direction est associée aux arêtes reliant les sommets..

Graphique non dirigé

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 reliant les sommets du graphe. La figure 1 illustre un graphe non orienté avec un ensemble de sommets V = V1, V2, V3. L'ensemble des arêtes du graphique ci-dessus peut être écrit sous la forme V = (V1, V2), (V2, V3), (V1, V3). On peut également noter que rien n'empêche l'écriture de 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 dirigé ne sont pas des paires ordonnées. C'est la caractéristique principale d'un graphe non dirigé. Les graphiques 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 dirigé. 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 dirigé

Un graphe orienté est un graphe dans lequel les arêtes du graphe reliant les sommets ont une direction. La figure 2 décrit un graphe orienté avec un ensemble de sommets V = V1, V2, V3. L'ensemble des arêtes du graphique ci-dessus peut être écrit sous la forme V = (V1, V2), (V2, V3), (V1, V3). Les arêtes d'un graphe non dirigé sont des paires ordonnées. Formellement, l’arête e d’un graphe dirigé peut être représentée par le couple ordonné e = (x, y), où x est le sommet appelé origine, source ou le point initial de l’arête e, et le sommet y est appelé terminus. , sommet de terminaison 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 graphique non dirigé. 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 du trafic sur la route..

Quelle est la différence entre le graphe dirigé et le graphe non dirigé??

Dans un graphe orienté, une arête est une paire ordonnée, la paire ordonnée représentant la direction de l'arête reliant les deux sommets. En revanche, dans un graphe non dirigé, une arête est une paire non ordonnée, car aucune direction n'est associée à une arête. Les graphiques non orientés peuvent être utilisés pour représenter des relations symétriques entre des objets. Les degrés d'entrée et de sortie de chaque nœud dans un graphe non dirigé sont égaux, mais ce n'est pas le cas pour un graphe dirigé. Lorsque vous utilisez une matrice pour représenter un graphe non orienté, celle-ci devient toujours un graphe symétrique, mais ce n'est pas le cas pour les graphes orientés. Un graphe non orienté peut être converti en un graphe dirigé 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 dirigé en un graphe non orienté.