[Solved]: Is Directed Graph a Graph?

ignougroup
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 Vright}$.

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