Ең аз таралу ағашы немесе ең аз салмақты қамтитын ағаш - барлық төбелерді бір-бірімен ешқандай циклсыз және ең төменгі ықтимал жалпы жиек салмағымен қосатын қосылған, жиегімен өлшенген бағытталмаған графиктің жиектерінің жиыны. Яғни, бұл жиек салмағының қосындысы мүмкіндігінше аз болатын созылатын ағаш.
Мысалдағы ең аз таралу ағашы дегеніміз не?
Ең кіші ағаш - ағаштың жиектерінің ұзындығын (немесе «салмақтарын») азайтатын ерекше ағаш түрі. Мысал ретінде кабельдік компания бірнеше ауданға желі тартқысы келеді; төселген кабель көлемін азайту арқылы кабельдік компания ақшаны үнемдейді. Ағаштың кез келген екі шыңды қосатын бір жолы бар.
Ең аз таралу ағашын қалай табуға болады?
қызыл тармақшаның ең жақын боялмаған көршісін табыңыз (яғни, кез келген қызыл төбеге ең жақын шың). Оны және төбені қызыл субграфқа қосатын жиекті қызыл түспен белгілеңіз. Барлық шыңдар қызыл болып белгіленгенше 2-қадамды қайталаңыз. Қызыл субграф - ең аз таралу ағашы.
Ағаштың кеңеюі және ең аз таралу ағашы дегенді қалай түсінесіз?
Графиктің ауқымды ағашы - графиктің әрбір төбесін қамтитын, бірақ цикл құрмайтын жалғанған жиектер жиынтығы. … Ең аз таралатын ағаш жиынтық жиектері ең кіші мәнге ие, бірақ.
Жалпы ағаш пен ең аз созылатын ағаштың айырмашылығы неде?
Егер график болсажиегі бойынша салмақталған, біз салмағы таралатын ағаштың барлық жиектерінің салмақтарының қосындысы ретінде анықтауға болады. Ең аз созылатын ағаш - салмағы мүмкін болатын барлық ағаштар арасындағы ең кішісі болатын аралық ағаш.
