Ең қысқа желілік нүктелер қосылысы

Кіріспе

Ең қысқа желі нүктелерді байланыстырады.

Евклидтік жазықтықтағы немесе жоғары өлшемді Евклидтік кеңістіктегі шекті нүктелер жиынының Евклидтік ең аз жабатын ағашы нүктелерді сызық сегменттерінің жүйесімен байланыстырады, мұнда нүктелер сегменттердің соңғы нүктелері болып табылады, ал сегменттердің жалпы ұзындығы ең төменгі мәнге дейін азайтылады. Мұнда кез келген екі нүкте сызық сегменттері арқылы бір-біріне жете алады. Оны нүктелерді төбелер ретінде және нүктелер арасындағы Евклидтік қашықтықты қабырға салмағы ретінде қарастыратын толық графтың ең аз жабатын ағашы ретінде табуға болады. Ең аз жабатын ағаштың қабырғалары кемінде 60° бұрышта қиылысады, әр төбеде ең көп дегенде алты қабырға болады. Жоғары өлшемдерде әр төбедегі қабырғалар саны жанама бірлік сфералардың тиісу санымен шектеледі. Бөлектелген бірлік шаршыдағы нүктелер үшін қабырғалардың жалпы ұзындығы нүктелер санының квадрат түбіріне пропорционалды. Әр қабырға жазықтықтың бос аймағында орналасқан, және осы аймақтарды Евклидтік ең аз жабатын ағаштың басқа геометриялық графтардың, соның ішінде туыстық көршілік графигі және Делоне үшбұрыштығының кіші графигі екенін дәлелдеу үшін пайдалануға болады. Делоне үшбұрыштығын құрастырып, содан кейін графтың ең аз жабатын ағаш алгоритмін қолдану арқылы берілген жазық нүктелердің ең аз жабатын ағашын үлкен O нотациясымен көрсетілген уақыт ішінде табуға болады. Бұл кейбір есептеу модельдерінде оңтайлы, бірақ бүтін сандық координаттары бар нүктелер үшін жылдам рандомизацияланған алгоритмдер бар. Жоғары өлшемдегі нүктелер үшін оңтайлы алгоритмді табу әлі де ашық мәселе болып қала береді.

Бұрыштар мен түбірлер дәрежесі

Евклидтік ең төменгі аралықтағы ағаштың екі жиегі бір төбеде түйіскенде, олар 60° немесе одан жоғары бұрыш құрауы керек, тек қана теңқабырлы үшбұрыштың екі қабырғасын құрағанда ғана теңдік болуы мүмкін. Себебі, егер екі жиек өткір бұрыш жасаса, олар құрайтын үшбұрыштың үшінші, ең қысқа жиегімен біреуін алмастыруға болады, нәтижесінде жалпы ұзындығы аз ағаш пайда болады. Қарама-қарсылығы, Штайнер ағашының мәселесі күштірек бұрыштық шектеуге ие: ең оңтайлы Штайнер ағашының барлық бұрыштары кем дегенде 120° болуы керек. Сол 60° бұрыштық шектеу «үйірілу саны» мәселесінде де кездеседі, ол – Евклид кеңістігінде орталық бірлік шарға жанасқан бірлік шарлардың ең көп саны, екі шардың түйісуі тек жанасу нүктесімен шектелген. Бұл шарлардың орталық нүктелері жұлдыз тәрізді ең төменгі аралықтағы ағаш құрайды, орталық нүкте барлық басқа нүктелерге іргелес. Керісінше, кез келген ең төменгі аралықтағы ағаштың кез келген төбесі үшін, сол төбеден және оның әр жиегі бойында екі бірлік қашықтықта орналасқан нүктелерден ортақ центрі бар, бірін-бірі қимайтын бірлік шарларды салуға болады. Сондықтан, *n* өлшемді кеңістікте төбеге қосылған жиектердің максималды саны (ағаштың бұл төбедегі дәрежесі) *n* өлшемдегі шарлардың үйірілу санына тең. Жазық ең төменгі аралықтағы ағаштардың дәрежесі ең көп алтыға жетеді, және егер ағаштың дәрежесі алты болса, онда максималды дәрежесі бес болатын тағы бір ең төменгі аралықтағы ағаш табылады. Үш өлшемді ең төменгі аралықтағы ағаштардың дәрежесі ең көп он екіге жетеді. Үйірілу санының нақты мәні тек төрт, сегіз және 24 өлшемдер үшін ғана белгілі. Егер нүктелер белгілі бір үздіксіз таралым бойынша кездейсоқ түрде жасалса, онда ең төменгі аралықтағы ағаш дерлік бірегей болады. Кез келген берілген дәрежедегі төбелердің саны, төбелер санының өсуімен, сол төбелер санына пропорционал тұрақтыға жақындайды. Бұл тұрақтылардың мәні дәрежеге және таралымға байланысты. Алайда, тіпті қарапайым жағдайларда да – мысалы, бірлік шаршыда тегіс таратылған нүктелер үшін жапырақтар саны – олардың нақты мәні әлі белгісіз.

