fbpx
วิกิพีเดีย

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

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

กราฟซึ่งมี 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.CS1 maint: ref=harv (link)
  • 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.CS1 maint: multiple names: authors list (link)
  • 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.CS1 maint: multiple names: authors list (link)

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

ดยอด, ทฤษฎ, กราฟ, ในทฤษฎ, กราฟ, ดยอด, หร, โหนด, เป, นส, วนประกอบอย, างหน, งท, ทำให, เก, ดกราฟ, กราฟไม, ระบ, ศทางประกอบด, วยเซตของจ, ดยอดและเซตของเส, นเช, อม, ไม, นด, บของจ, ดยอด, ในขณะท, กราฟระบ, ศทางประกอบด, วยเซตของจ, ดยอดและเซตของเส, นเช, อมท, ศทาง, นด, บขอ. inthvsdikraf cudyxd hrux ohnd epnswnprakxbxyanghnungthithaihekidkraf krafimrabuthisthangprakxbdwyestkhxngcudyxdaelaestkhxngesnechuxm khuimxndbkhxngcudyxd inkhnathikrafrabuthisthangprakxbdwyestkhxngcudyxdaelaestkhxngesnechuxmthimithisthang khuxndbkhxngcudyxd krafsungmi 6 cudyxdaela 7 esnechuxm aelacudyxdhmayelkh 6 epncudyxdplay sahrbkhwamhmayxun duthi cudyxd aekkhwamkakwm cudyxd w eriykwaxyu prachid adjacent kbcudyxd v odythi v imich w ktxemuxkrafnnmiesnechuxm v w aelaephuxnbankhxngcudyxd v khuxcudyxdthnghmdthiprachidkb vpraephthkhxngcudyxd aekikhcudyxdthitidkbesnechuxmeriykwa cudyxdplay end vertices khxngesnechuxm aelaesnechuxm tx incident kbcudyxdplayesmxdikri khxngcudyxdinkraf khuxcanwnkhxngesnechuxmthitidkbcudyxdnn cudyxdoddediyw epncudyxdthimidikri 0 aelaimtidkbesnechuxmidely cudyxdplay epncudyxdthimidikri 1sahrbkrafrabuthisthangyngsamarthaebngdikrixxkepn 2 praephthkhuxdikriekha canwnesnechuxmthiphungekhacudyxdnn kbdikrixxk canwnesnechuxmthiphungxxkcudyxdnn cudyxdtnthang khuxcudyxdthimidikriekha 0 swn cudyxdplaythang khuxcudyxdthimidikrixxk 0xangxing aekikhGallo Giorgio Pallotino Stefano 1988 Shortest Path Algorithms Annals of Operations Research 13 1 1 79 doi 10 1007 BF02288320 CS1 maint ref harv link Berge Claude Theorie des graphes et ses applications Collection Universitaire de Mathematiques II Dunod Paris 1958 viii 277 pp English edition Wiley 1961 Methuen amp 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 CS1 maint multiple names authors list link 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 CS1 maint multiple names authors list link aehlngkhxmulxun aekikhexrik dbebilyu iwssitn Graph Vertex cakaemthewild ekhathungcak https th wikipedia org w index php title cudyxd thvsdikraf amp oldid 4710650, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,

บทความ

, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม