วิชาการ.คอม-บทเรียนออนไลน์-กราฟออยเลอร์ | บทเรียน วิชาการ.คอม
คณิตศาสตร์
 

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

สร้างเมื่อ 20 พ.ค. 2556 16:28:54
  • ระดับม.5
  • 7,084 view

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

               ในปี ค.ศ. 1736 เลออนฮารด์ ออยเลอร์ (Leonhard Euler) ซึ่งเป็นนักคณิตศาสตร์ ชาวสวิส ได้แก้ปัญหาที่มีชื่อว่า ปัญหาสะพานเคอนิกส์เบิร์ก” (Konigberg Bridge Problem) เป็นปัญหาที่กล่าวถึงสะพาน 7 สะพานในเมืองเคอนิกส์เบิรก์ สะพานเหล่านี้ใช้เกาะสองเกาะและแผ่นดิน ดังรูป

รูปที่ 1

 

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

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

รูปที่ 2

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

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

 

บทนิยาม  

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

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

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

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

 

ตัวอย่างที่  1   จงพิจารณาว่ากราฟ G เป็นกราฟออยเลอร์หรือไม่

รูปที่ 3

วิธีทำ   เนื่องจากกราฟ G มีแนวเดิน v2 , v3 , v5 , v6 , v4 , v5 , v2 , v4 , , v3 , v1 , v2

                          ซึ่งเป็นวงจรออยเลอร์

                           ดังนั้น กราฟ G เป็นกราฟออยเลอร์

ข้อสังเกต   นอกจากวงจรออยเลอร์ที่กล่าวมาแล้ว ยังมีวงจรออย์เลอร์อื่นในกราฟ G อีกเช่น

                                     1.   วงจร     v3 , v2 , v5 , v6 , v4 , v5 , v3 , v1 ,  v2 , v4 , v3 ,

                                     2.   วงจร      v6 , v5 , v3 , v1 , v2 , v4 , v3 , v2 , v5 , v4 , v6 ,

 

ตัวอย่างที่  3   จงพิจารณาว่ากราฟต่อไปนี้เป็นกราฟออยเลอร์หรือไม่

วิธีทำ   การจะพิจารณาว่ากราฟที่กำหนดให้เป็นกราฟออยเลอร์หรือไม่นั้นจะต้องพิจารณาว่ากราฟที่กำหนดให้มีวงจรออยเลอร์หรือไม่

            สังเกตว่าแนวเดินที่เป็นวงจรออยเลอร์ต้องมีสมบัติสามประการ ดังนี้

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

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

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

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

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

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

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

            ต่อไป พิจารณาที่จุดเริมต้นและจุดสิ้นสุดของวงจร   เราเริ่มต้นเดินออกจากจุดยอดนั้น และอาจเดินทางผ่านกลับมายังจุดยอดนี้ได้อีก

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

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

            ดังนั้นถ้ากราฟ G มีจุดยอดซึ่งมีดีกรีเป็นจำนวนคี่แล้ว กราฟ G ไม่เป็นกราฟออยเลอร์

            จากที่กล่าวช้างต้น   ทำให้สรุปได้โดยง่ายว่า   กราฟในตัวอย่างที่ 2 ไม่เป็น กราฟออยเลอร์ เพราะมีจุดยอด A และ B ที่มีดีกรีเป็นจำนวนคี่

            การให้เหตุผลในตัวอย่างที่ 2 สามารถใช้ได้กับกราฟทั่วไปๆ ทำฝห้สรุปได้ว่ากราฟออยเลอร์มีจุดยอดทุกจุดยอดคู่เสมอ

            ต่อไปนี้จะศึกษาว่าถ้ากราฟเชื่อมโยงมีจุดยอดจุกจุดเป็นจุดยอดคู่แล้วกราฟนั้นจะต้องเป็นกราฟออยเลอร์ด้วย   เราจะแสดงวิธีสร้างวงจรออยเลอร์โดยอธิบายในตัวอย่างต่อไปนี้

 

ตัวอย่างที่  3   กำหนดกราฟเชื่อมโยง G ซึ่งจุดยอดทุกจุดเป็นจุดยอดคู่ ดังรูป จงแสดงวิธีหาวงจอรออยเลอร์ในกราฟนี้