Whenever two edges of a Euclidean minimum spanning tree meet at a vertex, they must form an angle of 60° or more, with equality only when they form two sides of an equilateral triangle. This is because, for two edges forming any sharper angle, one of the two edges could be replaced by the third, shorter edge of the triangle they form, forming a tree with smaller total length. In comparison, the Steiner tree problem has a stronger angle bound: an optimal Steiner tree has all angles at least 120°. The same 60° angle bound also occurs in the kissing number problem, of finding the maximum number of unit spheres in Euclidean space that can be tangent to a central unit sphere without any two spheres intersecting (beyond a point of tangency). The center points of these spheres have a minimum spanning tree in the form of a star, with the central point adjacent to all other points. Conversely, for any vertex of any minimum spanning tree, one can construct non overlapping unit spheres centered at and at points two units along each of its edges, with a tangency for each neighbor of Therefore, in dimensional space the maximum possible degree of a vertex (the number of spanning tree edges connected to it) equals the kissing number of spheres in dimensions. Planar minimum spanning trees have degree at most six, and when a tree has degree six there is always another minimum spanning tree with maximum degree five. Three dimensional minimum spanning trees have degree at most twelve. The only higher dimensions in which the exact value of the kissing number is known are four, eight, and 24 dimensions. For points generated at random from a given continuous distribution, the minimum spanning tree is almost surely unique. The numbers of vertices of any given degree converge, for large number of vertices, to a constant times that number of vertices. The values of these constants depend on the degree and the distribution. However, even for simple cases—such as the number of leaves for points uniformly distributed in a unit square—their precise values are not known.

Бос аймақтар

Кез келген Евклидтік ең аз аралықтағы ағаштың кез келген қабырғасы үшін, екі шеңберді радиустары ретінде қиып алу арқылы қалыптасқан линзаның (немесе vesica piscis) ішкі бөлігінде басқа берілген төбе орналасуы мүмкін емес. Басқаша айтқанда, егер кез келген ағаштың қабырғасы үшінші нүктені қамтитын линзаға ие болса, онда ол ең аз ұзындығы жоқ. Өйткені, екі шеңбердің геометриясы бойынша, сол үшінші нүкте екі төбеден де бір-біріне қарағанда жақын болады. Егер ағаштан қабырға алынып тасталса, үшінші нүкте төбелердің бірімен байланысты болып қалады, бірақ екіншісімен – жоқ. Алынған қабырғаны немесе (осы екі қабырғаның қайсысы ажыратылған нүктені бастапқы төбесіне қайта қосса) қабырғасымен алмастыру нәтижесінде қысқарақ ағаш пайда болады. Кез келген Евклидтік ең аз аралықтағы ағаштың кез келген қабырғасы үшін 60° және 120° бұрыштары бар ромб, оның ұзын диагоналі ретінде, барлық басқа қабырғалар арқылы ұқсас түрде құрылған ромбтардан бөлек болады. Бір төбесін бөлісетін екі қабырғаның ромбтары үстіне жатпауы керек, өйткені бұл 60°-тан кіші қабырға бұрышын білдіреді, және екі бөлек қабырғаның ромбтары үстіне жатпауы керек; егер жатса, екі қабырғаның ұзынырақ қабырғасы сол төрт төбе арасындағы қысқа қабырғамен алмастырылуы мүмкін.

