ทฤษฎีกราฟเบื้องต้น(Introduction to graph theory)

ทฤษฎีกราฟเบื้องต้น(Introduction to graph theory)

ทฤษฎีกราฟเบื้องต้น มีเนื้อหาที่เน้นทางด้านทฤษฎีมากกว่าบทประยุกต์ โดยเนื้อหาสำคัญทางทฤษฎีกราฟในเรื่องกราฟต้นไม้ สภาพเชื่อมโยง กราฟออยเลอเรียนและกราฟแฮลิโทเนียน รวมทั้งกราฟเชิงระนาบ และการฝังของกราฟบนผิว การประยุกต์ของกราฟต้นไม้ กราฟออยเลอเรียน และกราฟแฮมิลโทเนียน

หนังสือทฤษฎีกราฟเบื้องต้นเล่มนี้เหมาะสมกับผู้เรียนในระดับปริญญาตรีที่ศึกษารายวิชาทฤษฎีกราฟหรือรายวิชาทางคณิตศาสตร์ที่เกี่ยวข้อง อีกทั้งสามารถเป็นหนังสืออ่านประกอบในระดับบัณฑิตศึกษา โดยผู้อ่านควรมีความรู้พื้นฐานด้านการพิสูจน์ทางคณิตศาสตร์ผู้เขียนได้พยายามเรียบเรียงเนื้อหาสาระให้อ่านเข้าใจง่าย โดยให้ตัวอย่างประกอบ พร้อมทั้งแสดงรูปภาพประกอบให้เห็นแนวทางการพิสูจน์ของทฤษฎีบท เพื่อให้ผู้อ่านสามารถเรียนรู้การพิสูจน์ทฤษฎีได้ด้วยตนเอง ในแต่ละหัวข้อของหนังสือจะมีแบบฝึกหัดเพื่อช่วยในการฝึก การพิสูจน์และการวิเคราะห์เนื้อหา พร้อมทั้งเฉลยแบบฝึกหัดในบางหัวข้ออีกด้วย

1.กราฟ

                                                     ทฤษฎีกราฟ

• กราฟเป็นแบบจำลองทางคณิตศาสตร์ ซึ่งใช้สำหรับจำลองปัญหาบางอย่าง

ด้วยแผนภาพที่ประกอบด้วยจุด และเส้นที่เชื่อมระหว่างจุด 2 จุด
• ตัวอย่างเช่น
– แผนภาพที่แสดงเส้นทางของรถไฟฟ้า BTS
– แผนภาพที่แสดงถนนที่เชื่อมเมืองต่าง ๆ
– แผนภาพแสดงโครงสร้างทางเคมีของสารประกอบ
ไฮโดรคาร์บอน
– วงจรไฟฟ้า
– แผนภาพเครือข่ายคอมพิวเตอร์
– แผนภาพแสดงเส้นทางการบิน

                                        จุดกำเนิดของทฤษฎีกราฟ

• ทฤษฎีกราฟ เกิดขึ้นเมื่อ ค.ศ. 1736 โดยนักคณิตศาสตร์ชาว
สวิสเซอร์แลนด์ ชื่อ เลออนฮาร์ด ออยเลอร์ (Leonhard Euler)
• ออยเลอร์ ได้สร้างทฤษฎีที่เรียกว่า “ทฤษฎีออยเลอร์” (ทฤษฎีกราฟ)
ขึ้นมาเพื่อแก้ปัญหาสะพานเคอนิกส์เบอร์ก “Konigsberg Bridge
Problem” ได้เป็นผลสำเร็จ
• ดังนั้น เลออนฮาร์ด ออยเลอร์ จึงได้ชื่อว่าเป็นบิดาของทฤษฎีกราฟ

จุดกำเนิดของทฤษฎีกราฟ

• ปัญหาสะพานเคอนิกส์เบอร์ก
มีเกาะ 2 เกาะ อยู่กลางแม่น้ำพรีเกล (Pregel) ในเมืองเคอนิกส์เบอร์ก
(ปัจจุบันเปลี่ยนชื่อเป็น คาลินิการ์ด: Kalinigrad) มีสะพาน 7 สะพาน เชื่อม
ระหว่างเกาะกับแผ่นดิน ดังรูป

ในเชิงคณิตศาสตร์ นิยาม “กราฟ” ดังนี้

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

 ข้อสังเกต V(G) ≠ ∅ แต่ E(G) อาจเป็นเซตว่างได้

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

จากกราฟ G ที่กำหนดให้ จะได้ว่า

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

E(G) = {e₁, e₂, e₃, e₄}

