ระดับขั้น
จากวิกิพีเดีย สารานุกรมเสรี
ในคณิตศาสตร์สาขาทฤษฎีกราฟ ระดับขั้น (degree) ของจุดยอด v คือจำนวนของเส้นเชื่อมที่เชื่อมจุดยอด v (ถ้าเป็นวงวน (loop) ให้นับ 2 ครั้ง) เราเขียน deg(v) แทนระดับขั้นของ v
สารบัญ |
[แก้] กราฟไม่ระบุทิศทาง
ระดับขั้นของจุดยอดในกราฟไม่ระบุทิศทาง คือ จำนวนเส้นเชื่อมที่ต่อกับจุดยอดนั้น ซึ่งถ้าเป็นเส้นเชื่อมที่เป็นวงวน (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 |
[แก้] กรณีพิเศษ
[แก้] จุดเอกเทศ
จุดยอดที่ deg(v) = 0 เรียกว่า จุดเอกเทศ
[แก้] ใบ
จุดยอดที่ deg(v) = 1 เรียกว่า ใบ (leaf)
[แก้] กราฟปรกติ
ถ้าจุดยอดทุกจุดในกราฟมีระดับขั้นเท่ากับ k กราฟนี้จะเรียกว่า กราฟปรกติ-k และกราฟนี้จะมีระดับขั้นเท่ากับ k
[แก้] แหล่งต้นทาง
จุดยอดที่ deg + (v) = 0 เรียกว่า แหล่งต้นทาง (source)
[แก้] แหล่งปลายทาง
จุดยอดที่ deg − (v) = 0 เรียกว่า แหล่งปลายทาง (sink)
[แก้] ทฤษฎีบท
กำหนดกราฟ G=(V,E) จะได้
เพราะว่าเส้นเชื่อมแต่ละเส้นจะต่อกับจุดยอด 2 จุดเสมอ สูตรนี้ทำให้กล่าวได้ว่า กราฟใดๆจะมีจำนวนจุดยอดที่มีระดับขั้นเป็นจำนวนคี่อยู่เป็นจำนวนคู่เสมอ