Data Structure

Multigraph and Hypergraph

Question 1
Marks : +2 | -2
Pass Ratio : 100%
Given Adjacency matrices determine which of them are PseudoGraphs?
only i)
ii) and iii)
i) and iii)
i) ii) and iii)
Explanation:
In i) self loops exist for both the vertices, in iii) self loop exists in the second vertex.
Question 2
Marks : +2 | -2
Pass Ratio : 100%
What is the degree sequence of the given HyperGraph, in non-increasing order.
3,2,1,1,1,1
3,2,2,2,1,1
3,2,2,2,2,1
3,2,2,1,1,1
Explanation:
The degree of v1,v2,v3,v4,v5,v6 is 3,2,1,2,2,1 respectively.
Question 3
Marks : +2 | -2
Pass Ratio : 100%
All undirected Multigraphs contain eulerian cycles.
True
False
Explanation:
Only graphs with every vertex having even degree have eulerian circuits or cycles.
Question 4
Marks : +2 | -2
Pass Ratio : 100%
What would be the Incidence Matrix of the given HyperGraph?
{{1,0,1,0},
{{1,1,0,0},
{{0,1,0,1},
None of the Mentioned
Explanation:
The columns represent edges while rows represent vertices.
Question 5
Marks : +2 | -2
Pass Ratio : 100%
Determine the number of vertices for the given Graph or Multigraph?
3
6
4
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.
Question 6
Marks : +2 | -2
Pass Ratio : 100%
Which of the following is a HyperGraph, where V is the set of vertices, E is the set of edges?
V = {v1, v2, v3} E = {e1, e2} = {{v2, v3} {v1, v3}}
V = {v1, v2} E = {e1} = {{v1, v2}}
V = {v1, v2, v3} E = {e1, e2, e3} = {{v2, v3}{v3, v1}{v2, v1}}
All of the mentioned
Explanation:
In a uniform Graph all the hyper-edges have the same cardinality.
Question 7
Marks : +2 | -2
Pass Ratio : 100%
Possible number of labelled simple Directed, Pseudo and Multigarphs exist having 2 vertices?
3, Infinite, 4
4, 3, Infinite
4, Infinite, infinite
4, Infinite, Infinite
Explanation:
MultiGraphs and PseudoGraphs may have infinite number of edges, while 4 possible simple graphs exist.
Question 8
Marks : +2 | -2
Pass Ratio : 100%
Given Adjacency matrices determine which of them are PseudoGraphs?
only i)
ii) and iii)
i) and iii)
i) ii) and iii)
Explanation:
In i) self loops exist for both the vertices, in iii) self loop exists in the second vertex.
Question 9
Marks : +2 | -2
Pass Ratio : 100%
MultiGraphs having self-loops are called PseudoGraphs?
True
False
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.
Question 10
Marks : +2 | -2
Pass Ratio : 100%
Which of the following statement is true.
There exists a Simple Graph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9
There exists a MultiGraph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9
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
None of the mentioned
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.