กราฟ

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

• ทฤษฎีกราฟ เกิดขึ้นเมื่อ ค.ศ. 1736 โดยนักคณิตศาสตร์ชาว สวิสเซอร์แลนด์ ชื่อ เลออนฮาร์ด ออยเลอร์ (Leonhard Euler)

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

• ดังนั้น เลออนฮาร์ด ออยเลอร์ จึงได้ชื่อว่าเป็นบิดาของทฤษฎีกราฟ จุดกำเนิดของทฤษฎีกราฟ

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

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

• ออยเลอร์ได้ไขปริศนานี้โดยแปลงปัญหาดังกล่าวเป็นกราฟโดยให้พื้นดิน แทนจุดยอด และสะพานแทนด้วยเส้นเชื่อม ดังรูป 

• ออยเลอร์สามารถพิสูจน์ยืนยันคำตอบว่าเป็นไปไม่ได้้ที่จะหาเส้นทาง ดังกล่าว

• จะมีเส้นทางดังกล่าวได้ก็ต่อเมื่อกราฟนั้นจะต้องต่อเนื่องและมีจำนวนเส้นของแต่ละจุดเป็นจำนวนคู่

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

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

ตัวอย่างของกราฟ

  

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

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

จากรูปข้างต้นจะเห็นว่า 

                    e₁ และ e₂ เป็น เส้นเชื่อมขนาน เส้นเชื่อม e₅ เป็นวงวน  ในกรณีที่กราฟไม่มีเส้นเชื่อมขนาน สามารถใช้สัญลักษณ์ 

         AB เพื่อแทนเส้นเชื่อมระหว่างจุดยอด A และ B ได้ เช่น กราฟในตัวอย่างที่ 1 สามารถเขียนเซตของเส้นเชื่อม E(G)

     ได้ใหม่เป็น E(G) = {AB, BC, AC, CD}

ตัวอย่าง จุดยอดประชิด

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

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

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

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

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

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

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

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

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

ตัวอย่างของจำนวนดีกรี

จะเห็นว่า เส้นเชื่อมที่เกิดกับจุดยอด a ได้แก่ เส้นเชื่อม ab และ ac ดังนั้น จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด a คือ 2 สำหรับจุดยอด b มีเส้นเชื่อมที่เกิดกับจุดยอด b ได้แก่ เส้นเชื่อม ba, bc และ bb เป็นวงวน เกิดกับจุดยอด b กรณีที่มีเส้นเชื่อมเป็นวงวนจะกำหนดให้นับจำนวนเส้นเชื่อมที่เกิดกับจุดยอดนั้นเพิ่มขึ้น โดยให้นับเส้นเชื่อมที่เป็นวงวน 1 วง วงวนเป็น 2 ดังนั้น

ทฤษฎีบท 1       

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

จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด b จึงเป็น 4บทนิยาม ดีกรี (Degree) ของจุดยอด V ในกราฟ คือ จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด v

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

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

 บทนิยาม

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

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

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

                        deg b = 1

                        deg c = 3

                        deg d = 4

ดังนั้น จุดยอด a,d เป็นจุดยอดคู่

        จุดยอด b,c เป็นจุดยอดคี่

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

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

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

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

u = u₀, e₁, u₁, e₂, u₂, …, u_n-1, e_n, u_n = v

โดยเริ่มต้นที่จุดยอด u และสิ้นสุดที่จุดยอด v และแต่ละเส้นเชื่อม e_i จะเกิดกับจุดยอด              u_i-1 และ u_i เมื่อ i ∈ {1, 2, …, n}

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

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

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

 บทนิยาม  

รอยเดิน (trail) คือ แนวเดินในกราฟที่เส้นเชื่อมทั้งหมดแตกต่างกัน  

วิถี(Path) คือ แนวเดินในกราฟที่จุดยอดทั้งหมดแตกต่างกัน 

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

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

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

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

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

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

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

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

การประยุกต์ของกราฟ

บทนิยาม 

   ค่าน้ำหนัก(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 เป็นวิถีที่สั้นที่สุด

บทนิยาม  วิถี(Path) คือ แนวเดินในกราฟที่จุดยอดทั้งหมดแตกต่างกัน               

วิถีที่สั้นที่สุด(shortest path) จากจุดยอด A ถึง Z ในกราฟถ่วงน้ำหนัก คือวิถี A-Z ที่ผลรวมของน้ำหนักของเส้นเชื่อมทุกเส้นในวิถี A-Z น้อยที่สุด

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

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

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

บทนิยาม กราฟย่อย (subgraph) ของกราฟ G คือ กราฟที่ประกอบด้วยจุดยอดและเส้นเชื่อมใน G กล่าวคือ กราฟ H เป็นกราฟย่อยของกราฟ G ก็ต่อเมื่อ V(H) เป็นสับเซตของ V(G)และ E(H) เป็นสับเซตของ E(G)

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

ต้นไม้แผ่ทั่วที่น้อยที่สุด (minimal spanning tree) คือต้นไม้แผ่ทั่วที่มีผลรวมของค่าน้ำหนักของแต่ละเส้นเชื่อมที่น้อยที่สุด

•                  ในกรณีที่เราหาการเชื่อมต่อที่สั้นที่สุดโดยมีลักษณะเป็นต้นไม้แผ่ทั่ว เราจะเรียกต้นไม้ที่ได้ว่า ต้นไม้แผ่ทั่วน้อยสุด

•                  จากตัวอย่าง จากการต่อจุด 4 จุด ที่มีตำแหน่งการวาง ดังรูป (ก) สามารถเขียนต้นไม้แผ่ทั่วได้ดังรูป (ข) และ (ค) 

พบว่า ต้นไม้แผ่ทั่วรูป (ค) คือ ต้นไม้แผ่ทั่วน้อยสุด