JNU CS M.Phil 2019 Shift-1
October 24, 2023DSSSB PGT 2018 Male
October 24, 2023UGC NET CS 2008-june-Paper-2
|
Question 1
|
Which of the following does not define a tree ?
|
A tree is a connected acyclic graph.
|
|
|
A tree is a connected graph with n-1 edges where ‘n’ is the number of vertices in the graph.
|
|
|
A tree is an acyclic graph with n-1 edges where ‘n’ is the number of vertices in the graph.
|
|
|
A tree is a graph with no cycles.
|
Question 1 Explanation:
→ An undirected graph is connected when there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices. A graph that is not connected is disconnected. An undirected graph G is said to be disconnected if there exist two nodes in G such that no path in G has those nodes as endpoints.
→ An acyclic graph is a graph having no graph cycles. Acyclic graphs are bipartite.
→ A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).
→ All first 3 options are correctly defining tree without any loss of information, whereas “A tree is a graph with no cycles.” is not always correct as it can be bipartite.
Hence D does not define a tree.
→ An acyclic graph is a graph having no graph cycles. Acyclic graphs are bipartite.
→ A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).
→ All first 3 options are correctly defining tree without any loss of information, whereas “A tree is a graph with no cycles.” is not always correct as it can be bipartite.
Hence D does not define a tree.
Correct Answer: D
Question 1 Explanation:
→ An undirected graph is connected when there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices. A graph that is not connected is disconnected. An undirected graph G is said to be disconnected if there exist two nodes in G such that no path in G has those nodes as endpoints.
→ An acyclic graph is a graph having no graph cycles. Acyclic graphs are bipartite.
→ A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).
→ All first 3 options are correctly defining tree without any loss of information, whereas “A tree is a graph with no cycles.” is not always correct as it can be bipartite.
Hence D does not define a tree.
→ An acyclic graph is a graph having no graph cycles. Acyclic graphs are bipartite.
→ A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).
→ All first 3 options are correctly defining tree without any loss of information, whereas “A tree is a graph with no cycles.” is not always correct as it can be bipartite.
Hence D does not define a tree.
Subscribe
Login
0 Comments