Engineering Questions with Answers - Multiple Choice Questions

Data Structure MCQ – Multigraph and Hypergraph

1 - Question

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)

View Answer

Answer: c
Explanation: In i) self loops exist for both the vertices, in iii) self loop exists in the second vertex.




2 - Question

All undirected Multigraphs contain eulerian cycles.
a) True
b) False

View Answer

Answer: a
Explanation: Only graphs with every vertex having even degree have eulerian circuits or cycles.




3 - Question

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

View Answer

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




4 - Question

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

View Answer

Answer: b
Explanation: If a vertex has a degree 9 that means it is connected to all the other vertices, in case of Multigraphs for an isolate vertex, and a multiple edge may compensate.




5 - Question

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)

View Answer

Answer: c
Explanation: In i) self loops exist for both the vertices, in iii) self loop exists in the second vertex.




6 - Question

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

View Answer

Answer: d
Explanation: MultiGraphs and PseudoGraphs may have infinite number of edges, while 4 possible simple graphs exist.




7 - Question

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

View Answer

Answer: d
Explanation: In a uniform Graph all the hyper-edges have the same cardinality.




8 - Question

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

View Answer

Answer: a
Explanation: The columns represent edges while rows represent vertices.




9 - Question

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

View Answer

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




10 - Question

MultiGraphs having self-loops are called PseudoGraphs?
a) True
b) False

View Answer

Answer: a
Explanation: All PsuedoGraphs are MultiGraphs, but all MultiGraphs are not PseudoGraphs as all PseudoGraphs have self loop, but all MultiGraphs do not have self loops.

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners