COMP 182 Quiz 9 - Graph Part 2

Question 1

What is the number of vertices of degree 2 in a path graph having n vertices,here n > 2 n - 2 n 2 0

Question 2

What would the time complexity to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix? O(E*E) O(V*V) O(E) O(V)

Question 3

A graph having an edge from each vertex to every other vertex is called a _____ Tightly Connected Strongly Connected Weakly Connected Loosely Connected

Question 4

What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices? 2 4 5 9

Question 5

Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of ____ O(V*V) O(V*V*V) O(E*V) O(E*E),

Question 6

Assuming value of every weight to be greater than 10, in which of the following cases the shortest path of a directed weighted graph from 2 vertices u and v will never change? add all values by 10 subtract 10 from all the values multiply all values by 10 in both the cases of multiplying and adding by 10,

Question 7

What is the maximum possible number of edges in a directed graph with no self loops having 8 vertices? 28 64 256 56,

Question 8

What is the maximum number of edges present in a simple directed graph with 7 vertices if there exists no cycles in the graph? 21 7 6 49,

Question 9

The topological sorting of any Directed Acyclic Graph can be done in ___ time. cubic quadratic linear logarithmic,

Question 10

Which of the given statement is true? All the Cyclic Directed Graphs have topological sortings All the Acyclic Directed Graphs have topological sortings All Directed Graphs have topological sortings All the cyclic directed graphs hace non topological sortings,

Question 11

What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph? Depends on a Graph Will always be zero Will always be greater than zero May be zero or greater than zero,

Question 12

Determine the number of vertices for the given Graph or Multigraph? G is a 4-regular Graph having 12 edges. 3 6 4 Information given is insufficient,

Question 13

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

Question 14

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

Question 15

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}} 3,2,1,1,1,1 3,2,2,2,1,1 3,2,2,2,2,1 3,2,2,1,1,1