เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
|
|
|
{{รอการตรวจสอบ}}
ใน[[คณิตศาสตร์]]สาขา[[ทฤษฎีกราฟ]] '''ระดับขั้น''' (degree) ของ [[จุดยอด (ทฤษฎีกราฟ)|จุดยอด]] ''v'' คือใน [[กราฟ (คณิตศาสตร์)|กราฟ]] เป็นจำนวนของ [[เส้นเชื่อมที่ (ทฤษฎีกราฟ)|เส้นเชื่อม]] ซึ่งต่อกับจุดยอด ''v'' (ถ้าสำหรับเส้นเชื่อมที่เป็น[[วงวน]]ห่วง (loopทฤษฎีกราฟ)|ห่วง]] ให้นับ 2 ครั้ง) เรา<ref>Diestel p.5</ref> ดีกรีของจุดยอด <math>v</math> เขียนแทนในทางคณิตศาสตร์ว่า <math>\deg(v).</math> ดีกรีสูงสุดของกราฟ ''G'' เขียนแทนระดับขั้นด้วย Δ(''G'') และดีกรีต่ำสุดของกราฟเขียนแทนด้วย δ(''vG'')
==กราฟไม่ระบุทิศทาง==
จุดยอดที่ <math>\deg^-(v)=0</math> เรียกว่า '''แหล่งปลายทาง''' (sink)
==ทฤษฎีการจับมือ==
==ทฤษฎีบท==
{{main|ทฤษฎีการจับมือ}}
ทฤษฎีบทกล่าวไว้ว่า กำหนดกราฟ <math>G=(V, E)</math>
:<math>\sum_{v \in V} \deg(v) = 2|E| \, .</math> ▼กำหนดกราฟ ''G''=(''V'',''E'') จะได้
▲:<math>\sum_{v \in V} \deg(v) = 2|E|</math>
เพราะว่าเส้นเชื่อมแต่ละเส้นจะต่อกับจุดยอด 2 จุดเสมอ สูตรจากทฤษฎีบทนี้ทำให้กล่าวได้ว่า สำหรับกราฟใดๆจะมี จำนวนของจุดยอดที่มีระดับขั้นดีกรีคี่จะมีเป็นจำนวนคู่เสมอ ทฤษฎีบทนี้รู้จักในอีกชื่อว่า [[[ทฤษฎีการจับมือ]]. ชื่อนี้มาจากปัญหาทางคณิตศาสตร์ที่ว่าให้พิสูจน์ว่าในกลุ่มของผู้คนนั้น ผู้ที่จับมือกับคนอื่นเป็นจำนวนคี่ครั้งจะมีอยู่เป็นจำนวนคู่คนเสมอ
[[หมวดหมู่:ทฤษฎีกราฟ]]
|
