Discussion
Consider a complete graph \(K_{n}\) with \(n\) vertices (\(n \gt 4\)). Note that multiple spanning trees can be constructed over \(K_{n}\). Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two sets.
Which one of the following options gives the lowest possible value for the Jaccard coefficient between any two spanning trees of \(K_{n}\) ?
Answer: C
The lowest possible Jaccard coefficient is 0.
The coefficient is |T1 ∩ T2| / |T1 ∪ T2|, so it is 0 exactly when two spanning trees share no edge. Kn has n(n-1)/2 edges and a spanning tree uses n - 1, so there are more than enough edges for two disjoint trees once n ≥ 4.
A concrete pair for n > 4, with vertices 1 to n: the path 1-2-3-...-n, and the path that visits the odd vertices in increasing order and then the even ones (1-3-5-...-2-4-6-...). Every edge of the second path joins two numbers that differ by at least 2, while every edge of the first joins consecutive numbers, so the two spanning trees share no edge and their Jaccard coefficient is 0.
The other values assume two trees must share an edge: 1/(2n-3) is the value when they share exactly one edge (union 2(n-1) - 1 = 2n - 3), and 1/n and 1/(n-1) are not minimal.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development