Design And Analysis Of Algorithms Set 14

Computer Science Engineering (CSE)

Practice Mode Previous Next
On This Page

This set of Design and Analysis of Algorithms Multiple Choice Questions & Answers (MCQs) focuses on Design And Analysis Of Algorithms Set 14

Q1 | It is possible to have a negative chromatic number of bipartite graph.
  • true
  • false
Answer: false
Explaination:
a graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. the smallest number of graphs needed to color the graph is the chromatic number. but the chromatic number cannot be negative.
Q2 | Every Perfect graph has forbidden graph characterization.
  • true
  • false
Answer: true
Explaination:
berge theorem proves the forbidden graph characterization of every perfect graphs. because of that reason every bipartite graph is perfect graph.
Q3 | Which structure can be modelled by using Bipartite graph?
  • hypergraph
  • perfect graph
  • hetero graph
  • directed graph
Answer: hypergraph
Explaination:
a combinatorial structure such as hypergraph can be made using the bipartite graphs. a hypergraph in graph
Q4 | Which type of graph has all the vertex of the first set connected to all the vertex of the second set?
  • bipartite
  • complete bipartite
  • cartesian
  • pie
Answer: complete bipartite
Explaination:
the graph is known as bipartite if the graph does not contain any odd length cycle in it. the complete bipartite graph has all the vertex of first set connected to all the vertex of second set.
Q5 | Which graph is also known as biclique?
  • histogram
  • complete bipartite
  • cartesian
  • tree
Answer: complete bipartite
Explaination:
a graph is known as complete bipartite graph if and only if it has all the vertex of first set connected to all the vertex of second set. complete bipartite graph is also known as biclique.
Q6 | Which term defines all the complete bipartite graph that are trees?
  • symmetric
  • anti – symmetric
  • circular
  • stars
Answer: stars
Explaination:
star is a complete bipartite graph with one internal node and k leaves. therefore, all complete bipartite graph which is trees are known as stars in graph theory.
Q7 | How many edges does a n vertex triangle free graph contains?
  • n2
  • n2 + 2
  • n2 / 4
  • n3
Answer: n2 / 4
Explaination:
a n vertex triangle free graph contains a total of n2 / 4 number of edges. this is stated by mantel’s theorem which is a special case in turan’s theorem for r=2.
Q8 | Which graph is used to define the claw free graph?
  • bipartite graph
  • claw graph
  • star graph
  • cartesian graph
Answer: claw graph
Explaination:
star is a complete bipartite graph with one internal node and k leaves. star with three edges is called a claw. hence this graph is used to define claw free graph.
Q9 | What is testing of a complete bipartite subgraph in a bipartite graph problem called?
  • p problem
  • p-complete problem
  • np problem
  • np-complete problem
Answer: np-complete problem
Explaination:
np stands for nondeterministic polynomial time. in a bipartite graph, the testing of a complete bipartite subgraph in a bipartite graph is an np-complete problem.
Q10 | Which graph cannot contain K3, 3 as a minor of graph?
  • planar graph
  • outer planar graph
  • non planar graph
  • inner planar graph
Answer: planar graph
Explaination:
minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off
Q11 | Which of the following is not an Eigen value of the adjacency matrix of the complete bipartite graph?
  • (nm)1/2
  • (-nm)1/2
  • nm
Answer: nm
Explaination:
the adjacency matrix is a square matrix that is used to represent a finite graph. therefore, the eigen values for the complete bipartite graph is found to be (nm)1/2, (-nm)1/2, 0.
Q12 | Which complete graph is not present in minor of Outer Planar Graph?
  • k3, 3
  • k3, 1
  • k3, 2
  • k1, 1
Answer: k3, 2
Explaination:
minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off vertices from a graph. hence outer planar graph cannot contain k3, 2 as a minor graph.
Q13 | Is every complete bipartite graph a Moore Graph.
  • true
  • false
