กำเนิดทฤษฎีกราฟ  ( The origin of graph theory )

คริสต์ศตวรรษที่ 18  มีเมืองๆหนึ่งชื่อ เคอนิกส์แบร์ก ( Koningsberg )  ตั้งอยู่บนสองฝั่งของแม่น้ำปรีเกล ( Pregel ) ต่อมาเปลี่ยนชื่อเป็นคาลินินกราด ( Kalininggrad ) อยู่ในสหภาพโซเวียตรัสเซียทางด้านตะวันออก ปัจจุบันเมื่อสหภาพโซเวียตถูกแบ่งแยกแล้วเมืองนี้สังกัดอยู่กับสหพันธรัฐรัสเซีย เมืองเคอนิกส์แบร์กประกอบด้วยเกาะ 2 เกาะ คือ เกาะ A และ เกาะ B ซึ่งเชื่อมระหว่างเกาะกับตัวเมืองด้วยสะพาน 7 แห่ง ดังรูป  ก

 

                                                                                     รูป  ก

เนื่องจากชาวเมืองมีนิสัยชอบเดินเล่น จึงตั้งปัญหาเกี่ยวกับการเดินขึ้นว่า    “ เป็นไปได้หรือไม่ที่คน คนหนึ่งจะเดินข้ามสะพานทั้ง 7 เพียงสะพานละหนึ่งครั้ง โดยจะตั้งต้นที่ไหนและจะสิ้นสุดที่ใดก็ได้ ” ปัญหานี้ไม่มีใครให้คำตอบได้ จนกระทั่งในปี ค.ศ. 1736  เลออนฮาร์ด ออยเลอร์ ( Leonhard Euler ) นักคณิตศาสตร์  ชาวสวิสได้ให้คำตอบพร้อมคำอธิบายว่าการเดินลักษณะดังกล่าว เป็นไปไม่ได้ เพราะการที่คนคนหนึ่งจะทำเช่นนั้นได้ เขาจะต้องเดินมาที่เกาะ A ( หรือเกาะ B ) แล้วกลับออกไปโดยใช้สะพานที่ที่ต่างกันในจำนวนครั้งที่เท่ากันซึ่งไม่อาจทำได้

                ถ้าคำตอบของออยเลอร์มีเพียงเท่านี้ ปัญหาสะพานเคอนิกส์แบร์ก คงไม่กลายเป็นปัญหาอมตะในวิชาคณิตศาสตร์ แต่ธรรมชาติของนักคณิตศาสตร์มักไม่พอใจเพียงคำตอบเฉพาะกรณี เขามักแสวงหาคำตอบทั่วไปเพื่อจะตอบปัญหาอื่นๆที่มีลักษณะเดียวกันด้วย ออยเลอร์ได้เปลี่ยนรูปแบบของปัญหาแล้วเสนอเป็นตัวแบบนามธรรม คือ แทนฝั่งแม่น้ำและเกาะด้วย จุดยอด ( vertex หรือ node ) แทนสะพานด้วยเส้นเชื่อมระหว่าง       จุดยอด 2 จุด   เรียกว่า   ด้าน ( edge หรือ arc ) แผนภาพนี้เรียกว่า กราฟ ( ซึ่งแตกต่างจากกราฟที่แทนฟังก์ชันของจำนวนจริงในเรขาคณิต )          ดังรูป  ข

 

                                                                                    รูป  ข

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

บทนิยาม       กราฟ G ประกอบด้วยเซตจำนวน 2 เซต คือ
                   1. เซตที่ไม่เป็นเซตว่างของจุดยอด  (Vertex)  แทนด้วยสัญลักษณ์ V(G)
                            2. เซตของเส้นเชื่อม  (Edge)  ที่เชื่อมระหว่างจุดยอดแทนด้วยสัญลักษณ์ E(G)

จุดยอดและเส้นเชื่อม

   บทนิยาม            กราฟ G ประกอบด้วยเซตจำกัด  เซต คือ