บทนิยาม จุดยอด u และจุดยอด v ของกราฟ เป็นจุดยอดประชิด (Adjacent Vertices) ก็      ต่อเมื่อ มีเส้นเชื่อมระหว่างจุดทั้งสอง และเราเรียกจุดยอด u และ v ว่า จุดปลาย (End Point) ของเส้นเชื่อมนั้น  เส้นเชื่อม e ของกราฟ เกิดกับ (Incident) จุดยอด v ถ้าจุดยอด v เป็นจุดปลายจุดหนึ่งของเส้นเชื่อม

         
           ตัวอย่างที่  จากกราฟของตัวอย่างที่ 1 จะเห็นว่า

                 จุดยอด A และจุดยอด B เป็นจุดยอดประชิด

                 จุดยอด A และจุดยอด C เป็นจุดยอดประชิด

                 จุดยอด B และจุดยอด C เป็นจุดยอดประชิด

                จุดยอด C และจุดยอด D เป็นจุดยอดประชิด

แต่ จุดยอด A และจุดยอด D ไม่เป็นจุดยอดประชิด
จุดยอด B และจุดยอด D ไม่เป็นจุดยอดประชิด

หมายเหตุ

1. ในการเขียนแผนภาพของกราฟนั้น จะกำหนดตำแหน่งของจุดยอด ณ ตำแหน่งใดก็ได้ และจะลากเส้นเชื่อมของกราฟเป็นเส้นตรงหรือเส้นโค้งมีความยาวเป็นเท่าใดก็ได้
   โดยที่เส้นที่ลากจะไม่ตัดกับตัวมันเอง และไม่ลากผ่านจุดยอดที่ไม่ใช่จุดยอดของเส้นนั้น เช่น กราฟต่อไปนี้ ถือว่าเป็นกราฟเดียวกัน
   
2. เส้นเชื่อมสองเส้นของกราฟ อาจลากตัดกันก็ได้ โดยที่จุดตัดของเส้นทั้งสองไม่ถือว่าเป็นจุดยอดของกราฟ

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

                  เส้นเชื่อมขนาน(Parallel Edges)

                  เส้นเชื่อมที่เชื่อมจุดยอดเพียงจุดเดียว เรียกว่า วงวน (Loop)

ดีกรีของจุดยอด
พิจารณากราฟต่อไปนี้

จุดยอด	จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด
a	2
b	4
c	4
d	2

          

   บทนิยาม ดีกรี (Degree) ของจุดยอด v ในกราฟ คือ จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด v
ต่อไปจะเรียกจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอดว่า ดีกรี ใช้สัญลักษณ์ deg v แทนดีกรีของจุดยอด v
           
             ตัวอย่างที่  กำหนดกราฟ ดังรูป

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

                   deg b = 1

                  deg c = 3

                  deg d = 4

ทฤษฎีบท

ให้ u₁, u₂, u₃, …, u)G(V เป็นจุดยอดทั้งหมดในกราฟ G จะได้ว่า
นั่นคือ ผลรวมของดีกรีของจุดยอดทุดจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ

พิสูจน์

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

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

ข้อสังเกต

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

บทนิยาม

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

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

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

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

                    deg b = 3

                   deg c = 0

                  deg d = 3

                  deg e = 2

ดังนั้น จุดยอด a, c และ e เป็นจุดยอดคู่    จุดยอด b และ d เป็นจุดยอดคี่

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

บทนิยาม

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

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


                   ตัวอย่าง  กราฟต่อไปนี้เป็นถ่วงน้ำหนัก

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

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

จำนวน 2 เกาะ และมีสะพานที่เชื่อมระหว่างเกาะและเมืองดังรูปต่อไปนี้

        ชาวเมืองเคอนิกส์เบิร์กพยายามหาวิธีเดินข้ามสะพานให้ครบทุกสะพาน โดยที่ข้ามสะพานแต่ละสะพานเพียงครั้งเดียวและกลับมาที่จุดยอดเริ่มต้น
เลออนฮาร์ด ออยเลอร์ได้แปลงปัญหานี้ให้อยู่ในรูปกราฟ โดยให้อาณาบริเวณ A, B, C, D แทนด้วยจุดยอดของกราฟ และสะพานแต่ละพานแทนด้วยเส้นเชื่อมของกราฟ

บทนิยาม

       วงจรออยเลอร์(Euler trail) คือ รอยเดินซึ่งผ่านจุดยอดทุกจุดและเส้นเชื่อมทุกเส้นของกราฟ

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

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

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

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

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

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

ถ้า G มีวัฎจักรแฮมิลตัน จะเรียก G ว่าเป็นกราฟแฮมิลตัน(Hamiltonian graph)

ต้นไม้  

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

           บทนิยาม ต้นไม้ (tree) คือ กราฟเชื่อมโยงที่ไม่มีวัฏจักร
              ตัวอย่าง พิจารณากราฟต่อไปนี้

  

ลักษณะเฉพาะของต้นไม้
ทฤษฎีบท
            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 จุด