-1
$\begingroup$

It is commonly known that directed graphs are defined as a double $G_d:=(V,E)$ such that $E \subseteq V^2$, and that undirected graphs $G_u:=(V,E)$ such that $E \subseteq \left\{ \{a,b\}\Big\vert a \in V \land b\in V \right\}$.

Why? Why does one not just define, say, an undirected graph to be a directed graph wherein each edge merely happens to have a symmetric counterpart? Alternatively, why not say directed graphs are but undirected graphs so that one could write $v \in e \in E$ to say a vertex lies on an edge?

Currently very frustrated with the lack of standardisation of Graph Theory at the moment.

$\endgroup$
1
  • 1
    $\begingroup$ Undirected graphs are a special case of directed graphs, as you note. But they are a special case of such enormous importance that it's usually better to think of them as having undirected edges than to think of them having pairs of symmetric edges. $\endgroup$ Commented Nov 17 at 9:00

1 Answer 1

Reset to default
2
$\begingroup$

Because it would not be correct. For example, the complete graph $K_3$ has three edges, not six edges as your suggested definition would give it. Fundamental concepts like "Euler circuit" (using every edge exactly once) would become trivial if every edge was replaced by two opposing directed edges. We would get so fed up with talking about adding or removing some number of "pairs of opposing edges" that we would eventually realise everything would become much easier if we made "pair of opposing edges" the basic unit - and then we would get back to the standard definition.

$\endgroup$
4
  • $\begingroup$ I am sympathetic to the idea that such a definition would not be useful, but (and I concede that this problem might only be of my own) I still find it incredibly annoying that directed graphs and undirected graphs are considered the same class of objects when basic concepts such as "adjacency", "degree" and "vertex being on an edge" have vastly distinct definitions between the two objects. Is there some other formalism of the "vertex and edge" idea which more clearly differentiates the two objects? $\endgroup$ Commented Nov 19 at 2:47
  • 1
    $\begingroup$ @Ultrio but they aren't considered the same class of objects. They are merely similar enough that a lot of the same questions apply to both (but have different answers). They are different in pretty much the same way that equivalence relations and preorders are. You could formalise them in terms of a set equipped with an "adjacency" relation if you wanted, but again this is not so helpful if you want to manipulate edges. $\endgroup$ Commented Nov 19 at 9:06
  • $\begingroup$ Then whose idea was it to call both of them "Graphs"? If they are so different then why are they not given more distinct names? $\endgroup$ Commented Nov 20 at 6:42
  • 1
    $\begingroup$ @Ultrio One reason the term "directed graphs" is a better choice than, say, "one-way systems" is that it makes it clear they're likely to be of interest to people who are interested in graphs. But you shouldn't expect them to be graphs, any more than skew fields are fields. $\endgroup$ Commented Nov 20 at 8:47

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.