[Solved]: Is Directed Graph a Graph?

Problem Detail: 

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?

Asked By : scaaahu

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/737