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

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


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

         จะเห็นว่า เส้นเชื่อมที่เกิดกับจุดยอด a ได้แก่ เส้นเชื่อม ab และ ac ดังนั้น จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด คือ สำหรับจุดยอด มีเส้นเชื่อมที่เกิดกับจุดยอด ได้แก่ เส้นเชื่อม ba, bc และ bb เป็นวงวน เกิดกับจุดยอด กรณีที่มีเส้นเชื่อมเป็นวงวนจะกำหนดให้นับจำนวนเส้นเชื่อมที่เกิดกับจุดยอดนั้นเพิ่มขึ้น โดยให้นับเส้นเชื่อมที่เป็นวงวน วง วงวนเป็น ดังนั้นจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด จึงเป็น 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 ครั้ง ดังนั้นเส้นเชื่อมแต่ละเส้น    
             จะถูกนับ ครั้งในผลรวมของดีกรีของจุดยอดทุกจุด  
             นั่นคือ ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ 
    
       ข้อสังเกต  ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเป็นจำนวนคู่เสมอ
ตัวอย่างที่ 3 จงหาจำนวนเส้นเชื่อมของกราฟที่มีผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับ 22
       วิธีทำ   สมมติว่า กราฟมีเส้นเชื่อม n เส้น
                   จากทฤษฎีบท 1 ผลรวมของดีกรีของจุดยอดทุดจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ
                 
             
                   ดังนั้น 22 = 2n
                   นั่นคือ      n = 11
                   สรุปได้ว่า กราฟมีเส้นเชื่อม11 เส้น


ตัวอย่างที่ 4 จงหาจำนวนจุดยอดของกราฟที่มีเส้นเชื่อม 15 เส้น และมีจุดยอด จุด ที่มีดีกรี 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 และ ตามลำดับ
             ตัวอย่างที่ 6 กำหนดกราฟ ดังรูป    

                

        จากรูปจะได้ว่า   deg a = 2
                                    deg b = 3
                                    deg c = 0
                                    deg d = 3
                                    deg e = 2
                    ดังนั้น  จุดยอด a, c และ เป็นจุดยอดคู่
                                จุดยอด b และ เป็นจุดยอดคี่

                
  ทฤษฎีบท2  ทุกกราฟจะมีจุดยอดคี่เป็นจำนวนคู่
        พิสูจน์  ให้ เป็นกราฟ
                    ถ้า G ไม่มีจุดยอดคี่ นั่นคือ มีจำนวนจุดยอดคี่เป็นศูนย์
                    
                    จึงได้ว่ามีจำนวนจุดยอดคี่เป็นจำนวนคู่
                    ต่อไปสมมติว่า กราฟ G มีจุดยอดคี่ จุด คือ 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 เราให้เหตุผลโดยอาศัยทฤษฎีบท ดังนี้
                    สมมติว่า มีกราฟที่มีจุดยอด 4 จุด และดีกรีของจุดยอด คือ 1, 1, 2 และ 3
                    จะได้ว่า กราฟมีจุดยอดคี่เป็นจำนวน 3 จุด ซึ่งขัดแย้งกับทฤษฎีบท สรุปได้ว่า ไม่มีกราฟที่มีสมบัติดังกล่าว


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

     วิธีทำ  แปลงปัญหาดังกล่าวเป็นกราฟ โดยให้จุดยอดแทนผู้เข้าร่วมประชุม และเส้นเชื่อมแทน การจับมือทักทายของผู้เข้าร่วมประชุม
               จะได้ว่า กราฟนี้มีจุดยอด 23 จุด และจุดยอดแต่ละจุดมีดีกรี 7
               นั้นคือ กราฟมีจุดยอดคี่เป็นจำนวน 23 จุด ซึ่งเป็นจำนวนคี่ ขัดแย้งกับทฤษฎีบท 2
               ดังนั้น เป็นไปไม่ได้ที่ผู้เข้าร่วมประชุมแต่ละคนจับมือกับคนอื่นเพียง 7 เท่านั้น

        3.  กราฟออยเลอร์

อยเลอร์ได้ให้ทฤษฎีที่เกี่ยวกับปัญหานี้ไว้ดังนี้

  • เครือข่าย ที่แสดงเป็นกราฟจะประกอบด้วยจุดเชื่อมโยง (Vertices) และเส้นเชื่อมโยงระหว่างจุด เรียกว่า arcs
     


  • จุด ที่มีจำนวนเส้นที่เชื่อมออกไปยังจุดอื่นเป็นจำนวนคี่ เรียกว่า odd และถ้าจุดนั้นมีเส้นเชื่อมออกไปยังจุดอื่นเป็นจำนวนคู่ จะเรียกว่า even
     


  • เส้นทางออยเลอร์ คือเส้นทางที่ลากผ่านเส้นต่าง ๆ ในเครือข่าย โดยแต่ละเส้นลากผ่านได้เพียงครั้งเดียว
     


  • ทฤษฎีของออยเลอร์ กล่าวว่า ถ้าหากว่าเครือข่ายใดมีจุดที่เป็น odd มากกว่าสองขึ้นไป จะไม่มีทางสร้างเส้นทางออยเลอร์ได้



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