Data Structures Multiple Choice Questions and Answers on Multigraph and Hypergraph

1. Given Adjacency matrices determine which of them are Pseudo Graphs?

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)
Answer: c

Explanation: In i) self loops exist for both the vertices, in iii) self loop exists in the second vertex.
2. All undirected Multigraphs contain eulerian cycles.

a) True
b) False
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
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. 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) None of the mentioned
d) 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
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)
Answer: c

Explanation: In i) self loops exist for both the vertices, in iii) self loop exists in the second vertex.
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
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.
Answer: d

Explanation: In a uniform Graph all the hyper-edges have the same cardinality.
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
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
Answer: b

Explanation: The degree of v1,v2,v3,v4,v5,v6 is 3,2,1,2,2,1 respectively.
10. MultiGraphs having self-loops are called PseudoGraphs?

a) True
b) False
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.

Related

Multiple Choice Questions 7035676917709204786

Post a Comment

emo-but-icon
:noprob:
:smile:
:shy:
:trope:
:sneered:
:happy:
:escort:
:rapt:
:love:
:heart:
:angry:
:hate:
:sad:
:sigh:
:disappointed:
:cry:
:fear:
:surprise:
:unbelieve:
:shit:
:like:
:dislike:
:clap:
:cuff:
:fist:
:ok:
:file:
:link:
:place:
:contact:

item