ดีกรี

     2.  ดีกรี
     ดีกรีของจุดยอด

         จะเห็นว่า เส้นเชื่อมที่เกิดกับจุดยอด a ได้แก่ เส้นเชื่อม ab และ ac ดังนั้น จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด a คือ 2 สำหรับจุดยอด b มีเส้นเชื่อมที่เกิดกับจุดยอด b ได้แก่ เส้นเชื่อม ba, bc และ bb เป็นวงวน เกิดกับจุดยอด b กรณีที่มีเส้นเชื่อมเป็นวงวนจะกำหนดให้นับจำนวนเส้นเชื่อมที่เกิดกับจุดยอดนั้นเพิ่มขึ้น โดยให้นับเส้นเชื่อมที่เป็นวงวน 1 วง วงวนเป็น 2 ดังนั้นจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด b จึงเป็น 4บทนิยาม   ดีกรี (Degree) ของจุดยอด V ในกราฟ คือ จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด v
            จะเห็นว่า เส้นเชื่อมที่เกิดกับจุดยอด a ได้แก่ เส้นเชื่อม ab และ ac ดังนั้น จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด a คือ 2 สำหรับจุดยอด b มีเส้นเชื่อมที่เกิดกับจุดยอด b ได้แก่ เส้นเชื่อม ba, bc และ bb เป็นวงวน เกิดกับจุดยอด b กรณีที่มีเส้นเชื่อมเป็นวงวนจะกำหนดให้นับจำนวนเส้นเชื่อมที่เกิดกับจุดยอดนั้นเพิ่มขึ้น โดยให้นับเส้นเชื่อมที่เป็นวงวน 1 วง วงวนเป็น 2 ดังนั้นจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด b จึงเป็น 4บทนิยาม   ดีกรี (Degree) ของจุดยอด V ในกราฟ คือ จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด v

    ต่อไปจะเรียกจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอดว่า  ดีกรี ใช้สัญลักษณ์ deg v แทนดีกรีของจุดยอด v ตัวอย่างที่ 1 กำหนดกราฟ ดังรูป

    จากรูปจะได้ว่า  deg a = 2

                        deg b = 1

                        deg c = 3

                        deg d = 4
ตัวอย่างที่ 2 กำหนดกราฟ ดังรูป

            จากรูปจะได้ว่า    deg a = 5 

                                        deg b = 5

                                        deg c = 5

                                        deg d = 4

 พิสูจน์ เนื่องจากเส้นเชื่อมแต่ละเส้นในกราฟเกิดกับจุดยอดเป็นจำนวน 2 ครั้ง ดังนั้นเส้นเชื่อมแต่ละเส้น    

             จะถูกนับ 2 ครั้งในผลรวมของดีกรีของจุดยอดทุกจุด  

             นั่นคือ ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ 

    

       ข้อสังเกต  ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเป็นจำนวนคู่เสมอ

ตัวอย่างที่ 3 จงหาจำนวนเส้นเชื่อมของกราฟที่มีผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับ 22

       วิธีทำ   สมมติว่า กราฟมีเส้นเชื่อม n เส้น

                   จากทฤษฎีบท 1 ผลรวมของดีกรีของจุดยอดทุดจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ                 

                   ดังนั้น 22 = 2n

                   นั่นคือ      n = 11

                   สรุปได้ว่า กราฟมีเส้นเชื่อม11 เส้น

ตัวอย่างที่ 4 จงหาจำนวนจุดยอดของกราฟที่มีเส้นเชื่อม 15 เส้น และมีจุดยอด 3 จุด ที่มีดีกรี 4 ส่วนจุดยอดที่เหลือมีดีกรี 3

     วิธีทำ ให้ n เป็นจำนวนจุดยอดที่มีดีกรี 3

              ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟ คือ (3)(4) + 3n

              จากทฤษฎีบท 1 ผลรวมของดีกรีของจุดยอดทุดจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ

              ดังนั้น (3)(4) + 3 

              เพราะฉะนั้น n = 6

              ดังนั้น จำนวนจุดยอดทั้งหมดของกราฟ คือ 3 + 6 = 9 จุด

        วิธีทำ สมมติว่า มีดีกรีที่มีจุดยอด 4 จุด และดีกรีของจุดยอดเท่ากับ 1, 1, 2 และ 3

                 ดังนั้น ผลรวมของดีกรีของจุดยอดทุกจุด คือ 1 + 1 + 2 + 3 = 7

                 ซึ่งเป็นจำนวนคี่ ขัดแย้งกับทฤษฎีบท 1

                 ดังนั้น เป็นไปไม่ได้ที่จะมีกราฟดังกล่าว  

