ต้นไม้ครอบคลุมขั้นต่ำ ( MST ) หรือต้นไม้ครอบคลุมที่มีน้ำหนักขั้นต่ำคือเซตย่อยของขอบของกราฟ แบบไม่มีทิศทาง ที่เชื่อมต่อกันและมีน้ำหนักขอบ ซึ่งเชื่อมต่อ จุดยอดทั้งหมดเข้าด้วยกัน โดยไม่มีวงจรและมีน้ำหนักขอบรวมน้อยที่สุดเท่าที่จะเป็นไปได้^{[ 1 ]}กล่าวคือ เป็นต้นไม้ครอบคลุมที่มีผลรวมของน้ำหนักขอบน้อยที่สุด^{[ 2 ]}โดยทั่วไปแล้ว กราฟแบบไม่มีทิศทางที่มีน้ำหนักขอบใดๆ (ไม่จำเป็นต้องเชื่อมต่อกัน) จะมีป่าครอบคลุมขั้นต่ำซึ่งเป็นการรวมกันของต้นไม้ครอบคลุมขั้นต่ำสำหรับส่วนประกอบที่เชื่อมต่อกัน

ต้นไม้แผ่คลุมขั้นต่ำ (Minimum Spanning Tree) มีการใช้งานหลายกรณี ตัวอย่างเช่น บริษัทโทรคมนาคมที่พยายามวางสายเคเบิลในย่านที่อยู่อาศัยใหม่ หากบริษัทถูกจำกัดให้ฝังสายเคเบิลเฉพาะตามเส้นทางที่กำหนด (เช่น ถนน) ก็จะมีกราฟที่แสดงจุด (เช่น บ้าน) ที่เชื่อมต่อกันด้วยเส้นทางเหล่านั้น บางเส้นทางอาจมีค่าใช้จ่ายสูงกว่า เนื่องจากยาวกว่า หรือต้องฝังสายเคเบิลลึกกว่า เส้นทางเหล่านี้จะถูกแทนด้วยขอบที่มีน้ำหนักมากกว่า หน่วยเงินตราสามารถใช้เป็นหน่วยน้ำหนักของขอบได้ – ไม่จำเป็นต้องให้ความยาวของขอบเป็นไปตามกฎเรขาคณิตทั่วไป เช่น อสมการสามเหลี่ยมต้นไม้แผ่คลุมสำหรับกราฟนั้นจะเป็นส่วนย่อยของเส้นทางเหล่านั้นที่ไม่มีวงจร แต่ยังคงเชื่อมต่อบ้านทุกหลัง อาจมีต้นไม้แผ่คลุมได้หลายต้นต้นไม้แผ่คลุมขั้นต่ำจะเป็นต้นไม้ที่มีต้นทุนรวมต่ำที่สุด ซึ่งแสดงถึงเส้นทางที่ประหยัดที่สุดสำหรับการวางสายเคเบิล

ถ้า กราฟมี จุดยอด n จุด ต้นไม้แผ่คลุมแต่ละต้นจะมีขอบ n − 1เส้น

อาจมีต้นไม้แผ่คลุมขั้นต่ำหลายต้นที่มีน้ำหนักเท่ากัน โดยเฉพาะอย่างยิ่ง หากน้ำหนักของขอบทั้งหมดในกราฟที่กำหนดเท่ากัน ต้นไม้แผ่คลุมทุกต้นของกราฟนั้นจะเป็นต้นไม้แผ่คลุมขั้นต่ำ

ถ้าแต่ละขอบมีน้ำหนักที่แตกต่างกัน ก็จะมีต้นไม้แผ่คลุมขั้นต่ำเพียงหนึ่งเดียวที่ไม่ซ้ำกันนี่เป็นความจริงในสถานการณ์จริงหลายๆ สถานการณ์ เช่น ตัวอย่างบริษัทโทรคมนาคมข้างต้น ที่ไม่น่าจะมีเส้นทางสองเส้นใดที่มี ต้นทุนเท่ากัน เป๊ะๆ หลักการ นี้ยังสามารถนำไปใช้กับป่าแผ่คลุมได้เช่นกัน

การพิสูจน์:

1. สมมติในทางตรงกันข้ามว่ามี MST ที่แตกต่างกันสองแบบคือAและB
2. เนื่องจากAและBแตกต่างกันแม้จะมีโหนดเดียวกัน จึงมีอย่างน้อยหนึ่งขอบที่อยู่ในกลุ่มใดกลุ่มหนึ่งแต่ไม่อยู่ในอีกกลุ่มหนึ่ง ในบรรดาขอบเหล่านั้น ให้e ₁ เป็นขอบที่มีน้ำหนักน้อยที่สุด การเลือกนี้เป็นเอกลักษณ์เพราะน้ำหนักของขอบทั้งหมดแตกต่างกัน โดยไม่เสียความเป็นทั่วไป สมมติว่าe ₁อยู่ในA
3. เนื่องจากBเป็น MST ดังนั้น{ e 1 _} ∪ Bจะต้องมีวัฏจักรCที่มีe ₁
4. เนื่องจากเป็นโครงสร้าง แบบต้นไม้Aจึงไม่มีวัฏจักร ดังนั้นCจะต้องมีขอบe ₂ที่ไม่ได้อยู่ในA
5. เนื่องจากe ₁ ถูกเลือกให้เป็นขอบที่มีน้ำหนักน้อยที่สุดเพียง เส้นเดียวในบรรดาขอบที่เป็นของAหรือB เพียงกลุ่มเดียว ดังนั้นน้ำหนักของe ₂จึงต้องมากกว่าน้ำหนักของe ₁
6. เนื่องจากe ₁และe ₂เป็นส่วนหนึ่งของวัฏจักรCการแทนที่e ₂ด้วยe ₁ในBจึงทำให้ได้ต้นไม้แผ่ขยายที่มีน้ำหนักน้อยลง
7. สิ่งนี้ขัดแย้งกับสมมติฐานที่ว่าBเป็น MST

โดยทั่วไป หากน้ำหนักขอบไม่แตกต่างกันทั้งหมด เฉพาะชุดน้ำหนัก (หลายชุด) ในต้นไม้ครอบคลุมขั้นต่ำเท่านั้นที่จะเป็นเอกลักษณ์อย่างแน่นอน ซึ่งเหมือนกันสำหรับต้นไม้ครอบคลุมขั้นต่ำทั้งหมด^{[ 3 ]}

ถ้าค่าน้ำหนักเป็นบวกต้นไม้แผ่คลุมขั้นต่ำก็คือกราฟย่อยที่ มีต้นทุนต่ำที่สุด ที่เชื่อมต่อจุดยอดทั้งหมด เนื่องจากถ้ากราฟย่อยมีวงจรการลบขอบใดๆ ตามวงจรนั้นจะลดต้นทุนและรักษาการเชื่อมต่อไว้ได้

สำหรับวงจรC ใดๆ ในกราฟ หากน้ำหนักของขอบeของCมีค่ามากกว่าน้ำหนักของขอบอื่นๆ ทั้งหมดในCแล้ว ขอบนั้นจะไม่สามารถเป็นส่วนหนึ่งของ MST ได้

พิสูจน์: สมมติในทางตรงกันข้าม กล่าวคือeเป็นส่วนหนึ่งของ MST T ₁การลบeจะทำให้T ₁ แตก ออกเป็นสองต้นไม้ย่อย โดยที่ปลายทั้งสองของeอยู่ในต้นไม้ย่อยที่แตกต่างกัน ส่วนที่เหลือของCจะเชื่อมต่อต้นไม้ย่อยเหล่านั้นเข้าด้วยกัน ดังนั้นจึงมีขอบfของCที่มีปลายอยู่ในต้นไม้ย่อยที่แตกต่างกัน กล่าวคือ มันเชื่อมต่อต้นไม้ย่อยเหล่านั้นเข้าด้วยกันเป็นต้นไม้T ₂ที่มีน้ำหนักน้อยกว่าT ₁เนื่องจากน้ำหนักของfน้อยกว่าน้ำหนักของ e

สำหรับส่วนตัดC ใดๆ ของกราฟ หากน้ำหนักของขอบeในเซตส่วนตัดของCมีค่าน้อยกว่าน้ำหนักของขอบอื่นๆ ทั้งหมดในเซตส่วนตัดของC อย่างเคร่งครัด แล้ว ขอบนี้จะอยู่ในต้นไม้ครอบคลุมน้อยที่สุด (MST) ทั้งหมดของกราฟ

บทพิสูจน์: สมมติว่ามีต้นไม้ครอบคลุมน้อยที่สุด (MST) ชื่อTที่ไม่มีขอบeการเพิ่มeเข้าไปในTจะทำให้เกิดวงจร ซึ่งตัดผ่านเส้นตัดที่ขอบe หนึ่งครั้ง และตัดกลับที่ขอบe' อีกครั้ง การลบe' ออกไป จะทำให้ได้ต้นไม้ครอบคลุมT ∖{ e' } ∪ { e }ที่มีน้ำหนักน้อยกว่าT อย่างชัดเจน ซึ่งขัดแย้งกับสมมติฐานที่ว่าTเป็น MST

ด้วยเหตุผลที่คล้ายกัน หากมีขอบมากกว่าหนึ่งขอบที่มีน้ำหนักน้อยที่สุดเมื่อข้ามการตัด ขอบแต่ละขอบดังกล่าวจะอยู่ในต้นไม้แผ่คลุมขั้นต่ำบางต้น

ถ้าขอบe ที่มีต้นทุนต่ำที่สุด ของกราฟมีเพียงขอบเดียว ขอบนั้นจะถูกรวมอยู่ใน MST ทุกกราฟ

พิสูจน์: หากeไม่ได้รวมอยู่ใน MST การลบขอบใดๆ (ที่มีต้นทุนสูงกว่า) ในวงจรที่เกิดขึ้นหลังจากเพิ่มeเข้าไปใน MST จะทำให้ได้ต้นไม้แผ่คลุมที่มีน้ำหนักน้อยลง

ถ้าTเป็นต้นไม้ของขอบ MST เราสามารถยุบTให้เหลือเพียงจุดยอดเดียวในขณะที่ยังคงรักษาคุณสมบัติที่ไม่เปลี่ยนแปลงไว้ว่า MST ของกราฟที่ยุบแล้วบวกกับTจะให้ MST สำหรับกราฟก่อนการยุบ^{[ 4 ]}

ในอัลกอริธึมทั้งหมดด้านล่างนี้mคือจำนวนขอบในกราฟ และnคือจำนวนจุดยอด

อัลกอริทึมแรกสำหรับการค้นหาต้นไม้ครอบคลุมขั้นต่ำได้รับการพัฒนาโดยนักวิทยาศาสตร์ชาวเช็กOtakar Borůvkaในปี 1926 (ดูอัลกอริทึมของ Borůvka ) จุดประสงค์คือการครอบคลุมทางไฟฟ้าที่มีประสิทธิภาพในMoraviaอัลกอริทึมดำเนินไปตามลำดับขั้นตอน ในแต่ละขั้นตอนที่เรียกว่าขั้นตอน Boruvkaจะระบุป่าFที่ประกอบด้วยขอบที่มีน้ำหนักน้อยที่สุดที่เชื่อมต่อกับแต่ละจุดยอดในกราฟGจากนั้นสร้างกราฟG ₁ = G \ Fเป็นอินพุตสำหรับขั้นตอนถัดไป ในที่นี้G \ Fหมายถึงกราฟที่ได้มาจากGโดยการยุบขอบในF (โดยคุณสมบัติ Cutขอบเหล่านี้เป็นของ MST) แต่ละขั้นตอนของ Boruvka ใช้เวลาเชิงเส้น เนื่องจากจำนวนจุดยอดลดลงอย่างน้อยครึ่งหนึ่งในแต่ละขั้นตอน อัลกอริทึมของ Boruvka จึงใช้เวลาO ( m log n ) ^{[ 4 ]}

อัลกอริทึมที่สองคืออัลกอริทึมของ Primซึ่งคิดค้นโดยVojtěch Jarníkในปี 1930 และถูกค้นพบใหม่โดยPrimในปี 1957 และDijkstraในปี 1959 โดยพื้นฐานแล้ว อัลกอริทึมนี้จะขยาย MST ( T ) ทีละขอบ ในตอนเริ่มต้นTจะมีจุดยอดใดๆ ก็ได้ ในแต่ละขั้นตอนTจะถูกเพิ่มด้วยขอบที่มีน้ำหนักน้อยที่สุด( x , y )โดยที่xอยู่ในTและyยังไม่อยู่ในTด้วยคุณสมบัติ Cutขอบทั้งหมดที่เพิ่มเข้าไปในTจะอยู่ใน MST เวลาในการทำงานของอัลกอริทึมนี้คือO ( m log n )หรือO ( m + n log n )ขึ้นอยู่กับโครงสร้างข้อมูลที่ใช้

อัลกอริทึมที่สามที่ใช้กันทั่วไปคืออัลกอริทึมของ Kruskalซึ่งใช้เวลา O ( m log n ) เช่นกัน

อัลกอริทึมที่สี่ ซึ่งไม่ค่อยได้ใช้กันทั่วไป คืออัลกอริทึมการลบแบบย้อนกลับซึ่งเป็นการย้อนกลับของอัลกอริทึมของ Kruskal เวลาในการทำงานของมันคือO ( m log n (log log n ) ³ )

อัลกอริ ทึมทั้งสี่นี้เป็นอัลกอริทึมแบบโลภ (greedy algorithms ) เนื่องจากทำงานได้ในเวลาพหุนาม (polynomial time) ปัญหาการค้นหาต้นไม้ดังกล่าวจึงอยู่ใน กลุ่มปัญหาเชิงเส้นบวก (FP ) และปัญหาการตัดสินใจ ที่เกี่ยวข้อง เช่น การพิจารณาว่าขอบใดขอบหนึ่งอยู่ในต้นไม้ครอบคลุมขั้นต่ำ (MST) หรือการพิจารณาว่าน้ำหนักรวมขั้นต่ำเกินค่าที่กำหนดหรือไม่นั้นอยู่ในกลุ่ม ปัญหาเชิงเส้น บวก (P )

นักวิจัยหลายคนพยายามค้นหาอัลกอริทึมที่มีประสิทธิภาพในการคำนวณมากขึ้น

ในแบบจำลองการเปรียบเทียบซึ่งอนุญาตให้ดำเนินการกับน้ำหนักขอบได้เพียงการเปรียบเทียบแบบคู่เท่านั้นKarger, Klein & Tarjan (1995)พบอัลกอริทึมแบบสุ่มที่มีเวลาเชิงเส้นโดยอิงจากการรวมกันของอัลกอริทึมของ Borůvka และอัลกอริทึมการลบแบบย้อนกลับ^{[ 5 ] [ 6 ]}

อัลกอริทึมที่เร็วที่สุดที่ไม่ใช้การสุ่มแบบเปรียบเทียบที่มีความซับซ้อนที่ทราบแล้ว ซึ่งพัฒนาโดยBernard Chazelleนั้น อิงตามsoft heapซึ่งเป็นคิวลำดับความสำคัญโดยประมาณ^{[ 7 ] [ 8 ]}เวลาในการทำงานคือO ( m α( m , n ))โดยที่αคือฟังก์ชันผกผันแบบคลาสสิกของฟังก์ชัน Ackermannฟังก์ชันαเติบโตช้ามาก ดังนั้นในทางปฏิบัติแล้วอาจถือได้ว่าเป็นค่าคงที่ไม่เกิน 4 ดังนั้นอัลกอริทึมของ Chazelle จึงใช้เวลาใกล้เคียงกับเวลาเชิงเส้น

ถ้ากราฟมีความหนาแน่น (เช่นm / n ≥ log log log n )อัลกอริทึมเชิงกำหนดโดย Fredman และ Tarjan จะค้นหา MST ได้ในเวลาO( m ) [ ^{9 ]}อัลกอริทึมนี้ดำเนินการหลายเฟส แต่ละเฟสจะดำเนินการอัลกอริทึมของ Prim หลายครั้ง โดยแต่ละครั้งจะ ^ใช้จำนวนขั้นตอนที่จำกัด เวลาทำงานของแต่ละเฟสคือO( m + n )ถ้าจำนวนจุดยอดก่อนเฟสคือn'จำนวนจุดยอดที่เหลืออยู่หลังจากเฟสจะมีค่าสูงสุด n ' ดังนั้นจึงต้องใช้เฟสอย่างมากที่สุดlog* nเฟส ซึ่งทำให้เวลาทำงานเป็นเชิงเส้นสำหรับกราฟที่มีความหนาแน่น^{[ 4 ]}${\displaystyle {\tfrac {n'}{2^{m/n'}}}}$

มีอัลกอริธึมอื่นๆ ที่ทำงานในเวลาเชิงเส้นบนกราฟหนาแน่น^{[ 7 ] [ 10 ]}

หากน้ำหนักขอบเป็นจำนวนเต็มที่แสดงในรูปแบบไบนารี จะมีอัลกอริทึมเชิงกำหนดที่ทราบกันดีว่าสามารถแก้ปัญหาได้ในการดำเนินการจำนวนเต็มO ( m + n ) ^{[ 11 ]} ยังคงเป็นคำถามที่เปิดอยู่ว่าปัญหาจะสามารถแก้ไข ได้อย่างเป็นระบบสำหรับกราฟทั่วไปในเวลาเชิงเส้นโดยใช้อัลกอริทึมแบบเปรียบเทียบ หรือไม่

อัลกอริทึมเชิงกำหนดเป็นที่รู้จักซึ่งแก้ปัญหาสำหรับกราฟระนาบในเวลาเชิงเส้น^{[ 12 ] [ 13 ]}โดยลักษณะเฉพาะของออยเลอร์ของกราฟระนาบm ≤ 3 n - 6 ∈ O ( n )ดังนั้นสิ่งนี้จึงใช้เวลา O ( n )

กำหนดให้กราฟGซึ่งโหนดและขอบคงที่ แต่ค่าน้ำหนักไม่ทราบ เราสามารถสร้างต้นไม้ตัดสินใจ แบบไบนารี (DT) เพื่อคำนวณต้นไม้ครอบคลุมน้อยที่สุด (MST) สำหรับการเรียงสับเปลี่ยนค่าน้ำหนักใดๆ ก็ได้ แต่ละโหนดภายในของ DT จะมีการเปรียบเทียบระหว่างขอบสองขอบ เช่น "ค่าน้ำหนักของขอบระหว่างxและyมากกว่าค่าน้ำหนักของขอบระหว่างwและzหรือไม่" ลูกสองตัวของโหนดนั้นจะสอดคล้องกับคำตอบที่เป็นไปได้สองคำตอบคือ "ใช่" หรือ "ไม่ใช่" ในแต่ละใบของ DT จะมีรายการของขอบจากGที่สอดคล้องกับ MST ความซับซ้อนของเวลาในการทำงานของ DT คือจำนวนคำถามที่มากที่สุดที่จำเป็นในการค้นหา MST ซึ่งก็คือความลึกของ DT นั่นเอง DT สำหรับกราฟGเรียกว่าเหมาะสมที่สุด (optimal)หากมีความลึกน้อยที่สุดในบรรดา DT ที่ถูกต้องทั้งหมดสำหรับ G

สำหรับจำนวนเต็มr ทุกจำนวน สามารถค้นหาต้นไม้ตัดสินใจที่เหมาะสมที่สุดสำหรับกราฟทั้งหมดที่มี จุดยอด rจุดได้โดยใช้การค้นหาแบบบรูทฟอร์ซการค้นหานี้ดำเนินการในสองขั้นตอน

ก. การสร้าง DT ที่เป็นไปได้ทั้งหมด

• มีกราฟที่แตกต่างกันบน จุดยอด rจุด${\displaystyle 2^{r \choose 2}}$
• สำหรับแต่ละกราฟ สามารถค้นหา MST ได้เสมอโดยใช้ การเปรียบเทียบ r ( r − 1)ครั้ง เช่น โดยใช้ อัลกอริทึม ของPrim
• ดังนั้น ความลึกของ DT ที่เหมาะสมที่สุดจึงน้อยกว่าr ²
• ดังนั้น จำนวนโหนดภายในใน DT ที่เหมาะสมที่สุดจึงน้อยกว่า${\displaystyle 2^{r^{2}}}$
• โหนดภายในแต่ละโหนดจะ เปรียบเทียบขอบสองเส้น จำนวนขอบมีอย่างมากที่สุดr²ดังนั้นจำนวนการเปรียบเทียบที่แตกต่างกันจึงมีอย่าง^{มากที่สุด}r⁴
• ดังนั้น จำนวน DT ที่เป็นไปได้จึงน้อยกว่า

