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

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

กราฟซึ่งมี 6 จุดยอดและ 7 เส้นเชื่อม และจุดยอดหมายเลข 6 เป็นจุดยอดปลาย

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

ประเภทของจุดยอด

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

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

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

อ้างอิง

• Gallo, Giorgio; Pallotino, Stefano (1988). "Shortest path algorithms". Annals of Operations Research. 13 (1): 1–79. doi:10.1007/BF02288320. S2CID 62752810.
• , 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)
• (1985). Introductory graph theory. New York: Dover. ISBN .
• Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). . Oxford [Oxfordshire]: Clarendon Press. ISBN .
• (1969). Graph theory. Reading, Mass.: Addison-Wesley Publishing. ISBN .
• Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. New York, Academic Press. ISBN .

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

• เอริก ดับเบิลยู. ไวส์สไตน์, "Graph Vertex" จากแมทเวิลด์.