How many edges must be removed to produce the spanning forest of a graph with N vertices, M edges and C connected components? (A) M+N-C (B) M-N-C (C) M-N+C (D) M+N+C

How many edges must be removed to produce the spanning forest of a graph with N vertices, M edges and C connected components? (A) M+N-C (B) M-N-C (C) M-N+C (D) M+N+C
by

1 Answer

Answer :

(C) M-N+C
by

Related questions

Cyclometric complexity of a flow graph G with n vertices and e edges is (A) V(G) = e+n-2 (B) V(G) = e-n+2 (C) V(G) = e+n+2 (D) V(G) = e-n-2

Description : Cyclometric complexity of a flow graph G with n vertices and e edges is (A) V(G) = e+n-2 (B) V(G) = e-n+2 (C) V(G) = e+n+2 (D) V(G) = e-n-2

Last Answer : (B) V(G) = e-n+2

Given a flow graph with 10 nodes, 13 edges and one connected components, the number of regions and the number of predicate (decision) nodes in the flow graph will be (A) 4, 5 (B) 5, 4 (C) 3, 1 (D) 13, 8

Description : Given a flow graph with 10 nodes, 13 edges and one connected components, the number of regions and the number of predicate (decision) nodes in the flow graph will be (A) 4, 5 (B) 5, 4 (C) 3, 1 (D) 13, 8

Last Answer : (B) 5, 4

A graph is a collection of nodes, called ………. And line segments called arcs or ……….. that connect pair of nodes. A) vertices, edges B) edges, vertices C) vertices, paths D) graph node, edges

Description : A graph is a collection of nodes, called ………. And line segments called arcs or ……….. that connect pair of nodes. A) vertices, edges B) edges, vertices C) vertices, paths D) graph node, edges

Last Answer : A) vertices, edges

A graph is said to be ……………… if the vertices can be split into two sets V1 and V2 such there are no edges between two vertices of V1 or two vertices of V2. A) Partite B) Bipartite C) Rooted D) Bisects

Description : A graph is said to be ……………… if the vertices can be split into two sets V1 and V2 such there are no edges between two vertices of V1 or two vertices of V2. A) Partite B) Bipartite C) Rooted D) Bisects

Last Answer : B) Bipartite

Consider a Hamiltonian Graph (G) with no loops and parallel edges. Which of the following is true with respect to this Graph (G) ? (a) deg(v) ≥ n/2 for each vertex of G (b) |E(G)| ≥ 1/2 (n-1)(n-2)+2 edges (c) deg(v) + deg(w) ≥ n for every v and w not connected by an edge (A) (a) and (b) (B) (b) and (c) (C) (a) and (c) (D) (a), (b) and (c)

Description : Consider a Hamiltonian Graph (G) with no loops and parallel edges. Which of the following is true with respect to this Graph (G) ? (a) deg(v) ≥ n/2 for each vertex of G (b) |E(G)| ≥ 1/2 (n-1)(n-2)+2 edges (c) deg(v) + deg( ... edge (A) (a) and (b) (B) (b) and (c) (C) (a) and (c) (D) (a), (b) and (c)

Last Answer : (D) (a), (b) and (c)

Which of the following connected simple graph has exactly one spanning tree? (A) Complete graph (B) Hamiltonian graph (C) Euler graph (D) None of the above

Description : Which of the following connected simple graph has exactly one spanning tree? (A) Complete graph (B) Hamiltonian graph (C) Euler graph (D) None of the above

Last Answer : (D) None of the above

State True or False. i) An undirected graph which contains no cycles is called forest. ii) A graph is said to be complete if there is an edge between every pair of vertices. A) True, True B) False, True C) False, False D) True, False

Description : State True or False. i) An undirected graph which contains no cycles is called forest. ii) A graph is said to be complete if there is an edge between every pair of vertices. A) True, True B) False, True C) False, False D) True, False

Last Answer : A) True, True

State True of False. i) Network is a graph that has weights or costs associated with it. ii) An undirected graph which contains no cycles is called a forest. iii) A graph is said to be complete if there is no edge between every pair of vertices. A) True, False, True B) True, True, False C) True, True, True D) False, True, True

Description : State True of False. i) Network is a graph that has weights or costs associated with it. ii) An undirected graph which contains no cycles is called a forest. iii) A graph is said to be complete if there is no ... ) True, False, True B) True, True, False C) True, True, True D) False, True, True