Суперграфтар

Кейбір геометриялық графтарда нүктелік жиынтықтағы бос аймақтарды қолданатын анықтамалар бар, олардың салдарынан Евклидтік ең аз қамтитын ағаштың бөлігі бола алатын барлық жиектері бар. Оларға мыналар жатады: салыстырмалы көршілік графы, егер олар анықтаған линза бос болса, кез келген екі нүктенің арасында жиегі болады. Габриэль графы, егер диаметрі осы екі нүктеге тең болатын шеңбер бос болса, кез келген екі нүктенің арасында жиегі болады. Делоне триангуляциясы, егер осы екі нүктені хорда ретінде пайдаланатын бос шеңбер болса, кез келген екі нүктенің арасында жиегі болады. Үркхарт графы, әрбір үшбұрыштың ең ұзын жиегін жою арқылы Делоне триангуляциясынан құрылған. Қалған әрбір жиек үшін, осы жиекті пайдаланатын Делоне үшбұрыштарының төбелері салыстырмалы көршілік графының бос лунасының ішінде жата алмайды. Бұл графтардың бос аймақтарға қойылатын талаптары прогрессивті түрде жеңілдегендіктен, олар субграфтардың реттелген тізбегін құрайды. Яғни, олардың жиектері арасындағы қосалқы жиын қатынасын «⊆» символымен белгілесек, бұл графтарда мынадай қатынастар бар:

Ең аз қамтитын ағашты қамтуға кепілдік берілген тағы бір граф – Яо графы. Ол жазықтықтағы нүктелер үшін жазықтықты әрбір нүкте төңірегінде алты 60° бұрышқа бөліп, әр нүктені әр бұрыштағы ең жақын көршісімен қосу арқылы анықталады. Нәтижесінде алынған граф салыстырмалы көршілік графты қамтиды, себебі бос линзасы бар екі төбе олардың бұрыштарында бір-біріне ең жақын көрші болуы керек. Жоғарыда аталған көптеген геометриялық графтар сияқты, бұл анықтаманы жоғары өлшемдерге жалпылауға болады және (Делоне триангуляциясынан айырмашылығы) оның жалпылаулары әрқашан сызықтық санында жиектерді қамтиды.

Жалпы ұзындығы

Бірлік шаршыдағы (немесе кез келген басқа тұрақты пішінді) нүктелер үшін ең аз арақашықтықтағы ағаш жиектерінің жалпы ұзындығы белгілі. Бұл шекке нүктелер жиынтығы, мысалы торда біркелкі арақашықтықтағы нүктелер, жетеді. Дөңгелек кеңістіктегі бірлік гиперкубтағы нүктелер үшін тиісті шектеуіш – . Бірлік квадраттан немесе бірлік гиперкубтан біркелкі және тәуелсіз таңдалған нүктелер үшін ең аз аралықтағы ағаштың жалпы ұзындығына сәйкес келетін шектеуіш те осылай. Бірлік квадратқа қайта оралайық, ең аз аралықтағы ағаштың жиектері ұзындықтарының квадраттарының қосындысы – . Бұл шектерде жалғаспалы ромбтар бар, ал олардың ауданы жиек ұзындықтарының квадратына пропорционал. Жалпы ұзындығы бойынша шектеу Коши-Шварц теңсіздігін қолдану арқылы туындайды. Бұл нәтижелердің тағы бір түсіндірмесі – бірлік шаршыдағы кез келген нүктелер жиынтығының орташа жиек ұзындығы , ең көп дегенде, тұрақты тордағы нүктелердің арақашықтығына пропорционалды; ал бірлік шаршыдағы кездейсоқ нүктелер үшін орташа ұзындығы пропорционалды. Алайда, кездейсоқ жағдайда, ең ұзын жиектің ұзындығы орташадан шамамен тұрақты емес фактормен ұзағырақ болады. Мүмкіндік жоғары, ең ұзын жиек аралық ағаштың жапырағын құрайды және басқа нүктелерден алыс нүктелерді оның ең жақын көршісіне байланыстырады. Көптеген нүктелер үшін ең ұзын жиек ұзындығының оның күтілетін мәні айналасындағы үлестірілуі Лапластың үлестіріміне жақындайды. Кез келген геометриялық шүмектің, ең қысқа жолы Евклид қашықтығына жуықтаған толық геометриялық графтың субграфы, ең аз арақашықтықтағы ағаштың жалпы ұзындығы ең аз шүмектің ағашынан кем болмауы керек, ал геометриялық шүмектің стандартты сапа өлшемдерінің бірі – оның жалпы ұзындығы мен ең аз шүмектің ағашы арасындағы қатынас. Геометриялық шүмек сияқты шүмек құрудың бірнеше әдістері осы қатынас үшін тұрақты шекке жетеді. Ең аз арақашықтықтағы ағаштың жалпы ұзындығы мен Штайнер ағашы арасындағы ең үлкен мүмкін қатынас – Штайнер қатынасы деп болжанады, ол теңбұрыш үшбұрыштағы үш нүкте үшін қатынасқа тең.

