และ จุดสุดท้ายเป็นจุดเดียวกัน
บทนิยาม วงจรออยเลอร์ (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 เป็นต้น
ไม่มีความคิดเห็น:
แสดงความคิดเห็น