Answer: true
Explaination:
in graph theory, moore graph is defined as a regular graph that has a degree d and diameter k. therefore, every complete bipartite graph is a moore graph.
Q14 | What is the multiplicity for the adjacency matrix of complete bipartite graph for 0 Eigen value?
  • 1
  • n + m – 2
  • 2
Answer: n + m – 2
Explaination:
the adjacency matrix is a square matrix that is used to represent a finite graph. the multiplicity of the adjacency matrix off complete bipartite graph with eigen value 0 is n + m – 2.
Q15 | Which of the following is not an Eigen value of the Laplacian matrix of the complete bipartite graph?
  • n + m
  • n
  • n*m
Answer: n*m
Explaination:
the laplacian matrix is used to represent a finite graph in the mathematical field of graph theory. therefore, the eigen values for the complete bipartite graph is found to be n + m, n, m, 0.
Q16 | What is the multiplicity for the laplacian matrix of the complete bipartite graph for n Eigen value?
  • 1
  • m-1
  • n-1
Answer: m-1
Explaination:
the laplacian matrix is used to represent a finite graph in the mathematical field of graph theory. the multiplicity of the laplacian matrix of complete bipartite graph with eigen value n is m-1.
Q17 | Is it true that every complete bipartite graph is a modular graph.
  • true
  • false
Answer: true
Explaination:
yes, the modular graph in graph theory is defined as an undirected
Q18 | How many spanning trees does a complete bipartite graph contain?
  • nm
  • mn-1 * nn-1
  • 1
Answer: mn-1 * nn-1
Explaination:
spanning tree of a given graph is defined as the subgraph or the tree with all the given vertices but having minimum number of edges. so, there are a total of mn-1
Q19 | What does Maximum flow problem involve?
  • finding a flow between source and sink that is maximum
  • finding a flow between source and sink that is minimum
  • finding the shortest path between source and sink
  • computing a minimum spanning tree
Answer: finding a flow between source and sink that is maximum
Explaination:
the maximum flow problem involves finding a feasible flow between a source and a sink in a network that is maximum and not minimum.
Q20 | A network can have only one source and one sink.
  • false
  • true
Answer: true
Explaination:
a network can have only one source and one sink inorder to find the feasible flow in a weighted connected graph.
Q21 | What is the source?
  • vertex with no incoming edges
  • vertex with no leaving edges
  • centre vertex
  • vertex with the least weight
Answer: vertex with no incoming edges
Explaination:
vertex with no incoming edges is called as a source. vertex with no leaving edges is called as a sink.
Q22 | Which algorithm is used to solve a maximum flow problem?
  • prim’s algorithm
  • kruskal’s algorithm
  • dijkstra’s algorithm
  • ford-fulkerson algorithm
Answer: ford-fulkerson algorithm
Explaination:
ford-fulkerson algorithm is used to compute the maximum feasible flow between a source and a sink in a network.
Q23 | Does Ford- Fulkerson algorithm use the idea of?
  • naïve greedy algorithm approach
  • residual graphs
  • minimum cut
  • minimum spanning tree
Answer: residual graphs
Explaination:
ford-fulkerson algorithm uses the idea of residual graphs which is an extension of naïve greedy approach allowing undo operations.
Q24 | The first step in the naïve greedy algorithm is?
  • analysing the zero flow
  • calculating the maximum flow using trial and error
  • adding flows with higher values
  • reversing flow if required
Answer: analysing the zero flow
Explaination:
the first step in the naïve greedy algorithm is to start with the zero flow followed by adding edges with higher values.
Q25 | Under what condition can a vertex combine and distribute flow in any manner?
  • it may violate edge capacities
  • it should maintain flow conservation
  • the vertex should be a source vertex
  • the vertex should be a sink vertex
Answer: it should maintain flow conservation
Explaination:
a vertex can combine and distribute flow in any manner but it should not violate edge capacities and it should maintain flow conservation.
Previous Next