คณิตศาสตร์ไม่ต่อเนื่อง - ต้นไม้ที่ทอดยาว

ต้นไม้ที่ทอดของกราฟที่ไม่มีทิศทางที่เชื่อมต่อ $ G $ คือต้นไม้ที่รวมจุดยอดทั้งหมดของ $ G $ ไว้น้อยที่สุด กราฟอาจมีต้นไม้ที่ทอดยาวมากมาย

ตัวอย่าง

ต้นไม้ระยะขั้นต่ำ

ต้นไม้ทอดที่มีน้ำหนักที่กำหนดน้อยกว่าหรือเท่ากับน้ำหนักของกราฟที่มีน้ำหนักเชื่อมต่อและไม่ได้กำหนดทิศทาง $ G $ เรียกว่าต้นไม้ระยะต่ำสุด (MST) น้ำหนักของต้นไม้ทอดคือผลรวมของน้ำหนักทั้งหมดที่กำหนดให้กับขอบแต่ละด้านของต้นไม้ที่ทอด

ตัวอย่าง

อัลกอริทึมของ Kruskal

อัลกอริทึมของ Kruskal เป็นอัลกอริธึมแบบละโมบที่ค้นหาต้นไม้ที่มีระยะเวลาขั้นต่ำสำหรับกราฟถ่วงน้ำหนักที่เชื่อมต่อ พบต้นไม้ของกราฟนั้นซึ่งรวมทุกจุดยอดและน้ำหนักรวมของขอบทั้งหมดในต้นไม้นั้นน้อยกว่าหรือเท่ากับต้นไม้ที่ทอดเป็นไปได้ทั้งหมด

อัลกอริทึม

Step 1 - จัดเรียงขอบทั้งหมดของกราฟที่กำหนด $ G (V, E) $ จากน้อยไปมากตามน้ำหนักขอบ

Step 2 - เลือกขอบถ่วงน้ำหนักที่เล็กที่สุดจากกราฟและตรวจสอบว่ามันก่อตัวเป็นวัฏจักรโดยมีต้นไม้ทอดที่ก่อตัวขึ้นจนถึงตอนนี้หรือไม่

Step 3 - หากไม่มีรอบให้รวมขอบนี้เข้ากับต้นไม้ที่ทอดแล้วทิ้ง

Step 4 - ทำซ้ำขั้นตอนที่ 2 และขั้นตอนที่ 3 จนกว่า $ (V-1) $ จำนวนขอบจะเหลืออยู่ในต้นไม้ที่ทอด

Problem

สมมติว่าเราต้องการหาโครงสร้างสแปนนิงขั้นต่ำสำหรับกราฟ G ต่อไปนี้โดยใช้อัลกอริทึมของ Kruskal

Solution

จากกราฟด้านบนเราสร้างตารางต่อไปนี้ -

ขอบเลขที่	คู่เวอร์เท็กซ์	น้ำหนักขอบ
E1	(ก, ข)	20
E2	(ก, ค)	9
E3	(ก, ง)	13
E4	(ข, ค)	1
E5	(ข, จ)	4
E6	(ข, ฉ)	5
E7	(ค, ง)	2
E8	(ง, จ)	3
E9	(ง, ฉ)	14

ตอนนี้เราจะจัดเรียงตารางใหม่ตามลำดับจากน้อยไปหามากตามน้ำหนักขอบ -

ขอบเลขที่	คู่เวอร์เท็กซ์	น้ำหนักขอบ
E4	(ข, ค)	1
E7	(ค, ง)	2
E8	(ง, จ)	3
E5	(ข, จ)	4
E6	(ข, ฉ)	5
E2	(ก, ค)	9
E3	(ก, ง)	13
E9	(ง, ฉ)	14
E1	(ก, ข)	20

เนื่องจากเราได้ขอบทั้ง 5 ด้านในรูปสุดท้ายเราจึงหยุดอัลกอริทึมและนี่คือต้นไม้ที่มีการขยายน้อยที่สุดและน้ำหนักรวมคือ $ (1 + 2 + 3 + 5 + 9) = 20 $

อัลกอริทึมของ Prim

อัลกอริทึมของ Prim ค้นพบในปี 1930 โดยนักคณิตศาสตร์ Vojtech Jarnik และ Robert C. พบต้นไม้ของกราฟนั้นซึ่งรวมทุกจุดยอดและน้ำหนักรวมของขอบทั้งหมดในต้นไม้นั้นน้อยกว่าหรือเท่ากับต้นไม้ที่ทอดเป็นไปได้ทั้งหมด อัลกอริทึมของ Prim เร็วกว่าบนกราฟที่หนาแน่น

อัลกอริทึม

เริ่มต้นต้นไม้ที่ทอดน้อยที่สุดด้วยจุดยอดเดียวโดยสุ่มเลือกจากกราฟ
ทำซ้ำขั้นตอนที่ 3 และ 4 จนกว่าจุดยอดทั้งหมดจะรวมอยู่ในแผนภูมิ
เลือกขอบที่เชื่อมต่อต้นไม้กับจุดยอดที่ยังไม่ได้อยู่ในต้นไม้เพื่อให้น้ำหนักของขอบน้อยที่สุดและการรวมขอบจะไม่ก่อให้เกิดวัฏจักร
เพิ่มขอบที่เลือกและจุดยอดที่เชื่อมต่อกับต้นไม้

Problem

สมมติว่าเราต้องการหาโครงสร้างสแปนนิงขั้นต่ำสำหรับกราฟ G ต่อไปนี้โดยใช้อัลกอริทึมของ Prim