ระดับขั้น

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

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

 

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

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

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

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

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

 

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

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

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

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

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

กรณีพิเศษ

 

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

จุดเอกเทศ

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

ใบ

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

กราฟปรกติ

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

แหล่งต้นทาง

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

แหล่งปลายทาง

จุดยอดที่ ${\displaystyle \deg ^{-}(v)=0}$  เรียกว่า แหล่งปลายทาง (sink)

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

ดูบทความหลักที่: ทฤษฎีการจับมือ

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

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

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

อ้างอิง

1. Diestel p.5