ตัวอย่างที่ 5  จงพิจารณาว่าเป็นไปได้หรือไม่ว่า จะมีกราฟที่มีจุดยอด 4 จุด และดีกรีของจุดยอด คือ 1, 1, 2 และ 3 ตามลำดับ

             ตัวอย่างที่ 6 กำหนดกราฟ ดังรูป    

        จากรูปจะได้ว่า   deg a = 2

                                    deg b = 3

                                    deg c = 0

                                    deg d = 3

                                    deg e = 2

                    ดังนั้น  จุดยอด a, c และ e เป็นจุดยอดคู่

                                จุดยอด b และ d เป็นจุดยอดคี่

             ทฤษฎีบท2  ทุกกราฟจะมีจุดยอดคี่เป็นจำนวนคู่

        พิสูจน์  ให้ G เป็นกราฟ

                    ถ้า G ไม่มีจุดยอดคี่ นั่นคือ G มีจำนวนจุดยอดคี่เป็นศูนย์

                    

                    จึงได้ว่าG มีจำนวนจุดยอดคี่เป็นจำนวนคู่

                    ต่อไปสมมติว่า กราฟ G มีจุดยอดคี่ k จุด คือ v1, v2, v3, …, vk

                    และมีจุดยอดคู่ n จุด คือ u1, u2, u3, …, un จากทฤษฎีบท 1

                    จะได้ว่า (deg v1 + deg v2 + … + deg vk) + (deg u1 + deg u2 + … + deg un) = 2q

                    เมื่อ q คือ จำนวนเส้นเชื่อมของ G

                    ดังนั้น deg v1 + deg v2 + … + deg vk = 2q - (deg u1 + deg u2 + … + deg un)

                    เนื่องจาก deg u1 + deg u2 + … + deg un ต่างก็เป็นจำนวนคู่

                    ดังนั้น 2q - (deg u1 + deg u2 + … + deg un) เป็นจำนวนคู่

                    นั่นคือ deg v1 + deg v2 + … + deg vk เป็นจำนวนคู่

                    แต่เนื่องจาก deg v1 + deg v2 + … + deg vk เป็นจำนวนคี่

                    เพราะฉะนั้น k จะต้องเป็นจำนวนคู่ จึงจะทำให้ deg v1 + deg v2 + … + deg vk

                    เป็นจำนวนคู่ สรุปได้ว่า กราฟ G มีจุดยอดคี่เป็นจำนวนคู่

                    จากตัวอย่างที่ 5 เราให้เหตุผลโดยอาศัยทฤษฎีบท 2 ดังนี้

                    สมมติว่า มีกราฟที่มีจุดยอด 4 จุด และดีกรีของจุดยอด คือ 1, 1, 2 และ 3

                    จะได้ว่า กราฟมีจุดยอดคี่เป็นจำนวน 3 จุด ซึ่งขัดแย้งกับทฤษฎีบท 2 สรุปได้ว่า ไม่มีกราฟที่มีสมบัติดังกล่าว

ตัวอย่างที่ 7  ถ้าในห้องประชุมแห่งหนึ่งมีผู้เข้าร่วมประชุมทั้งหมด 23 คน เป็นไปได้หรือไม่

                     ว่าผู้เข้าร่วมประชุมแต่ละคนจับมือทักทายผู้เข้าร่วมประชุมคนอื่นเพียง 7 คนเท่านั้น

     วิธีทำ  แปลงปัญหาดังกล่าวเป็นกราฟ โดยให้จุดยอดแทนผู้เข้าร่วมประชุม และเส้นเชื่อมแทน การจับมือทักทายของผู้เข้าร่วมประชุม

               จะได้ว่า กราฟนี้มีจุดยอด 23 จุด และจุดยอดแต่ละจุดมีดีกรี 7 

               นั้นคือ กราฟมีจุดยอดคี่เป็นจำนวน 23 จุด ซึ่งเป็นจำนวนคี่ ขัดแย้งกับทฤษฎีบท 2

               ดังนั้น เป็นไปไม่ได้ที่ผู้เข้าร่วมประชุมแต่ละคนจับมือกับคนอื่นเพียง 7 เท่านั้น