ดีกรีของจุดยอด
จะเห็นว่า เส้นเชื่อมที่เกิดกับจุดยอด a ได้แก่ เส้นเชื่อม ab และ ac ดังนั้น จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด a คือ 2 สำหรับจุดยอด b มีเส้นเชื่อมที่เกิดกับจุดยอด b ได้แก่ เส้นเชื่อม ba, bc และ bb เป็นวงวน เกิดกับจุดยอด b กรณีที่มีเส้นเชื่อมเป็นวงวนจะกำหนดให้นับจำนวนเส้นเชื่อมที่เกิดกับจุดยอดนั้นเพิ่มขึ้น โดยให้นับเส้นเชื่อมที่เป็นวงวน 1 วง วงวนเป็น 2 ดังนั้นจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด b จึงเป็น 4บทนิยาม ดีกรี (Degree) ของจุดยอด V ในกราฟ คือ จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด v
ต่อไปจะเรียกจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอดว่า ดีกรี ใช้สัญลักษณ์ deg v แทนดีกรีของจุดยอด v
ต่อไปจะเรียกจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอดว่า ดีกรี ใช้สัญลักษณ์ deg v แทนดีกรีของจุดยอด v
ตัวอย่างที่ 1 กำหนดกราฟ ดังรูป
จากรูปจะได้ว่า deg a = 2
deg b = 1
deg c = 3
deg d = 4
จากรูปจะได้ว่า deg a = 5
deg b = 5
deg c = 5
deg d = 4
สังเกตว่า deg a + deg b + deg c + deg d = 16 และกราฟมีจำนวนเส้นเชื่อมทั้งหมด 8 เส้น
ความสัมพันธ์ระหว่างผลรวมของดีกรีของจุดยอดทุกจุดในกราฟกับจำนวนเส้นเชื่อมของกราฟเป็นไปตามทฤษฎีบทต่อไปนี้.png)
พิสูจน์ เนื่องจากเส้นเชื่อมแต่ละเส้นในกราฟเกิดกับจุดยอดเป็นจำนวน 2 ครั้ง ดังนั้นเส้นเชื่อมแต่ละเส้น
จะถูกนับ 2 ครั้งในผลรวมของดีกรีของจุดยอดทุกจุด
นั่นคือ ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ
ข้อสังเกต ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเป็นจำนวนคู่เสมอ
ตัวอย่างที่ 3 จงหาจำนวนเส้นเชื่อมของกราฟที่มีผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับ 22
วิธีทำ สมมติว่า กราฟมีเส้นเชื่อม n เส้น
ดังนั้น 22 = 2n
ตัวอย่างที่ 6 กำหนดกราฟ ดังรูป
ทฤษฎีบท
2 ทุกกราฟจะมีจุดยอดคี่เป็นจำนวนคู่
นั่นคือ n = 11
สรุปได้ว่า กราฟมีเส้นเชื่อม11 เส้น
ตัวอย่างที่ 4 จงหาจำนวนจุดยอดของกราฟที่มีเส้นเชื่อม 15 เส้น และมีจุดยอด 3 จุด ที่มีดีกรี 4 ส่วนจุดยอดที่เหลือมีดีกรี3
วิธีทำ ให้ n เป็นจำนวนจุดยอดที่มีดีกรี 3
ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟ คือ (3)(4) + 3n
จากทฤษฎีบท 1 ผลรวมของดีกรีของจุดยอดทุดจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ
ดังนั้น (3)(4) + 3
เพราะฉะนั้น n = 6
ดังนั้น จำนวนจุดยอดทั้งหมดของกราฟ คือ 3 + 6 = 9 จุด
ตัวอย่างที่ 5 จงพิจารณาว่าเป็นไปได้หรือไม่ว่า จะมีกราฟที่มีจุดยอด 4 จุด และดีกรีของจุดยอด คือ 1, 1, 2 และ 3 ตามลำดับ
วิธีทำ สมมติว่า มีดีกรีที่มีจุดยอด 4 จุด และดีกรีของจุดยอดเท่ากับ 1, 1, 2 และ 3
ดังนั้น ผลรวมของดีกรีของจุดยอดทุกจุด คือ 1 + 1 + 2 + 3 = 7
ซึ่งเป็นจำนวนคี่ ขัดแย้งกับทฤษฎีบท 1
ดังนั้น เป็นไปไม่ได้ที่จะมีกราฟดังกล่าว
จากรูปจะได้ว่า deg a = 2
deg b = 3
deg c = 0
deg d = 3
deg e = 2
ดังนั้น จุดยอด a, c และ e เป็นจุดยอดคู่
จุดยอด b และ d เป็นจุดยอดคี่
ทฤษฎีบท
พิสูจน์ ให้ 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 เท่านั้น
ไม่มีความคิดเห็น:
แสดงความคิดเห็น