1.เซตที่ไม่เป็นเซตว่างของจุดยอด

             2.เซตของเส้นเชื่อม ที่เชื่อมระหว่างจุดยอด

                 

       

หมายเหตุ

1.            
ในการเขียนแผนภาพของกราฟนั้น  จะกำหนดตำแหน่งของจุดยอด ณ ตำแหน่งใดก็ได้

        และลากเส้นเชื่อมของกราฟเป็นเส้นตรงหรือเส้นโค้งมีความยาวเป็นเท่าใดก็ได้  เช่น

  

                                                          รูปที่ 1                                               รูปที่ 2

                       

                                           กราฟรูปที่ 1 และกราฟรูปที่ 2 ถือว่าเป็น กราฟเดียวกัน

2.             เส้นเชื่อมสองเส้นของกราฟอาจลากตัดกันได้  โดยที่จุดตัดของเส้นทั้งสองไม่ถือว่า

       เป็นจุดยอดของกราฟ 

เส้นเชื่อมขนาน และ วงวน

              บทนิยาม  เส้นเชื่อมตั้งแต่ 2 เส้นที่เชื่อมระหว่างจุดยอดคู่เดียวกันเรียกว่า เส้นเชื่อมขนาน (Parallel edges)                                     เส้นเชื่อมที่เชื่อมจุดยอดเพียงจุดเดียว เรียกว่า วงวน ( Loop )

จุดยอดประชิด 

                   บทนิยาม    จุดยอดu และจุดยอดv ของกราฟ เป็นจุดยอดประชิด ก็ต่อเมื่อมีเส้นเชื่อมระหว่างจุดทั้งสอง

                                     เส้นเชื่อม e  ของกราฟเกิดกับ ( incident ) จุดยอด v ถ้าจุดยอด v เป็นจุดปลายจุดหนึ่งของ

                                     เส้นเชื่อม e

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

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

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

              จากบทนิยาม จะได้ว่า ดีกรีของจุดยอดในกราฟก็คือ จำนวนเส้นทั้งหมดที่ตกกระทบกับจุดยอดนั้นๆ

                                              กรณีเส้นเชื่อมเป็นวงวนให้นับเส้นเชื่อมเป็น  2  เส้น

                                           จุดยอดที่ไม่มีเส้นเชื่อมให้ถือว่าดีกรีของจุดยอดเป็นศูนย์  

การหาผลรวมของดีกรีของจุดยอด

 การหาผลรวมของดีกรีของจุดยอดทุกจุดในกราฟ จะอาศัยทฤษฎีบท ดังต่อไปนี้

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

                       ในกราฟ

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

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

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

                                               

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

                                                   มีจุดยอด 3 จุดที่มีดีกรีเท่ากับ  4  ส่วนจุดยอดที่เหลือมีดีกรีเท่ากับ  3

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

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

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

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

                                                                              12  +  3n               =     30

                                                                                            n               =      6

                                  \    จำนวนจุดยอดที่มีดีกรีเท่ากับ  3   มีจุดยอดทั้งหมด  6  จุด

                                            จำนวนจุดยอดที่มีดีกรีเท่ากับ  4   มีจุดยอดทั้งหมด  3  จุด

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

                  สรุป

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

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

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

จุดยอดคู่ , จุดยอดคี่

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

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

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

แนวเดิน

                           บทนิยาม    ให้  u  และ  v  เป็นจุดยอดของกราฟ

                                                แนวเดิน  u – v  ( u – v  walk ) คือลำดับจำกัดของจุดยอดและเส้นเชื่อมสลับกัน

                                                u =  u₀ , e1 , u₁ , e₂ , u ₂ , e₃ ,… , u _{n - 1} , e_n , u_n  =   v

                                               โดยเริ่มต้นที่จุดยอด u และสิ้นสุดที่จุดยอด v และแต่ละเส้นเชื่อม e₁ จะเกิดกับ

                                               จุดยอด u_{i – 1}  และ u_i  เมื่อ  i  Î { 1 , 2 , 3 , … , n }

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

                                       ในการเดินทางจากอำเภอ A ไปยังอำเภอ D มีเส้นทางการเดินทางหลายเส้นทาง

                                                    เส้นทางต่างๆ จะแทนดัวยลำดับของจุดยอดและเส้นเชื่อม ดังนี้

                                                                                          เส้นทาง A, e₁, E, e₅, D

กราฟเชื่อมโยง

                        บทนิยาม       กราฟ  G  เรียกว่า กราฟเชื่อมโยง ( connected graph ) ก็ต่อเมื่อ สำหรับ

                                                จุดยอด u และ v   ที่เป็นจุดยอดต่างกันในกราฟ  G  มีแนวเดิน u – v 

             จากบทนิยามจะได้ว่า  กราฟที่จะเป็นกราฟเชื่อมโยง จะต้องมีแนวเดินระหว่างจุดยอดทุกจุดในกราฟ

วงจรออยเลอร์

                         บทนิยาม    วงจร ( circuit ) คือ แนวเดินที่เส้นเชื่อมทั้งหมดแตกต่างกัน โดยมีจุดยอดเริ่มต้น

                                              และจุดสุดท้ายเป็นจุดเดียวกัน

                         บทนิยาม      วงจรออยเลอร์ ( Euler circuit ) คือ วงจรที่ผ่านจุดยอดทุกจุด

                                                และเส้นเชื่อมทุกเส้นของกราฟ

จากบทนิยามของวงจรออยเลอร์สรุปสมบัติของวงจรออยเลอร์ได้ดังนี้

1.              แนวเดินผ่านเส้นเชื่อมทุกเส้นของกราฟ

2.              แนวเดินจะต้องไม่ผ่านเส้นเชื่อมใดเกินหนึ่งครั้ง

3.              มีจุดเริ่มต้นและจุดสิ้นสุดเป็นจุดเดียวกัน

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

                                        

                                บทนิยาม      กราฟที่มีวงจรออยเลอร์ เรียกว่ากราฟออยเลอร์ ( Eulerian  graph )

จากบทนิยาม  กราฟออยเลอร์จะเป็นกราฟเชื่อมโยงเสมอ เพราะว่า ถ้า u และ v เป็นจุดยอดสองจุด

       ที่แตกต่างกันบนกราฟออยเลอร์  แล้วส่วนของวงจรออยเลอร์ที่เชื่อม u และ v จะเป็นแนวเดิน u – v 

ในการตรวจสอบว่ากราฟใดๆจะเป็นกราฟออยเลอร์หรือไม่นั้น นอกจากตรวจสอบด้วย

วงจรออยเลอร์แล้ว ยังมีวิธีการตรวจสอบอีกโดยใช้ทฤษฎีบท  3  ด้วย

                     ทฤษฎีบท 3    กำหนดให้   G  เป็นกราฟเชื่อมโยง

                              G  จะเป็นกราฟออยเลอร์ ก็ต่อเมื่อ จุดยอดทุกจุดของ  G  เป็นจุดยอดคู่

สรุป

1. กราฟออยเลอร์จะเป็นกราฟเชื่อมโยงเสมอ

2. การตรวจสอบว่ากราฟใดเป็นออยเลอร์นั้นให้ดูว่าจุดยอดทุกจุดในกราฟต้องเป็นจุดยอดคู่หาวงจรออยเลอร์ได้ 

ค่าน้ำหนักของเส้นเชื่อม

                

                  บทนิยาม   ค่าน้ำหนัก ( weight ) ของเส้นเชื่อม e  คือจำนวนที่ไม่เป็นลบที่กำหนดให้บนเส้นเชื่อม  e 

                  จากบทนิยาม จะได้ว่า ค่าน้ำหนักของเส้นเชื่อมใดๆในกราฟก็คือ จำนวนบวกที่เขียนกำกับไว้บน

      เส้นเชื่อมนั่นเอง

