ระดับขั้น

จากวิกิพีเดีย สารานุกรมเสรี

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

สารบัญ

[แก้] กราฟไม่ระบุทิศทาง

กราฟที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น
ขยาย
กราฟที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น

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

กราฟในรูปทางขวามีระดับขั้นดังนี้

จุดยอด ระดับขั้น
1 2
2 3
3 2
4 3
5 3
6 1

[แก้] กราฟระบุทิศทาง

กราฟระบุทิศทางที่มีจุดยอด 4 จุด และเส้นเชื่อม 5 เส้น
ขยาย
กราฟระบุทิศทางที่มีจุดยอด 4 จุด และเส้นเชื่อม 5 เส้น

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

ระดับขั้นเข้าเขียนแทนด้วย deg + (v) และระดับขั้นออกเขียนแทนด้วย deg (v)

กราฟในรูปทางขวามีระดับขั้นดังนี้

จุดยอด ระดับขั้นเข้า ระดับขั้นออก
1 0 2
2 2 0
3 2 2
4 1 1

[แก้] กรณีพิเศษ

[แก้] จุดเอกเทศ

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

[แก้] ใบ

กราฟไม่ระบุทิศทาง มีจุดยอด 4, 5, 6, 7, 10, 11, 12 เป็นใบ
ขยาย
กราฟไม่ระบุทิศทาง มีจุดยอด 4, 5, 6, 7, 10, 11, 12 เป็นใบ

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

[แก้] กราฟปรกติ

ถ้าจุดยอดทุกจุดในกราฟมีระดับขั้นเท่ากับ k กราฟนี้จะเรียกว่า กราฟปรกติ-k และกราฟนี้จะมีระดับขั้นเท่ากับ k

[แก้] แหล่งต้นทาง

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

[แก้] แหล่งปลายทาง

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

[แก้] ทฤษฎีบท

กำหนดกราฟ G=(V,E) จะได้

\sum_{v \in V} \deg(v) = 2|E|

เพราะว่าเส้นเชื่อมแต่ละเส้นจะต่อกับจุดยอด 2 จุดเสมอ สูตรนี้ทำให้กล่าวได้ว่า กราฟใดๆจะมีจำนวนจุดยอดที่มีระดับขั้นเป็นจำนวนคี่อยู่เป็นจำนวนคู่เสมอ

ภาษาอื่น