จุดยอด (ทฤษฎีกราฟ)

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

จุดยอด w เรียกว่าอยู่ ประชิด (adjacent) กับจุดยอด v โดยที่ v ไม่ใช่ w ก็ต่อเมื่อกราฟนั้นมีเส้นเชื่อม (v,w) และเพื่อนบ้านของจุดยอด v คือจุดยอดทั้งหมดที่ประชิดกับ v

 ประเภทของจุดยอด 
จุดยอดที่ติดกับเส้นเชื่อมเรียกว่า จุดยอดปลาย (end vertices) ของเส้นเชื่อม
และเส้นเชื่อม ต่อ (incident) กับจุดยอดปลายเสมอ

ดีกรี ของจุดยอดในกราฟ คือจำนวนของเส้นเชื่อมที่ติดกับจุดยอดนั้น
จุดยอดโดดเดี่ยว เป็นจุดยอดที่มีดีกรี 0 และไม่ติดกับเส้นเชื่อมใดเลย
จุดยอดปลาย เป็นจุดยอดที่มีดีกรี 1

สำหรับกราฟระบุทิศทางยังสามารถแบ่งดีกรีออกเป็น 2 ประเภทคือดีกรีเข้า (จำนวนเส้นเชื่อมที่พุ่งเข้าจุดยอดนั้น ๆ) 
กับดีกรีออก (จำนวนเส้นเชื่อมที่พุ่งออกจุดยอดนั้น
ๆ) 
จุดยอดต้นทาง คือ จุดยอดที่มีดีกรีเข้า 0 ส่วน จุดยอดปลายทาง คือ จุดยอดที่มีดีกรีออก 0

 อ้างอิง 


 Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)





 แหล่งข้อมูลอื่น 

หมวดหมู่:วัตถุทฤษฎีกราฟ