Last Answer : B) True, True, False

A vertex cover of an undirected graph G(V, E) is a subset V1 ⊆ V vertices such that (A) Each pair of vertices in V1 is connected by an edge (B) If (u, v) ∈ E then u ∈ V1 and v ∈ V1 (C) If (u, v) ∈ E then u ∈ V1 or v ∈ V1 (D) All pairs of vertices in V1 are not connected by an edge

Description : A vertex cover of an undirected graph G(V, E) is a subset V1 ⊆ V vertices such that (A) Each pair of vertices in V1 is connected by an edge (B) If (u, v) ∈ E then u ∈ V1 and v ∈ V1 (C) If (u, v) ∈ E then u ∈ V1 or v ∈ V1 (D) All pairs of vertices in V1 are not connected by an edge

Last Answer : (C) If (u, v) ∈ E then u ∈ V1 or v ∈ V1

A certain tree has two vertices of degree 4, one vertex of degree 3 and one vertex of degree 2. If the other vertices have degree 1, how many vertices are there in the graph? (A) 5 (B) n – 3 (C) 20 (D) 11

Description : A certain tree has two vertices of degree 4, one vertex of degree 3 and one vertex of degree 2. If the other vertices have degree 1, how many vertices are there in the graph? (A) 5 (B) n – 3 (C) 20 (D) 11

Last Answer : (D) 11

Which one of the following is used to compute cyclomatic complexity ? (A) The number of regions – 1 (B) E – N + 1, where E is the number of flow graph edges and N is the number of flow graph nodes. (C) P – 1, where P is the number of predicate nodes in the flow graph G. (D) P + 1, where P is the number of predicate nodes in the flow graph G.

Description : Which one of the following is used to compute cyclomatic complexity ? (A) The number of regions - 1 (B) E - N + 1, where E is the number of flow graph edges and N is the number of flow graph nodes. (C) ... in the flow graph G. (D) P + 1, where P is the number of predicate nodes in the flow graph G.

Last Answer : (D) P + 1, where P is the number of predicate nodes in the flow graph G.

The number of different spanning trees in complete graph, K4 and bipartite graph K2,2 have .......... and .....…. respectively. (A) 14, 14 (B) 16, 14 (C) 16, 4 (D) 14, 4

Description : The number of different spanning trees in complete graph, K4 and bipartite graph K2,2 have .......... and .....…. respectively. (A) 14, 14 (B) 16, 14 (C) 16, 4 (D) 14, 4

Last Answer : (C) 16, 4 

For general graph, how one can get rid of repeated states? a) By maintaining a list of visited vertices b) By maintaining a list of traversed edges c) By maintaining a list of non-visited vertices d) By maintaining a list of non-traversed edges

Description : For general graph, how one can get rid of repeated states? a) By maintaining a list of visited vertices b) By maintaining a list of traversed edges c) By maintaining a list of non-visited vertices d) By maintaining a list of non-traversed edges

Last Answer : a) By maintaining a list of visited vertices

Which of the following statements is false? (A) Optimal binary search tree construction can be performed efficiently using dynamic programming. (B) Breadth-first search cannot be used to find connected components of a graph. (C) Given the prefix and postfix walks of a binary tree, the tree cannot be reconstructed uniquely. (D) Depth-first-search can be used to find the components of a graph. (1) A (2) B (3) C (4) D

Description : Which of the following statements is false? (A) Optimal binary search tree construction can be performed efficiently using dynamic programming. (B) Breadth-first search cannot be used to find connected components of a graph. (C) ... used to find the components of a graph. (1) A (2) B (3) C (4) D 

Last Answer : Answer: 2

A ................. complete subgraph and a ................. subset of vertices of a graph G=(V,E) are a clique and a vertex cover respectively. (A) minimal, maximal (B) minimal, minimal (C) maximal, maximal (D) maximal, minimal

Description : A ................. complete subgraph and a ................. subset of vertices of a graph G=(V,E) are a clique and a vertex cover respectively. (A) minimal, maximal (B) minimal, minimal (C) maximal, maximal (D) maximal, minimal

Last Answer : (D) maximal, minimal 

A ……….. is a graph that has weights of costs associated with its edges. A) Network B) Weighted graph C) Both A and B D) None A and B

Description : A ……….. is a graph that has weights of costs associated with its edges. A) Network B) Weighted graph C) Both A and B D) None A and B

