7
$\begingroup$

I came across an issue with the definition of a (directed) graph in Sipser's Introduction to the theory of computation, 2nd Ed.

On pp.10, An undirected graph, or simply a graph, is a set of points with lines connecting some of the points. The points are called nodes or vertices, and the lines are called edges, ...

On the same page,

No more than one edge is allowed between any two nodes.

On pp.12,

If it has arrows instead of lines, the graph is a directed graph,...

In Figure 0.16 on pp.12, there is an example of a directed graph, an arrow from node 1 to node 2 and an arrow from node 2 to node 1.

So, we have two arrows in opposite direction between two nodes.

I understand all of these basics.

My question is,

Is directed graph a graph?

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ To the downvoter: downvoting without leaving a comment on how to improve the post is not very helpful or kind to the OP. $\endgroup$ – Alex ten Brink Mar 24 '12 at 11:42
  • $\begingroup$ yes, directed graph is a graph. Actually there can be various kinds of classifications like: undirected graph and directed graph. Other could be simple graph, multi-graph, hyper-graph. Read all the definitions from wikipedia or some standard book for more details. $\endgroup$ – singhsumit Mar 24 '12 at 11:48
  • $\begingroup$ I guess I am challenging the sentence “No more than one edge is allowed between any two nodes” in the book. Is this why people prefer to call it diagraph instead of directed graph to avoid this issue? $\endgroup$ – scaaahu Mar 24 '12 at 11:55
  • 1
    $\begingroup$ @singhsumit: The OP is reading a standard book. $\endgroup$ – Raphael♦ Mar 24 '12 at 12:06
  • 3
    $\begingroup$ Sometimes a red herring is a herring, and sometimes it isn't. $\endgroup$ – JeffE Mar 24 '12 at 20:58
12
$\begingroup$

As is often the case, using a formal definition is helpful:

Let $V$ a finite set. $G=(V,E)$ is

  • a graph if $E \subseteq \left\{\{v_1, v_2\} \mid v_1, v_2 \in V \right\}$ and
  • a digraph if $E \subseteq \left\{(v_1,v_2) \mid v_1, v_2 \in V\right\}$.

Note the central difference: edges are sets in graphs and pairs in digraphs. In particular, simpleness is implied by this definition. Extending the definition is also easy:if $E$ was a multiset, you could have non-simple graphs. If the edges had more than two components, you'd have hypergraphs.

Disclaimer: People define (di)graphs in different ways; this is one very common variant. For example, if you are uncomfortable with digraphs (formally) not being graphs, you define them like this:

Let $V$ a finite set and $E \subseteq V^2$. We call the pair $G=(V,E)$ a graph. We say

  • $G$ is undirected if and only if $(v_1,v_2) \in E \Longleftrightarrow (v_2,v_1) \in E$ and
  • $G$ is directed otherwise.

This defines undirected graphs as special cases of directed graphs. Note that with this definition, extensions to labeled graphs (edges get markings) may be awkward: We want the complete digraph with to be different from the complete undirected graph (as the former has two labeled edges between between every pair of nodes, the latter only one); by this definition, they are the same. Note how the first definition I gave circumvents this issue nicely; sometimes definitions are (re)made with later needs in mind.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Correct me if I am wrong. From the definition above, a diagraph is not a graph. A graph is a subset of a set of two-element(doubleton?) sets. A diagraph is a subset of a set of (ordered)pairs. So, they are different things. $\endgroup$ – scaaahu Mar 24 '12 at 14:05
  • $\begingroup$ If you define it like this, yes. I will add an alternative. $\endgroup$ – Raphael♦ Mar 24 '12 at 15:38
  • 4
    $\begingroup$ @scaaahu: Your problem is one of words. Words are immaterial; the formal properties are of essence. As long as it is clear from context what you mean, you can say "graph" to all kinds of objects. $\endgroup$ – Raphael♦ Mar 24 '12 at 15:48
  • 4
    $\begingroup$ @scaaahu To put it plainly: a directed graph has arrows between the nodes, an undirected graph has lines. “Graph” can mean either directed graph or undirected graph depending on the context. Beware of treating an undirected graph as a special kind of directed graph, because some words will end up having a different meaning. For example, $a \leftrightarrows b$ (i.e. $E=\{(a,b),(b,a)\}$) is a directed graph with a cycle $(a,b,a)$; $a-b$ (i.e. $E=\{\{a,b\}\}$) is an undirected graph with no cycle. $\endgroup$ – Gilles 'SO- stop being evil' Mar 24 '12 at 15:57
9
$\begingroup$

The word 'graph' has two meanings: it can be a shorthand for 'undirected graphs' (like how your book defines it) or it can refer to something that is 'graph-like', such as a directed or an undirected graph. The first meaning is most common.

Directed graphs and undirected graphs are not the same thing (arrows versus lines), although one can view undirected graphs as directed graphs if you replace every (undirected) edge by two arrows, one for either direction (so A -- B becomes A <-> B).

Additionally, for some problems, you can transform a directed graph to a similar-looking undirected graph on which your problem has the same solution. The proof that the Hamiltonian cycle problem is NP-hard on undirected graphs is usually done by a reduction from the directed version, by transforming the directed graph into an undirected graph that will have a Hamiltonian cycle if and only if the original graph had one.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "replace every(undirected) edge by two arrows" answered my question. Thanks. $\endgroup$ – scaaahu Mar 24 '12 at 12:06
  • 1
    $\begingroup$ It is noteworthy that simpleness (for graphs: no more than on edge between any two nodes) is usually defined/assumed similarly for digraphs, too: no more than one edge in one direction for every pair of nodes. $\endgroup$ – Raphael♦ Mar 24 '12 at 12:08
  • 2
    $\begingroup$ “The first meaning is most common.” I think that that is true in graph theory, but not necessarily true in computer science. $\endgroup$ – Tsuyoshi Ito Mar 24 '12 at 17:04
  • 1
    $\begingroup$ "simplicity is usually defined/assumed" — I think this is more because it shortens the definition than because simple graphs are inherently more useful. Most graph algorithms do not require their input graphs to be simple. $\endgroup$ – JeffE Mar 24 '12 at 21:02
  • $\begingroup$ @JefE: I would expect many combinatoric and algorithmic results to break as you would usually assume that $\operatorname{deg}(v)=k$ implies $v$ has $k$ adjacent nodes. $\endgroup$ – Raphael♦ Mar 25 '12 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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