Graph-Theory
February 2, 2024GATE 1990
February 2, 2024GATE 1997
|
Question 42
|
Let G be a graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent if |i – j| = 8 or |i – j| = 12. The number of connected components in G is
|
8
|
|
|
4
|
|
|
12
|
|
|
25
|
Question 42 Explanation:
From the description, it is clear that vertices are connected as follows:
1 — 9 — 17 — ……… — 97
2 — 10 — 18 — ……… — 98
3 — 11 — 19 — ……… — 99
4 — 12 — 20 — ……… — 100
5 — 13 — 21 — ……… — 93
6 — 14 — 22 — ……… — 94
7 — 15 — 23 — ……… — 95
8 — 16 — 24 — ……… — 96
We have covered all vertices using 8 vertex sets considering only |i – j| = 8. Using |i – j| = 12 we can see the vertex 1 is connected to 13, 2 to 14, 3 to 15 and 4 to 16. So the top 4 vertex sets are infact connected to the bottom 4 sets, thus reducing the connected components to 4.
1 — 9 — 17 — ……… — 97
2 — 10 — 18 — ……… — 98
3 — 11 — 19 — ……… — 99
4 — 12 — 20 — ……… — 100
5 — 13 — 21 — ……… — 93
6 — 14 — 22 — ……… — 94
7 — 15 — 23 — ……… — 95
8 — 16 — 24 — ……… — 96
We have covered all vertices using 8 vertex sets considering only |i – j| = 8. Using |i – j| = 12 we can see the vertex 1 is connected to 13, 2 to 14, 3 to 15 and 4 to 16. So the top 4 vertex sets are infact connected to the bottom 4 sets, thus reducing the connected components to 4.
Correct Answer: B
Question 42 Explanation:
From the description, it is clear that vertices are connected as follows:
1 — 9 — 17 — ……… — 97
2 — 10 — 18 — ……… — 98
3 — 11 — 19 — ……… — 99
4 — 12 — 20 — ……… — 100
5 — 13 — 21 — ……… — 93
6 — 14 — 22 — ……… — 94
7 — 15 — 23 — ……… — 95
8 — 16 — 24 — ……… — 96
We have covered all vertices using 8 vertex sets considering only |i – j| = 8. Using |i – j| = 12 we can see the vertex 1 is connected to 13, 2 to 14, 3 to 15 and 4 to 16. So the top 4 vertex sets are infact connected to the bottom 4 sets, thus reducing the connected components to 4.
1 — 9 — 17 — ……… — 97
2 — 10 — 18 — ……… — 98
3 — 11 — 19 — ……… — 99
4 — 12 — 20 — ……… — 100
5 — 13 — 21 — ……… — 93
6 — 14 — 22 — ……… — 94
7 — 15 — 23 — ……… — 95
8 — 16 — 24 — ……… — 96
We have covered all vertices using 8 vertex sets considering only |i – j| = 8. Using |i – j| = 12 we can see the vertex 1 is connected to 13, 2 to 14, 3 to 15 and 4 to 16. So the top 4 vertex sets are infact connected to the bottom 4 sets, thus reducing the connected components to 4.