เร็วกว่าเบราว์เซอร์!
13 ความสัมพันธ์: กราฟ (คณิตศาสตร์)กราฟบริบูรณ์กราฟเชิงระนาบระนาบจุดยอดทฤษฎีกราฟขั้นตอนวิธีขั้นตอนวิธีของพริมขั้นตอนวิธีของครูสกาลขั้นตอนวิธีของโบรุฟกาต้นไม้ (ทฤษฎีกราฟ)ต้นไม้แบบทอดข้ามต้นไม้แบบทอดข้ามน้อยสุด
กราฟ (คณิตศาสตร์)
วาดของกราฟระบุชื่อที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ กราฟ (Graph) ประกอบไปด้วยเซตของวัตถุที่เรียกว่าจุดยอด (vertex) ซึ่งเชื่อมต่อกันด้วยเส้นเชื่อม (edge) โดยทั่วไปแล้วเรามักวาดรูปแสดงกราฟโดยใช้จุด (แทนจุดยอด) เชื่อมกันด้วยเส้น (แทนเส้นเชื่อม) กราฟเป็นวัตถุพื้นฐานของการศึกษาในวิยุตคณิต หัวข้อทฤษฎีกราฟ เส้นเชื่อมอาจมีทิศทางหรือไม่ก็ได้ ตัวอย่างเช่น สมมุติให้จุดยอดแทนคนและเส้นเชื่อมแทนการจับมือกัน เส้นเชื่อมก็จะเป็นเส้นเชื่อมไม่มีทิศ เพราะการที่ A จับมือ B ก็แปลว่า B จับมือ A อย่างไรก็ตาม สมมุติถ้าจุดยอดแทนคนและเส้นเชื่อมแทนการรู้จัก เส้นเชื่อมก็ต้องเป็นเส้นเชื่อมมีทิศทาง เพราะ A รู้จัก B ไม่จำเป็นว่า B ต้องรู้จัก A หรือนั่นก็คือความสัมพันธ์การรู้จักไม่เป็นความสัมพันธ์สมมาตร จุดยอดอาจจะถูกเรียกว่าโหนด ปม หรือจุด ในขณะที่เส้นเชื่อมอาจถูกเรียกว่าเส้น คำว่า "กราฟ" ถูกใช้ครั้งแรกโดย J.J. Sylvester ในปี..
ใหม่!!: ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและกราฟ (คณิตศาสตร์) · ดูเพิ่มเติม »
กราฟบริบูรณ์
กราฟบริบูรณ์ (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. Prim ในปี1957 และ Edsger Dijkstra ในปี1959 ดังนั้น อัลกอริทึมนี้บางทีจึงมักเรียกว่า DJP Algorithm, Jarnik Algorithm หรือ Prim-Jarnik Algorithm ซึ่งเป็นอัลกอริทึมที่ใช้ในการหาขนาด หรือน้ำหนักของต้นไม้ทอดข้ามที่น้อยที่สุด เราจะเริ่มจากการทำ minimum spanning tree เล็ก ๆในกราฟก่อน จากนั้นจะค่อยๆเลือก edge ที่ ไม่ต่อกับ minimum spanning tree ย่อย ๆเดิมมาต่อเพิ่มไปเรื่อย ๆ จนได้ครบทุก node ซึ่ง algorithm ตัวนี้ จะ implement คล้ายๆกับ Dijkstra's Algorithm ตัวอย่างขั้นตอนวิธีการของพริม.
ใหม่!!: ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและขั้นตอนวิธีของพริม · ดูเพิ่มเติม »
ขั้นตอนวิธีของครูสกาล
การจำลองการทำงานของขั้นตอนวิธีของครูสกาล ขั้นตอนวิธีของครูสกาล (อังกฤษ: Kruskal's algorithm) เป็นขั้นตอนวิธีแบบละโมบในทฤษฎีกราฟ ที่ใช้หา ต้นไม้แบบทอดข้ามน้อยสุด (Minimum spanning tree) สำหรับกราฟเชื่อมโยงแบบมีน้ำหนัก นั้นหมายความว่าเราจะได้เซตย่อยของเส้นเชื่อมในต้นไม้ที่เชื่อมทุกๆปม โดยที่ผลรวมของน้ำหนักบนเส้นเชื่อมจะมีค่าน้อยที่สุด หากกราฟไม่เป็นกราฟเชื่อมโยง เราจะได้ ป่าแบบทอดข้ามน้อยสุด (คือต้นไม้แบบทอดข้ามน้อยสุดแต่ละต้นในกราฟ) ขั้นตอนวิธีนี้ปรากฏครั้งแรกบนนิตยสารทางวิทยาศาสตร์ชื่อ Proceedings of the American Mathematical Society หน้. 48-50 ในปี 1956, และเขียนโดย โจเซฟ ครูสกาล และยังมีขั้นตอนวิธีสำหรับแก้ปัญหาแบบเดียวกัน เช่น ขั้นตอนวิธีของพริม ขั้นตอนวิธีการลบย้อนกลับ และ ขั้นตอนวิธีของโบรุฟก.
ใหม่!!: ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและขั้นตอนวิธีของครูสกาล · ดูเพิ่มเติม »
ขั้นตอนวิธีของโบรุฟกา
ั้นตอนวิธีโบรุฟกา (Borůvka's algorithm) คือขั้นตอนวิธีสำหรับหาต้นไม้ทอดข้ามน้อยที่สุดในกราฟที่ทุกเส้นเชื่อมมีน้ำหนักไม่เท่ากัน.
ใหม่!!: ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและขั้นตอนวิธีของโบรุฟกา · ดูเพิ่มเติม »
ต้นไม้ (ทฤษฎีกราฟ)
กราฟที่เป็นต้นไม้ ต้นไม้ คือ กราฟที่สองจุดยอดใดๆจะมีวิถีเดินทางถึงกันได้เพียงวิถีเดียว หรือกล่าวอีกนัยหนึ่งว่า เป็นกราฟที่ไม่มีวัฏจักรแต่เป็นกราฟที่เชื่อมต่อกันหมด สำหรับกราฟที่ไม่เชื่อมต่อกันหมดเราเรียกว่า ป่า (forest).
ใหม่!!: ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและต้นไม้ (ทฤษฎีกราฟ) · ดูเพิ่มเติม »
ต้นไม้แบบทอดข้าม
ต้นไม้ทอดข้ามกราฟ ต้นไม้ทอดข้าม หรือ ต้นไม้แผ่ทั่ว หมายถึง กราฟย่อยซึ่งมีลักษณะเป็นต้นไม้และมีทุกจุดยอดของกราฟเป็นจุดยอดทุกจุดของต้นไม้ด้วย การหาต้นไม้ทอดข้ามในกราฟใดๆ โดยเฉพาะต้นไม้ทอดข้ามน้อยสุด เป็นปัญหาที่พบบ่อยในวิทยาการคอมพิวเตอร์รูปแบบหนึ่ง.
ใหม่!!: ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและต้นไม้แบบทอดข้าม · ดูเพิ่มเติม »
ต้นไม้แบบทอดข้ามน้อยสุด
ตัวอย่างการเชื่อมต่อโหนดแต่ละโหนดเข้าหากันด้วยน้ำหนักรวมน้อยที่สุดวิธีหนึ่งจากกราฟถ่วงน้ำหนัก ต้นไม้แผ่ทั่วที่น้อยที่สุด คือ การเชื่อมต่อโหนดทุก ๆ โหนดในกราฟไม่มีทิศทางเข้าหากัน โดยแต่ละแขนของกราฟมีน้ำหนัก และเป้าหมายคือเชื่อมต่อด้วยน้ำหนักรวมน้อยที่สุด หมวดหมู่:ทฤษฎีกราฟ หมวดหมู่:ปัญหาฟังก์ชันพหุนาม หมวดหมู่:ต้นไม้ทอดข้าม.
ใหม่!!: ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิดและต้นไม้แบบทอดข้ามน้อยสุด · ดูเพิ่มเติม »
เปลี่ยนเส้นทางที่นี่:
ต้นไม้ทอดข้ามที่น้อยที่สุดแบบยุคลิดต้นไม้ทอดข้ามเล็กสุดแบบยุคลิดต้นไม้แผ่ทั่วที่น้อยที่สุดแบบยุคลิดต้นไม้แบบทอดข้ามเล็กสุดของยุคลิด
