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

2.2   ดีกรีของจุดยอด  

            พิจารณากราฟต่อไปนี้

 

 

จุดยอด

จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด

a

b

c

d

2

4

4

2

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

            ต่อไปจะเรียกจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอดว่า <b>ดีกรี</b>

 

บทนิยาม  

            ดีกรี (degree) ของจุดยอด v ในกราฟคือ จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด v 

            ใช้สัญลักษณ์ deg v แทนดีกรีของจุดยอด v


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

รูปที่ 1

 

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

                                       deg b = 1

                                       deg c = 3

                                       deg d = 4

 

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

รูปที่ 2

 

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

                                       deg b = 5

                                       deg c = 5

                                       deg d = 4

            สังเกตว่า   deg a + deg b + deg c + deg d = 16 และกราฟมีจำนวนเส้นเชื่อมทั้งหมด 8 เส้น

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

 

ทฤษฎีบท 1  

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

พิสูจน์  

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

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

ข้อสังเกต

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

 

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

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

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

                          สองเท่าของจำนวนเส้นเชื่อมในกราฟ

                          ดังนั้น   22   =   2n

                          นั่นคือ    n   =   11

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

 

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

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

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

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

                          สองเท่าของจำนวนเส้นเชื่อมในกราฟ

                          ดังนั้น          (3)(4) +3n   =   2(15)

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

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

 

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

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

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

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

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

บทนิยาม  

              จุดยอดที่มีดีกรีเป็นจำนวนคู่ เรียกว่า จุดยอดคู่ (even vertex)

               จุดยอดที่มีดีกรีเป็นจำนวนคี่ เรียกว่า จุดยอดคี่ (odd vertex)

 

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

รูปที่ 3

 

            จากรูป   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)   เป็นจำนวนคู่

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

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

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

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

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

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

                            สรุปได้ว่าไม่มีกราฟที่มีสมบัติดังกล่าว

 

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

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

                          เส้นเชื่อมแทนการจับมือทักทายของผู้เข้าร่วมประชุม

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

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

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

 

ตัวอย่างที่  8  จงพิจารณาว่าเป็นไปได้หรือไม่ที่จังหวัดหนึ่งซึ่งมี 5 อำเภอ โดยมี 3 อำเภอซึ่งแต่ละอำเภอมีถนนเชื่อมกับอำเภออื่นเพียง 3 สาย มี 1 อำเภอ ที่มีถนนเชื่อมกับอำเภออื่นเพียง 2 สาย และมี 1 อำเภอมีถนนเชื่อมกับอำเภออื่นที่เหลือทุกอำเภอ

วิธีทำ   แปลงปัญหาดังกล่าวเป็นกราฟ โดยให้จุดยอดแทนอำเภอ และ

                          เส้นเชื่อมแทนถนนที่เชื่อมระหว่างสองอำเภอใดๆ

                          นั่นคือ กราฟนี้มีจุดยอด 5 จุด และมีดีกรี 3, 3, 3, 2, 4 จะได้ว่า

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

                         ดังนั้นเป็นไปไม่ได้ที่จังหวัดหนึ่งที่มี 5 อำเภอ จะมี 3 อำเภอ ซึ่งแต่ละอำเภอ

                         มีถนนเชื่อมกับอำเภออื่นเพียง 3 สาย มี 1 อำเภอ ที่มีถนนเชื่อมกับอำเภอ

                        อื่นเพียง 2 สาย และมี 1 อำเภอมีถนนเชื่อมกับอำเภออื่นที่เหลือทุกอำเภอ