I have the following two questions in my book:

Question # 1

Determine whether the graph shown has directed or undirected edges, whether it has multiple edges, and whether it has one or more loops.


Because Graph (7) has multiple edges (as the book says "A Directed graph may have multiple directed edges from a vertex to a second (possibly the same) vertex are called as directed multigraphs") and it also has loops at vertex c and e. Similar is the case with Graph (9). They should both be Directed Multigraphs but the book says that Graph(7) is a directed graph only and Graph (9) is a Directed Multigraph. Why Graph(7) is only a directed graph instead of a directed multigraph?

Question # 2

Describe a graph model that represents whether each person at a party knows the name of each other person at the part. Should the edges be directed or undirected? Should multiple edges be allowed? Should loops be allowed?

I think the graph should be directed because its not necessary that if A knows the name of B then B would also the know the name of A. Moreover, because of this reason I think that the graph should have multiple edge but the answer at the back of the book is different. The book says that the the graph should be directed but it should not have multiple edges. Why is that?



Read a bit more carefully the definition that your book gives: "A directed graph may have multiple directed edges from a vertex to a second (possibly the same) vertex are called as directed multigraphs."

The key thing to notice here is that the multiple directed edges have the same origin and destination. Thus, in your first graph there is only one directed edge from vertex $c$ to vertex $d$ (and also only one directed edge from $d$ to $c$). So this graph is just a directed graph. On the other hand, in the second graph, there are two edges from $e$ to $d$, and two edges from $b$ to $c$. So this graph is a directed multigraph.

| cite | improve this answer | |
  • $\begingroup$ Thank you Casteels but what about the loop at c in graph(7)? A simple directed graph doesn't have a loop. $\endgroup$ – Tehmas Dec 16 '14 at 11:34
  • $\begingroup$ You didn't mention simple in your question, but yes it is not simple because of the loops. $\endgroup$ – Casteels Dec 16 '14 at 11:36
  • $\begingroup$ I didn't mention it because I thought "simple directed" and "directed" graphs are the same thing. Thanks for clearing that! $\endgroup$ – Tehmas Dec 16 '14 at 11:45
  • $\begingroup$ No problem. Yeah it can be a bit confusing sometimes because very often writers will say "graph" when they really mean "simple graph". Usually in this case there will be a note at the beginning saying something like "all graphs considered are simple graphs." $\endgroup$ – Casteels Dec 16 '14 at 11:54

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.