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

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
by

1 Answer

Answer :

(D) maximal, minimal 
by

Related questions

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

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

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)

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

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

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

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

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

Given the following statements : S1 : The subgraph-isomorphism problem takes two graphs G1 and G2 and asks whether G1 is a subgraph of G2. S2 : The set-partition problem takes as input a set S of numbers and asks whether the numbers can be partitioned into two sets A Image Which of the following is true ? (A) S1 is NP problem and S2 is P problem. (B) S1 is NP problem and S2 is NP problem. (C) S1 is P problem and S2 is P problem. (D) S1 is P problem and S2 is NP problem.

Description : Given the following statements :  S1 : The subgraph-isomorphism problem takes two graphs G1 and G2 and asks whether G1 is a subgraph of G2.  S2 : The set-partition problem takes as input a set S of numbers and ... S1 is P problem and S2 is P problem. (D) S1 is P problem and S2 is NP problem.

Last Answer : (B) S1 is NP problem and S2 is NP problem.

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 

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

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.

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.

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

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

In ΔABC and ΔDEF, AB = DE, AB || DE, BC = EF and BC || EF. Vertices A, B and C are joined to vertices D, E and F respectively (see Fig. 8.22). Show that (i) quadrilateral ABED is a parallelogram (ii) quadrilateral BEFC is a parallelogram (iii) AD || CF and AD = CF (iv) quadrilateral ACFD is a parallelogram (v) AC = DF (vi) ΔABC ≅ ΔDEF. -Maths 9th

Description : In ΔABC and ΔDEF, AB = DE, AB || DE, BC = EF and BC || EF. Vertices A, B and C are joined to vertices D, E and F respectively (see Fig. 8.22). Show that (i) quadrilateral ABED is a parallelogram ( ... CF and AD = CF (iv) quadrilateral ACFD is a parallelogram (v) AC = DF (vi) ΔABC ≅ ΔDEF. -Maths 9th

Last Answer : . Solution: (i) AB = DE and AB || DE (Given) Two opposite sides of a quadrilateral are equal and parallel to each other. Thus, quadrilateral ABED is a parallelogram (ii) Again BC = EF and BC || EF ... (Given) BC = EF (Given) AC = DF (Opposite sides of a parallelogram) , ΔABC ≅ ΔDEF [SSS congruency]

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

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

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

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

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

The number of function points of a proposed system is calculated as 500. Suppose that the system is planned to be developed in Java and the LOC/FP ratio of Java is 50. Estimate the effort (E) required to complete the project using the effort formula of basic COCOMO given below: E = a(KLOC)b Assume that the values of a and b are 2.5 and 1.0 respectively. (A) 25 person months (B) 75 person months (C) 62.5 person months (D) 72.5 person months

Description : The number of function points of a proposed system is calculated as 500. Suppose that the system is planned to be developed in Java and the LOC/FP ratio of Java is 50. Estimate the effort (E) required to ... ) 25 person months (B) 75 person months (C) 62.5 person months (D) 72.5 person months

Last Answer : (C) 62.5 person months 

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

State true or false i) A candidate key is a minimal super key. ii) A candidate key can also refer to as surrogate key. A) i-true, ii-false B) i-false, ii-true C) i-true, ii-true D) i-false, ii-false

Description : State true or false i) A candidate key is a minimal super key. ii) A candidate key can also refer to as surrogate key. A) i-true, ii-false B) i-false, ii-true C) i-true, ii-true D) i-false, ii-false

Last Answer : C) i-true, ii-true

Minimal deterministic finite automaton for the language L={ 0n | n≥0, n≠4 } will have: (A) 1 final state among 5 states (B) 4 final states among 5 states (C) 1 final state among 6 states (D) 5 final states among 6 states

Description : Minimal deterministic finite automaton for the language L={ 0n | n≥0, n≠4 } will have: (A) 1 final state among 5 states (B) 4 final states among 5 states (C) 1 final state among 6 states (D) 5 final states among 6 states

Last Answer : (D) 5 final states among 6 states

Given the symbols A, B, C, D, E, F, G and H with the probabilities 1/30, 1/30, 1/30, 2/30, 3/30, 5/30, 5/30 and 12/30 respectively. The average Huffman code size in bits per symbol is: (A) 67/30 (B) 70/34 (C) 76/30 (D) 78/30

Description : Given the symbols A, B, C, D, E, F, G and H with the probabilities 1/30, 1/30, 1/30, 2/30, 3/30, 5/30, 5/30 and 12/30 respectively. The average Huffman code size in bits per symbol is: (A) 67/30 (B) 70/34 (C) 76/30 (D) 78/30

Last Answer : (C) 76/30

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

What is the vertex of the graph of the function below y x2 plus 6x plus 5?

Description : What is the vertex of the graph of the function below y x2 plus 6x plus 5?

Last Answer : Need answer

What is the vertex of the graph of the function below y x2 - 8x plus 12?

Description : What is the vertex of the graph of the function below y x2 - 8x plus 12?

Last Answer : Need answer

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

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

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:

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