For points in the unit square (or any other fixed shape), the total length of the minimum spanning tree edges is Some sets of points, such as points evenly spaced in a grid, attain this bound. For points in a unit hypercube in dimensional space, the corresponding bound is The same bound applies to the expected total length of the minimum spanning tree for points chosen uniformly and independently from a unit square or unit hypercube. Returning to the unit square, the sum of squared edge lengths of the minimum spanning tree is This bound follows from the observation that the edges have disjoint rhombi, with area proportional to the edge lengths squared. The bound on total length follows by application of the Cauchy–Schwarz inequality. Another interpretation of these results is that the average edge length for any set of points in a unit square is , at most proportional to the spacing of points in a regular grid; and that for random points in a unit square the average length is proportional to However, in the random case, with high probability the longest edge has length approximately longer than the average by a non constant factor. With high probability, the longest edge forms a leaf of the spanning tree, and connects a point far from all the other points to its nearest neighbor. For large numbers of points, the distribution of the longest edge length around its expected value converges to a Laplace distribution. Any geometric spanner, a subgraph of a complete geometric graph whose shortest paths approximate the Euclidean distance, must have total edge length at least as large as the minimum spanning tree, and one of the standard quality measures for a geometric spanner is the ratio between its total length and of the minimum spanning tree for the same points. Several methods for constructing spanners, such as the greedy geometric spanner, achieve a constant bound for this ratio. It has been conjectured that the Steiner ratio, the largest possible ratio between the total length of a minimum spanning tree and Steiner tree for the same set of points in the plane, is , the ratio for three points in an equilateral triangle.

Бөлімшелер

Егер Евклидтік ең аз аралықтағы ағаштың әрбір қабырғасы ортасынан жаңа нүкте қосу арқылы бөлінсе, нәтижедегі ағаш кеңейтілген нүктелер жиынының ең аз аралықтағы ағашы болып қалады. Осы бөлу процесін қайталап тұру арқасында Евклидтік ең аз қамтитын ағашты кез келген қалаған дәрежеде бөлуге болады. Дегенмен, тек кейбір қабырғаларды ғана бөлу немесе қабырғаларды ортасынан басқа нүктелерде бөлу, нәтижесінде алынған ағаш ең аз қамтитын ағаш болмайтын нүктелер жиынын тудыруы мүмкін.

Есептеу күрделілігі

Кез келген өлшемдегі нүктелер үшін ең аз жабатын ағаш, кез келген екі нүкте арасына қашықтық бойынша салмақталған толық графты құру арқылы, және содан кейін Prim–Dijkstra–Jarník алгоритмі немесе Borůvka алгоритмі сияқты графтың ең аз жабатын ағаш алгоритмін қолдану арқылы салынды. Бұл алгоритмдер толық графтарда уақыт алады, ал Крускаль алгоритмі сияқты тағы бір танымал әдіс барлық қашықтықтарды сұрыптау қажеттілігінен баяурақ. Төмен өлшемді кеңістіктегі нүктелер үшін мәселе одан да жылдам шешілуі мүмкін, бұл төменде егжей-тегжейлі сипатталған. Евклид қашықтығын есептеуде квадрат түбірді табу қажет. Қабырға салмақтарын салыстыру кезінде Евклид қашықтықтарының өзінің орнына квадраттарын салыстыру бірдей реттеуді береді және ағаштың қалған есептеулерін өзгертпейді. Бұл әдіс есептеуді жылдамдатады және бүтін координаттары бар нүктелер үшін ең аз жабатын ағашты тек бүтін арифметиканы қолдана отырып салуға мүмкіндік береді.

