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

Data Structures MultipleChoice Questions and Answers on Preorder Traversal

1. For the tree below, write the pre-order traversal. a) 2, 7, 2, 6, 5, 11, 5, 9, 4 b) 2, 7, 5, 2, 6, 9, 5, 11, 4 c) 2, 5, 11, 6, 7, 4, 9, 5, 2 d) 2, 7, 5, 6, 11, 2, 5, 4, 9 Answer: a Explanatio...

Data Structures Multiple Choice Questions and Answers on Binary Tree Properties

1. The number of edges from the root to the node is called __________ of the tree. a) Heightb) Depthc) Lengthd) None of the mentioned Answer: b Explanation: By definition. 2. The number of edges...

Data Structures Multiple Choice Questions and Answers on Binary Search Tree

1. Which of the following is false about a binary search tree? a) The left child is always lesser than its parentb) The right child is always greater than its parentc) The left and right sub-trees ...

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