Différence entre graphique dirigé et non dirigé

Dirigé vs graphique non dirigé

Un graphique est une structure mathématique constituée d'un ensemble de sommets et de bords. Un graphique représente un ensemble d'objets (représentés par des sommets) qui sont connectés via certains liens (représentés par les bords). En utilisant des notations mathématiques, un graphique peut être représenté par G, où g = (V, E) et V est l'ensemble des sommets et E est l'ensemble des bords. Dans un graphique non dirigé, il n'y a pas de direction associée aux bords qui relient les sommets. Dans un graphique dirigé, il y a une direction associée aux bords qui relient les sommets.

Graphique non dirigée

Comme mentionné précédemment, un graphique non dirigé est un graphique dans lequel il n'y a pas de direction dans les bords qui relient les sommets dans le graphique. La figure 1 représente un graphique non dirigé 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 qu'il n'y a rien qui empêche d'écrire l'ensemble des bords comme v = (v2, v1), (v3, v2), (v3, v1) ​​puisque les bords n'ont pas de direction. Par conséquent, les bords dans un graphique non dirigé ne sont pas des paires commandées. C'est la principale caractéristique d'un graphique non dirigé. Des graphiques non dirigés peuvent être utilisés pour représenter des relations symétriques entre des objets qui sont 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 bords représentent les routes bidirectionnelles qui relient les villes.

Graphique dirigé

Un graphique dirigé est un graphique dans lequel les bords du graphique qui relient les sommets ont une direction. La figure 2 représente un graphique dirigé 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 bords d'un graphique non dirigé sont des paires commandées. Fond, le bord E dans un graphique dirigé peut être représenté par la paire ordonnée E = (x, y) où x est le sommet qui est appelé l'origine, la source ou le point initial du bord E, et le sommet y est appelé le terminus , terminant le sommet ou le point terminal. Par exemple, un réseau routier qui relie un ensemble de villes à l'aide de routes uniques peut être représentée à l'aide d'un graphique non dirigé. Les villes peuvent être représentées par les sommets du graphique et les bords dirigés représentent les routes qui relient les villes en considérant la direction que la circulation circule sur la route.

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

Dans un graphique dirigé, un bord est une paire ordonnée, où la paire commandée représente la direction du bord qui relie les deux sommets. D'un autre côté, dans un graphique non dirigé, un bord est une paire non ordonnée, car il n'y a pas de direction associée à un bord. Des graphiques non dirigés peuvent être utilisés pour représenter les relations symétriques entre les objets. En degré et hors degré de chaque nœud dans un graphique non dirigé sont égaux, mais ce n'est pas vrai pour un graphique dirigé. Lorsque vous utilisez une matrice pour représenter un graphique non dirigé, la matrice devient toujours un graphique symétrique, mais ce n'est pas vrai pour un graphique dirigé. Un graphique non dirigé peut être converti en un graphique dirigé 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 graphique dirigé en un graphique non dirigé.