Жоғары өлшемдер

Мәселені өлшемдік кеңістіктегі нүктелерге де жалпылауға болады. Жоғары өлшемдерде Делоне үшбұрышымен анықталатын байланыс (сондай-ақ, дөңгелек қабықты өлшемдік симплекстерге бөледі) ең аз қамтитын ағашты қамтиды; алайда, үшбұрышта толық граф болуы мүмкін. Сондықтан, Евклидтік ең аз қамтитын ағашты толық графтың қамтитын ағашы ретінде немесе Делоне үшбұрышының қамтитын ағашы ретінде табуға уақыт кетеді. Үш өлшем үшін ең аз қамтитын ағашты уақыт ішінде, ал кез келген үлкен өлшемде — толық граф пен Делоне үшбұрышы алгоритмдеріне қарағанда жылдам уақыт ішінде табуға болады. Жоғары өлшемді ең аз қамтитын ағаштар үшін оңтайлы уақыт күрделілігі әлі белгісіз, бірақ екі түсті ең жақын жұптарды есептеудің күрделілігімен тығыз байланысты. Екі түсті ең жақын жұп мәселесінде кіріс екі түрлі түспен (мысалы, қызыл және көк) берілген нүктелер жиынтығы болып табылады. Шығыс – ең аз қашықтықтағы қызыл және көк нүктелер жұбы. Бұл жұп әрқашан ең аз қамтитын ағаштың қабырғаларының бірін құрайды. Сондықтан, ең жақын жұп мәселесін ең аз қамтитын ағашты құрастыруға және оның қабырғаларын ең қысқа қызыл-көк қабырғасы үшін қарауға жұмсалатын уақыт көлемінде шешуге болады. Керісінше, берілген нүктелер жиынтығының кез келген қосалқы жиынтығының қызыл-көк түсті кез келген қосалқы жиынтығының ең жақын екі түсті жұбы қосалқы жиынтықтың ең аз қамтитын ағашының бір қабырғасын құрайды. Кіші жиынтықтардың бояуларының тізбесін мұқият таңдап, әр кіші проблеманың ең жақын екі түсті жұбын табу арқылы, ең аз қамтитын ағашты сол нүктелер саны үшін ең жақын екі түсті жұптарды табудың оңтайлы уақытына пропорционалды уақыт ішінде табуға болады, ол оңтайлы уақыт қандай болса да. Кез келген шектелген өлшемдегі біркелкі кездейсоқ нүктелер жиынтығы үшін Яо графигі немесе Делоне үшбұрышы сызықтық күтілетін қабырғалар санына ие, ең аз қамтитын ағашты қамтуы кепілдендірілген және сызықтық күтілетін уақытта құрастырылуы мүмкін. Осы графиктерден ең аз қамтитын ағаштың өзі графиктік ең аз қамтитын ағаштар үшін кездейсоқ сызықтық уақыт алгоритмін қолдану арқылы сызықтық уақытта құруға болады. Алайда, кластерленген деректерден келетін кіріс бойынша осы әдістердің нашар жұмыс істеуі алгоритмдік инженерлік зерттеушілерді кездейсоқ кіріс немесе арақашықтығы мен кластерлеуі кездейсоқ деректерге ұқсас кіріс үшін біраз баяу уақытпен байланысты әдістерді әзірлеуге әкелді, сонымен қатар нақты әлемдегі деректерде жақсы жұмыс істейді. Жақсы бөлінген жұптар ыдырауы – берілген нүктелердің қосалқы жиынтық жұптарының отбасы, сондықтан әрбір нүктелер жұбы осы қосалқы жиынтық жұптарының біріне жатады және сол қосалқы жиынтық жұптарынан келетін барлық нүктелер жұптарының ұзындығы шамамен бірдей болады. Сызықтық сандағы қосалқы жиынтықтармен жақсы бөлінген жұптар ыдырауын және әр қосалқы жиынтық үшін нүктелердің өкілдік жұбын табуға болады. Осы өкілдік жұптар құрайтын графиктің ең аз қамтитын ағашы ең аз қамтитын ағастың шамасына жақын. Осы идеяларды қолдану арқылы уақыт бойынша ең аз қамтитын ағастың шамасын табуға болады, тұрақты. Нақтырақ айтқанда, әрбір өкілдік жұпты өзінің баламалық класындағы ең жақын жұпты шамалау үшін таңдап, әртүрлі жұптар үшін осы шамалаудың сапасын мұқият өзгертіп, кез келген белгіленген өлшем үшін уақытпен байланысты тәуелділік беріледі.

