Кіріспе
График төбелерін қосатын ең аз салмақты ағаш
Ең аз салмақты ағаш (MST) немесе ең аз салмақты жайылмалы ағаш – бұл жиектері салмақталған, байланысты, бағытталмаған графтың жиектерінің жиынтығы, ол барлық төбелерді циклсыз байланыстырады және мүмкіндігінше ең төменгі жиек салмағына ие. Яғни, бұл жиек салмақтарының қосындысы ең аз болатын жайылмалы ағаш. Кез келген жиектері салмақталған бағытталмаған графтың (қажет емес, байланысты) ең аз жайылмалы орман болады, ол оның байланысқан компоненттері үшін ең аз жайылмалы ағаштардың бірігімі. Ең аз жайылмалы ағаштардың көптеген қолданыс орындары бар. Мысалы, телекоммуникациялық компания жаңа ауданда кабель тартуға тырысады. Егер кабельді тек белгілі бір жолдармен (мысалы, көшелермен) ғана жерге көмуге шектеу болса, онда сол жолдармен байланысты нүктелерді (мысалы, үйлерді) қамтитын граф пайда болады. Кейбір жолдар ұзақ болуы немесе кабельді тереңге көмуді талап етуі себепті қымбатқа түсуі мүмкін; мұндай жолдар үлкен салмақты жиектермен бейнеленеді. Валюта жиек салмағы үшін қабылданатын бірлік – жиек ұзындығы үшбұрыш теңсіздігі сияқты геометрияның қалыпты ережелерін сақтауға міндетті емес. Осы граф үшін жайылмалы ағаш – бұл циклдары жоқ, бірақ барлық үйлерді байланыстыратын жолдардың кіші жиынтығы. Мүмкін бірнеше жайылмалы ағаш болуы мүмкін. Ең аз жайылмалы ағаш – ең төменгі жалпы құны бар, кабель тартудың ең арзан жолын көрсететін ағаш.
Мүмкін көптік
Егер графта n төбе болса, онда кез келген жайылған ағашта n - 1 қабырға болады. Бірдей салмаққа ие бірнеше ең кіші жайылған ағаштар болуы мүмкін; әсіресе, егер берілген графтың барлық қабырға салмақтары бірдей болса, онда осы графтың кез келген жайылған ағашы ең кіші болады.
Ең төменгі шығындар субграфы
Егер салмақтар оң болса, онда ең төменгі аралықтағы ағаш, шындығында, барлық төбелерді байланыстыратын ең төменгі құнды субграф болып табылады, себебі егер субграфта цикл болса, онда осы цикл бойындағы кез келген қабырғаны жою оның құнын төмендетеді және байланысты сақтайды.
Цикл қасиеттері
Графиктегі кез келген цикл C үшін, егер C циклындағы e қабырғасының салмағы, C циклындағы қалған барлық қабырғалардың жеке салмақтарынан үлкен болса, онда бұл қабырға ең төмен салмақты ағашқа (MST) жатпайды. Дәлел: Керісінше, e қабырғасы ең төмен салмақты ағашқа жатады деп есептейік. Онда e қабырғасын жою екі тармаққа бөлінеді, ал e қабырғасының екі ұшы әртүрлі тармақтарда қалады. C циклының қалған бөлігі бұл тармақтарды қайта қосады, демек, C циклында әртүрлі тармақтардағы ұштары бар f қабырғасы табылады, яғни ол f қабырғасының салмағы e қабырғасының салмағынан кем болғандықтан, e қабырғасынан жеңіл ағашты қайта құрайды.
Кесу мүлкі
Егер графиктің кез келген C кесіндісі үшін C кесінді жиынтығындағы e жиегінің салмағы C кесінді жиынтығындағы барлық басқа жиектердің салмағынан қатаң түрде кіші болса, онда бұл жиек графиктің барлық ең аз қамту ағаштарына (MST) жатады. Дәлел: Егер e жиегін қамтамайтын Т ең аз қамту ағашы бар деп есептейік. Т ағашына e жиегін қоссақ, цикл пайда болады. Бұл цикл кесіндіні e жиегі арқылы бір рет кесіп өтеді де, басқа жиек e' арқылы кері кесіп өтеді. e' жиегін жойсақ, Т\{e'\} ∪ {e} ең аз қамту ағашы Т-дан қатаң түрде кіші салмақты ағашқа айналады. Бұл Т ағашының ең аз қамту ағашы болғаны туралы болжамға қайшы келеді. Осыған ұқсас аргумент бойынша, егер кесіндіде бірнеше ең аз салмақты жиектер болса, онда әрбір осындай жиек кемінде бір ең аз қамту ағашында болады.
Ең төменгі шығындар шегі
Егер графтың ең төменгі құнға ие жиегі e бірегей болса, онда бұл жиек кез келген ең кіші жайылма ағашқа (MST) кіреді. Дәлел: егер e MST-ге қосылмаса, e-ні MST-ге қосып, пайда болған циклдағы (жоғарырақ құнға ие) кез келген жиекті алып тастағанда, салмағы аз жайылма ағаш алынады.
Қысылу
Егер T – MST қабырғаларының ағашы болса, онда біз T-ді бір ғана төбеге жиырыстыра аламыз, сонда жиырылған графтың MST + T, жиырылудан бұрынғы графтың MST-ін береді. Белгілі бір күрделілігі бар, кездейсоқ емес, салыстыруға негізделген ең жылдам алгоритм, Бернард Шазельдің жұмсақ үйіндісі, шамамен басымдық кезегіне негізделген. Оның орындалу уақыты – [[Big O нотациясы, мұнда α – Акерман функциясының классикалық функционалдық кері функциясы. α функциясы өте баяу өседі, сондықтан барлық практикалық мақсаттар үшін оны 4-тен аспайтын тұрақты сан деп қарастыруға болады; осылайша Шазель алгоритмі сызықтық уақытқа өте жақын.
Тығыз графиктер
Егер график тығыз болса (яғни m/n ≥ log log log n), онда Фредман мен Таржанның детерминистік алгоритмі MST-ні O(m) уақытында табады. Алгоритм бірнеше кезеңді орындайды. Әрбір кезеңде Прим алгоритмі бірнеше рет орындалады, әрқайсысы шектеулі қадамдар санымен. Әрбір кезеңнің жұмыс уақыты O(m + n) құрайды. Егер кезеңге дейінгі төбелер саны n' болса, кезеңнен кейін қалған төбелер саны ең көп дегенде n' / 2 болады. Сондықтан, ең көп дегенде log*n кезең қажет, бұл тығыз графтар үшін сызықтық жұмыс уақытын қамтамасыз етеді.
Бүкіл сандық салмақтар
Егер қабырға салмақтары бинарлық түрде көрсетілген бүтін сандар болса, онда O(m + n) бүтін сан операциясында мәселені шешетін детерминистік алгоритмдер белгілі. Бірақ, жалпы граф үшін салыстыру негізінде жұмыс істейтін алгоритм арқылы сызықтық уақытта детерминистік түрде шешуге болатыны әлі де ашық мәселе болып қалып отыр.
Параллельді және үлестірілген алгоритмдер
Зерттеулер ең аз қамтылған ағаш мәселесі үшін параллель алгоритмдерді де қарастырды. Процессорлардың сызықтық санымен мәселені O(log n) уақытында шешуге болады. Мәселені таратылған (үлестірілген) тәсілмен де қарастыруға болады. Егер әрбір түйін компьютер ретінде қарастырылса және ешбір түйін өзінің жалғасқан байланыстарынан басқа ештеңе білмесе, таратылған ең аз қамтылған ағашты есептеуге болады.
Кездейсоқ салмақпен толық графиктердегі MST
Алан Фриз n төбесі бар толық графты қарастырды, онда қабырға салмақтары тәуелсіз, бірдей үлестірілген кездейсоқ шамалармен берілген, ал үлестірім функциясы шартын қанағаттандырады. Онда n +∞-ға жақындағанда, ең аз қамтитын ағаштың (MST) күтілетін салмағы , мұнда Риманның зетта функциясы (нақтырақ айтқанда, Апери тұрақтысы). Фриз бен Стил ықтималдық бойынша жинақтылықты да дәлелдеді. Сванте Янсон MST салмағы үшін орталық шек теоремасын дәлелдеді. біркелкі кездейсоқ салмақтар үшін, кіші толық графтар үшін ең аз қамтитын ағаштың нақты күтілетін мөлшері есептелді. Төбелер Күтілетін мөлшер Шамамен күтілетін мөлшер 20,530,7540,885714350,966450261,018315171,05371681,079058891,0979027
Бөлшек түрлер
MST-нің фракциялық нұсқасы бар, онда әр қабырғаның «фракциялық» болуына рұқсат етіледі. Формальды түрде, графтың (V,E) фракциялық жайылма жиыны – E-дегі f теріс емес функциясы, сондықтан V-нің кез келген тривиальды емес W (яғни W бос емес және V-ге тең емес) ішкі жиыны үшін W түйінімен V\W түйінін байланыстыратын барлық қабырғалар бойынша f(e) қосындысы кем дегенде 1-ге тең. Интуитивті түрде f(e) – бұл e-нің жайылма жиынындағы үлесін көрсетеді. Минималды фракциялық жайылма жиыны – бұл жиынның қосындысы мүмкіндігінше кіші болатын фракциялық жайылма жиыны. Егер f(e) фракциялары {0,1} жиынымен шектелсе, онда f(e)=1 тең қабырғалардың T жиыны жайылма жиын болады, өйткені түйіндердің кез келген түйіні немесе ішкі жиыны T-ның кем дегенде бір қабырғасы арқылы графтың қалған бөлігімен байланысады. Сонымен қатар, егер f минимумға жеткізілсе, алынған жайылма жиын міндетті түрде ағаш болады, өйткені егер ол циклді қамтыса, онда жайылма шартына әсер етпей, қабырғаны алып тастауға болады. Осылайша, ең кіші фракциялық жайылма жиыны мәселесі – MST мәселесінің жеңілдетілген түрі, және оны фракциялық MST мәселесі деп те атауға болады. Фракциялық MST мәселесін эллипсоидтық әдіс арқылы полиномиалдық уақытта шешуге болады. Алайда, егер f(e) жартылай бүтін сан болуы керек деген талап қосылса (яғни f(e) {0, 1/2, 1} жиынында болуы керек), онда мәселе NP-қиын болады. k ең кіші жайылма ағаш (k MST) – графтың k төбесінің кез келген ішкі жиынын қамтитын, ең төмен салмағы бар ағаш. k ең кіші жайылма ағаштар жиыны – бұл k жайылма ағаштардың (барлық мүмкін жайылма ағаштардың ішінде) ішкі жиыны, сондықтан жиынның сыртындағы жайылма ағаштың салмағы кішірек болмайды. (Бұл мәселенің k ең кіші жайылма ағаштан ешқандай қатысы жоқ екеніне назар аударыңыз.) Евклидтік ең кіші жайылма ағаш – бұл жазықтықтағы (немесе кеңістіктегі) нүктелер арасындағы Евклидтік қашықтыққа сәйкес келетін қабырға салмақтары бар графтың жайылма ағашы. Тікбұрышты ең кіші жайылма ағаш – бұл жазықтықтағы (немесе кеңістіктегі) нүктелер арасындағы тікбұрышты қашықтыққа сәйкес келетін қабырға салмақтары бар графтың жайылма ағашы. Бөлінген ең кіші жайылма ағаш – бұл MST-нің бөлінген модельге кеңейтілуі, онда әр түйін компьютер ретінде қарастырылады және ешқандай түйін өзінің байланысты сілтемелерінен басқа ештеңе білмейді. Мәселенің математикалық анықтамасы бірдей, бірақ оны шешудің әртүрлі тәсілдері бар. Сыйымдылығы бар ең кіші жайылма ағаш – бұл белгіленген түйінге (түпнұсқа немесе тамыр) ие ағаш және түйінге қосылған әрбір кіші ағашта c түйінінен артық болмайды. c – ағаш сыйымдылығы деп аталады. CMST-ді оптималды түрде шешу NP-қиын, бірақ Эсау Уильямс және Шарма сияқты жақсы эвристикалар полиномиалдық уақытта оптималды шешімге жақын шешімдер шығарады. Дәрежесі шектеулі ең кіші жайылма ағаш – бұл әрбір түйін белгілі бір сан d үшін d-ден артық емес басқа түйіндерге байланысты болатын MST. d = 2 жағдайы – бұл саяхатшы сатушы мәселесінің ерекше жағдайы, сондықтан дәрежесі шектеулі ең кіші жайылма ағаш жалпы алғанда NP-қиын. Арбоrescence – бағытталған графтар үшін MST нұсқасы. Оны Чжу-Лиу/Эдмондс алгоритмін қолдану арқылы уақытта шешуге болады. Максималды жайылма ағаш – бұл салмағы басқа жайылма ағаштардың салмағынан артық немесе оған тең болатын жайылма ағаш. Мұндай ағашты Prim немесе Kruskal сияқты алгоритмдермен қабырға салмақтарын 1 еселеп, жаңа граф бойынша MST мәселесін шешкеннен кейін табуға болады. Максималды жайылма ағаштағы жол – бұл екі ұшы арасындағы ең кең жол: барлық мүмкін жолдардың ішінде ол ең аз салмақты қабырғаның салмағын арттырады. Максималды жайылма ағаштар табиғи тілдер үшін талдау алгоритмдерінде және шартты кездейсоқ өрістер үшін оқыту алгоритмдерінде қолданылады. Динамикалық MST мәселесі бастапқы графтағы қабырға салмағының өзгеруі немесе түйіннің енгізілуі/жойылғанынан кейін бұрын есептелген MST-ны жаңартуға қатысты. Минималды таңбалауды қамтитын жайылма ағаштар мәселесі – егер графтың әрбір қабырғасы салмақтың орнына шекті таңбалар жиынтығының таңбасымен байланысты болса, ең аз таңба түріне ие жайылма ағашты табу. Бөтелкелік қабырға – жайылма ағаштағы ең жоғары салмақты қабырға. Жайылма ағаш – ең аз бөтелкелік жайылма ағаш (немесе MBST), егер графта бөтелкелік қабырға салмағы аз болатын жайылма ағаш болмаса. MST міндетті түрде MBST (кесу қасиеті бойынша), бірақ MBST міндетті түрде MST емес. Ең төменгі құн жайылма ағаш ойыны – бұл ойыншылар оңтайлы жайылма ағашты құру шығындарын бөлісетін кооперативтік ойын.
The k minimum spanning tree (k MST) is the tree that spans some subset of k vertices in the graph with minimum weight. A set of k smallest spanning trees is a subset of k spanning trees (out of all possible spanning trees) such that no spanning tree outside the subset has smaller weight. (Note that this problem is unrelated to the k minimum spanning tree.) The Euclidean minimum spanning tree is a spanning tree of a graph with edge weights corresponding to the Euclidean distance between vertices which are points in the plane (or space). The rectilinear minimum spanning tree is a spanning tree of a graph with edge weights corresponding to the rectilinear distance between vertices which are points in the plane (or space). The distributed minimum spanning tree is an extension of MST to the distributed model, where each node is considered a computer and no node knows anything except its own connected links. The mathematical definition of the problem is the same but there are different approaches for a solution. The capacitated minimum spanning tree is a tree that has a marked node (origin, or root) and each of the subtrees attached to the node contains no more than c nodes. c is called a tree capacity. Solving CMST optimally is NP hard, but good heuristics such as Esau Williams and Sharma produce solutions close to optimal in polynomial time. The degree constrained minimum spanning tree is a MST in which each vertex is connected to no more than d other vertices, for some given number d. The case d = 2 is a special case of the traveling salesman problem, so the degree constrained minimum spanning tree is NP hard in general. An arborescence is a variant of MST for directed graphs. It can be solved in time using the Chu–Liu/Edmonds algorithm. A maximum spanning tree is a spanning tree with weight greater than or equal to the weight of every other spanning tree. Such a tree can be found with algorithms such as Prim's or Kruskal's after multiplying the edge weights by 1 and solving the MST problem on the new graph. A path in the maximum spanning tree is the widest path in the graph between its two endpoints: among all possible paths, it maximizes the weight of the minimum weight edge. Maximum spanning trees find applications in parsing algorithms for natural languages and in training algorithms for conditional random fields. The dynamic MST problem concerns the update of a previously computed MST after an edge weight change in the original graph or the insertion/deletion of a vertex. The minimum labeling spanning tree problem is to find a spanning tree with least types of labels if each edge in a graph is associated with a label from a finite label set instead of a weight. A bottleneck edge is the highest weighted edge in a spanning tree. A spanning tree is a minimum bottleneck spanning tree (or MBST) if the graph does not contain a spanning tree with a smaller bottleneck edge weight. A MST is necessarily a MBST ( by the cut property), but a MBST is not necessarily a MST. A minimum cost spanning tree game is a cooperative game in which the players have to share among them the costs of constructing the optimal spanning tree.