ในคณ ตศาสตร สาขาทฤษฎ กราฟ ระด บข น degree ของ จ ดยอด v ใน กราฟ เป นจำนวนของ เส นเช อม ซ งต อก บจ ดยอด v สำหร บเส นเช อมท

ในคณิตศาสตร์สาขาทฤษฎีกราฟ ระดับขั้น (degree) ของ จุดยอด v ใน กราฟ เป็นจำนวนของ เส้นเชื่อม ซึ่งต่อกับจุดยอด v (สำหรับเส้นเชื่อมที่เป็น ให้นับ 2 ครั้ง) ดีกรีของจุดยอด $v$ เขียนแทนในทางคณิตศาสตร์ว่า $\deg(v).$ ดีกรีสูงสุดของกราฟ G เขียนแทนด้วย Δ(G) และดีกรีต่ำสุดของกราฟเขียนแทนด้วย δ(G)

กราฟไม่ระบุทิศทาง

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

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

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

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

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

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

ระดับขั้นเข้าเขียนแทนด้วย $\deg ^{+}(v)$ และระดับขั้นออกเขียนแทนด้วย $\deg ^{-}(v)$

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

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

กรณีพิเศษ

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

จุดเอกเทศ: จุดยอดที่ $\deg(v)=0$ เรียกว่า จุดเอกเทศ
ใบ: จุดยอดที่ $\deg(v)=1$ เรียกว่า ใบ (leaf)
กราฟปรกติ: ถ้าจุดยอดทุกจุดในกราฟมีระดับขั้นเท่ากับ k กราฟนี้จะเรียกว่า และกราฟนี้จะมีระดับขั้นเท่ากับ k
แหล่งต้นทาง: จุดยอดที่ $\deg ^{+}(v)=0$ เรียกว่า แหล่งต้นทาง (source)
แหล่งปลายทาง: จุดยอดที่ $\deg ^{-}(v)=0$ เรียกว่า แหล่งปลายทาง (sink)

ทฤษฎีการจับมือ

ทฤษฎีบทกล่าวไว้ว่า กำหนดกราฟ $G=(V,E)$

\sum _{v\in V}\deg(v)=2|E|\,.

จากทฤษฎีบทนี้ทำให้กล่าวได้ว่า สำหรับกราฟใดๆ จำนวนของจุดยอดที่มีดีกรีคี่จะมีเป็นจำนวนคู่เสมอ ทฤษฎีบทนี้รู้จักในอีกชื่อว่า ทฤษฎีการจับมือ. ชื่อนี้มาจากปัญหาทางคณิตศาสตร์ที่ว่าให้พิสูจน์ว่าในกลุ่มของผู้คนนั้น ผู้ที่จับมือกับคนอื่นเป็นจำนวนคี่ครั้งจะมีอยู่เป็นจำนวนคู่คนเสมอ

อ้างอิง

Diestel p.5

[1] Diestel p.5