k -spanner ของต้นไม้ ( หรือเรียกสั้น ๆ ว่าk -spanner ) ของกราฟ คือต้นไม้ย่อยที่แผ่คลุมกราฟซึ่งระยะห่างระหว่างจุดยอดทุกคู่มีค่าไม่เกิน เท่าของระยะห่าง ระหว่างจุดยอด ทั้งสองในกราฟ ${\displaystyle G}$${\displaystyle T}$${\displaystyle G}$${\displaystyle k}$${\displaystyle G}$

มีเอกสารหลายฉบับที่เขียนเกี่ยวกับเรื่อง tree spanners หนึ่งในนั้นคือเอกสารชื่อTree Spanners ^{[ 1 ]}ที่เขียนโดยนักคณิตศาสตร์ Leizhen Cai และDerek Corneilซึ่งสำรวจปัญหาเชิงทฤษฎีและเชิงอัลกอริทึมที่เกี่ยวข้องกับ tree spanners ข้อสรุปบางส่วนจากเอกสารนั้นแสดงไว้ด้านล่างคือจำนวนจุดยอดของกราฟเสมอ และคือจำนวนขอบของกราฟ ${\displaystyle n}$${\displaystyle m}$

1. ต้นไม้ 1-spanner หากมีอยู่จริง จะเป็นต้นไม้แผ่คลุมขั้นต่ำและสามารถค้นหาได้ในเวลา (ในแง่ของความซับซ้อน) สำหรับกราฟถ่วงน้ำหนัก โดยที่นอกจากนี้ กราฟถ่วงน้ำหนักที่ยอมรับต้นไม้ 1-spanner ทุกกราฟจะมีต้นไม้แผ่คลุมขั้นต่ำที่ไม่ซ้ำกันเพียงต้นเดียว${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$${\displaystyle \beta (m,n)=\min \left\{i\mid \log ^{i}n\leq m/n\right\}}$
2. สามารถสร้าง tree 2-spanner ได้ในเวลาที่กำหนด และปัญหา tree -spanner เป็นปัญหาNP-completeสำหรับจำนวนเต็มคงที่ใดๆ${\displaystyle {\คณิตศาสตร์ {O}}(m+n)}$${\displaystyle t}$${\displaystyle t>3}$
3. ความซับซ้อนในการหาต้นไม้แผ่ขยายขั้นต่ำในกราฟระบุทิศทางคือโดยที่คือฟังก์ชันผกผันของฟังก์ชัน Ackermann${\displaystyle {\mathcal {O}}((m+n)\cdot \alpha (m+n,n))}$${\displaystyle \alpha (m+n,n)}$
4. ค่า 1-spanner ขั้นต่ำของกราฟถ่วงน้ำหนักสามารถหาได้จากเวลา${\displaystyle {\mathcal {O}}(mn+n^{2}\log(n))}$
5. สำหรับจำนวนตรรกยะคงที่ใดๆการตรวจสอบว่ากราฟถ่วงน้ำหนักมี t-spanner ของต้นไม้หรือไม่นั้น เป็นปัญหา NP-complete แม้ว่าน้ำหนักของขอบทั้งหมดจะเป็นจำนวนเต็มบวกก็ตาม${\displaystyle t>1}$
6. สามารถค้นหา tree spanner (หรือ minimum tree spanner) ของ digraph ได้ในเวลาเชิงเส้น
7. กราฟระบุทิศทางจะมีตัวเชื่อมต้นไม้ได้มากที่สุดหนึ่งตัว
8. สแปนเนอร์ต้นไม้เสมือนของไดกราฟแบบถ่วงน้ำหนักสามารถพบได้ในเวลา${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$

• ประแจกราฟ
• ประแจเรขาคณิต