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?
Thanks!
Best Answer
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.