ระดับขั้น

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

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

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

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

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

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

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

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

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

เส้นเชื่อมในกราฟระบุทิศทาง จะประกอบด้วยจุดยอดปลาย 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 และกราฟนี้จะมีระดับขั้นเท่ากับ k
แหล่งต้นทาง 
จุดยอดที่ \deg^+(v)=0 เรียกว่า แหล่งต้นทาง (source)
แหล่งปลายทาง 
จุดยอดที่ \deg^-(v)=0 เรียกว่า แหล่งปลายทาง (sink)

ทฤษฎีการจับมือ[แก้]

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

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

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

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

อ้างอิง[แก้]

  1. Diestel p.5