Last Answer : C) Both A and B

Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j) | 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a, b) and (c, d) if |a – c| ≤ 1 or |b–d| ≤ 1. The number of edges in this graph is (A) 726 (B) 796 (C) 506 (D) 616

Description : Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j) | 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a, b) and (c, d) if |a – c| ≤ 1 or |b–d| ≤ 1. The number of edges in this graph is (A) 726 (B) 796 (C) 506 (D) 616

Last Answer : (D) 616

If the sides of a slab simply supported on edges and spanning in two directions are equal, the maximum bending moment is multiplied by (A) 0.2 (B) 0.3 (C) 0.4 (D) 0.5

Description : If the sides of a slab simply supported on edges and spanning in two directions are equal, the maximum bending moment is multiplied by (A) 0.2 (B) 0.3 (C) 0.4 (D) 0.5

Last Answer : Answer: Option D

If the sides o a slab simply supported on its edges and spanning in two way are equal, then the maximum bending moment is multiplied by. (a) 0.25 (b) 0.50 (c) 0.75 (d) 0.85

Description : If the sides o a slab simply supported on its edges and spanning in two way are equal, then the maximum bending moment is multiplied by. (a) 0.25 (b) 0.50 (c) 0.75 (d) 0.85

Last Answer : (b) 0.50

When the slab is supported on all the four edges and the ratio of long span to short span is small, bending takes place along both the spans, such a slab is known as (a) Slab spanning in one direction (b) One way slab. (c) Slab spanning in two direction. (d) Two-way slab.

Description : When the slab is supported on all the four edges and the ratio of long span to short span is small, bending takes place along both the spans, such a slab is known as (a) Slab spanning in one direction (b) One way slab. (c) Slab spanning in two direction. (d) Two-way slab.

Last Answer : (d) Two-way slab.

A tree with n vertices is called graceful, if its vertices can be labelled with integers 1, 2, ...,n such that the absolute value of the difference of the labels of adjacent vertices are all different. Which of the following trees are graceful?

Description : A tree with n vertices is called graceful, if its vertices can be labelled with integers 1, 2, ...,n such that the absolute value of the difference of the labels of adjacent vertices are all different. Which of the following trees are ... (B) (b) and (c) (C) (a) and (c) (D) (a), (b) and (c)

Last Answer : Answer: D

In the following graph, discovery time stamps and finishing time stamps of Depth First Search (DFS) are shown as x/y where x is discovery time stamp and y is finishing time stamp. Image It shows which of the following depth first forest? (A) {a,b,e} {c,d,f,g,h} (B) {a,b,e} {c,d,h} {f,g} (C) {a,b,e} {f,g} {c,d} {h} (D) {a,b,c,d} {e,f,g} {h}

Description : In the following graph, discovery time stamps and finishing time stamps of Depth First Search (DFS) are shown as x/y where x is discovery time stamp and y is finishing time stamp.  It shows which of the following depth first forest? (A ... {a,b,e} {f,g} {c,d} {h} (D) {a,b,c,d} {e,f,g} {h}

Last Answer : Answer: A

How do I show that a simple graph of size n >= 2 always has at least two vertices of the same degree?

Description : How do I show that a simple graph of size n >= 2 always has at least two vertices of the same degree?

Last Answer : Here's one idea... just use counting:

A directed graph is ………………. if there is a path from each vertex to every other vertex in the digraph. A) Weakly connected B) Strongly Connected C) Tightly Connected D) Linearly Connected

Description : A directed graph is ………………. if there is a path from each vertex to every other vertex in the digraph. A) Weakly connected B) Strongly Connected C) Tightly Connected D) Linearly Connected

Last Answer : B) Strongly Connected

In STL files Euler’s rule for solids can be written as a.No. of faces – No. of edges + No. of vertices = 3 x No. of bodies b.No. of faces – No. of edges + No. of vertices = No. of bodies c.No. of faces – No. of edges + No. of vertices = 2 x No. of bodies d.No. of faces – No. of edges + No. of vertices = 4 x No. of bodies

Description : In STL files Euler’s rule for solids can be written as a.No. of faces †No. of edges + No. of vertices = 3 x No. of bodies b.No. of faces †No. of edges + No. of vertices = No. of bodies c.No. of ... = 2 x No. of bodies d.No. of faces †No. of edges + No. of vertices = 4 x No. of bodies

Last Answer : c.No. of faces – No. of edges + No. of vertices = 2 x No. of bodies

How many edges and vertices are there for an octahedron which is a polyhedron with eight congruent triangular faces?

Description : How many edges and vertices are there for an octahedron which is a polyhedron with eight congruent triangular faces?

Last Answer : Need answer

How many face edges and vertices does a rectangular prism have?

Description : How many face edges and vertices does a rectangular prism have?

Last Answer : A rectangular prism has 6 faces, 12 edges and 8 vertices

What shape has 0 vertices 2 edges 2 faces and 1 curved surface?

Description : What shape has 0 vertices 2 edges 2 faces and 1 curved surface?

Last Answer : Feel Free to Answer

What shape has 2 flat faces 1 curved face 2 edges 0 vertices?

Description : What shape has 2 flat faces 1 curved face 2 edges 0 vertices?

Last Answer : A cylinder would fit the given description

What has 5 faces, 8 edges,5 vertices?

Description : What has 5 faces, 8 edges,5 vertices?

Last Answer : triangular prism

A t-error correcting q-nary linear code must satisfy: Image Where M is the number of code words and X is (1) qn (2) qt (3) q-n (4) q-t

Description : A t-error correcting q-nary linear code must satisfy:  Where M is the number of code words and X is (1) qn (2) qt (3) q-n (4) q-t

Last Answer : (1) qn 

Consider the following statements: (a) Depth - first search is used to traverse a rooted tree. (b) Pre - order, Post-order and Inorder are used to list the vertices of an ordered rooted tree. (c) Huffman's algorithm is used to find an optimal binary tree with given weights. (d) Topological sorting provides a labelling such that the parents have larger labels than their children. Which of the above statements are true ? (A) (a) and (b) (B) (c) and (d) (C) (a) , (b) and (c) (D) (a), (b) , (c) and (d)

Description : Consider the following statements: (a) Depth - first search is used to traverse a rooted tree. (b) Pre - order, Post-order and Inorder are used to list the vertices of an ordered rooted tree. (c) Huffman's algorithm is used to find an optimal ... (d) (C) (a) , (b) and (c) (D) (a), (b) , (c) and (d)

Last Answer : (D) (a), (b) , (c) and (d)

what- A triangle is formed by the intersection of the lines y = 0, y = -3x + 3, and y = 3x + 3.Is the triangle equilateral, isosceles, or scalene Graph the lines on grid paper to find the vertices of the triangle?

Description : what- A triangle is formed by the intersection of the lines y = 0, y = -3x + 3, and y = 3x + 3.Is the triangle equilateral, isosceles, or scalene Graph the lines on grid paper to find the vertices of the triangle?

Last Answer : isosceles

what- A triangle is formed by the intersection of the lines y = 2x + 4, y = -x – 2, and x = 1.Is the triangle equilateral, isosceles, or scalene Graph the lines on grid paper to find the vertices of the triangle?

Description : what- A triangle is formed by the intersection of the lines y = 2x + 4, y = -x – 2, and x = 1.Is the triangle equilateral, isosceles, or scalene Graph the lines on grid paper to find the vertices of the triangle?

Last Answer : scalene

How can i use a graph to find the number of vertices in a octagonal pyramid?

Description : How can i use a graph to find the number of vertices in a octagonal pyramid?

Last Answer : The number of vertices in an octagonal pyramid is 9,irrespective of any graph.

In a fully connected mesh network with n devices, there are ................ physical channels to link all devices. (A) n(n–1)/2 (B) n(n+1)/2 (C) 2n (D) 2n+1

Description : In a fully connected mesh network with n devices, there are ................ physical channels to link all devices. (A) n(n–1)/2 (B) n(n+1)/2 (C) 2n (D) 2n+1

Last Answer : (A) n(n–1)/2

A terminal multiplexer has six 1200 bps terminals and ‘n’ 300 bps terminals connected to it. If the outgoing line is 9600 bps, what is the value of n ? (A) 4 (B) 8 (C) 16 (D) 28

Description : A terminal multiplexer has six 1200 bps terminals and ‘n’ 300 bps terminals connected to it. If the outgoing line is 9600 bps, what is the value of n ? (A) 4 (B) 8 (C) 16 (D) 28

Last Answer : (B) 8

The size of the graph matrix is A. Number of edges in the flow graph B. V Number of nodes in the flow graph C. Number of paths in the flow graph D. Number of independent paths.

Description : The size of the graph matrix is A. Number of edges in the flow graph B. V Number of nodes in the flow graph C. Number of paths in the flow graph D. Number of independent paths.

Last Answer : B. V Number of nodes in the flow graph

An R.C.C. lintel is spanning an opening of 2 m span in a brick wall. The height of the roof is 2.9 m above the floor level and that of the opening is 2.1 m above the floor level. The lintel is to be designed for self weight plus (A) Triangular load of the wall (B) UDL of wall (C) UDL of wall + load from the roof (D) Triangular load + load from the roof

Description : An R.C.C. lintel is spanning an opening of 2 m span in a brick wall. The height of the roof is 2.9 m above the floor level and that of the opening is 2.1 m above the floor level. The lintel is to be ... (B) UDL of wall (C) UDL of wall + load from the roof (D) Triangular load + load from the roof

Last Answer : Answer: Option C

The directory structure used in Unix file system is called (A) Hierarchical directory (B) Tree structured directory (C) Directed acyclic graph (D) Graph structured directory

Description : The directory structure used in Unix file system is called (A) Hierarchical directory (B) Tree structured directory (C) Directed acyclic graph (D) Graph structured directory

Last Answer : (C) Directed acyclic graph

A graph is non-planar if and only if it contains a subgraph homeomorphic to (A) K3,2 or K5 (B) K3,3 and K6 (C) K3,3 or K5 (D) K2,3 and K5

Description : A graph is non-planar if and only if it contains a subgraph homeomorphic to (A) K3,2 or K5 (B) K3,3 and K6 (C) K3,3 or K5 (D) K2,3 and K5

Last Answer : (C) K3,3 or K5 Explanation: Kuratowski’s Theorem: A graph is non-planar if and only if it contains a subgraph that is homeomorphic to either K5 or K3,3.

Consider the Graph shown below : Image This graph is a ............... (A) Complete Graph (B) Bipartite Graph (C) Hamiltonian Graph (D) All of the above

Description : Consider the Graph shown below : This graph is a ............... (A) Complete Graph (B) Bipartite Graph (C) Hamiltonian Graph (D) All of the above

Last Answer : (C) Hamiltonian Graph

The cyclomatic complexity of a flow graph V(G), in terms of predicate nodes is: (A) P + 1 (B) P - 1 (C) P - 2 (D) P + 2 Where P is number of predicate nodes in flow graph V(G).

Description : The cyclomatic complexity of a flow graph V(G), in terms of predicate nodes is: (A) P + 1 (B) P - 1 (C) P - 2 (D) P + 2 Where P is number of predicate nodes in flow graph V(G).

Last Answer : (A) P + 1 

A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph. How many cliques are there in the graph shown below? Image (A) 2 (B) 4 (C) 5 (D) 6

Description : A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph. How many cliques are there in the graph shown below?  (A) 2 (B) 4 (C) 5 (D) 6

Last Answer : (C) 5

In Artificial Intelligence (AI), what is present in the planning graph? (1) Sequence of levels (2) Literals (3) Variables (4) Heuristic estimates

Description : In Artificial Intelligence (AI), what is present in the planning graph? (1) Sequence of levels (2) Literals (3) Variables (4) Heuristic estimates

Last Answer : Sequence of levels

Three resistors each of 2 ohm are connected together in a triangular shape. The resistance between any two vertices will be

Description : Three resistors each of 2 ohm are connected together in a triangular shape. The resistance between any two vertices will be

Last Answer : Three resistors each of 2 ohm are connected together in a triangular shape. The resistance between any two ... 3//4Omega` C. `3Omega` D. `6Omega`

A pushdown automation M = (Q, Σ, Γ, δ, q0, z, F) is set to be deterministic subject to which of the following condition(s), for every q ∈ Q, a ∈ Σ ∪ {λ} and b ∈ Γ (s1) δ(q, a, b) contains at most one element (s2) if δ(q, λ, b) is not empty then δ(q, c, b) must be empty for every c ∈ Σ (A) only s1 (B) only s2 (C) both s1 and s2 (D) neither s1 nor s2

Description : A pushdown automation M = (Q, Σ, Γ, δ, q0, z, F) is set to be deterministic subject to which of the following condition(s), for every q ∈ Q, a ∈ Σ ∪ {λ} and b ∈ Γ (s1) δ(q, a, b) contains at most one ... ) must be empty for every c ∈ Σ (A) only s1 (B) only s2 (C) both s1 and s2 (D) neither s1 nor s2

Last Answer : (C) both s1 and s2