किमान व्याप्तीचे झाड ग्राफला अशा प्रकारे अनुकूलित करते जे कडांच्या सर्व वजनाचे बेरीज कमी करते
प्रदान केलेल्या मजकूराच्या आधारे, किमान स्पॅनिंग ट्री काय ऑप्टिमाइझ करते?
Context:किमान व्याप्तीचे झाड (MST) किंवा किमान वजन व्याप्तीचे झाड हे जोडलेल्या, किनार-वजन असलेले अप्रत्यक्ष आलेखातील कडांचे उपसंच आहे जे सर्व वर्तुळे एकत्र जोडते, कोणत्याही चक्राशिवाय आणि किमान शक्य एकूण किनार वजन. म्हणजेच, हे एक व्याप्तीचे झाड आहे ज्याचे किनार्यावरील वजनाचे बेरीज शक्य तितके लहान आहे. अधिक सामान्यपणे, कोणत्याही किनार-वजन असलेले अप्रत्यक्ष आलेख (अपरिहार्यपणे जोडलेले नाही) मध्ये किमान व्याप्ती वन आहे, जे त्याच्या जोडलेल्या घटकांसाठी किमान व्याप्ती वृक्षांचे संघ आहे.  किमान स्पॅनिंग झाडांसाठी अनेक उपयोग आहेत. एक उदाहरण म्हणजे एक दूरसंचार कंपनी नवीन परिसरात केबल लावण्याचा प्रयत्न करत आहे. जर केबलला फक्त काही मार्गांवर (उदाहरणार्थ रस्ते) पुरण्यासाठी प्रतिबंधित केले गेले असेल तर त्या मार्गांनी जोडलेले बिंदू (उदाहरणार्थ घरे) असलेला आलेख असेल. काही मार्ग अधिक महाग असू शकतात, कारण ते जास्त लांब आहेत, किंवा केबलला खोलवर पुरण्याची आवश्यकता आहे; या मार्गांचे प्रतिनिधित्व मोठ्या वजनाच्या कडांनी केले जाईल. चलन हे किनार्याचे वजन <unk> साठी स्वीकार्य एकक आहे त्रिकोणाच्या असमानतेसारख्या सामान्य भूमितीच्या नियमांचे पालन करण्यासाठी किनार्यांच्या लांबीची आवश्यकता नाही. त्या ग्राफसाठी एक स्पॅनिंग ट्री त्या मार्गांचा उपसंच असेल ज्यात कोणतेही चक्र नाही परंतु तरीही प्रत्येक घराला जोडते; तेथे अनेक स्पॅनिंग झाडे असू शकतात. एक किमान स्पॅनिंग झाड सर्वात कमी एकूण किंमतीसह एक असेल, केबल घालण्यासाठी सर्वात कमी खर्चाचा मार्ग दर्शवितो.