Data Structure Questions and Answers – Multigraph and Hypergraph

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Multigraph and Hypergraph”.

1. Possible number of labelled simple Directed, Pseudo and Multigarphs exist having 2 vertices?
A) 3, Infinite, 4
B) 4, 3, Infinite
C) 4, Infinite, infinite
D) 4, Infinite, Infinite

Explanation: MultiGraphs and PseudoGraphs may have an infinite number of edges, while there are four different simple graphs.

2. Which of the following is a HyperGraph, where V is the set of vertices, E is the set of edges?
A) V = {v1, v2, v3} E = {e1, e2} = {{v2, v3} {v1, v3}}
B) V = {v1, v2} E = {e1} = {{v1, v2}}
C) V = {v1, v2, v3} E = {e1, e2, e3} = {{v2, v3}{v3, v1}{v2, v1}}
D) All of the mentioned

Explanation: Both hyper-edges in a uniform Graph have the same cardinality.

3. What would be the Incidence Matrix of the given HyperGraph?
V = {x,y,z} E = {{x,y}{y}{x,z}{z,y}}
A) {{1,0,1,0},
{1,1,0,1},
{0,0,1,1}}

B) {{1,1,0,0},
{0,1,0,0},
{1,1,1,0}}
C) {{0,1,0,1},
{0,0,1,0},
{1,1,0,0}}
D) None of the Mentioned

Explanation: The edges are represented by the columns, while the vertices are represented by the rows.

4. What is the degree sequence of the given HyperGraph, in non-increasing order.
V = {v1,v2,v3,v4,v5,v6} E = {{v1,v4,v5} {v2,v3,v4,v5} {v2} {v1} {v1,v6}}
A) 3,2,1,1,1,1
B) 3,2,2,2,1,1
C) 3,2,2,2,2,1
D) 3,2,2,1,1,1

Explanation: The degree of v1,v2,v3,v4,v5,v6 is 3,2,1,2,2,1 respectively.

5. MultiGraphs having self-loops are called PseudoGraphs?
A) True
B) False

Explanation: All PseudoGraphs are MultiGraphs, but not all MultiGraphs are PseudoGraphs, since all PseudoGraphs have self loops, but not all MultiGraphs do.

6. Given Adjacency matrices determine which of them are PseudoGraphs?
i) {{1,0} {0,1}}
ii) {{0,1}{1,0}}
iii) {{0,0,1}{0,1,0}{1,0,0}}
A) only i)
B) ii) and iii)
C) i) and iii)
D) i) ii) and iii)

Explanation: In I all vertices have self loops, and in ii) the second vertex has a self loop.

7. All undirected Multigraphs contain eulerian cycles.
A) True
B) False

Explanation: Eulerian circuits or cycles exist only in graphs with every vertex having an even degree.

8. Determine the number of vertices for the given Graph or Multigraph?
G is a 4-regular Graph having 12 edges.
A) 3
B) 6
C) 4
D) Information given is insufficient

Explanation: Sum of degrees of all the edges equal to 2 times the number of edges. 2*12=4*n, n=>6.

9. Which of the following statement is true.
A) There exists a Simple Graph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9
B) There exists a MultiGraph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9
C) There exists a MultiGraph as well as a Simple Graph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9
D) None of the mentioned

Explanation: In the case of Multigraphs for an isolate vertex, a degree 9 vertex means it is connected to all other vertices, and a multiple edge can compensate.

10. Given Adjacency matrices determine which of them are PseudoGraphs?
i) {{1,0} {0,1}}
ii) {{0,1}{1,0}}
iii) {{0,0,1}{0,1,0}{1,0,0}}
A) only i)
B) ii) and iii)
C) i) and iii)
D) i) ii) and iii)

Explanation: In I all vertices have self loops, and in ii) the second vertex has a self loop.

A graph with edges that are unordered pairs of vertices and several edges connecting the same pair of vertices. Formal Definition: E is a bag of edges, not a set, like graph. A multigraph is a graph that allows for multiple edges (also known as parallel edges), or edges with the same end nodes. As a result, more than one edge can connect two vertices. Simple graphs have only one form of connection connecting their nodes, such as road or rail links. Between the same two nodes in a multigraph, there may be more than one connection sort.

Leave a Reply

Your email address will not be published.