กราฟถ่วงน้ำหนัก

                 บทนิยาม  ค่าน้ำหนัก(weight) ของเส้นเชื่อม e ในกราฟ คือ จำนวนที่ไม่เป็นลบที่กำหนดไว้บนเส้นเชื่อม e

                                    กราฟถ่วงน้ำหนัก(weight graph) คือ กราฟที่เส้นเชื่อมทุกเส้นมีค่าน้ำหนัก

  จะหาเส้นทางจากเมือง  A ไปยังเมือง E ทั้งหมดที่ไม่ผ่านเมืองซ้ำกัน

   เส้นทางที่   1 A, B, D, E ระยะทางยาว 2 + 1 + 3 = 4 กิโลเมตร

    เส้นทางที่   2 A, B, D, F, E ระยะทางยาว 2 + 1 + 2 + 2 = 7 กิโลเมตร

   เส้นทางที่   3 A, B, D, C, F, E ระยะทางยาว 2 + 1 + 3 + 6 + 2 = 14    กิโลเมตร

   เส้นทางที่   4 A, C, F, E ระยะทางยาว 5 + 6 + 2 = 13 กิโลเมตร 

   เส้นทางที่   5 A, C, F, D, E ระยะทางยาว 5 + 6 + 2 + 3 = 16 กิโลเมตร

   เส้นทางที่   6 A, C, D, E ระยะทางยาว 5 + 3 + 3 = 11 กิโลเมตร

   เส้นทางที่   7 A, C, D, F, E ระยะทางยาว 5 + 3 + 2 + 2 = 12 กิโลเมตร

            จะเห็นว่าเส้นทางที่   1 A, B, D, E ระยะทางยาว 4 กิโลเมตรเป็นระยะทางที่สั้นที่สุด

จะเห็นว่า วิถี A, B, D, E เป็นวิถีที่สั้นที่สุด

สำหรับกราฟถ่วงนำหนักที่มีจุดยอดและเส้นเชื่อมเป็นจำนวนมาก การหาวิถี A - Z ที่สั้นที่สุด

โดยการค้นหาวิถี A - Z ทั้งหมดแล้วเลือกวิถีที่ผลรวมของค่าน้ำหนักน้อยที่สุด ทำได้ไม่สะดวกและเสียเวลา ในการหาวิถี A - Z ที่สั้นที่สุด

                   

                       บทนิยาม   จากจุดยอด A ถึงจุดยอด Z  ในกราฟถ่วงน้ำหนักคือวิถี  A – Z ที่ผลรวมของค่า                  

                                          น้ำหนักของเส้นเชื่อมทุกเส้นในวิถี  A – Z น้อยที่สุด

             

   จากบทนิยามสรุปได้ว่า วิถีที่สั้นที่สุด คือ แนวเดินที่มีผลรวมของค่าน้ำหนักของ เส้นเชื่อมในแนวเดิน ( วิถี )นั้นมีค่าน้อยที่สุด

วัฎจักร

บทนิยาม   วัฎจักร  คือ วงจรที่ไม่มีจุดยอดซ้ำกัน    ยกเว้นจุดเริ่มต้นและจุดสุดท้าย

ต้นไม้

        บทนิยาม        ต้นไม้  คือ กราฟเชื่อมโยงที่ไม่มีวัฎจักร   

จากบทนิยามสรุปได้ว่า กราฟใดๆจะเป็นต้นไม้จะต้องเป็นกราฟเชื่อมโยง และไม่มีวัฎจักร

จะเห็นว่า กราฟในรูป (A) และ (B) เป็นต้นไม้  กราฟในรูป (C) ไม่เป็นต้นไม้ เพราะมีวัฏจักรปรากฏอยู่  กราฟในรูป (D) ไม่เป็นต้นไม้ เพราะไม่ใช่กราฟเชื่อมโยง

