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

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
by

1 Answer

Answer :

(C) If (u, v) ∈ E then u ∈ V1 or v ∈ V1
by

Related questions

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 

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

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

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)

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

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

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

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

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 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

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

Description : 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

Last Answer : (C) M-N+C

For every context free grammar (G) there exists an algorithm that passes any w ∈ L(G) in number of steps proportional to (A) ln|w| (B) |w| (C) |w|2 (D) |w|3

Description : For every context free grammar (G) there exists an algorithm that passes any w ∈ L(G) in number of steps proportional to (A) ln|w| (B) |w| (C) |w|2 (D) |w|3

Last Answer : (D) |w|3

Which one is correct w.r.t. RDBMS? (1) primary key ⊆ super key ⊆ candidate key (2) primary key ⊆ candidate key ⊆ super key (3) super key ⊆ candidate key ⊆ primary key (4) super key ⊆ primary key ⊆ candidate key

Description : Which one is correct w.r.t. RDBMS? (1) primary key ⊆ super key ⊆ candidate key (2) primary key ⊆ candidate key ⊆ super key (3) super key ⊆ candidate key ⊆ primary key (4) super key ⊆ primary key ⊆ candidate key

Last Answer : Answer: 2

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

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 …………… is an acyclic digraph, which has only one node with indegree 0, and other nodes have indegree 1. A) Directed tree B) Undirected tree C) Dis-joint tree D) Direction oriented tree

Description : A …………… is an acyclic digraph, which has only one node with indegree 0, and other nodes have indegree 1. A) Directed tree B) Undirected tree C) Dis-joint tree D) Direction oriented tree

Last Answer : A) Directed tree

A fuzzy set A on R is ................. iff A(λx1 + (1 – λ)x2) ≥ min [A(x1), A(x2)] for all x1, x2 ∈ R and all λ ∈ [0, 1], where min denotes the minimum operator. (A) Support (B) α-cut (C) Convex (D) Concave

Description : A fuzzy set A on R is ................. iff A(λx1 + (1 – λ)x2) ≥ min [A(x1), A(x2)] for all x1, x2 ∈ R and all λ ∈ [0, 1], where min denotes the minimum operator. (A) Support (B) α-cut (C) Convex (D) Concave 

Last Answer : (C) Convex 

Which of the following is FALSE ? (A) The grammar S ⟶ aSb|bSa|SS|∈, where S is the only non-terminal symbol and ∈ is the null string, is ambiguous. (B) SLR is powerful than LALR. (C) An LL(1) parser is a top-down parser. (D) YACC tool is an LALR(1) parser generator.

Description : Which of the following is FALSE ? (A) The grammar S ⟶ aSb|bSa|SS|∈, where S is the only non-terminal symbol and ∈ is the null string, is ambiguous. (B) SLR is powerful than LALR. (C) An LL(1) parser is a top-down parser. (D) YACC tool is an LALR(1) parser generator.

Last Answer : (B) SLR is powerful than LALR.

The number of strings of length 4 that are generated by the regular expression (0|∈) 1+2* (3|∈), where | is an alternation character, {+, *} are quantification characters, and ∈ is the null string, is: (A) 08 (B) 10 (C) 11 (D) 12

Description : The number of strings of length 4 that are generated by the regular expression (0|∈) 1+2* (3|∈), where | is an alternation character, {+, *} are quantification characters, and ∈ is the null string, is: (A) 08 (B) 10 (C) 11 (D) 12

Last Answer : (D) 12

If A(3, 5), B(– 5, – 4), C(7, 10) are the vertices of a parallelogram taken in order, then the co-ordinates of the fourth vertex are: -Maths 9th

Description : If A(3, 5), B(– 5, – 4), C(7, 10) are the vertices of a parallelogram taken in order, then the co-ordinates of the fourth vertex are: -Maths 9th

Last Answer : (c) RhombusCo-ordinates of P are \(\bigg(rac{-1-1}{2},rac{-1+4}{2}\bigg)\)i.e, \(\big(-1,rac{3}{2}\big)\)Co-ordinates of Q are \(\bigg(rac{-1+5}{2},rac{4+4}{2}\bigg)\)i.e, (2, 4)Co-ordinates of R ... \sqrt{(2-2)^2+(4+1)^2}\) = \(\sqrt{25}\) = 5⇒ PR ≠ SQ ⇒ Diagonals are not equal ⇒ PQRS is a rhombus.