The problem can also be generalized to points in the dimensional space In higher dimensions, the connectivity determined by the Delaunay triangulation (which, likewise, partitions the convex hull into dimensional simplices) contains the minimum spanning tree; however, the triangulation might contain the complete graph. Therefore, finding the Euclidean minimum spanning tree as a spanning tree of the complete graph or as a spanning tree of the Delaunay triangulation both take time. For three dimensions the minimum spanning tree can be found in time , and in any greater dimension, in time

for any —faster than the quadratic time bound for the complete graph and Delaunay triangulation algorithms. The optimal time complexity for higher dimensional minimum spanning trees remains unknown, but is closely related to the complexity of computing bichromatic closest pairs. In the bichromatic closest pair problem, the input is a set of points, given two different colors (say, red and blue). The output is a pair of a red point and a blue point with the minimum possible distance. This pair always forms one of the edges in the minimum spanning tree. Therefore, the bichromatic closest pair problem can be solved in the amount of time that it takes to construct a minimum spanning tree and scan its edges for the shortest red–blue edge. Conversely, for any red–blue coloring of any subset of a given set of points, the bichromatic closest pair produces one edge of the minimum spanning tree of the subset. By carefully choosing a sequence of colorings of subsets, and finding the bichromatic closest pair of each subproblem, the minimum spanning tree may be found in time proportional to the optimal time for finding bichromatic closest pairs for the same number of points, whatever that optimal time turns out to be. For uniformly random point sets in any bounded dimension, the Yao graph or Delaunay triangulation have linear expected numbers of edges, are guaranteed to contain the minimum spanning tree, and can be constructed in linear expected time. From these graphs, the minimum spanning tree itself may be constructed in linear time, by using a randomized linear time algorithm for graph minimum spanning trees. However, the poor performance of these methods on inputs coming from clustered data has led algorithm engineering researchers to develop methods with a somewhat slower time bound, for random inputs or inputs whose distances and clustering resemble those of random data, while exhibiting better performance on real world data. A well separated pair decomposition is a family of pairs of subsets of the given points, so that every pair of points belong to one of these pairs of subsets, and so that all pairs of points coming from the same pair of subsets have approximately the same length. It is possible to find a well separated pair decomposition with a linear number of subsets, and a representative pair of points for each subset, in time The minimum spanning tree of the graph formed by these representative pairs is then an approximation to the minimum spanning tree. Using these ideas, a approximation to the minimum spanning tree may be found in time, for constant More precisely, by choosing each representative pair to approximate the closest pair in its equivalence class, and carefully varying the quality of this approximation for different pairs, the dependence on in the time bound can be given as for any fixed dimension.

Төменгі шек

Эвклидтік ең аз қамтылатын ағаш мәселесінің асимптотикалық төменгі шегі шектеулі есептеу модельдерінде анықталуы мүмкін. Оларға алгебралық шешім ағашы және алгебралық есептеу ағашы модельдері жатады, онда алгоритм кіріс нүктелеріне тек олардың координаттарында қарапайым алгебралық есептеулерді орындайтын белгілі бір шектеулі амалдар арқылы ғана қол жеткізе алады. Бұл модельдерде ең жақын нүктелер жұбын табу мәселесі белгілі бір уақытты қажет етеді, бірақ ең жақын жұп міндетті түрде ең аз қамтылатын ағаштың қабырғасы болып табылады, сондықтан ең аз қамтылатын ағашқа да осы уақыт қажет. Демек, осы модельде Делоне үшбұрышын пайдалану сияқты, жазықтықтағы ең аз қамтылатын ағашты құруға арналған уақыт бойынша алгоритмдер оңтайлы болып табылады. Алайда, бұл төменгі шектер бүтін сан координаталары бар есептеу модельдеріне қолданылмайды, онда осы координаталар бойынша биттік амалдар мен кестелік индекстеу амалдарына рұқсат етіледі. Бұл модельдерде, жоғарыда сипатталғандай, жылдам алгоритмдерге қол жеткізуге болады.