ลักษณะเฉพาะของต้นไม้ ทฤษฎีบท 

            1. ให้ T เป็นกราฟที่ไม่มีวงวน กราฟ T เป็นต้นไม้ ก็ต่อเมื่อ จุดยอด 2 จุดใดๆ ใน T เชื่อมโยงกันได้ด้วยวิถีเพียงวิถีเดียว 

            2. ให้ T เป็นกราฟที่มีจำนวนจุดยอดเป็น n จุด กราฟ T เป็นต้นไม้ ก็ต่อเมื่อ กราฟ T ไม่มีวัฏจักร

 และมีเส้นเชื่อม n – 1 เส้น 

            3. ให้ T เป็นกราฟที่มีจำนวนจุดยอดเป็น n จุด กราฟ T เป็นต้นไม้ ก็ต่อเมื่อ กราฟ T เป็นกราฟเชื่อมโยงและมีเส้นเชื่อม n – 1 เส้น 

            4. ถ้า T เป็นต้นไม้ที่มีจำนวนจุดยอดอย่างน้อย 2 จุด แล้ว กราฟ T จะมีดีกรี 1 อย่างน้อย 2 จุด

        

กราฟย่อย และ ต้นไม้แผ่ทั่ว

                      บทนิยาม   กราฟย่อย ( Subgraph )  ของกราฟ G   คือกราฟที่ประกอบด้วยจุดยอดและ

                                          เส้นเชื่อมใน  G กล่าวคือ กราฟ H เป็นกราฟย่อยของกราฟ G ถ้า  V(H) Ì V(G) 

                                          และ  E(H) Ì E(G)              

V(G) = { A, B, C, D }                           V(H) = { A, B, C, D }

                                                       E(G) = {AB, BC, CD, DA, BD}         E(H) = {AB, BC, DA, BD}

จะได้ว่า กราฟ H เป็นกราฟย่อยของกราฟ G พิจารณาว่ากราฟใด เป็นกราฟย่อยของกราฟ G

กราฟ G₂ และ G₆ ไม่เป็นกราฟย่อยของ G   พิจารณากราฟย่อยของกราฟ G จะเห็นว่ากราฟ G₁ , G₃ และ G₅ เป็นกราฟย่อยของ G และเป็นต้นไม้ด้วย

                      บทนิยาม   ต้นไม้แผ่ทั่ว ( spanning tree )  คือต้นไม้ซึ่งเป็นกราฟย่อยของกราฟเชื่อมโยง G ที่บรรจุ 

                                         จุดยอดทุกจุดของ G 

ต้นไม้แผ่ทั่วที่น้อยที่สุด

                      บทนิยาม   ต้นไม้แผ่ทั่วที่น้อยที่สุด ( minimal  spanning tree ) คือ ต้นไม้แผ่ทั่วที่มีผลรวมของ

                                          ค่าน้ำหนักของแต่ละเส้นเชื่อมน้อยที่สุด              

                 จากบทนิยาม  ต้นไม้แผ่ทั่วที่น้อยที่สุดหาได้โดยการหาผลรวมของค่าน้ำหนักของแต่ละเส้นเชื่อม

                                      ในต้นไม้แผ่ทั่วที่มีค่าน้อยที่สุด

การเลือกเส้นที่น้อยที่สุดจากกราฟเชื่อมโยงที่มีน้ำหนักติดต่อกันเพื่อสร้างเป็นกราฟเชื่อมโยงที่มีน้ำหนักโดยเลือกเส้นกราฟไม่เกิน n-1ครั้ง เมื่อกราฟมีจุด n จุด และการเลือกต้องไม้ก่อให้เกิดวัฏจักร การเลือกนี้จะสิ้นสุดลงเมื่อได้ต้นไม้แผ่ทั่ว และเราเรียกต้นไม้แผ่ทั่วที่มีผลรวมของน้ำหนักของเส้นเชื่อมน้อยที่สุดว่าต้นไม้แผ่ทั่วที่น้อยที่สุด(minimal spanning tree )