1.กราฟ
ด้วยแผนภาพที่ประกอบด้วยจุด และเส้นที่เชื่อมระหว่างจุด 2 จุด
• ตัวอย่างเช่น
- แผนภาพที่แสดงเส้นทางของรถไฟฟ้า BTS
- แผนภาพที่แสดงถนนที่เชื่อมเมืองต่าง ๆ
- แผนภาพแสดงโครงสร้างทางเคมีของสารประกอบ
ไฮโดรคาร์บอน
- วงจรไฟฟ้า
- แผนภาพเครือข่ายคอมพิวเตอร์
- แผนภาพแสดงเส้นทางการบิน
• ตัวอย่างเช่น
- แผนภาพที่แสดงเส้นทางของรถไฟฟ้า BTS
- แผนภาพที่แสดงถนนที่เชื่อมเมืองต่าง ๆ
- แผนภาพแสดงโครงสร้างทางเคมีของสารประกอบ
ไฮโดรคาร์บอน
- วงจรไฟฟ้า
- แผนภาพเครือข่ายคอมพิวเตอร์
- แผนภาพแสดงเส้นทางการบิน
จุดกำเนิดของทฤษฎีกราฟ
• ทฤษฎีกราฟ เกิดขึ้นเมื่อ ค.ศ. 1736 โดยนักคณิตศาสตร์ชาว
สวิสเซอร์แลนด์ ชื่อ เลออนฮาร์ด ออยเลอร์ (Leonhard Euler)
• ออยเลอร์ ได้สร้างทฤษฎีที่เรียกว่า “ทฤษฎีออยเลอร์” (ทฤษฎีกราฟ)
ขึ้นมาเพื่อแก้ปัญหาสะพานเคอนิกส์เบอร์ก “Konigsberg Bridge
Problem” ได้เป็นผลสำเร็จ
• ดังนั้น เลออนฮาร์ด ออยเลอร์ จึงได้ชื่อว่าเป็นบิดาของทฤษฎีกราฟ
สวิสเซอร์แลนด์ ชื่อ เลออนฮาร์ด ออยเลอร์ (Leonhard Euler)
• ออยเลอร์ ได้สร้างทฤษฎีที่เรียกว่า “ทฤษฎีออยเลอร์” (ทฤษฎีกราฟ)
ขึ้นมาเพื่อแก้ปัญหาสะพานเคอนิกส์เบอร์ก “Konigsberg Bridge
Problem” ได้เป็นผลสำเร็จ
• ดังนั้น เลออนฮาร์ด ออยเลอร์ จึงได้ชื่อว่าเป็นบิดาของทฤษฎีกราฟ
จุดกำเนิดของทฤษฎีกราฟ
• ปัญหาสะพานเคอนิกส์เบอร์ก
มีเกาะ 2 เกาะ อยู่กลางแม่น้ำพรีเกล (Pregel) ในเมืองเคอนิกส์เบอร์ก
(ปัจจุบันเปลี่ยนชื่อเป็น คาลินิการ์ด: Kalinigrad) มีสะพาน 7 สะพาน เชื่อม
ระหว่างเกาะกับแผ่นดิน ดังรูป
มีเกาะ 2 เกาะ อยู่กลางแม่น้ำพรีเกล (Pregel) ในเมืองเคอนิกส์เบอร์ก
(ปัจจุบันเปลี่ยนชื่อเป็น คาลินิการ์ด: Kalinigrad) มีสะพาน 7 สะพาน เชื่อม
ระหว่างเกาะกับแผ่นดิน ดังรูป
คำถามเป็นไปได้หรือไม่ที่ชาวเมืองเคอนิกส์เบอร์กจะท่องเที่ยวเมืองนี้โดยเริ่มต้นจาก
เกาะหรือฝั่งอันใดอันหนึ่งแล้วข้ามสะพานแต่ละแห่งเพียงครั้งเดียวเท่านั้นจนครบ
ทุกสะพาน และเมื่อข้ามสะพานสุดท้ายแล้วจะต้องกลับมาอยู่ที่บริเวณเริ่มต้น
• ออยเลอร์ได้ไขปริศนานี้โดยแปลงปัญหาดังกล่าวเป็นกราฟโดยให้พื้นดิน
แทนจุดยอด และสะพานแทนด้วยเส้นเชื่อม ดังรูป
• ออยเลอร์สามารถพิสูจน์ยืนยันคำตอบว่าเป็นไปไม่ได้้ที่จะหาเส้นทาง
ดังกล่าว
• จะมีเส้นทางดังกล่าวได้ก็ต่อเมื่อกราฟนั้นจะต้องต่อเนื่องและมีจำนวนเส้น
ของแต่ละจุดเป็นจำนวนคู่
ในเชิงคณิตศาสตร์ นิยาม “กราฟ” ดังนี้
บทนิยาม กราฟ G ประกอบด้วย เซตจำกัด 2 เซต คือ 1. เซตที่ไม่เป็นเซตว่างของจุดยอด (Vertex) แทนด้วยสัญลักษณ์ V(G) 2. เซตของเส้นเชื่อม (Edge) ที่เชื่อมระหว่างจุดยอด แทนด้วยสัญลักษณ์ E(G) |
ข้อสังเกต V(G) ≠ ∅ แต่ E(G) อาจเป็นเซตว่างได้
บทนิยาม จุดยอด 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 ไม่เป็นจุดยอดประชิด
บทนิยาม เส้นเชื่อมตั้งแต่ 2 เส้นที่เชื่อมระหว่างจุดยอดคู่เดียวกัน เรียกว่า เส้นเชื่อมขนาน(Parallel Edges) เส้นเชื่อมที่เชื่อมจุดยอดเพียงจุดเดียว เรียกว่า วงวน
(Loop)
|
จากรูปข้างต้นจะเห็นว่า
e1 และ e2 เป็น เส้นเชื่อมขนาน เส้นเชื่อม e5 เป็นวงวน ในกรณีที่กราฟไม่มีเส้นเชื่อมขนาน สามารถใช้สัญลักษณ์
AB เพื่อแทนเส้นเชื่อมระหว่างจุดยอด A และ B ได้ เช่น กราฟในตัวอย่างที่ 1 สามารถเขียนเซตของเส้นเชื่อม E(G)
ได้ใหม่เป็น E(G) = {AB, BC, AC, CD}
2.ดีกรีของจุดยอด
บทนิยาม ดีกรี (Degree) ของจุดยอด v ในกราฟ คือ จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด v
ใช้สัญลักษณ์ deg v แทนดีกรีของจุดยอด |
จะเห็นว่า เส้นเชื่อมที่เกิดกับจุดยอด a ได้แก่ เส้นเชื่อม ab และ ac ดังนั้น จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด a
คือ 2 สำหรับจุดยอด b มีเส้นเชื่อมที่เกิดกับจุดยอด b ได้แก่ เส้นเชื่อม ba, bc และ bb เป็นวงวน เกิดกับจุดยอด b
กรณีที่มีเส้นเชื่อมเป็นวงวน จะกำหนดให้นับจำนวนเส้นเชื่อมที่เกิดกับจุดยอดนั้นเพิ่มขึ้น โดยให้นับเส้นเชื่อมที่เป็นวงวน 1 วง วงวนเป็น 2 ดังนั้นจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด b จึงเป็น 4
ทฤษฎีบท 1
ผลรวมของดีกรีของจุดยอดทุดจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ
|
เนื่องจากเส้นเชื่อมแต่ละเส้นในกราฟเกิดกับจุดยอดเป็นจำนวน 2 ครั้ง ดังนั้นเส้นเชื่อมแต่ละเส้นจะถูกนับ 2 ครั้งในผลรวมของดีกรีของจุดยอดทุกจุด
นั่นคือ ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ
บทนิยาม
จุดยอดที่มีดีกรีเป็นจำนวนคู่ เรียกว่า จุดยอดคู่ (Even Vertex)
จุดยอดที่มีดีกรีเป็นจำนวนคี่ เรียกว่า จุดยอดคี่ (Odd Vertex)
|
ทฤษฎีบท 2 ทุกกราฟจะมีจุดยอดคี่เป็นจำนวนคู่
|
3.แนวเดินและกราฟเชื่อมโยง
บทนิยาม ให้ u และ v เป็นจุดยอดของกราฟแนวเดิน
u - v (u - v walk) คือ ลำดับจำกัดของจุดยอดและเส้นเชื่อมสลับกัน
u = u0, e1, u1, e2, u2, …, un-1, en, un = v
โดยเริ่มต้นที่จุดยอด u และสิ้นสุดที่จุดยอด v และแต่ละเส้นเชื่อม ei จะเกิดกับจุดยอดui-1 และ ui เมื่อ i ∈ {1, 2, …, n}
|
สมมติว่า แผนผังของเมืองหนึ่งแทนด้วยกราฟดังรูป โดยให้จุดยอดแทนอำเภอ และเส้นเชื่อมแทนถนนที่เชื่อมระหว่างอำเภอสองอำเภอ
ในการเดินทางจากอำเภอ A ไปยังอำเภอ D มีเส้นทางการเดินทางหลายเส้นทาง
เส้นทางต่างๆ จะแทนดัวยลำดับของจุดยอดและเส้นเชื่อม ดังนี้
เส้นทาง A, e1, E, e5, D
บทนิยาม
รอยเดิน (trail) คือ แนวเดินในกราฟที่เส้นเชื่อมทั้งหมดแตกต่างกัน
วิถี(Path) คือ แนวเดินในกราฟที่จุดยอดทั้งหมดแตกต่างกัน วงจร(Circuit) คือ แนวเดินที่เส้นเชื่อมทั้งหมดแตกต่างกัน โดยมีจุดเริ่มต้นและจุดสุดท้ายเป็นจุดยอดเดียวกัน วัฏจักร(Cycle) คือวงจรที่ไม่มีจุดยอดซ้ำกัน ยกเว้นจุดเริ่มต้นและจุดสุดท้าย
|
บทนิยาม กราฟ G เป็นกราฟเชื่อมโยง(connected graph) ถ้าจุดยอด 2 จุดใดๆ ใน G เชื่อได้ด้วยวิถี
|
4.กราฟถ่วงน้ำหนัก
บทนิยาม
ค่าน้ำหนัก(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 เป็นวิถีที่สั้นที่สุด
สำหรับกราฟถ่วงนำหนักที่มีจุดยอดและเส้นเชื่อมเป็นจำนวนมาก การหาวิถี A - Z ที่สั้นที่สุด
โดยการค้นหาวิถี A - Z ทั้งหมดแล้วเลือกวิถีที่ผลรวมของค่าน้ำหนักน้อยที่สุด ทำได้ไม่สะดวกและเสียเวลา ในการหาวิถี A - Z ที่สั้นที่สุด
บทนิยาม วิถีที่สั้นที่สุด จากจุด A ถึงจุดยอด Z ในกราฟถ่วงน้ำหนัก คือวิถี A - Z ที่ผลรวมของค่าน้ำหนักของเส้นเชื่อมทุกเส้นในวิถี A-Z น้อยที่สุด
|
5. กราฟออยเลอร์
ออยเลอร์ได้ให้ทฤษฎีที่เกี่ยวกับปัญหานี้ไว้ดังนี้
- เครือข่าย ที่แสดงเป็นกราฟจะประกอบด้วยจุดเชื่อมโยง (Vertices) และเส้นเชื่อมโยงระหว่างจุด เรียกว่า arcs
- จุด ที่มีจำนวนเส้นที่เชื่อมออกไปยังจุดอื่นเป็นจำนวนคี่ เรียกว่า odd และถ้าจุดนั้นมีเส้นเชื่อมออกไปยังจุดอื่นเป็นจำนวนคู่ จะเรียกว่า even
- เส้นทางออยเลอร์ คือเส้นทางที่ลากผ่านเส้นต่าง ๆ ในเครือข่าย โดยแต่ละเส้นลากผ่านได้เพียงครั้งเดียว
- ทฤษฎีของออยเลอร์ กล่าวว่า ถ้าหากว่าเครือข่ายใดมีจุดที่เป็น odd มากกว่าสองขึ้นไป จะไม่มีทางสร้างเส้นทางออยเลอร์ได้
บทนิยาม
วงจรออยเลอร์(Euler trail) คือ รอยเดินซึ่งผ่านจุดยอดทุกจุดและเส้นเชื่อมทุกเส้นของกราฟ
ทฤษฎีบท
ให้ G เป็นกราฟเชื่อมโยง จะได้ว่า
G เป็นกราฟออยเลอร์ ก็ต่อเมื่อ จุดยอดทุกจุดของ G มีดีกรีเป็นจำนวนคู่
กราฟที่มีวงจรออยเลอร์ เรียกว่า กราฟออยเลอร์ (Eulerian graph)
ุ6. ต้นไม้
ต่อไปเราจะศึกษากราฟที่มีลักษณะพิเศษชนิดหนึ่ง เรียกว่า ต้นไม้ ซึ่งมีบทบาทสำคัญในการศึกษาทฤษฎีกราฟ
และในการประยุกต์ทางด้านต่างๆ
และในการประยุกต์ทางด้านต่างๆ
เช่น โครงสร้างข้อมูลในวิชาคอมพิวเตอร์ การศึกษาโครงสร้างทางเคมีของสารประกอบไฮโดร์คาร์บอน หรือในการออกแบบวงจรไฟฟ้าและอิเล็กทรอนิกส์
บทนิยาม ต้นไม้ (tree) คือ กราฟเชื่อมโยงที่ไม่มีวัฏจักร |
ไม่มีความคิดเห็น:
แสดงความคิดเห็น