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

จากวิกิพีเดีย สารานุกรมเสรี
กราฟซึ่งมี 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. 
  • 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. 

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