เวกเตอร์

เวกเตอร์ ม.5

ภ

ขึ้นไป ^

ขึ้นไป ^

ขึ้นไป ^

ขึ้นไป ^

ขึ้นไป ^

ขึ้นไป ^

ความน่าจะเป็น ม.5

                          ความน่าจะเป็น ม.5

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

ทฤษฎีกราฟเบื้องต้น

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) อาจเป็นเซตว่างได้

บทนิยาม จุดยอด 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)

 

  

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

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

         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, e₁, E, e₅, 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) คือ กราฟเชื่อมโยงที่ไม่มีวัฏจักร