Is Directed Graph a Graph?

Question

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?

Answer 1

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.

Answer 2

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.