ระยะทาง (ทฤษฎีกราฟ)

พื้นที่ตัวชี้วัดที่กำหนดไว้กว่าชุดของจุดในแง่ของระยะทางในกราฟที่กำหนดไว้กว่าชุดที่เรียกว่าตัวชี้วัดกราฟ ชุดจุดยอด (ของกราฟที่ไม่ระบุทิศทาง) และฟังก์ชันระยะทางจะสร้างปริภูมิเมตริก หากเชื่อมต่อกราฟแล้วเท่านั้น

ความเบี้ยว ${\displaystyle \epsilon (v)}$ ของจุดยอด ${\displaystyle v}$ คือระยะห่างสูงสุดระหว่าง ${\displaystyle v}$และจุดยอดอื่นๆ ในสัญลักษณ์ที่เป็น${\displaystyle \epsilon (v)=\max _{u\in V}d(v,u)}$. สามารถคิดได้ว่าโหนดอยู่ห่างจากโหนดที่อยู่ห่างจากโหนดมากที่สุดในกราฟเท่าใด

รัศมี ${\displaystyle r}$ ของกราฟคือความเยื้องศูนย์กลางขั้นต่ำของจุดยอดใดๆ หรือในสัญลักษณ์ ${\displaystyle r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u)}$.

เส้นผ่าศูนย์กลาง ${\displaystyle d}$ของกราฟคือความเยื้องศูนย์กลางสูงสุดของจุดยอดใดๆ ในกราฟ นั่นคือ,${\displaystyle d}$ คือระยะห่างสูงสุดระหว่างจุดยอดคู่ใดๆ หรืออีกทางหนึ่ง ${\displaystyle d=\max _{v\in V}\epsilon (v)}$. เพื่อหาขนาดเส้นผ่าศูนย์กลางของกราฟเป็นครั้งแรกพบว่าเส้นทางที่สั้นที่สุดระหว่างคู่ของแต่ละจุด ความยาวสูงสุดของเส้นทางเหล่านี้คือเส้นผ่านศูนย์กลางของกราฟ

ยอดกลางในกราฟของรัศมี${\displaystyle r}$ เป็นคนหนึ่งที่มีความเยื้องศูนย์คือ ${\displaystyle r}$—นั่นคือจุดยอดที่บรรลุรัศมีหรือจุดยอดเท่ากัน ${\displaystyle v}$ ดังนั้น ${\displaystyle \epsilon (v)=r}$.

จุดสุดยอดอุปกรณ์ต่อพ่วงในกราฟของเส้นผ่าศูนย์กลาง${\displaystyle d}$ คือความห่างไกล ${\displaystyle d}$จากจุดยอดอื่นๆ นั่นคือจุดยอดที่มีเส้นผ่านศูนย์กลาง อย่างเป็นทางการ${\displaystyle v}$ เป็นอุปกรณ์ต่อพ่วง if ${\displaystyle \epsilon (v)=d}$.

จุดสุดยอดหลอกอุปกรณ์ต่อพ่วง ${\displaystyle v}$ มีคุณสมบัติที่สำหรับจุดยอดใดๆ ${\displaystyle u}$, ถ้า ${\displaystyle v}$ อยู่ไกลจาก ${\displaystyle u}$ ให้ได้มากที่สุดแล้ว ${\displaystyle u}$ อยู่ไกลจาก ${\displaystyle v}$เป็นไปได้. อย่างเป็นทางการ จุดยอดuคืออุปกรณ์ต่อพ่วงเทียม ถ้าสำหรับแต่ละจุดยอดvกับ${\displaystyle d(u,v)=\epsilon (u)}$ ถือ ${\displaystyle \epsilon (u)=\epsilon (v)}$.

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

กราฟดังกล่าวว่าสำหรับคู่ของจุดทุกมีความเป็นเส้นทางที่สั้นที่สุดที่ไม่ซ้ำกันเชื่อมต่อพวกเขาเรียกว่ากราฟ Geodetic ตัวอย่างเช่นต้นไม้ทั้งหมดมีลักษณะทางภูมิศาสตร์ ^[4]