Question:
In an undirected connected graph with \(n\) vertices and \(m\) edges, what is the number of edges in any Spanning Tree of the graph?
\(n\) शीर्षों और \(m\) किनारों वाले एक अप्रत्यक्ष जुड़े हुए ग्राफ में, ग्राफ के किसी भी स्पैनिंग ट्री (Spanning Tree) में किनारों की संख्या क्या होगी?
Options:
- \(n – 1\)
- \(n\)
- \(m – 1\)
- \(n + 1\)
- \(n – 1\)
- \(n\)
- \(m – 1\)
- \(n + 1\)
Correct Answer: a)
Explanation:
By graph theory definition, a tree spanning \(n\) vertices is an acyclic connected subgraph, which strictly contains exactly \(n – 1\) edges.
ग्राफ सिद्धांत के अनुसार \(n\) शीर्षों वाले किसी भी स्पैनिंग ट्री में चक्र-मुक्त जुड़े रहने के लिए ठीक \(n – 1\) किनारे (edges) होते हैं।