MathForLearn: 2013

วันพฤหัสบดีที่ 28 กุมภาพันธ์ พ.ศ. 2556

วันพุธที่ 27 กุมภาพันธ์ พ.ศ. 2556

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

ปัญหาสะพานเคอนิกส์เบิร์ก มีอยู่ว่า ณ เมืองเคอนิกส์เบิร์กมีเกาะกลางแม่น้ำพรีเกล (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

ดังนั้น (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 เท่านั้น

กราฟ

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