Roughly, an undirected graph is very similar to a directed graph where for each edge (v, w), there is always an edge (w, v). That suggests that it might be acceptable to view undirected graphs as a subset of directed graphs (perhaps with an additional restriction that adding/deleting edges can only be done in matching pairs).

However, textbooks usually don't follow this treatment, and prefer to define undirected graphs as a separate concept, rather than a subcategory of directed graphs. Is there any reason for that?

  • Note that there exist also "mixed graphs": a graph where edges can be directed or not. In this case a pair of directed edges is not the same as an undirected edge between two nodes. For example: consider streets: you can have a pair of one-way streets between two points going in opposite directions, or a single two-way street. This is important in some cases: e.g. you don't want a navigation device telling a user to perform a U-turn between two one-way streets if there is a barrier in the middle, while it may be possible to do that in a single two-way street. – Bakuriu Jan 27 '17 at 7:15
up vote 7 down vote accepted

You are absolutely correct; that's a perfectly valid way to view undirected graphs.

Sometimes, in undirected graphs, some things become easier and cleaner to reason about. For instance, you don't have to worry about the difference between weakly connected vs strongly connected components in undirected graphs. Algorithms for undirected graphs can sometimes be more efficient or simpler than if we were to apply the corresponding algorithm for directed graphs.

So: perhaps some textbooks choose to follow this treatment because it lets them introduce a problem first in the (easier) context of undirected graphs, and then generalize to the (harder) case of directed graphs. That's just speculation.

See this page for examples of problems for which the undirected-graph form is actually harder than the directed-graph form. These include, for example, finding a negative-weight cycle, and counting the number of Eulerian cycles. To me, these problems seem to be harder in undirected graphs because part of the task can be framed as somehow choosing the right "direction" for each edge -- which of course is "already done for us" when the graph is directed.

  • 1
    Oh right. For example, Eulerian cycle when defined in terms of directed graphs, would have to require that "no more than one edge is used from each pair (v, w), (w, v)" -- making the idea of representing undirected graph as a digraph less attractive. – max Jan 27 '17 at 4:41

It's hard to motivate something very general out of the blue; it might make the proofs and the textbooks simpler, but not necessarily easier to understand and intuitively follow.
People usually find it more intuitive to learn a simple concept and then generalize it to something more abstract, rather than to define some super-generalized and abstract concept and then instantiate its particular cases. This is probably one of those cases.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.