Un graphe non orienté est-il le même qu'un graphe orienté si chaque noeud a des arêtes dans les deux sens?

Question

Si j'ai un multigraph dirigé non pondéré où, pour chaque arête allant de node1 à node2, il y a une arête allant de node2 à node1, cela signifie-t-il que l'on peut traiter comme un graphe non orienté? Pour donner un contexte, je modélise un système de métro où, entre chaque station connectée, il y a une ligne où un train peut aller dans les deux sens.

PS Désolé pour le titre. Impossible de trouver une façon concise de le dire.

Answer 1

Bien que ces graphes se comportent de manière similaire, ils ont des propriétés fondamentalement différentes. Par exemple, considérons un graphe à deux nœuds avec un seul bord reliant les deux nœuds. Ce graphique n'a pas de cycles simples. Cependant, lorsque vous le convertissez en un graphique orienté avec des arêtes dans les deux sens, le graphique a maintenant un cycle simple formé en marchant vers l'avant puis vers l'arrière, puisque vous avez traversé deux arêtes différentes dans le processus. Cela ne veut pas dire que représenter le graphique de cette façon est une mauvaise idée. C'est en fait assez commun de le faire. Ce que cela signifie, c'est qu'il y a quelques cas où les propriétés mathématiques des graphiques seront différentes, en particulier si vous marchez autour d'un saut à la fois et de suivre les bords que vous avez utilisés.