Data Structure Questions and Answers – Multigraph and Hypergraph

«
»

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

1. 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.
advertisement

2. 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. 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.
advertisement
advertisement

4. 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. 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.
advertisement

6. 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. 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.
advertisement

8. 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. 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.
advertisement

10. 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.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter