แนวเดินแผ่ทั่วที่สั้นที่สุด

บทคัดย่อ

แนวเดินแผ่ทั่วของกราฟ คือ แนวเดินที่บรรจุจุดยอดทุกจุดในกราฟ จุดประสงค์ของบทความนี้ เพื่อหาจำนวนเส้นเชื่อมของแนวเดินแผ่ทั่วที่สั้นที่สุดในกราฟเชื่อมโยง G ที่มีจุดยอด n จุด ขอบเขตของการศึกษา คือ สนใจจุดยอดเริ่มต้นและสุดท้าย, สนใจจุดยอดเริ่มต้น และไม่สนใจจุดยอดเริ่มต้นและสุดท้าย
ให้ u, v ∈ V(G) กำหนด w₂ (G) คือ จำนวนเส้นเชื่อมของแนวเดินแผ่ทั่วที่สั้นที่สุดที่มีจุดปลายที่ u และ v เมื่อ u ≠ v,
w₁ (G) คือ จำนวนเส้นเชื่อมของแนวเดินแผ่ทั่วที่สั้นที่สุดโดยเริ่มต้นที่ v ,
และ w₀ (G) คือ จำนวนเส้นเชื่อมของแนวเดินแผ่ทั่วที่สั้นที่สุด
จะเห็นได้ชัดว่า w_i (G₁) = 0 และ w_i (G₂) = 1 สำหรับ i = 0,1,2 เมื่อ G_j คือกราฟเชื่อมโยงที่มีจุดยอด j = 1 หรือ 2 จุด สำหรับ n ≥ 3
เราหาขอบเขตแต่ละค่าซึ่งทุกขอบเขตเป็นค่าที่ดีที่สุด และสรุปความสัมพันธ์แต่ละกรณีได้ดังนี้
n - 1 ≤ w₂ (G) ≤ 2n-3;
n - 1 ≤ w₁ (G) ≤ 2n-3;
n - 1 ≤ w₀ (G) ≤ 2n-4,
และสำหรับ k ∈ N ที่อยู่ระหว่างค่าขอบเขตบนและขอบเขตล่างของ w_i สำหรับ i = 0,1,2 จะมีกราฟ G ที่มีจุดยอด n จุด ที่ w_i (G) = k