Қолданбалар

Евклидтік ең аз жабатын ағаштардың айқын қолданылуы – бірлік ұзындығы үшін белгіленген сомаға байланысты байланыстардың құны ескерілетін жағдайда, бірнеше нүктені қосу үшін сымдар немесе құбырлардың ең арзан желісін табу. Ең аз жабатын ағаштар туралы алғашқы жарияланымдар осы мәселенің географиялық нұсқасына қатысты болды, ол Оңтүстік Моравия үшін электр желісін жобалауды қамтыды, ал 1957 жылы Лоберман мен Вайнбергер тізбектердегі сымдардың ұзындығын азайтуға қолданылуын сипаттады. Ең аз жабатын ағаштар иерархиялық кластерлеудің бірнеше әдістерінің бірі – бір-бір байланысты кластерлеумен тығыз байланысты. Ең аз жабатын ағаштың ұзындығы бойынша реттелген қабырғалары осы кластерлеу әдісінде кластерлерді үлкен кластерлерге біріктіру ретін көрсетеді. Кез келген алгоритм арқылы табылғаннан кейін, осы қабырғаларды бір-бір байланысты кластерлеуді құру үшін уақытында пайдалануға болады. Бір-бір байланысты кластерлеудің нәтижесінде пайда болатын ұзын, жіңішке кластерлер кейбір деректер үшін, мысалы, Гаусс таралымдарының қосындысы үшін қолайсыз болуы мүмкін, бірақ кластерлердің өзі ұзын, жіңішке пішінге ие болғанда, мысалы, галактикалардың қара материя галондарын модельдеуде жақсы таңдау болуы мүмкін. Географиялық ақпарат ғылымында бірнеше зерттеушілер ғимараттардың центроидтарының ең аз жабатын ағаштарын пайдаланып, ғимараттардың мағыналы кластерлерін анықтады, мысалы, басқа тәсілмен сәйкессіз деп танылған қабырғаларды жою арқылы. Сондай-ақ, ең аз жабатын ағаштар жазықтықтағы қисықтардың пішінін анықтау үшін, қисық бойындағы үлгіленген нүктелер берілгенде қолданылды. Тегіс қисық үшін, жергілікті ерекшеліктерінен гөрі ұсақ үлгіленгенде, ең аз жабатын ағаш қисық бойындағы тікелей жатқан нүктелерді байланыстыратын жол құрайды. Жалпы алғанда, ұқсас әдістер бір-бірімен байланысты жиын ретінде емес, нүктелі немесе сызықты стильде салынған қисықтарды тануы мүмкін. Бұл қисықтарды табу техникасы бөлшектер физикасында, көпіршік камерасындағы бөлшектердің қалдырған іздерін автоматты түрде анықтау үшін қолданылады. Бұл идеяның күрделі нұсқалары қисық сызығын шамамен ұстанатын үлгілік нүктелер бұлтынан қисықтарды табуы мүмкін, ең аз квадраттар әдісін басқару үшін жабатын ағаштың топологиясын пайдаланады. Ең аз жабатын ағаштардың тағы бір қолданылуы – Евклидтің саяхатшы сатушы мәселесі үшін тұрақты коэффициенттік жуықтау алгоритмі, яғни нүктелер жиынтығының ең қысқа көпбұрыштығын табу мәселесі. Ең аз жабатын ағаштың шекарасы бойынша жүру, оптималды саяхатшы сатушы маршрутын оптималды ұзындығының екі есесінен аспайтын дәлдікпен жуықтауы мүмкін. Дегенмен, бұл мәселе үшін полиномиалдық уақытта жұмыс істейтін, одан да дәл жуықтау схемалары белгілі. Сымсыз желілерде хабарларды тарату, ең аз жабатын ағаштағы жолдар арқылы жүргізілсе, ең аз энергияны қажет ететін хабар тарату маршрутына жақын жуықтама береді, оны дәл есептеу қиын.

