ทฤษฎีกราฟเบื้องต้น

       1. กราฟ
กราฟเป็นแบบจำลองทางคณิตศาสตร์ ซึ่งใช้จำลองปัญหาบางปัญหาโดยเขียนแผนภาพที่ประกอบด้วยจุดและเส้น ปัจจุบันมีการนำทฤษฎีกราฟมาประยุกต์ใช้ในศาสตร์สาขาต่าง ๆ เช่น วิทยาศาสตร์ สังคมศึกษา เศรษฐศาสตร์ พันธุศาสตร์ วิศวกรรมศาสตร์ เป็นต้น
บทนิยาม       กราฟ G ประกอบด้วยเซตจำนวน 2 เซต  คือ
1. เซตที่ไม่เป็นเวตว่างของจุดยอด  (vertex)  แทนด้วยสัญลักษณ์  V(G)
2. เซตของเส้นเชื่อม  (edge)  ที่เชื่อมระหว่างจุดยอดแทนด้วยสัญลักษณ์  E(G)

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

จะเห็นว่า เส้นเชื่อมที่เกิดกับจุดยอด 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 จุด

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

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

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

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

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

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

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

deg b = 3

deg c = 0