ระดับขั้น

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

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

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

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

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

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

ระดับขั้นเข้าเขียนแทนด้วย  และระดับขั้นออกเขียนแทนด้วย 

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

กรณีพิเศษ

 จุดเอกเทศ  จุดยอดที่  เรียกว่า จุดเอกเทศ
 ใบ  จุดยอดที่  เรียกว่า ใบ (leaf)
 กราฟปรกติ  ถ้าจุดยอดทุกจุดในกราฟมีระดับขั้นเท่ากับ k กราฟนี้จะเรียกว่า กราฟปรกติ-k และกราฟนี้จะมีระดับขั้นเท่ากับ k
 แหล่งต้นทาง  จุดยอดที่  เรียกว่า แหล่งต้นทาง (source)
 แหล่งปลายทาง  จุดยอดที่  เรียกว่า แหล่งปลายทาง (sink)

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

ทฤษฎีบทกล่าวไว้ว่า กำหนดกราฟ 

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

ทฤษฎีกราฟ

อ้างอิง