patternMinor
Treating undirected graphs as a subcategory of directed graphs
Viewed 0 times
treatinggraphsdirectedundirectedsubcategory
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#69372, answer score: 8
Revisions (0)
No revisions yet.