วันศุกร์ที่ 31 สิงหาคม พ.ศ. 2550

ระดับขั้น (ทฤษฎีกราฟ)
ในคณิตศาสตร์สาขาทฤษฎีกราฟ ระดับขั้น (degree) ของจุดยอด v คือจำนวนของเส้นเชื่อมที่เชื่อมจุดยอด v (ถ้าเป็นวงวน (loop) ให้นับ 2 ครั้ง) เราเขียน deg(v) แทนระดับขั้นของ v

กราฟไม่ระบุทิศทาง
เส้นเชื่อมในกราฟระบุทิศทาง จะประกอบด้วยจุดยอดปลาย 2 ประเภทคือ หัว (จุดยอดปลายที่มีลูกศร) และ หาง ระดับขั้นเข้า คือ ผลบวกของจำนวนหัวที่ชี้เข้ามา และ ระดับขั้นออก คือ ผลบวกของจำนวนหางที่ชี้เข้ามา
ระดับขั้นเข้าเขียนแทนด้วย deg (v)
กราฟในรูปทางขวามีระดับขั้นดังนี้

กราฟระบุทิศทาง

กรณีพิเศษ
จุดยอดที่ deg(v) = 0 เรียกว่า จุดเอกเทศ

จุดเอกเทศ
จุดยอดที่ deg(v) = 1 เรียกว่า ใบ (leaf)

แหล่งต้นทาง
จุดยอดที่ deg (v) = 0 เรียกว่า แหล่งปลายทาง (sink)

ไม่มีความคิดเห็น: