Digital clock

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

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

บทนิยาม วงจร (circuit) คือแนวเดินที่เส้นเชื่อมทั้งหมด แตกต่างกัน โดยมีจุดเริ่มต้น
                และ จุดสุดท้ายเป็นจุดเดียวกัน
บทนิยาม     วงจรออยเลอร์ (Euler circuit) คือ วงจรที่ผ่านจุดยอดทุกจุด และ เส้นเชื่อมทุกเส้นของกราฟ
              โดยที่จุดสามารถซ้ำกันได้ และจะเรียกกราฟที่มีวงจรออยเลอร์ว่า กราฟออยเลอร์

ทฤษฏีบท 3 กำหนดกราฟ G เป็นกราฟเชื่อมโยง G จะเป็นกราฟออยเลอร์ก็ต่อเมื่อ
                    จุดยอดทุกจุดของ G เป็นจุดยอดคู่

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

คำตอบคือ ไม่ เพราะจุดยอดทุกจุดในกราฟนี้เป็นจุดยอดคี่

บทนิยาม  ค่าน้ำหนัก (weight) ของเส้นเชื่อม e ในกราฟ คือ จำนวนที่ไม่เป็นลบที่กำหนดไว้บนเส้นเชื่อม 

บทนิยาม        กราฟถ่วงน้ำหนัก ( weighted graph) คือกราฟที่เส้นเชื่อมทุกเส้นมีค่าน้ำหนัก
จากบทนิยาม  การกำหนดจำนวนไว้บนเส้นเชื่อมแต่ละเส้น อาจมีจุดมุ่งหมายเพื่อแทนระยะห่างของ
                        ตำแหน่งต่างๆ หรือเวลาที่ใช้เดินทางบนเส้นทางนั้น จากจุดหนึ่ง ถึง จุดที่ต้องการ
                       ในชีวิตประจำวัน [ค่าน้ำหนัก = เส้นทาง (ระยะ) , กราฟถ่วงน้ำหนัก = แผนที่]
                                         
บทนิยาม วิถี (path) คือ แนวเดินในกราฟที่จุดยอดทั้งหมด แตกต่างกัน (ไปโดยไม่ย้อนกลับ)
           
บทนิยาม    วิถีที่สั้นที่สุด จากจุดยอด A ถึง Z ในกราฟถ่วงน้ำหนัก คือ วิถี A-Z ที่ ผลรวม
                ของค่าน้ำหนักบนเส้นเชื่อมทุกเส้นในวิถี A-Z ที่มีค่าน้อยที่สุด (ไปถึงจุดหมายเร็วที่สุด)
                                   
ตัวอย่าง จงหาวิถีที่สั้นที่สุด จาก A ถึง E
                                   
             ตอบ วิถีที่สั้นที่สุดคือ A,B,D,E ค่าน้ำหนักคือ 2+1+3 = 6 ซึ่งมีค่าน้อยที่สุด
บทนิยาม วัฏจักร (cycle) คือ วงจร ทีี่ไม่มีจุดยอดซ้ำกัน ยกเว้น จุดเริ่มต้นและจุดสุดท้าย
                 (จุดเริ่มต้นและสิ้นสุดเป็นจุดเดียวกัน)
บทนิยาม ต้นไม้ (tree) คือ กราฟเชื่อมโยงที่ไม่มีวัฏจักร
ตัวอย่าง
 ไม่เป็น ต้นไม้ เพราะมีวัฏจักร

เป็นต้นไม้

ไม่เป้นต้นไม้เพราะไม่เป้นกราฟเชื่อมโยง
         
    เป็นต้นไม้

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

ตัวอย่าง

จากกราฟข้างต้นจงพิจารณาว่ากราฟใดเป็น กราฟย่อยของกราฟนี้
เป็นกราฟย่อย

ไม่เป็นกราฟย่อย

เป็นกราฟย่อย

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

ตัวอย่าง ต้นไม้แผ่ทั่วที่น้อยที่สุดจากกราฟนี้
พิจจารณา

1+2+1ไม่น้อยที่สุด1+2+1ไม่น้อยที่สุด

1+1+1น้อยที่สุด

ข้อสังเกตุ : ต้นไม้ จะไม่มีเส้นขนานและวงวน

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




ไม่มีความคิดเห็น:

แสดงความคิดเห็น