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)

1 Answer

Answer :

(D) (a), (b) and (c)

Related questions

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

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

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

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

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

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

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 

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.

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

Description : With respect to a loop in the transportation table, which one of the following is not correct? (1) Every loop has an odd no. of cells and at least 5. (2) Closed loops may or may not b square in ... starting cell, must be occupied cells. (4) Every loop has an even no. of cells and at least four.

Last Answer : Every loop has an odd no. of cells and at least 5.

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

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

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

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

Description : Loop unrolling is a code optimization technique: (A) that avoids tests at every iteration of the loop (B) that improves performance by decreasing the number of instructions in a basic block. ... loops with outer loops (D) that reorders operations to allow multiple computations to happen in parallel.

Last Answer : (A) that avoids tests at every iteration of the loop

Description : The grammar with production rules S → aSb |SS|λ generates language L given by: (A) L = {w∈{a, b}* | na(w) = nb(w) and na(v) ≥ nb(v) where v is any prefix of w} (B) L = {w∈{a, b}* | na(w) = nb(w) and na(v ... (D) L = {w∈{a, b}* | na(w) ≠ nb(w) and na(v) ≤ nb(v) where v is any prefix of w}

Last Answer : (A) L = {w∈{a, b}* | na(w) = nb(w) and na(v) ≥ nb(v) where v is any prefix of w} 

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

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

Description : Consider the table Student(stuid, name, course, marks). Which one of the following two queries is correct to find the highest marks student in course 5? Q.1. Select S.stuid From student S Where not exists (select * from student ... ) Q.1 (B) Q.2 (C) Both Q.1 and Q.2 (D) Neither Q.1 nor Q.2

Last Answer : (B) Q.2 Explanation: First query gives stuid of students whose marks are greater than all students taking course 5. Second query gives stuid of students whose marks are greater than any student taking ... comparison is between maximum of marks by any student in course 5. So the answer is option D.

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

Description : A set of processors P1, P2, ......, Pk can execute in parallel if Bernstein's conditions are satisfied on a pair wise basis; that is  P1 || P2 || P3 || ..... || Pk if and only if: (A) Pi || Pj for all i ≠ j (B) Pi || Pj for all i = j+1 (C) Pi || Pj for all i ≤ j (D) Pi || Pj for all i ≥ j

Last Answer : (A) Pi || Pj for all i ≠ j Explanation: Bernstein's Condition: 1. If process Pi writes to a memory cell Mi, then no process Pj can read the cell Mi. 2. If process Pi read from a memory ... Mi. 3. If process Pi writes to a memory cell Mi, then no process Pj can write to the cell Mi.

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

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

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 

Description : Compute the charge enclosed by a cube of 2m each edge centered at the origin and with the edges parallel to the axes. Given D = 10y 3 /3 j. a) 20 b) 70/3 c) 80/3 d) 30

Last Answer : c) 80/3

Description : The figure shows the front view of a convex lens, which originally had only one edge. Five holes of different shapes, namely triangle, square, pentagon, hexagon and circle, were drilled through it at points P ... . What is the total number of edges in the lens after the holes were drilled? 

Last Answer : 57

Description : In .............., the bodies of the two loops are merged together to form a single loop provided that they do not make any references to each other. (A) Loop unrolling (B) Strength reduction (C) Loop concatenation (D) Loop jamming

Last Answer : (D) Loop jamming

Description : When load is applied on concrete pavement (A) Away from edges, the maximum bending moment is negative (B) Away from edges, the maximum bending moment cause compression (C) On the edges, the maximum stress is parallel to the edge of the slab (D) None of these

Last Answer : Answer: Option C

Description : If the no of faces and vertex in a solid are 7 and 10 respectively the no of edges are?

Last Answer : A prism with an n-sided base will have 2n vertices, n + 2 faces,and 3n edges.15 edges

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 

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

Description : Consider f(N) = g(N) + h(N) Where function g is a measure of the cost of getting from the start node to the current node N and h is an estimate of additional cost of getting from the current ... ? (A) A* algorithm (B) AO* algorithm (C) Greedy best first search algorithm (D) Iterative A* algorithm

Last Answer : (C) Greedy best first search algorithm

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

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

Description : Consider the fractional knapsack instance n = 4, (p1, p2, p3, p4) = (10, 10, 12, 18), (w1, w2, w3, w4) = (2, 4, 6, 9) and M = 15. The maximum profit is given by (Assume p and w denotes profit and weight of objects respectively) (A) 40 (B) 38 (C) 32 (D) 30

Last Answer : (B) 38

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

Description : In a graph, the number of independent loops is 6 and the number of independent cut sets is 5, The total number of branches in the graph is A) 9 B) 12 C) 10 D) 11

Last Answer : In a graph, the number of independent loops is 6 and the number of independent cut sets is 5, The total number of branches in the graph is 11

Description : Consider the following statements S1 and S2 : S1 : A hard handover is one in which the channel in the source cell is retained and used for a while in parallel with the channel in the target cell. S2 : A soft handover ... and S2 is true. (C) Both S1 and S2 are true. (D) Both S1 and S2 are not true.

Last Answer : (D) Both S1 and S2 are not true.

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

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

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

Last Answer : 7

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

Last Answer : Need answer

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

Last Answer : Need answer

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

Last Answer : Need answer

Description : Consider the following database table having A, B, C and D as its four attributes and four possible candidate keys (I, II, III and IV) for this table: I: {B} II: {B, C} III: {A, D} IV: {C, D} If ... the database table? (A) I and III only (B) III and IV only (C) II only (D) I only

Last Answer : (C) II only

Description : Consider the following Entity-Relationship (E-R) diagram and three possible relationship sets (I, II and III) for this E-R diagram: If different symbols stand for different values (e.g., t1 is definitely not equal to t2 ... diagram ? (A) I only (B) I and II only (C) II only (D) I, II and III

Last Answer : (A) I only

Description : A resistor of value R/2 is connected in parallel with a resistor of value R/3. The voltage drop across the parallel combination is V. The total current supplied by the voltage source is: w) 2 V/R (read: 2 V over R) x) 3 V/R (read: 3 V over R) y) 4 V/R (read: 4 V over R) z) 5 V/R (read: 5 V over R)

Last Answer : ANSWER: Z -- 5 V/R