If A (-2, 4), B (0, 0) and C (4, 2) are the vertices of triangle ABC, then find the length of the median through the vertex A. -Maths 9th

Description : If A (-2, 4), B (0, 0) and C (4, 2) are the vertices of triangle ABC, then find the length of the median through the vertex A. -Maths 9th

Last Answer : D=slid ht of BC D≅(20+4​,20+2​) =(2,1) ∴ Length of median = Light of AD =root(−2−2)2+(4−1)2​=root42+32​=5 hope it helps thank u

Graph used to represent semantic network is _____________ a) Undirected graph b) Directed graph c) Directed Acyclic graph (DAG) d) Directed complete graph

Description : Graph used to represent semantic network is _____________ a) Undirected graph b) Directed graph c) Directed Acyclic graph (DAG) d) Directed complete graph

Last Answer : b) Directed graph

If D1, D2,…. Dn are domains in a relational model, then the relation is a table, which is a subset of (A) D1+D2+…. +Dn (B) D1x D2x… xDn (C) D1U D2U….UDn (D) D1- D2-….-Dn

Description : If D1, D2,…. Dn are domains in a relational model, then the relation is a table, which is a subset of (A) D1+D2+…. +Dn (B) D1x D2x… xDn (C) D1U D2U….UDn (D) D1- D2-….-Dn

Last Answer : (B) D1x D2x… xDn

acode is simply a subset of the vertices ofthe a. n bit b. ncube c. n single d. n double

Description : acode is simply a subset of the vertices ofthe a. n bit b. ncube c. n single d. n double

Last Answer : b. ncube

Consider a system with seven processes A through G and six resources R through W. Resource ownership is as follows: process A holds R and wants T process B holds nothing but wants T process C holds nothing but wants S process D holds U and wants S & T process E holds T and wants V process F holds W and wants S process G holds V and wants U Is the system deadlocked ? If yes, ............. processes are deadlocked. (A) No (B) Yes, A, B, C (C) Yes, D, E, G (D) Yes, A, B, F

Description : Consider a system with seven processes A through G and six resources R through W. Resource ownership is as follows: process A holds R and wants T process B holds nothing but wants T process C holds nothing but wants S process D holds U ... No (B) Yes, A, B, C (C) Yes, D, E, G (D) Yes, A, B, F

Last Answer : (C) Yes, D, E, G

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)

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

If we convert ∃u ∀v ∀x ∃y (P(f(u),v, x, y) → Q(u,v,y)) to ∀v ∀x (P(f(a),v, x, g(v,x)) → Q(a,v,g(v,x))) This process is known as (A) Simplification (B) Unification (C) Skolemization (D) Resolution

Description : If we convert ∃u ∀v ∀x ∃y (P(f(u),v, x, y) → Q(u,v,y)) to ∀v ∀x (P(f(a),v, x, g(v,x)) → Q(a,v,g(v,x))) This process is known as (A) Simplification (B) Unification (C) Skolemization (D) Resolution

Last Answer : (C) Skolemization

Write the coordinates of the vertices of a rectangle whose lenght and breadth are 7 and 4 units respectively,one vertex atthe the origin,the longer side lies on the x-axis and one of the vertices lies in the third quadrant. -Maths 9th

Description : Write the coordinates of the vertices of a rectangle whose lenght and breadth are 7 and 4 units respectively,one vertex atthe the origin,the longer side lies on the x-axis and one of the vertices lies in the third quadrant. -Maths 9th

Last Answer : Solution :-

Write the coordinates of the vertices of a rectangle whose length and breadth are 6 and 3 units respectively, one vertex at the origin, the longer side lies on the y-axis and one of the vertices lies in the second quadrant. -Maths 9th

Description : Write the coordinates of the vertices of a rectangle whose length and breadth are 6 and 3 units respectively, one vertex at the origin, the longer side lies on the y-axis and one of the vertices lies in the second quadrant. -Maths 9th

Last Answer : Solution :-

The area of a triangle is 5. Two of its vertices are (2, 1) and (3, –2). The third vertex is (x, y) -Maths 9th

Description : The area of a triangle is 5. Two of its vertices are (2, 1) and (3, –2). The third vertex is (x, y) -Maths 9th

