Différence Entre Les Graphiques Dirigés Et Non Dirigés

2024 Auteur: Mildred Bawerman | [email protected]. Dernière modifié: 2023-12-16 08:38

Graphique dirigé vs non dirigé

Un graphe est une structure mathématique composée d'un ensemble de sommets et d'arêtes. Un graphique représente un ensemble d'objets (représentés par des sommets) connectés via 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é, aucune direction n'est 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 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 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 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 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 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 dirigé

Un graphe orienté est un graphe dans lequel les arêtes du graphe reliant les sommets ont une direction. La figure 2 représente un graphe orienté avec un ensemble de sommets V = {V1, V2, V3}. L'ensemble d'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 qui est appelé l'origine, la source ou le point initial de l'arête e, et le sommet y est appelé le 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 orienté. Les villes peuvent être représentées par les sommets dans le graphique et les arêtes dirigées représentent les routes qui relient les villes en considérant la direction dans laquelle le trafic circule sur la route.

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

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, car il n'y a pas de direction associée à une arête. Les graphiques non orientés peuvent être utilisés pour représenter les relations symétriques entre les objets. Les degrés d'entrée et de sortie de chaque nœud dans un graphe non orienté sont égaux, mais ce n'est pas le cas 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 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 graphe non orienté.