ในทางคณิตศาสตร์ต้นไม้แผ่ขยายคอขวดขั้นต่ำ (MBST)ในกราฟแบบไม่มีทิศทาง คือต้นไม้แผ่ขยายที่ขอบที่แพงที่สุดมีราคาถูกที่สุดเท่าที่จะเป็นไปได้ ขอบคอขวดคือขอบที่มีน้ำหนักมากที่สุดในต้นไม้แผ่ขยาย ต้นไม้แผ่ขยายจะเป็นต้นไม้แผ่ขยายคอขวดขั้นต่ำ หากกราฟนั้นไม่มีต้นไม้แผ่ขยายที่มีน้ำหนักขอบคอขวดน้อยกว่า^{[ 1 ]}สำหรับกราฟแบบมีทิศทางปัญหาที่คล้ายกันนี้เรียกว่าต้นไม้แผ่ขยายคอขวดขั้นต่ำ (MBSA )

ในกราฟที่ไม่มีทิศทางG ( V ,  E )และฟังก์ชันw  :  E  →  Rให้Sเป็นเซตของต้นไม้แผ่ขยายทั้งหมดT _iให้B ( T _i ) เป็นขอบที่มีน้ำหนักสูงสุดสำหรับต้นไม้แผ่ขยายT _i ใดๆ เรากำหนดเซตย่อยของต้นไม้แผ่ขยายคอขวดขั้นต่ำ^S ′โดยที่สำหรับทุกT _j  ∈  S ′และT _k  ∈  SเรามีB ( T _j ) ≤  B ( T _k )สำหรับทุกiและ  k ^{[ 2} ]

กราฟทางด้านขวาเป็นตัวอย่างของ MBST โดยเส้นสีแดงในกราฟก่อให้เกิด MBST ของ G ( V ,  E )

โครงสร้างต้นไม้แบบมีทิศทาง (Arborescence) ของกราฟGคือต้นไม้แบบมีทิศทางของGซึ่งประกอบด้วยเส้นทางแบบมีทิศทางจากโหนดL ที่กำหนด ไปยังแต่ละโหนดของเซตย่อยV ′ ของV  \{ L }โหนดLเรียกว่ารากของโครงสร้างต้นไม้แบบมีทิศทาง โครงสร้างต้นไม้แบบมีทิศทางจะเป็นโครงสร้างต้นไม้แบบมีทิศทางครอบคลุม (Spanning Arborescence) ถ้าV ′ =  V  \{ L }ในกรณีนี้ MBST คือโครงสร้างต้นไม้แบบมีทิศทางครอบคลุมที่มีขอบคอขวดน้อยที่สุด MBST ในกรณีนี้เรียกว่าโครงสร้างต้นไม้แบบมีทิศทางครอบคลุมที่มีขอบคอขวดน้อยที่สุด (Minimum Bottleneck Spanning Arborescence หรือ MBSA)

กราฟทางด้านขวาเป็นตัวอย่างของ MBSA โดยเส้นขอบสีแดงในกราฟก่อให้เกิด MBSA ของ G ( V ,  E )

MST (หรือต้นไม้ครอบคลุมขั้นต่ำ ) จำเป็นต้องเป็น MBST แต่ MBST ไม่จำเป็นต้องเป็น MST ^{[ 3 ]}

^{[ 4 ]}

ในปี 1978 Camerini ได้เสนอ^{[ 5 ]}อัลกอริทึมที่ใช้ในการสร้างต้นไม้ครอบคลุมคอขวดขั้นต่ำ (MBST) ในกราฟแบบไม่มีทิศทาง เชื่อมต่อ และมีน้ำหนัก ขอบที่กำหนดไว้ โดยจะแบ่งขอบออกเป็นสองชุดเท่าๆ กัน น้ำหนักของขอบในชุดหนึ่งจะไม่เกินน้ำหนักของขอบในอีกชุดหนึ่ง หาก มี ต้นไม้ครอบคลุมอยู่ในกราฟย่อยที่ประกอบด้วยขอบในชุดขอบที่มีขนาดเล็กกว่าเท่านั้น ก็จะคำนวณ MBST ในกราฟย่อยนั้น ซึ่ง MBST ของกราฟย่อยนั้นก็คือ MBST ของกราฟดั้งเดิมนั่นเอง หาก ไม่มี ต้นไม้ครอบคลุมอยู่ ก็จะรวมส่วนประกอบที่ไม่เชื่อมต่อกันแต่ละส่วนเข้าเป็นจุดยอดใหญ่ใหม่ จากนั้นคำนวณ MBST ในกราฟที่สร้างขึ้นจากจุดยอดใหญ่เหล่านี้และขอบในชุดขอบที่มีขนาดใหญ่กว่า ป่าในแต่ละส่วนประกอบที่ไม่เชื่อมต่อกันเป็นส่วนหนึ่งของ MBST ในกราฟดั้งเดิม ทำซ้ำกระบวนการนี้จนกว่าจะเหลือจุดยอด (ใหญ่) สองจุดในกราฟ และจะต้องเพิ่มขอบเดียวที่มีน้ำหนักน้อยที่สุดระหว่างจุดยอดทั้งสองนั้น MBST จะถูกค้นพบโดยประกอบด้วยขอบทั้งหมดที่พบในขั้นตอนก่อนหน้า^{[ 4 ]}

^{ขั้น ตอน}ดังกล่าวมีพารามิเตอร์อินพุตสองตัวGคือกราฟwคืออาร์เรย์น้ำหนักของขอบทั้งหมดในกราฟG [ ^{6 ]}

ฟังก์ชัน MBST(กราฟG , น้ำหนักw ) E ← เซตของขอบของG ถ้า | E | = 1 ให้คืนค่าE มิฉะนั้นA ←ขอบครึ่งหนึ่งในEที่มีน้ำหนักไม่น้อยกว่าค่ามัธยฐาน B ← E - A F ← ป่าของG Bถ้าFเป็นต้นไม้แผ่คลุมให้คืนค่า MBST( G B , w ) มิฉะนั้นให้คืนค่า MBST(( G A ) η , w ) F${\displaystyle \cup }$

ใน ( G _A ) ข้างต้น _ηคือกราฟย่อยที่ประกอบด้วยจุดยอดหลัก (โดยถือว่าจุดยอดในส่วนประกอบที่ไม่เชื่อมต่อกันเป็นจุดยอดเดียว) และขอบใน A

อัลกอริทึมนี้ทำงานใน เวลา O ( E ) โดยที่Eคือจำนวนขอบ ขอบเขตนี้บรรลุได้ดังนี้:

• แบ่งออกเป็นสองชุดโดยใช้อัลกอริธึมการหาค่ามัธยฐานในO ( E )
• การค้นหาป่าในO ( E )
• เมื่อพิจารณาขอบครึ่งวงใน E ในแต่ละรอบการทำซ้ำ T(E)=T(E/2)+O(E) ตามทฤษฎีบทมาสเตอร์ความซับซ้อนของเวลาโดยรวมคือO ( E )

หมายเหตุ : การประมาณเวลาในการทำงานคือ O(E) แทนที่จะเป็น O(E+V) (การท่องกราฟใช้เวลา O(E+V)) แต่ในกรณีนี้กราฟเชื่อมต่อกัน ดังนั้น V-1<=E ดังนั้น O(E+V)=O(E)

ในตัวอย่างต่อไปนี้ เส้นขอบสีเขียวใช้ในการสร้าง MBST และพื้นที่สีแดงประแสดงถึงจุดยอดพิเศษที่เกิดขึ้นระหว่างขั้นตอนของอัลกอริทึม

	อัลกอริทึมนี้แบ่งขอบออกเป็นสองกลุ่มเท่าๆ กัน โดยพิจารณาจากน้ำหนัก ขอบสีเขียวคือขอบที่มีน้ำหนักน้อยที่สุด
	เนื่องจากมีต้นไม้แผ่ขยายอยู่ในกราฟย่อยที่สร้างขึ้นจากขอบในชุดขอบที่เล็กกว่าเท่านั้น ทำซ้ำขั้นตอนการหา MBST ในกราฟย่อยนี้
	เนื่องจากไม่มีต้นไม้แผ่ขยายในกราฟย่อยปัจจุบันที่สร้างขึ้นจากขอบในชุดขอบที่เล็กกว่าในปัจจุบัน จึงรวมจุดยอดของส่วนประกอบที่ไม่เชื่อมต่อกันเข้ากับจุดยอดหลัก (แสดงด้วยพื้นที่สีแดงประ) แล้วจึงหาต้นไม้แผ่ขยายขนาดใหญ่ (MBST) ในกราฟย่อยที่สร้างขึ้นจากจุดยอดหลักและขอบในชุดขอบที่ใหญ่กว่า ป่าที่เกิดขึ้นภายในส่วนประกอบที่ไม่เชื่อมต่อกันแต่ละส่วนจะเป็นส่วนหนึ่งของ MBST ในกราฟดั้งเดิม
	ทำซ้ำขั้นตอนที่คล้ายกันโดยการรวมจุดยอดเพิ่มเติมเข้าด้วยกันเป็นจุดยอดหลัก
	ในที่สุดอัลกอริทึมก็จะได้ MBST โดยใช้ขอบที่ค้นพบระหว่างการทำงานของอัลกอริทึม

มีอัลกอริธึมสองแบบที่ใช้ได้สำหรับกราฟแบบมีทิศทาง ได้แก่ อัลกอริธึมของ Camerini สำหรับการค้นหา MBSA และอีกอัลกอริธึมหนึ่งจาก Gabow และ Tarjan ^{[ 4 ]}

สำหรับกราฟแบบมีทิศทาง อัลกอริทึมของ Camerini มุ่งเน้นไปที่การค้นหาเซตของขอบที่จะมีค่าใช้จ่ายสูงสุดเป็นค่าใช้จ่ายคอขวดของ MBSA โดยทำโดยการแบ่งเซตของขอบEออกเป็นสองเซตAและBและรักษาเซตTซึ่งเป็นเซตที่ทราบว่าG _Tไม่มีอาร์โบเรสเซนซ์แบบครอบคลุม เพิ่มTด้วยBเมื่อใดก็ตามที่อาร์โบเรสเซนซ์สูงสุดของG ( B  ∪  T ) ไม่ใช่อาร์โบเรสเซนซ์แบบครอบคลุมของGมิฉะนั้นเราจะลดEด้วย  Aความซับซ้อนของเวลาทั้งหมดคือO ( E  log  E ) ^{[ 5 ] [ 4 ]}

ฟังก์ชัน MBSA( G , w , T ) คือE ← เซตของขอบของG ถ้า | E − T | > ​​1 แล้วA ← UH(ET) B ← ( E − T) − A F ← BUSH( G BUT ) ถ้าFเป็นอาร์โบเรสเซนซ์แผ่ขยายของ G แล้ว ส ← เอฟ MBSA(( G แต่ ), w , T ) อย่างอื่น MBSA(G, w , TUB ); 

1. T แทนเซตย่อยของ E ซึ่งทราบว่า G _Tไม่ประกอบด้วยโครงสร้างกิ่งก้านสาขาที่เชื่อมต่อกันโดยมีรากอยู่ที่โหนด “a” ในตอนเริ่มต้น T ว่างเปล่า
2. UH รับเซตของขอบ (E−T) ใน G และส่งคืน A ⊂ (E−T) โดยที่:
   1. ${\displaystyle |A|=\left\lfloor {\frac {(|ET|)}{2}}\right\rfloor }$
   2. W _a ≥ W _bสำหรับ a ∈ A และ b ∈ B
3. BUSH(G) ส่งคืนโครงสร้างกิ่งก้านสาขาที่ใหญ่ที่สุดของ G ที่รากอยู่ที่โหนด “a”
4. ผลลัพธ์สุดท้ายจะเป็น S

	หลังจากรันอัลกอริทึมรอบแรก เราได้ค่าFและFไม่ใช่กลุ่มต้นไม้แผ่ขยายของGดังนั้นเราจึงรันโค้ด⁠ ⁠${\displaystyle MBSA(G,w,T\cup B).}$
	ในการวนซ้ำครั้งที่สอง เราได้ผลลัพธ์ว่าและก็ไม่ใช่โครงสร้างกิ่งก้านสาขาที่แผ่ขยายของG เช่นกัน ดังนั้นเราจึงรันโค้ด${\displaystyle F'}$${\displaystyle F'}$${\displaystyle MBSA(G,w,T'\cup B')}$
	ในการวนซ้ำครั้งที่สาม เราจะได้และเป็นโครงสร้างกิ่งก้านสาขาที่แผ่ขยายของGดังนั้นเราจึงรันโค้ด${\displaystyle F''}$${\displaystyle F''}$${\displaystyle MBSA(G_{T''\cup B''},w,T'')}$
	เมื่อเรารันอัลกอริธึม ค่าที่ได้จะเท่ากับ 1 ซึ่งไม่เกิน 1 ดังนั้นอัลกอริธึมจึงส่งค่ากลับเป็น และผลลัพธ์สุดท้ายคือ ${\displaystyle MBSA(G_{T''\cup B''},w,T'')}$${\displaystyle |ET|}$${\displaystyle S=F''}$

GabowและTarjanได้นำเสนอการปรับเปลี่ยนอัลกอริทึมของ Dijkstraสำหรับเส้นทางที่สั้นที่สุดจากแหล่งกำเนิดเดียวที่สร้าง MBSA อัลกอริทึมของพวกเขาทำงานใน เวลา O ( E  +  V  log  V ) หากใช้ฮีปฟิโบนาชชี^{[ 7 ]}

สำหรับกราฟG(V,E) นั้น Fคือกลุ่มของจุดยอดในV ในขั้นต้นF = { s } โดยที่sคือจุดเริ่มต้นของกราฟGและc ( s ) = -∞ 1 ฟังก์ชัน MBSA-GT( G , w, T )ทำซ้ำ 2 ครั้ง (V) 3 เลือกvที่มีค่าc ( v ) น้อยที่สุดจากF ; 4. ลบออกจากF ; 5 สำหรับขอบทุกเส้น ( v, w ) ให้ทำ 6 ถ้าw ∉ Fหรือ ∉ Tree แล้ว 7 เพิ่มw ลงในF; 8 c ( w ) = c ( v,w ); 9 p ( w ) = v ; 10 มิฉะนั้น 11 ถ้าw ∈ Fและc(w) > c(v, w) แล้ว 12 c ( w ) = c ( v, w ); 13 p ( w ) = v ; 

ตัวอย่างต่อไปนี้แสดงให้เห็นว่าอัลกอริธึมทำงานอย่างไร

แนวทางอื่นที่เสนอโดย Tarjan และ Gabow ที่มีขอบเขตO ( E  log ^*  V )สำหรับกราฟเบาบาง ซึ่งคล้ายกับอัลกอริทึมของ Camerini สำหรับ MBSA มาก แต่แทนที่จะแบ่งเซตของขอบออกเป็นสองเซตในแต่ละรอบการทำซ้ำ จะมีการแนะนำ K ( i )โดยที่iคือจำนวนการแบ่งที่เกิดขึ้น หรือกล่าวอีกนัยหนึ่งคือหมายเลขการทำซ้ำ และK ( i )เป็นฟังก์ชันเพิ่มขึ้นที่แสดงถึงจำนวนเซตที่แบ่งแล้วที่ควรมีในแต่ละรอบการทำซ้ำK ( i ) = 2 ^{k ( i  − 1)}โดยที่k (1) = 2อัลกอริทึมจะค้นหาλ ^*ซึ่งเป็นค่าของขอบคอขวดใน MBSA ใดๆ หลังจากที่พบλ ^{* แล้ว arborescence ที่ครอบคลุมใด ๆ} ใน G ( λ ^* )จะเป็น MBSA โดยที่G ( λ ^* )คือกราฟที่ต้นทุนของขอบทั้งหมด≤  λ ^* [ ^{4 ] [ 7 ]}