Last Answer : Let A(x1, y1) = (3, 4), B(x2, y2) ≡ (0, 5), C(x3, y3) ≡ (2, -1)and D(x4, y4) ≡ (3, -2) be the vertices of quadrilateral ABCD.Area of quad. ABCD = \(rac{1}{2}\) |{(x1 y2 - x2 y1) + (x2y3 - x3y2) + (x3y4 - x4y3) ... ) + (12 + 6)}|= \(rac{1}{2}\) |{15 - 11 + 0 + 18}| = \(rac{1}{2}\)x 22 = 11 sq. units.

The two vertices of a triangle are (2, –1), (3, 2) and the third vertex lies on the line x + y = 5. The area of the triangle is 4 units. -Maths 9th

Description : The two vertices of a triangle are (2, –1), (3, 2) and the third vertex lies on the line x + y = 5. The area of the triangle is 4 units. -Maths 9th

Last Answer : (c) (5, 0) or (1, 4) Let the third vertex of the triangle be P(a, b). Since it lies on the line x + y = 5, a + b = 5 ...(i) Also, given area of triangle formed by the points (2, -1), (3, 2) and (a, b) = 4 ... b) - (-3a + b) = 5 + 15⇒ 4a = 20 ⇒ a = 5 ⇒ b = 0. ∴ The points are (1, 4) and (5, 0).

The property of binary tree is A) The first subset is called left subtree B) The second subtree is called right subtree C) The root cannot contain NULL D) The right subtree can be empty

Description : The property of binary tree is A) The first subset is called left subtree B) The second subtree is called right subtree C) The root cannot contain NULL D) The right subtree can be empty

Last Answer : D) The right subtree can be empty

Select operator is not a unary operator. ii) Project operator chooses subset of attributes or columns of a relation. A) i-True, ii-False B) i-True, ii-True C) i-False, ii-True D) i-False, ii-False

Description : Select operator is not a unary operator. ii) Project operator chooses subset of attributes or columns of a relation. A) i-True, ii-False B) i-True, ii-True C) i-False, ii-True D) i-False, ii-False

Last Answer : C) i-False, ii-True

Reflexivity property says that X Y is true if Y is …………………. A) Subset of X B) Null set of X C) Super set of Y D) Subset of Y

Description : Reflexivity property says that X Y is true if Y is …………………. A) Subset of X B) Null set of X C) Super set of Y D) Subset of Y

Last Answer : A) Subset of X

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.

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

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

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

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

In the …………….. traversal we process all of a vertex’s descendents before we move to an adjacent vertex. A) Depth First B) Breadth First C) With First D) Depth Limited

Description : In the …………….. traversal we process all of a vertex’s descendents before we move to an adjacent vertex. A) Depth First B) Breadth First C) With First D) Depth Limited

Last Answer : A) Depth First

A triangulation of a polygon is a set of T chords that divide the polygon into disjoint triangles. Every triangulation of n-vertex convex polygon has ................ chords and divides the polygon into ............... triangles. (A) n-2, n-1 (B) n-3, n-2 (C) n-1, n (D) n-2, n-2

Description : A triangulation of a polygon is a set of T chords that divide the polygon into disjoint triangles. Every triangulation of n-vertex convex polygon has ................ chords and divides the polygon into ............... triangles. (A) n-2, n-1 (B) n-3, n-2 (C) n-1, n (D) n-2, n-2

Last Answer : (B) n-3, n-2

Professional independence is a subset of which one of the following pairs of fundamental principles? a) Integrity and Due Diligence

Description : Professional independence is a subset of which one of the following pairs of fundamental principles? a) Integrity and Due Diligenceb) Integrity and Objectivity c) Integrity and Professional Competence d) Objectivity and Professional behaviour

Last Answer : b) Integrity and Objectivity

In case of a double line river, contours are (A) Stopped at the banks of the river (B) Stopped at the edge of the river (C) Drawn across the water (D) Drawn by parabolic curves having their vertex at the centre of the water

Description : In case of a double line river, contours are (A) Stopped at the banks of the river (B) Stopped at the edge of the river (C) Drawn across the water (D) Drawn by parabolic curves having their vertex at the centre of the water

Last Answer : (B) Stopped at the edge of the river

Which equation represents a graph with a vertex at (1,-6?

Description : Which equation represents a graph with a vertex at (1,-6?

Last Answer : 7

What are the vertex and x-intercepts of the graph of the function below y x2 - 2x - 24?

Description : What are the vertex and x-intercepts of the graph of the function below y x2 - 2x - 24?

Last Answer : Need answer