รูปที่ 4

            1.   เริ่มต้น ณ จุดยอดใดจุดยอดหนึ่งของกราฟ G เช่นให้ v1  เป็นจุดเริ่มต้นสร้างวงจร C1  ซึ่งแทนด้วยลำดับของจุดยอด v1 ,v2 , v5 , v6 , v7 , v3 , v1 

            2.   พิจารณาว่าวงจร C1  ผ่านเสนเชื่อมครอบทุกเส้นหรือไม่   ถ้าไม่จะเลือกจุดยอดบนวงจร C1 ที่มีเส้นเชื่อมที่เกิดกับจุดยอดนั้นซึ่งไม่อยู่บนวงจร C1   เช่นเลือก จุดยอด V3  จะได้แนวเดิน P1 ซึ่งประกอบด้วยลำดับของจุดยอด v3 , v2 , v4 , v9 , v8 , v4 , v3  และแนวเดิน P1  เป็นวงจร

            3.   นำวงจร P1  ไปต่อกับวงจร C1   จะได้วงจร C2  ซึ่งแทนด้วยลำดับของจุดยอดดังนี้  v1 , v2 , v5 , v6 , v7 , v3 , v2 , v4 , v9 , v8 , v4 , v3 , v1    

            4.    พิจารณาว่า C2   ผ่านเส้นเชื่อมทุกเส้นของกราฟหรือไม่   ถ้าไม่จะต้องสร้างแนวเดิน P2  โดยเลือก  V4   เป็นจุดเริ่มต้น   โดยที่มีเส้นเชื่อมที่เกิดกับจุดยอด v4   ซึ่งไม่อยู่ใน C2  จะได้วงจร  P2  ซึ่งแทนด้วยลำดับของจุดยอด  v4 , v5 , v7 , v4  

            5.   สร้างวงจร C3  โดยนำวงจร P2  ไปต่อกับวงจร C2  จะได้วงจรซึ่งแทนด้วยลำดับของจุดยอด  v1 , v2 , v5 , v6 , v7 , v3 , v2 , v4 , v9 , v8 , v4 , v5 , v7 , v4 , v3 , v1  ซึ่งวงจร C3  จะเป็นวงจรออย์เลอร์ของกราฟ G

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

            โดยทั่วไป   สามารถสรุปเป็นทฤษฎีบทเกี่ยวกับกราฟออยเลอร์ได้ดังนี้

 

ทฤษฎีบท 3  

             กำหนดให้ G เป็นกราฟเชื่อมโยง

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

            จากทฤษฎีบท 3 จะทำให้สามารถตรวจสอบว่ากราฟที่กำหนดให้เป็นกราฟออยเลอร์หรือไม่ได้โดยง่าย

 

ตัวอย่างที่  4   จงพิจารณาว่ากราฟ G1 , G2  และ G3  เป็นกราฟออยเลอร์หรือไม่   ถ้าเป็น จงหาวงจรออยเลอร์

วิธีทำ    กราฟ G1  เป็นกราฟออยเลอร์เพราะจุดทุกจุดของ G1   เป็นจุดยอดคู่และมีวงจรออยเลอร์ซึ่งแทนด้วยลำดับของจุดยอดดังนี้ v1 , v2 , v3 , v5 , v3 , v4 , v1 

            กราฟ  G2  ไม่เป็นกราฟออยเลอร์   เพราะมีจุดยอด v2   ซึ่ง deg v2 = 3   

            กราฟ G3  ไม่เป็นกราฟออยเลอร์เพราะ G3   ไม่เป็นกราฟเชื่อมโยง

 

ตัวอย่างที่  5   กำหนดให้รูปที่ 5 เป็นแผนผังของบ้านหลังหนึ่งซึ่งมีทางเดินระหว่างห้องแต่ละห้อง   และด้านนอกของตัวบ้าน   เป็นไปได้หรือไม่ที่จะเดินจากที่ใดที่หนึ่งในบ้านหรือด้านนอกของตัวบ้านผ่านประตูต่าง แต่ละประตูเพียงครั้งเดียวแล้วกลับมาที่เดิม

รูปที่ 5

วิธีทำ   

            แปลงปัญหานี้เป็นกราฟโดยกำหนดให้

            จุดยอด A, B, C, D, E แทนห้อง A, B, C, D, E  และให้จุดยอด O แทนบริเวณด้านนอกของตัวบ้าน

             เส้นเชื่อมแต่ละเส้น   แทนทางเดินระหว่างห้องหรือทางเดินระหว่างห้องกับด้านนอกของตัวบ้าน

            จะได้กราฟ G ดังรูป

รูปที่ 6

            จะเห็นว่า กราฟ G มีจุดยอด B, D, E และ O เป็นจุดยอดคี่

            ดังนั้น G ไม่เป็นกราฟออยเลอร์

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

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