An obvious application of Euclidean minimum spanning trees is to find the cheapest network of wires or pipes to connect a set of places, assuming the links cost a fixed amount per unit length. The first publications on minimum spanning trees more generally concerned a geographic version of the problem, involving the design of an electrical grid for southern Moravia, and an application to minimizing wire lengths in circuits was described in 1957 by Loberman and Weinberger. Minimum spanning trees are closely related to single linkage clustering, one of several methods for hierarchical clustering. The edges of a minimum spanning tree, sorted by their length, give the order in which to merge clusters into larger clusters in this clustering method. Once these edges have been found, by any algorithm, they may be used to construct the single linkage clustering in time Although the long thin cluster shapes produced by single linkage clustering can be a bad fit for certain types of data, such as mixtures of Gaussian distributions, it can be a good choice in applications where the clusters themselves are expected to have long thin shapes, such as in modeling the dark matter halos of galaxies. In geographic information science, several researcher groups have used minimum spanning trees of the centroids of buildings to identify meaningful clusters of buildings, for instance by removing edges identified in some other way as inconsistent. Minimum spanning trees have also been used to infer the shape of curves in the plane, given points sampled along the curve. For a smooth curve, sampled more finely than its local feature size, the minimum spanning tree will form a path connecting consecutive points along the curve. More generally, similar methods can recognize curves drawn in a dotted or dashed style rather than as a single connected set. Applications of this curve finding technique include particle physics, in automatically identifying the tracks left by particles in a bubble chamber. More sophisticated versions of this idea can find curves from a cloud of noisy sample points that roughly follows the curve outline, by using the topology of the spanning tree to guide a moving least squares method. Another application of minimum spanning trees is a constant factor approximation algorithm for the Euclidean traveling salesman problem, the problem of finding the shortest polygonalization of a point set. Walking around the boundary of the minimum spanning tree can approximate the optimal traveling salesman tour within a factor of two of the optimal length. However, more accurate polynomial time approximation schemes are known for this problem. In wireless ad hoc networks, broadcasting messages along paths in a minimum spanning tree can be an accurate approximation to the minimum energy broadcast routing, which is, again, hard to compute exactly.

Орындалуы

Эвклидтік ең аз аралықтағы ағаштардың іске асыру мәселесі абстрактілі ағашты кіріс ретінде қабылдайды және ағаштың әрбір төбесі үшін геометриялық орналасқан жерді (кейбір белгілі бір өлшемдегі кеңістікте) іздейді, сонда берілген ағаш сол нүктелердің ең аз аралықтағы ағашына тең болады. Кез келген абстрактілі ағашқа мұндай іске асыру мүмкін емес; мысалы, ағаш әр төбесінің дәрежесіне қатысты «сүйісу саны» шегін сақтауы керек. Қосымша шектеулер де бар; мысалы, жазық ең аз аралықтағы ағаштағы алты дәрежелі төбе бес немесе алты дәрежелі төбемен тікелей байланысты бола алмайды. Екі өлшемді іске асырудың болу-болмауын анықтау NP-қиын мәселе. Дегенмен, қиындықты дәлелдеу ағаштағы алты дәрежелі төбелердің өте шектеулі іске асыру жиынтығына байланысты: мұндай төбенің көршілері сол төбеге ортақталған дұрыс алтыбұрыштың төбелеріне орналастырылуы керек. Шындығында, ең жоғары бес дәрежелі ағаштар үшін жазық іске асыру әрқашан мүмкін. Сол сияқты, ең жоғары он дәрежелі ағаштар үшін үш өлшемді іске асыру әрқашан бар. Мұндай іске асырулар үшін кейбір ағаштарға экспоненциалды ұзындықтағы қабырғалар және олардың ең қысқа қабырғасының ұзындығына пропорционалды экспоненциалды ауданы бар шектеулі қораптар қажет болуы мүмкін. Ең жоғары төрт дәрежелі ағаштарда кішкентай жазық іске асырулар бар, олар полиномдық шектелген қабырға ұзындығына және шектеулі қораптарға ие.