ที่มาของข้อมูล

ที่มาของข้อมูล

http://www.tewlek.com/anet_vector.html

https://sites.google.com/site/sukanyameksuwansite/khwam-pen-ma-khxng-thvsti-kraf

กราฟแบบออยเลอร์และกราฟแบบแฮมิลตัน

ปัญหาสะพานเคอนิกส์เบิร์ก มีอยู่ว่า ณ เมืองเคอนิกส์เบิร์กมีเกาะกลางแม่น้ำพรีเกล (Pregel)จำนวน2 เกาะ และมีสะพานที่เชื่อมระหว่างเกาะและเมืองดังรูปต่อไปนี้

 

       

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

        เลออนฮาร์ด ออยเลอร์ได้แปลงปัญหานี้ให้อยู่ในรูปกราฟ โดยให้อาณาบริเวณ

A, B, C, D แทนด้วยจุดยอดของกราฟ และสะพานแต่ละพานแทนด้วยเส้นเชื่อมของกราฟ

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

 

       
         ตัวอย่างกราฟต่อไปนี้เป็นกราฟออยเลอร์

        ปัญหาหนี่งที่ดูคล้ายกับปัญหาวงจรออยเลอร์ คือปัญหาการหาวิถีในกราฟที่ไม่ใช้จุดยอดซ้ำกันยกเว้นจุดเริ่มต้นและจุดสิ้นสุดต้องเป็นจุดเดียวกัน ซึ่งก็คือ วัฎจักรและวัฎจักรนี้ผ่านครบทุกจุดยอดในกราฟนี้ จะเรียกวัฎจักรนี้ว่า วัฎจักรแฮมิลตัน  ถ้า G มีวัฎจักรแฮมิลตัน จะเรียก G ว่าเป็นกราฟแฮมิลตัน(Hamiltonian 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 ที่สั้น

 ที่สุดมีขั้นตอนวิธีที่ใช้หาวิถีที่สั้นที่สุด เช่น ขั้นตอนวิธีของ Dijkstra

    

    

     ในที่นี้เราจะศึกษา ขั้นตอนวิธีของ Dijkstra พร้อมแสดงตัวอย่าง จงหาวิถี A - H ที่สั้นที่สุดของกราฟต่อไปนี้

            จากกราฟข้างต้น เราได้ว่า   

            วิถี A-H ที่สั้นที่สุดคือ A, B, E, H

            วิถี A-D ที่สั้นที่สุดคือ A, C, D

            วิถี A-G ที่สั้นที่สุดคือ A, C, G 

            วิถี A-F ที่สั้นที่สุดคือ A, B, F  หมายเหตุ      จากขั้นตอนวิธีของ Dijkstra ข้างต้นเราจะได้วิถีที่สั้นที่สุดจาก A ไปยังจุดยอดใดๆ                    เท่านั้น ถ้าเราจะหาวิถีที่สั้นที่สุดจากจุดยอดที่ไม่ใช่จุด A จะต้องเริ่มขั้นตอนวิธีของ Dijkstra ใหม่

ต้นไม้

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

ลักษณะเฉพาะของต้นไม้

    ทฤษฎีบทต่อไปนี้เป็นทฤษฎีบทที่บ่งบอกลักษณะเฉพาะ 
      (characterization) ของต้นไม้ทฤษฎีบท      

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 จุด  

  

ต้นไม้แผ่ทั่ว  (spanning tree)

ก่อนที่จะศึกษาต้นไม้แผ่ทั่ว เราจะเริ่มต้นศึกษากราฟย่อยก่อน

แนวเดินและกราฟเชื่อมโยง

แนวเดินและกราฟเชื่อมโยง

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

ในการเดินทางจากอำเภอ

A ไปยังอำเภอ D มีเส้นทางการเดินทางหลายเส้นทางเส้นทางต่างๆ จะแทนดัวยลำดับของจุดยอดและเส้นเชื่อม ดังนี้เส้นทาง A, e1, E, e5, D

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

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

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

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

                             deg b = 5

                             deg c = 5

                             deg d = 4

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

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

พิสูจน์ เนื่องจากเส้นเชื่อมแต่ละเส้นในกราฟเกิดกับจุดยอดเป็นจำนวน 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

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

                    นั่นคือ 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 เท่านั้น

กราฟ

กราฟ

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

บทนิยาม

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

 1. เซตที่ไม่เป็นเวตว่างของจุดยอด  (vertex)  แทนด้วยสัญลักษณ์  V(G)

 2. เซตของเส้นเชื่อม  (edge)  ที่เชื่อมระหว่างจุดยอดแทนด้วยสัญลักษณ์  E(G)