จุดยอด (ทฤษฎีกราฟ)
ในทฤษฎีกราฟ จุดยอด หรือ โหนด เป็นส่วนประกอบอย่างหนึ่งที่ทำให้เกิดกราฟ กราฟไม่ระบุทิศทางประกอบด้วยเซตของจุดยอดและเซตของเส้นเชื่อม (คู่ไม่อันดับของจุดยอด) ในขณะที่กราฟระบุทิศทางประกอบด้วยเซตของจุดยอดและเซตของเส้นเชื่อมที่มีทิศทาง (คู่อันดับของจุดยอด)
จุดยอด 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.
- 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)
- Chartrand, Gary (1985). Introductory graph theory. New York: Dover. ISBN 0-486-24775-9.
- Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.
- Harary, Frank (1969). Graph theory. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8.
- Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. New York, Academic Press. ISBN 0-12-324245-2.