adplus-dvertising
frame-decoration

Question

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

Answer: (d).maximal, minimal

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. A ___________ complete subgraph and a __________ subset of vertices of a graph G = (V, E) are a clique and a vertex cover respectively.

Similar Questions

Discover Related MCQs

Q. 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?

Q. Consider a set A {1, 2, 3,……… 1000}. How many members of A shall be divisible by 3 or by 5 or by both 3 and 5?

Q. A computer program selects an integer in the set {k : 1 < k < 10,00,000} at random and prints out the result. This process is repeated 1 million times. What is the probability that the value k = 1 appears in the printout at least once?

Q. Which one of the following is used to compute cyclomatic complexity?

Q. If we define the functions f, g and h that map R into R by :

f(x) = x4, g(x) = √x2 + 1, h(x) = x2 + 72,  then the value of the composite functions ho(gof) and (hog)of are given as

Q. Dijkstra algorithm, which solves the single-source shortest-paths problem, is a_______________, and the Floyd-Warshall algorithm, which finds shortest paths between all pairs of vertices, is a _____________.

Q. Equivalent logical expression for the Well Formed Formula (WFF), ~(∀ x)F[x] is

Q. An A * algorithm is a heuristic search technique which

Q. The resolvent of the set of clauses (A v B, ~ A v D, C v ~B) is

Q. How many strings of 5 digits have the property that the sum of their digits is 7 ?

Q. Consider an experiment of tossing two fair dice, one black and one red. What is the probability that the number on the black die divides the number on red die ?

Q. In how many ways can 15 indistinguishable fishes be placed into 5 different ponds, so that each pond contains atleast one fish ?

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

Q. An all-pairs shortest-paths problem is efficiently solved using :

Q. The travelling salesman problem can be solved in :

Q. Let f (n) and g(n) be asymptotically non-negative functions. Which of the following is correct?

Q. Given the following equalities :

E1 : nK+∈ + nK lg n = Ф(nK+∈) for all fixed K and ∈, K ≥ 0 and ∈ > 0.

E2 : n32n + 6n23n = O(n32n)

Which of the following is true ?

Q. How many different equivalence relations with exactly three different equivalence classes are there on a set with five elements

Q. Suppose that R1 and R2 are reflexive relations on a set A.
Which of the following statements is correct ?

Q. There are three cards in a box. Both sides of one card are black, both sides of one card are red, and the third card has one black side and one red side. we pick a card at random and observe only one side. What is the probability that the opposite side is the same colour as the one side we observed ?