ผลต่างระหว่างรุ่นของ "จุดยอด (ทฤษฎีกราฟ)"

เนื้อหาที่ลบ เนื้อหาที่เพิ่ม

ในบรรทัด

รุ่นแก้ไขเมื่อ 23:17, 23 พฤศจิกายน 2565

กราฟซึ่งมี 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.
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.

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

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

@@ บรรทัด 20: / บรรทัด 20: @@
 == อ้างอิง ==
+{{reflist}}
 * {{cite journal
-  | last = Gallo
+  | last1 = Gallo
-  | first = Giorgio
+  | first1 = Giorgio
-  | authorlink = Giorgio Gallo
   | last2 = Pallotino
   | first2 = Stefano
+  | title = Shortest path algorithms
-  | authorlink2 = Stefano Pallottino
-  | title =  Shortest Path Algorithms
   | journal = Annals of Operations Research
   | volume = 13
@@ บรรทัด 33: / บรรทัด 33: @@
   | pages = 1–79 <!-- the inline reference refers to page 4 -->
   | year = 1988
-  | doi =  10.1007/BF02288320
+  | doi = 10.1007/BF02288320
-  | ref=harv
+  | s2cid = 62752810
-  }}
+ }}
-* [[Claude Berge|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)
+* [[Claude Berge|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)
-* {{Cite book | last=Chartrand | first=Gary | authorlink=Gary Chartrand | coauthors= | title=Introductory graph theory | url=https://archive.org/details/introductorygrap0000char | date=1985 | publisher=Dover | location=New York  | isbn=0-486-24775-9 | pages=}}
+* {{Cite book | last=Chartrand | first=Gary | author-link=Gary Chartrand | title=Introductory graph theory | date=1985 | publisher=Dover | location=New York | isbn=0-486-24775-9 | url-access=registration | url=https://archive.org/details/introductorygrap0000char }}
-* {{Cite book | author=Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. | authorlink= | coauthors= | title=Graph theory, 1736-1936 | date=1986 | publisher=Clarendon Press | location=Oxford [Oxfordshire]  | isbn=0-19-853916-9 | pages=}}
+* {{Cite book |author1=Biggs, Norman |author2=Lloyd, E. H. |author3=Wilson, Robin J. | title=Graph theory, 1736-1936 | date=1986 | publisher=Clarendon Press | location=Oxford [Oxfordshire] | isbn=0-19-853916-9 |title-link=Graph Theory, 1736–1936}}
-* {{Cite book | last=Harary | first=Frank | authorlink=Frank Harary | coauthors= | title=Graph theory | url=https://archive.org/details/graphtheory0000hara | date=1969 | publisher=Addison-Wesley Publishing | location=Reading, Mass.  | isbn=0-201-41033-8 | pages=}}
+* {{Cite book | last=Harary | first=Frank | author-link=Frank Harary | title=Graph theory | date=1969 | publisher=Addison-Wesley Publishing | location=Reading, Mass. | isbn=0-201-41033-8 }}
-* {{Cite book | author=Harary, Frank; Palmer, Edgar M. | authorlink= | coauthors= | title=Graphical enumeration | date=1973 | publisher=New York, Academic Press | location= | isbn=0-12-324245-2 | pages=}}
+* {{Cite book |author1=Harary, Frank |author2=Palmer, Edgar M. | title=Graphical enumeration | date=1973 | publisher=New York, Academic Press | isbn=0-12-324245-2 }}
 == แหล่งข้อมูลอื่น ==