In the context of a Hamiltonian problem, which of the following are correct? A. Hamiltonian cycle problem is NP-Complete B. If G is an undirected Bipartite graph with an odd number of vertices, then G is Hamiltonian. C. Hamiltonian path problem cannot be solved in polynomial time on directed acyclic graph D. If G is a connected undirected graph with at least three vertices and G3 is the graph obtained by connecting all pairs of vertices that are connected by a path in G of length at most 3. E. If any NP complete problem is polynomial time solvable the P=NP. Choose the most appropriate answer from the options given below:
A, D, E only
A Hamiltonian cycle visits every vertex exactly once and returns to the start; a Hamiltonian path visits every vertex exactly once. Deciding whether a general graph has either is one of Karp's classic NP-complete problems.
A — Correct. The Hamiltonian cycle problem is in NP (a cycle is a polynomially checkable certificate) and is NP-hard, so it is NP-complete.
B — Incorrect. A Hamiltonian cycle in a bipartite graph alternates between the two parts, so it has even length and needs equal part sizes; with an odd number of vertices a bipartite graph can never be Hamiltonian.
C — Incorrect. In a DAG a Hamiltonian path exists exactly when consecutive vertices of a topological order are joined by edges, which is checked in \(O(V+E)\) time, so it is polynomial.
D — Correct as the intended theorem: for every connected graph G with at least three vertices, its cube \(G^{3}\) (vertices joined when their distance in G is at most 3) is Hamiltonian.
E — Correct. Every NP problem reduces in polynomial time to any NP-complete problem, so a polynomial algorithm for one NP-complete problem solves all of NP in polynomial time, giving P = NP.
Any combination containing B or C includes a false statement, so only the set of A, D and E fits.
A, D, E only option is correct.
Similar Questions
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 ?
Codes :
Consider the graph given below :
The two distinct sets of vertices, which make the graph bipartite are :
Which of the following statement(s) is/are false ?
(a) A connected multigraph has an Euler Circuit if and only if each of its vertices has even degree.
(b) A connected multigraph has an Euler Path but not an Euler Circuit if and only if it has exactly two vertices of odd degree.
(c) A complete graph \((K_{n})\) has a Hamilton Circuit whenever \(n \geq 3\).
(d) A cycle over six vertices \((C_{6})\) is not a bipartite graph but a complete graph over 3 vertices is bipartite.
Codes :
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) \geq n/2\) for each vertex of G
(b) \(|E(G)| \geq 1/2\ (n-1)(n-2)+2\) edges
(c) deg \((v)\) + deg \((w) \geq n\) for every \(v\) and \(w\) not connected by an edge
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 ?
Consider a complete bipartite graph \(k_{m,n}\). For which values of m and n does this, complete graph have a Hamilton circuit
Consider the graph given below as :
Which one of the following graph is isomorphic to the above graph ?
Arrange the following graph on the basis of number of edges in increasing order [for n = 4]
A. Kn (Complete Graph)
B. Cn (Cycle graph)
C. Wn (Wheel graph)
D. Kn,n (Complete Bipartite Graphs)
E. Qn (n-cubes graph)
Choose the correct answer from the options given below:
A graph G with number of vertices greater and equal than three i.e. (n ≥ 3) is a Hamiltonian graph, if the degree of each vertex is greater and equal to . . . .
Let ‘G’ be a simple, undirected graph with n (n>10) vertices and ‘k’ connected components. What is the minimum possible number of edges of ‘G’?
Important Questions from Graph Theory
A principal node is a
Which of the following statement(s) is/are correct regarding about the undirected graph?
I. Number of odd degree vertices is even.
II. Sum of degrees of all vertices is even.
Let $G(V, E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u, v)$, $u, v \in V$ such that $u \neq v$, be 30. Let T be any breadth-first-search tree of G. Which ONE of the given options is CORRECT for every such graph G?
- Maintaining a graph in memory by means of its adjacency matrix is known as
Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on plane is equal to_________.
