สารบัญ
13 ความสัมพันธ์: กราฟ (คณิตศาสตร์)กราฟบริบูรณ์กราฟเชิงระนาบระนาบจุดยอดทฤษฎีกราฟขั้นตอนวิธีขั้นตอนวิธีของพริมขั้นตอนวิธีของครูสกาลขั้นตอนวิธีของโบรุฟกาต้นไม้ (ทฤษฎีกราฟ)ต้นไม้แบบทอดข้ามต้นไม้แบบทอดข้ามน้อยสุด
- ต้นไม้ทอดข้าม
กราฟ (คณิตศาสตร์)
วาดของกราฟระบุชื่อที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ กราฟ (Graph) ประกอบไปด้วยเซตของวัตถุที่เรียกว่าจุดยอด (vertex) ซึ่งเชื่อมต่อกันด้วยเส้นเชื่อม (edge) โดยทั่วไปแล้วเรามักวาดรูปแสดงกราฟโดยใช้จุด (แทนจุดยอด) เชื่อมกันด้วยเส้น (แทนเส้นเชื่อม) กราฟเป็นวัตถุพื้นฐานของการศึกษาในวิยุตคณิต หัวข้อทฤษฎีกราฟ เส้นเชื่อมอาจมีทิศทางหรือไม่ก็ได้ ตัวอย่างเช่น สมมุติให้จุดยอดแทนคนและเส้นเชื่อมแทนการจับมือกัน เส้นเชื่อมก็จะเป็นเส้นเชื่อมไม่มีทิศ เพราะการที่ A จับมือ B ก็แปลว่า B จับมือ A อย่างไรก็ตาม สมมุติถ้าจุดยอดแทนคนและเส้นเชื่อมแทนการรู้จัก เส้นเชื่อมก็ต้องเป็นเส้นเชื่อมมีทิศทาง เพราะ A รู้จัก B ไม่จำเป็นว่า B ต้องรู้จัก A หรือนั่นก็คือความสัมพันธ์การรู้จักไม่เป็นความสัมพันธ์สมมาตร จุดยอดอาจจะถูกเรียกว่าโหนด ปม หรือจุด ในขณะที่เส้นเชื่อมอาจถูกเรียกว่าเส้น คำว่า "กราฟ" ถูกใช้ครั้งแรกโดย J.J.
ดู ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและกราฟ (คณิตศาสตร์)
กราฟบริบูรณ์
กราฟบริบูรณ์ (complete graph) เป็น กราฟ ที่ทุกคู่ของ จุดยอด ถูกเชื่อมต่อด้วย เส้นเชื่อม เป็น กราฟสม่ำเสมอ ที่มีระดับขั้น n-1 กราฟบริบูรณ์บนจุดยอด n จุด ใช้สัญลักษณ์ K_n, มี n จุดยอด, และ \frac เส้นเชื่อม ไดกราฟบริบูรณ์ (complete digraph) ก็เป็นลักษณะเดียวกับกราฟ ต่างกันที่เส้นเชื่อมแต่ละเส้น จะถูกแทนด้วยเป็นเส้นเชื่อมระบุทิศทาง 2 เส้น ในทิศทางตรงข้ามกัน.
ดู ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและกราฟบริบูรณ์
กราฟเชิงระนาบ
กราฟเชิงระนาบ (planar graph) ในทฤษฎีกราฟ คือกราฟที่สามารถวาดบนระนาบได้โดยไม่มีเส้นเชื่อมใดๆ ตัดกัน เช่น กราฟต่อไปนี้เป็นกราฟเชิงระนาบ ไฟล์:6n-graf.svg 200px (รูปที่สอง สามารถวาดให้ไม่มีเส้นเชื่อมตัดกันได้ โดยย้ายเส้นทแยงมุมเส้นหนึ่งออกไปข้างนอก) แต่กราฟสองรูปข้างล่างนี้ ไม่เป็นกราฟเชิงระนาบ ''K''5 ''K''3,3 เนื่องจากเป็นไปไม่ได้ที่จะวาดกราฟสองรูปนี้โดยไม่มีเส้นเชื่อมตัดกัน กราฟสองรูปนี้เป็นกราฟที่ไม่เป็นกราฟเชิงระนาบที่เล็กที่สุดด้ว.
ดู ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและกราฟเชิงระนาบ
ระนาบ
องระนาบตัดกันในปริภูมิสามมิติ ในทางคณิตศาสตร์ ระนาบ (plane) คือแผ่นราบใดๆ ในพื้นผิวสองมิติ ระนาบคืออุปมัยสองมิติของจุด (ศูนย์มิติ), เส้นตรง (หนึ่งมิติ) และปริภูมิ (สามมิติ) ระนาบสามารถเกิดขึ้นจากปริภูมิย่อยของปริภูมิที่มีมิติมากกว่า อย่างกำแพงในห้อง หรืออาจอยู่อย่างอิสระด้วยตัวเอง ตามในนิยามของเรขาคณิตแบบยุคลิด ในอีกความหมายหนึ่งก็คือ ระนาบเป็นพื้นผิวสองมิติมีความกว้างและความยาว เกิดจากแนวเส้นที่ต่อเนื่องกัน ปิดล้อมพื้นที่ใดพื้นที่หนึ่งทำ ให้เกิดรูปร่าง หรือกลุ่มของจุดและเส้นซึ่งเรามองผ่านไปแล้วเกิดลักษณะของระนาบ ในทางคณิตศาสตร์โดยเฉพาะเรื่องเรขาคณิต, ตรีโกณมิติ, ทฤษฎีกราฟ และกราฟของฟังก์ชันการกระทำจำนวนมากกระทำอยู่ในระน.
ดู ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและระนาบ
จุดยอด
อด (vertex) อาจหมายถึง; คณิตศาสตร.
ดู ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและจุดยอด
ทฤษฎีกราฟ
กราฟที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น ทฤษฎีกราฟ (graph theory) เป็นหนึ่งในสาขาคณิตศาสตร์และวิทยาการคอมพิวเตอร์ ที่ศึกษาถึงคุณสมบัติต่าง ๆ ของกราฟ.
ดู ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและทฤษฎีกราฟ
ขั้นตอนวิธี
ั้นตอนวิธี หรือ อัลกอริทึม (algorithm) หมายถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic) โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน ในการทำงานอย่างเดียวกัน เราอาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time), และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง หนึ่งในขั้นตอนวิธีอย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้.
ดู ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและขั้นตอนวิธี
ขั้นตอนวิธีของพริม
ั้นตอนวิธีของพริม (Prim's algorithm)Prim's Algorithm ถูกพัฒนาโดยนักคณิตศาสตร์ชื่อ Vojtech Jarnik ในปี1930 ต่อมาถูก พัฒนาต่อโดยนักคอมพิวเตอร์ชื่อ Robert C.
ดู ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและขั้นตอนวิธีของพริม
ขั้นตอนวิธีของครูสกาล
การจำลองการทำงานของขั้นตอนวิธีของครูสกาล ขั้นตอนวิธีของครูสกาล (อังกฤษ: Kruskal's algorithm) เป็นขั้นตอนวิธีแบบละโมบในทฤษฎีกราฟ ที่ใช้หา ต้นไม้แบบทอดข้ามน้อยสุด (Minimum spanning tree) สำหรับกราฟเชื่อมโยงแบบมีน้ำหนัก นั้นหมายความว่าเราจะได้เซตย่อยของเส้นเชื่อมในต้นไม้ที่เชื่อมทุกๆปม โดยที่ผลรวมของน้ำหนักบนเส้นเชื่อมจะมีค่าน้อยที่สุด หากกราฟไม่เป็นกราฟเชื่อมโยง เราจะได้ ป่าแบบทอดข้ามน้อยสุด (คือต้นไม้แบบทอดข้ามน้อยสุดแต่ละต้นในกราฟ) ขั้นตอนวิธีนี้ปรากฏครั้งแรกบนนิตยสารทางวิทยาศาสตร์ชื่อ Proceedings of the American Mathematical Society หน้.
ดู ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและขั้นตอนวิธีของครูสกาล
ขั้นตอนวิธีของโบรุฟกา
ั้นตอนวิธีโบรุฟกา (Borůvka's algorithm) คือขั้นตอนวิธีสำหรับหาต้นไม้ทอดข้ามน้อยที่สุดในกราฟที่ทุกเส้นเชื่อมมีน้ำหนักไม่เท่ากัน.
ดู ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและขั้นตอนวิธีของโบรุฟกา
ต้นไม้ (ทฤษฎีกราฟ)
กราฟที่เป็นต้นไม้ ต้นไม้ คือ กราฟที่สองจุดยอดใดๆจะมีวิถีเดินทางถึงกันได้เพียงวิถีเดียว หรือกล่าวอีกนัยหนึ่งว่า เป็นกราฟที่ไม่มีวัฏจักรแต่เป็นกราฟที่เชื่อมต่อกันหมด สำหรับกราฟที่ไม่เชื่อมต่อกันหมดเราเรียกว่า ป่า (forest).
ดู ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและต้นไม้ (ทฤษฎีกราฟ)
ต้นไม้แบบทอดข้าม
ต้นไม้ทอดข้ามกราฟ ต้นไม้ทอดข้าม หรือ ต้นไม้แผ่ทั่ว หมายถึง กราฟย่อยซึ่งมีลักษณะเป็นต้นไม้และมีทุกจุดยอดของกราฟเป็นจุดยอดทุกจุดของต้นไม้ด้วย การหาต้นไม้ทอดข้ามในกราฟใดๆ โดยเฉพาะต้นไม้ทอดข้ามน้อยสุด เป็นปัญหาที่พบบ่อยในวิทยาการคอมพิวเตอร์รูปแบบหนึ่ง.
ดู ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและต้นไม้แบบทอดข้าม
ต้นไม้แบบทอดข้ามน้อยสุด
ตัวอย่างการเชื่อมต่อโหนดแต่ละโหนดเข้าหากันด้วยน้ำหนักรวมน้อยที่สุดวิธีหนึ่งจากกราฟถ่วงน้ำหนัก ต้นไม้แผ่ทั่วที่น้อยที่สุด คือ การเชื่อมต่อโหนดทุก ๆ โหนดในกราฟไม่มีทิศทางเข้าหากัน โดยแต่ละแขนของกราฟมีน้ำหนัก และเป้าหมายคือเชื่อมต่อด้วยน้ำหนักรวมน้อยที่สุด หมวดหมู่:ทฤษฎีกราฟ หมวดหมู่:ปัญหาฟังก์ชันพหุนาม หมวดหมู่:ต้นไม้ทอดข้าม.
ดู ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและต้นไม้แบบทอดข้ามน้อยสุด
ดูเพิ่มเติม
ต้นไม้ทอดข้าม
- ขั้นตอนวิธีการลบย้อนกลับ
- ขั้นตอนวิธีของคริสโตไฟด์
- ขั้นตอนวิธีของครูสกาล
- ขั้นตอนวิธีของพริม
- ขั้นตอนวิธีของโบรุฟกา
- ต้นไม้วิถีสั้นสุด
- ต้นไม้แบบทอดข้าม
- ต้นไม้แบบทอดข้ามน้อยสุด
- ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิด
- เกณฑ์วิธีต้นไม้แบบทอดข้าม
หรือที่รู้จักกันในชื่อ ต้นไม้ทอดข้ามที่น้อยที่สุดแบบยุคลิดต้นไม้ทอดข้ามเล็กสุดแบบยุคลิด