I came across an issue with the definition of a (directed) graph in Sipser\'s In

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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.