${\displaystyle {(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}.}$

B. การระบุ DT ที่ถูกต้อง ในการตรวจสอบว่า DT นั้นถูกต้องหรือไม่ ควรตรวจสอบกับลำดับการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมดของค่าน้ำหนักของขอบ

• จำนวนการเรียงสับเปลี่ยนดังกล่าวมีค่าสูงสุดเพียง( r ² )!เท่านั้น
• สำหรับแต่ละลำดับการเรียงสับเปลี่ยน ให้แก้ปัญหา MST บนกราฟที่กำหนดโดยใช้อัลกอริทึมที่มีอยู่ใดๆ ก็ได้ แล้วเปรียบเทียบผลลัพธ์กับคำตอบที่ได้จาก DT
• เวลาในการทำงานของอัลกอริทึม MST ใดๆ จะไม่เกินr²ดังนั้นเวลาทั้งหมดที่จำเป็นในการตรวจสอบการเรียงสับเปลี่ยนทั้งหมดจึงไม่เกิน^{( r²} + 1 ) !

ดังนั้น เวลาทั้งหมดที่ต้องการในการค้นหา DT ที่เหมาะสมที่สุดสำหรับกราฟทั้งหมด ที่มี rจุดยอดคือ: ^{[ 4 ]}

${\displaystyle 2^{r \choose 2}\cdot r^{2^{(r^{2}+2)}}\cdot (r^{2}+1)!,}$

ซึ่งน้อยกว่า

${\displaystyle 2^{2^{r^{2}+o(r)}}.}$

Seth PettieและVijaya Ramachandranได้ค้นพบอัลกอริทึมต้นไม้ครอบคลุมขั้นต่ำแบบกำหนดที่เหมาะสมที่สุดที่พิสูจน์ได้^{[ 4 ]}ต่อไปนี้เป็นคำอธิบายแบบย่อของอัลกอริทึม

1. ให้r = log log log nโดยที่nคือจำนวนจุดยอด จงหาต้นไม้ตัดสินใจที่เหมาะสมที่สุดทั้งหมดบน จุดยอด rจุด ซึ่งสามารถทำได้ในเวลาO ( n ) (ดูหัวข้อ ต้นไม้ตัดสินใจด้านบน)
2. แบ่งกราฟออกเป็นส่วนประกอบ โดยแต่ละส่วนประกอบมีจุดยอดไม่เกินrจุด การแบ่งส่วนนี้ใช้โครงสร้างข้อมูลแบบซอฟต์ฮีป (soft heap ) ซึ่งจะ "ทำให้" ขอบจำนวนเล็กน้อยของกราฟ "เสียหาย"
3. ใช้ต้นไม้ตัดสินใจที่เหมาะสมที่สุดเพื่อค้นหา MST สำหรับกราฟย่อยที่ไม่เสียหายภายในแต่ละส่วนประกอบ
4. ย่อส่วนประกอบที่เชื่อมต่อกันแต่ละส่วนซึ่งครอบคลุมโดย MST ให้เหลือเพียงจุดยอดเดียว และใช้อัลกอริธึมใดๆ ที่ใช้ได้กับกราฟหนาแน่นในเวลาO ( m )กับการย่อส่วนของกราฟย่อยที่ไม่เสียหาย
5. เพิ่มขอบที่เสียหายกลับเข้าไปในป่าที่ได้ เพื่อสร้างกราฟย่อยที่รับประกันว่าจะประกอบด้วยต้นไม้แผ่คลุมขั้นต่ำ และมีขนาดเล็กกว่ากราฟเริ่มต้นโดยมีค่าคงที่ จากนั้นใช้ขั้นตอนวิธีที่เหมาะสมที่สุดกับกราฟนี้แบบเรียกซ้ำ

เวลาในการทำงานของทุกขั้นตอนในอัลกอริธึมคือO ( m )ยกเว้นขั้นตอนการใช้ต้นไม้ตัดสินใจเวลาในการทำงานของขั้นตอนนี้ไม่เป็นที่ทราบแน่ชัด แต่ได้รับการพิสูจน์แล้วว่าเป็นเวลาที่เหมาะสมที่สุด กล่าวคือ ไม่มีอัลกอริธึมใดที่ทำงานได้ดีกว่าต้นไม้ตัดสินใจที่เหมาะสมที่สุด ดังนั้น อัลกอริธึมนี้จึงมีคุณสมบัติพิเศษคือ สามารถพิสูจน์ได้ว่าเหมาะสมที่สุดแม้ว่าความซับซ้อนของเวลาในการทำงานจะ ไม่เป็น ที่ทราบแน่ชัดก็ตาม

งานวิจัยยังพิจารณาถึงอัลกอริธึมแบบขนานสำหรับปัญหาต้นไม้ครอบคลุมขั้นต่ำอีกด้วย ด้วยจำนวนโปรเซสเซอร์เชิงเส้น จะสามารถแก้ปัญหาได้ในเวลาO (log n ) ^{[ 14 ] [ 15 ]}

ปัญหาดังกล่าวสามารถแก้ไขได้ในลักษณะแบบกระจาย เช่นกัน หากแต่ละโหนดถือเป็นคอมพิวเตอร์ และไม่มีโหนดใดรู้ข้อมูลใดๆ นอกจากลิงก์ที่เชื่อมต่อของตนเอง ก็ยังสามารถคำนวณต้นไม้ครอบคลุมขั้นต่ำแบบกระจายได้

Alan M. Friezeแสดงให้เห็นว่า เมื่อกำหนดกราฟสมบูรณ์ที่มีnจุดยอด โดยมีน้ำหนักของขอบเป็นตัวแปรสุ่มอิสระที่มีการแจกแจงเหมือนกัน และมี ฟังก์ชันการแจกแจงที่สอดคล้อง กับ แล้วเมื่อnเข้าใกล้+∞น้ำหนักที่คาดหวังของ MST จะเข้าใกล้โดยที่คือฟังก์ชันซีตาของรีมันน์ (หรือกล่าวให้เจาะจงกว่านั้นคือค่าคงที่ของ Apéry ) Frieze และSteeleยังพิสูจน์การลู่เข้าในความน่าจะเป็นด้วยSvante Jansonพิสูจน์ทฤษฎีบทลิมิตกลางสำหรับน้ำหนักของ MST ${\displaystyle F}$${\displaystyle F'(0)>0}$${\displaystyle \zeta (3)/F'(0)}$${\displaystyle \zeta }$${\displaystyle \zeta (3)}$

สำหรับน้ำหนักสุ่มแบบสม่ำเสมอในขนาดที่คาดหวังที่แน่นอนของต้นไม้ครอบคลุมขั้นต่ำได้รับการคำนวณสำหรับกราฟสมบูรณ์ขนาดเล็ก^{[ 16 ]}${\displaystyle [0,1]}$

มีรูปแบบเศษส่วนของ MST ซึ่งอนุญาตให้แต่ละขอบปรากฏ "เป็นเศษส่วน" ได้ ในทางทฤษฎีเซตแผ่คลุมเศษส่วนของกราฟ (V,E) คือฟังก์ชันที่ไม่เป็นลบfบนEโดยที่สำหรับทุกเซตย่อยW ที่ไม่ใช่เซตว่าง ของV (กล่าวคือWไม่ว่างเปล่าและไม่เท่ากับV ) ผลรวมของf ( e ) บนขอบทั้งหมดที่เชื่อมต่อโหนดของWกับโหนดของV \ Wมีค่าอย่างน้อย 1 โดยทั่วไปf ( e ) แทนเศษส่วนของ e ที่อยู่ในเซตแผ่คลุม เซตแผ่คลุมเศษส่วนขั้นต่ำคือเซตแผ่คลุมเศษส่วนที่มีผลรวมน้อยที่สุดเท่าที่จะเป็นไปได้ ${\displaystyle \sum _{e\in E}f(e)\cdot w(e)}$

ถ้าเศษส่วนf ( e ) ถูกบังคับให้อยู่ใน {0,1} แล้วเซตTของขอบที่มี f(e)=1 จะเป็นเซตแผ่คลุม (spanning set) เนื่องจากทุกโหนดหรือกลุ่มย่อยของโหนดเชื่อมต่อกับส่วนที่เหลือของกราฟด้วยขอบอย่างน้อยหนึ่งขอบของTยิ่งไปกว่านั้น ถ้าfทำให้ค่าต่ำสุด เซตแผ่คลุมที่ได้จะเป็นต้นไม้เสมอ เพราะถ้ามีวัฏจักร ขอบหนึ่งสามารถถูกลบออกได้โดยไม่ส่งผลกระทบต่อเงื่อนไขการแผ่คลุม ดังนั้นปัญหาเซตแผ่คลุมเศษส่วนต่ำสุดจึงเป็นการผ่อนคลายของปัญหา MST และอาจเรียกได้ว่าเป็นปัญหา MST เศษส่วน ก็ได้${\displaystyle \sum _{e\in E}f(e)\cdot w(e)}$

ปัญหา MST เศษส่วนสามารถแก้ไขได้ในเวลาพหุนามโดยใช้วิธีวงรี^{[ 17 ] : 248} อย่างไรก็ตาม หากเราเพิ่มข้อกำหนดว่าf ( e ) ต้องเป็นจำนวนเต็มครึ่ง (นั่นคือf ( e ) ต้องอยู่ใน {0, 1/2, 1}) ปัญหาจะกลายเป็น NP - hard ^{[ 17 ] : 248} เนื่องจากรวมถึงกรณีพิเศษของปัญหาวงจรแฮมิลโท เนียน : ในกราฟที่ไม่มีน้ำหนัก n จุดยอด MST จำนวนเต็มครึ่งที่มีน้ำหนัก n สามารถหาได้โดยการกำหนดน้ำหนัก 1/2 ให้กับขอบแต่ละด้านของวงจรแฮมิลโทเนียนเท่านั้น ${\displaystyle n}$${\displaystyle n/2}$

• ต้นไม้สไตเนอร์ของเซตย่อยของจุดยอดคือต้นไม้ขั้นต่ำที่ครอบคลุมเซตย่อยที่กำหนด การค้นหาต้นไม้สไตเนอร์เป็นปัญหา NP- complete ^{[ 18 ]}
• ต้นไม้แผ่คลุมขั้นต่ำk จุด ( k -MST)คือต้นไม้ที่แผ่คลุมกลุ่มย่อยของ จุดยอด kจุดในกราฟด้วยน้ำหนักที่น้อยที่สุด
• เซตของต้นไม้แผ่ขยายที่เล็กที่สุด k ต้นคือเซตย่อยของ ต้นไม้แผ่ขยาย k ต้น (จากต้นไม้แผ่ขยายที่เป็นไปได้ทั้งหมด) โดยที่ไม่มีต้นไม้แผ่ขยายใดนอกเซตย่อยนี้มีน้ำหนักน้อยกว่า^{[ 19 ] [ 20 ] [ 21 ]} (โปรดทราบว่าปัญหานี้ไม่เกี่ยวข้องกับ ต้นไม้แผ่ขยายขั้นต่ำ k ต้น )
• ต้นไม้แผ่คลุมขั้นต่ำแบบยุคลิดคือต้นไม้แผ่คลุมของกราฟที่มีค่าน้ำหนักของขอบสอดคล้องกับระยะทางแบบยุคลิดระหว่างจุดยอด ซึ่งเป็นจุดในระนาบ (หรือในอวกาศ)
• ต้นไม้แผ่คลุมขั้นต่ำแบบเส้นตรงคือ ต้นไม้แผ่คลุมของกราฟที่มีค่าน้ำหนักของขอบสอดคล้องกับระยะทางเชิงเส้นตรงระหว่างจุดยอด ซึ่งเป็นจุดในระนาบ (หรือในอวกาศ)
• ต้นไม้ครอบคลุมขั้นต่ำแบบกระจาย (Distributed Minimum Spanning Tree: MST) เป็นส่วนขยายของ MST ไปสู่แบบจำลองแบบกระจายโดยที่แต่ละโหนดถือเป็นคอมพิวเตอร์ และไม่มีโหนดใดรู้ข้อมูลใดๆ นอกจากลิงก์ที่เชื่อมต่อกับตัวเองเท่านั้น นิยามทางคณิตศาสตร์ของปัญหาเหมือนกัน แต่มีวิธีการแก้ปัญหาที่แตกต่างกัน
• ต้นไม้ครอบคลุมขั้นต่ำที่มีความจุคือต้นไม้ที่มีโหนดที่ทำเครื่องหมายไว้ (จุดกำเนิดหรือราก) และต้นไม้ย่อยแต่ละต้นที่แนบกับโหนดนั้นมีโหนด ไม่เกิน c โหนด โดย cเรียกว่าความจุของต้นไม้ การแก้ปัญหา CMST อย่างเหมาะสมนั้นเป็นปัญหาNP-hard [ ^{22 ]}แต่ฮิวริสติกที่ดี เช่น Esau-Williams และ Sharma สามารถสร้างโซลูชันที่ใกล้เคียงกับค่าที่เหมาะสมที่สุดได้ในเวลาพหุ^นาม
• ต้นไม้แผ่คลุมขั้นต่ำที่มีข้อจำกัดด้านดีกรีคือMST ที่แต่ละจุดยอดเชื่อมต่อกับจุดยอดอื่นไม่เกินdจุด สำหรับค่าd ที่กำหนดให้ กรณีd  = 2 เป็นกรณีพิเศษของปัญหาพนักงานขายเดินทางดังนั้น ต้นไม้แผ่คลุมขั้นต่ำที่มีข้อจำกัดด้านดีกรีจึงเป็นปัญหาNP-hardโดยทั่วไป
• โครงสร้างแบบต้นไม้ (Arborescence)เป็นรูปแบบหนึ่งของ MST สำหรับกราฟแบบมีทิศทางสามารถแก้ไขได้ในเวลาที่เหมาะสมโดยใช้อัลกอริทึม Chu–Liu/ Edmonds${\displaystyle O(E+V\log V)}$
• ต้นไม้ครอบคลุมสูงสุด (Maximum Spanning Tree)คือต้นไม้ครอบคลุมที่มีน้ำหนักมากกว่าหรือเท่ากับน้ำหนักของต้นไม้ครอบคลุมอื่นๆ ทุกต้น ต้นไม้ดังกล่าวสามารถค้นพบได้ด้วยอัลกอริทึม เช่น อัลกอริทึมของ Prim หรือ Kruskal หลังจากคูณน้ำหนักของขอบด้วย −1 และแก้ปัญหา MST บนกราฟใหม่ เส้นทางในต้นไม้ครอบคลุมสูงสุดคือเส้นทางที่กว้างที่สุดในกราฟระหว่างจุดปลายทั้งสอง: ในบรรดาเส้นทางที่เป็นไปได้ทั้งหมด เส้นทางนี้จะเพิ่มน้ำหนักของขอบที่มีน้ำหนักน้อยที่สุดให้สูงสุด^{[ 23 ]} ต้นไม้ครอบคลุม สูงสุดมีการประยุกต์ใช้ใน อัลกอริทึมการ แยกวิเคราะห์สำหรับภาษาธรรมชาติ^{[ 24 ]}และในอัลกอริทึมการฝึกอบรมสำหรับฟิลด์สุ่มแบบมีเงื่อนไข
• โครงสร้างหลักอัลตราเมตริกเป็นโครงสร้างหลักระยะทาง ที่เล็กที่สุดที่เป็นไปได้ ของกราฟทิศทางและกราฟไม่ทิศทางที่มีน้ำหนักเป็นบวก^{[ 25 ]} โครงสร้างหลักอัลตราเมตริกคือการรวมกันของป่าครอบคลุมขั้นต่ำในกราฟไม่ทิศทาง (น้ำหนักเป็นบวก) และให้การวางนัยทั่วไปของต้นไม้ครอบคลุมขั้นต่ำไปยังกราฟทิศทาง ซึ่งแตกต่างจากกราฟเทียบเท่าขั้นต่ำและโครงสร้างต้นไม้ครอบคลุมขั้นต่ำ โดยจะรักษาเส้นทางที่สั้นที่สุดสูงสุด-ต่ำสุดทั้งหมดและความสอดคล้องตามกฎของเดอ มอร์แกน^{[ 26 ]}
• ปัญหาMST แบบไดนามิกเกี่ยวข้องกับการอัปเดต MST ที่คำนวณไว้ก่อนหน้านี้หลังจากการเปลี่ยนแปลงน้ำหนักขอบในกราฟเดิมหรือการแทรก/ลบจุดยอด^{[ 27 ] [ 28 ] [ 29 ]}
• ปัญหาต้นไม้แผ่ขยายที่มีป้ายกำกับขั้นต่ำคือการค้นหาต้นไม้แผ่ขยายที่มีประเภทของป้ายกำกับน้อยที่สุด หากขอบแต่ละขอบในกราฟเชื่อมโยงกับป้ายกำกับจากชุดป้ายกำกับที่จำกัดแทนที่จะเป็นน้ำหนัก^{[ 30 ]}
• ขอบคอขวดคือขอบที่มีน้ำหนักสูงสุดในต้นไม้แผ่ขยาย ต้นไม้แผ่ขยายจะเป็นต้นไม้แผ่ขยายคอขวดขั้นต่ำ (หรือMBST ) หากกราฟไม่มีต้นไม้แผ่ขยายที่มีน้ำหนักขอบคอขวดน้อยกว่า MST จำเป็นต้องเป็น MBST (พิสูจน์ได้โดยคุณสมบัติการตัด ) แต่ MBST ไม่จำเป็นต้องเป็น MST ^{[ 31 ] [ 32 ]}
• เกมต้นไม้แผ่ขยายต้นทุนต่ำสุดเป็นเกมร่วมมือกันที่ผู้เล่นต้องแบ่งปันต้นทุนในการสร้างต้นไม้แผ่ขยายที่เหมาะสมที่สุดร่วมกัน
• ปัญหาการออกแบบเครือข่ายที่เหมาะสมที่สุดคือ ปัญหาการคำนวณเซตที่ประกอบด้วยต้นไม้แผ่คลุม (spanning tree) ภายใต้ข้อจำกัดด้านงบประมาณ โดยที่ผลรวมของเส้นทางที่สั้นที่สุดระหว่างโหนดทุกคู่มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้

ต้นไม้ครอบคลุมขั้นต่ำมีการประยุกต์ใช้โดยตรงในการออกแบบเครือข่าย รวมถึงเครือข่ายคอมพิวเตอร์เครือข่ายโทรคมนาคมเครือข่ายการขนส่งเครือข่ายประปาและโครงข่ายไฟฟ้า (ซึ่งเป็นสิ่งที่คิดค้นขึ้นเป็นครั้งแรก ดังที่กล่าวไว้ข้างต้น) ^{[ 33 ]}มีการเรียกใช้เป็นซับรูทีนในอัลกอริธึมสำหรับปัญหาอื่นๆ รวมถึงอัลกอริธึม Christofidesสำหรับการประมาณปัญหาพนักงานขายเดินทาง [ ^{34 ]} การประมาณปัญหาการตัดขั้นต่ำแบบหลายเทอร์มินัล (ซึ่งเทียบเท่ากับ ปัญหาการไหลสูงสุดในกรณีเทอร์มินัลเดียว⁾ [ ^{35 ] และ} การประมาณการ จับคู่ ที่สมบูรณ์แบบ ที่ มีน้ำหนักต้นทุนต่ำสุด^{[ 36 ]}

การประยุกต์ใช้งานเชิงปฏิบัติอื่นๆ ที่อิงตามต้นไม้เชื่อมโยงขั้นต่ำ ได้แก่:

• อนุกรมวิธาน^{[ 37 ]}
• การวิเคราะห์คลัสเตอร์ : การจัดกลุ่มจุดในระนาบ^{[ 38 ]}การจัดกลุ่มแบบเชื่อมโยงเดี่ยว (วิธีการจัดกลุ่มแบบลำดับชั้น ) ^{[ 39 ]}การจัดกลุ่มตามทฤษฎีกราฟ^{[ 40 ]}และการจัดกลุ่มข้อมูลการแสดงออกของยีน^{[ 41 ]}
• การสร้างต้นไม้สำหรับการกระจายเสียงในเครือข่ายคอมพิวเตอร์^{[ 42 ]}
• การลงทะเบียนภาพ^{[ 43 ]}และการแบ่งส่วน^{[ 44 ]} – ดูการแบ่งส่วนตามต้นไม้ครอบคลุมขั้นต่ำ
• การสกัดคุณลักษณะเส้นโค้งในคอมพิวเตอร์วิชั่น^{[ 45 ]}
• การจดจำลายมือของนิพจน์ทางคณิตศาสตร์^{[ 46 ]}
• การออกแบบวงจร : การนำการคูณค่าคงที่หลายค่าที่มีประสิทธิภาพมาใช้ ดังที่ใช้ในตัวกรองการตอบสนองแบบอิมพัลส์จำกัด^{[ 47 ]}
• การแบ่งเขตพื้นที่ทางสังคมและภูมิศาสตร์ คือการจัดกลุ่มพื้นที่เข้าเป็นภูมิภาคที่ต่อเนื่องกันและเป็นเนื้อเดียวกัน^{[ 48 ]}
• การเปรียบเทียบข้อมูลพิษวิทยาทางนิเวศวิทยา^{[ 49 ]}
• การสังเกตเชิงโทโพโลยีในระบบไฟฟ้า^{[ 50 ]}
• การวัดความเป็นเนื้อเดียวกันของวัสดุสองมิติ^{[ 51 ]}
• การควบคุมกระบวนการมินิแม็กซ์^{[ 52 ]}
• ต้นไม้ครอบคลุมขั้นต่ำยังสามารถใช้เพื่ออธิบายตลาดการเงินได้อีกด้วย^{[ 53 ] [ 54 ]}สามารถสร้างเมทริกซ์สหสัมพันธ์ได้โดยการคำนวณสัมประสิทธิ์สหสัมพันธ์ระหว่างหุ้นสองตัวใดๆ เมทริกซ์นี้สามารถแสดงในเชิงโทโพโลยีเป็นเครือข่ายที่ซับซ้อน และสามารถสร้างต้นไม้ครอบคลุมขั้นต่ำเพื่อแสดงภาพความสัมพันธ์ได้

• Otakar Boruvka เรื่องปัญหาต้นไม้ขยายขั้นต่ำ (แปลทั้งเอกสาร ความคิดเห็น ประวัติ) (2000) Jaroslav Nešetřil , Eva Milková, Helena Nesetrilová (ส่วนที่ 7 ให้อัลกอริทึมของเขา ซึ่งดูเหมือนเป็นลูกผสมระหว่าง Prim's และ Kruskal's)
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. RivestและClifford Stein . Introduction to Algorithms , ฉบับพิมพ์ครั้งที่สอง. MIT Press และ McGraw-Hill, 2001. ISBN 0-262-03293-7บทที่ 23: ต้นไม้แผ่คลุมขั้นต่ำ (Minimum Spanning Trees), หน้า 561–579
• Eisner, Jason (1997). อัลกอริทึมที่ทันสมัยที่สุดสำหรับต้นไม้ครอบคลุมขั้นต่ำ: การอภิปรายเชิงแนะนำ . ต้นฉบับ, มหาวิทยาลัยเพนซิลเวเนีย, เมษายน. 78 หน้า.
• Kromkowski, John David. "ยังคงไม่ละลายหายไปหลังจากผ่านไปหลายปี" ใน Annual Editions, Race and Ethnic Relations, 17/e (2009 McGraw Hill) (การใช้แผนผังต้นไม้เชื่อมโยงขั้นต่ำเป็นวิธีการวิเคราะห์ทางประชากรศาสตร์ของความหลากหลายทางชาติพันธุ์ทั่วสหรัฐอเมริกา)

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับต้นไม้เชื่อมโยงขั้นต่ำ (Minimum spanning trees )

• Boost Graph Library ถูกพัฒนาขึ้นโดยใช้ภาษา BGL
• คลังเก็บอัลกอริทึมของสโตนีบรูก - โค้ดต้นไม้ครอบคลุมขั้นต่ำ
• พัฒนาโดยใช้ QuickGraph สำหรับ .Net