Digital-Logic-Design
January 23, 2024APPSC-2016-DL-CS
January 23, 2024APPSC-2016-DL-CS
|
Question 1
|
The minimum number of edges of a graph containing n vertices and c connected components is
|
n-c
|
|
|
c
|
|
|
c(n-1)
|
|
|
n/c
|
Question 1 Explanation:
We have to find a minimum no. of edges. So for c connected components let’s assume c-1 independent vertices which are also c-1 components and remaining 1 component will contain n-(c-1) vertices or n-c+1 vertices. So for minimum no. of edges will be no. of vertices in the single component (which contains n-c+1 vertices) -1, which is
(n-c+1)-1 = n-c
(n-c+1)-1 = n-c
Correct Answer: A
Question 1 Explanation:
We have to find a minimum no. of edges. So for c connected components let’s assume c-1 independent vertices which are also c-1 components and remaining 1 component will contain n-(c-1) vertices or n-c+1 vertices. So for minimum no. of edges will be no. of vertices in the single component (which contains n-c+1 vertices) -1, which is
(n-c+1)-1 = n-c
(n-c+1)-1 = n-c