Traiter les graphiques non dirigés comme une sous-catégorie de graphiques dirigés

10

En gros, un graphe non orienté est très similaire à un graphe orienté où pour chaque arête (v, w), il y a toujours une arête (w, v). Cela suggère qu'il pourrait être acceptable de visualiser les graphiques non dirigés comme un sous-ensemble de graphiques dirigés (peut-être avec une restriction supplémentaire selon laquelle l'ajout / la suppression de bords ne peut être effectué que par paires correspondantes).

Cependant, les manuels ne suivent généralement pas ce traitement et préfèrent définir les graphiques non dirigés comme un concept distinct plutôt que comme une sous-catégorie de graphiques dirigés. Y a-t-il une raison à cela?

graphs terminology max
la source
2
Notez qu'il existe également des "graphes mixtes": un graphe où les bords peuvent être orientés ou non. Dans ce cas, une paire de bords dirigés n'est pas la même chose qu'un bord non dirigé entre deux nœuds. Par exemple: considérez les rues: vous pouvez avoir une paire de rues à sens unique entre deux points allant dans des directions opposées, ou une seule rue à double sens. Ceci est important dans certains cas: par exemple, vous ne voulez pas qu'un appareil de navigation dise à un utilisateur d'effectuer un demi-tour entre deux rues à sens unique s'il y a une barrière au milieu, alors qu'il peut être possible de le faire dans un rue à double sens.
Bakuriu

Réponses:

8

Vous avez tout à fait raison; c'est une façon parfaitement valide d'afficher des graphiques non orientés.

Parfois, dans les graphiques non orientés, certaines choses deviennent plus faciles et plus propres à raisonner. Par exemple, vous n'avez pas à vous soucier de la différence entre les composants faiblement connectés et fortement connectés dans les graphiques non orientés. Les algorithmes pour les graphes non dirigés peuvent parfois être plus efficaces ou plus simples que si nous devions appliquer l'algorithme correspondant pour les graphes dirigés.

Donc: certains manuels choisissent peut-être de suivre ce traitement, car il leur permet d'abord d'introduire un problème dans le contexte (plus facile) des graphiques non dirigés, puis de généraliser au cas (plus difficile) des graphiques dirigés. C'est juste de la spéculation.

DW
la source
3

Voir cette page pour des exemples de problèmes pour lesquels la forme de graphique non orienté est en fait plus difficile que la forme de graphique dirigé. Il s'agit, par exemple, de trouver un cycle de poids négatif et de compter le nombre de cycles eulériens. Pour moi, ces problèmes semblent être plus difficiles dans les graphiques non orientés, car une partie de la tâche peut être définie comme choisissant en quelque sorte la bonne "direction" pour chaque bord - ce qui bien sûr est "déjà fait pour nous" lorsque le graphique est dirigé.

j_random_hacker
la source
1
Ah oui. Par exemple, le cycle eulérien, lorsqu'il est défini en termes de graphes dirigés, devrait exiger que "pas plus d'un bord ne soit utilisé pour chaque paire (v, w), (w, v)" - ce qui donne l'idée de représenter un graphe non orienté comme un digraphe moins attrayant.
max
0

Il est difficile de motiver quelque chose de très général à l'improviste; cela pourrait rendre les épreuves et les manuels plus simples, mais pas nécessairement plus faciles à comprendre et à suivre intuitivement.
Les gens trouvent généralement plus intuitif d'apprendre un concept simple, puis de le généraliser à quelque chose de plus abstrait, plutôt que de définir un concept super-généralisé et abstrait, puis d'instancier ses cas particuliers. C'est probablement l'un de ces cas.

user541686
la source