While a spanning tree spans all ver

While a spanning tree spans all vertices of a given graph, a Steiner tree spans a given subset of
vertices. In the Steiner minimal tree problem, the vertices are divided into two parts: terminals
and nonterminal vertices. The terminals are the given vertices which must be included in the
solution. The cost of a Steiner tree is defined as the total edge weight. A Steiner tree may contain
some nonterminal vertices to reduce the cost. Let V be a set of vertices. In general, we are given
a set L ⊂ V of terminals and a metric defining the distance between any two vertices in V . The
objective is to find a connected subgraph spanning all the terminals of minimal total cost. Since
the distances are all nonnegative in a metric, the solution is a tree structure. Depending on the
given metric, two versions of the Steiner tree problem have been studied.

ผลลัพธ์ (ไทย) 1:

ในขณะที่ต้นไม้ spanning ครอบคลุมทุกจุดของกราฟกำหนด ต้นไม้ Steiner ครอบคลุมกำหนดชุดย่อยของจุด ในการที่น้อยที่สุดเหตุการณ์ จุดแบ่งออกเป็นสองส่วน: อาคารผู้โดยสารและจุดยอด nonterminal อาคารผู้โดยสารจะกำหนดจุดที่ต้องรวมในการการแก้ปัญหา มีกำหนดต้นทุนของ Steiner ต้นไม้เป็นน้ำหนักรวมขอบ ต้นไม้สไตเนอร์อาจประกอบด้วยบางจุด nonterminal เพื่อลดต้นทุน ให้เป็นชุดของจุดยอด V ทั่วไป เราจะได้รับเป็นชุด L ⊂ V ของอาคารผู้โดยสารและการวัดการกำหนดระยะห่างระหว่างจุดยอดใด ๆ สองใน V การวัตถุประสงค์คือการ หา subgraph การเชื่อมต่อที่ครอบคลุมอาคารทั้งหมดของต้นทุนรวมน้อยที่สุด ตั้งแต่ระยะทาง nonnegative ทั้งหมดในการวัด การแก้ปัญหาคือ โครงสร้างแผนภูมิ ขึ้นอยู่กับการให้วัด รุ่นที่สองของเหตุการณ์ได้รับการศึกษา

ผลลัพธ์ (ไทย) 2:

ในขณะที่ต้นไม้ครอบคลุมครอบคลุมทุกจุดของกราฟต้นไม้ทิครอบคลุมกลุ่มย่อยกำหนด
จุด ในปัญหาต้นไม้ทิน้อยที่สุดจุดจะถูกแบ่งออกเป็นสองส่วนอาคาร
และจุด nonterminal ขั้วเป็นจุดที่กำหนดซึ่งจะต้องรวมอยู่ใน
การแก้ปัญหา ค่าใช้จ่ายของต้นไม้ทิหมายถึงน้ำหนักที่ขอบทั้งหมด ต้นไม้ทิอาจมี
จุด nonterminal บางอย่างเพื่อลดค่าใช้จ่าย Let V เป็นชุดของจุด โดยทั่วไปเราจะได้รับ
ชุด L ⊂ V ของอาคารและตัวชี้วัดการกำหนดระยะห่างระหว่างสองจุดใน V
วัตถุประสงค์คือการหา subgraph เชื่อมต่อทอดขั้วทั้งหมดของค่าใช้จ่ายทั้งหมดที่น้อยที่สุด เนื่องจาก
ระยะทางที่มีทั้งหมดไม่เป็นลบในตัวชี้วัดการแก้ปัญหาคือโครงสร้าง ทั้งนี้ขึ้นอยู่กับ
ตัวชี้วัดที่กำหนดสองรุ่นของปัญหาต้นไม้ทิได้รับการศึกษา

ผลลัพธ์ (ไทย) 3:

ในขณะที่ต้นไม้ทอดข้ามครอบคลุมทุกจุดของกราฟที่ไม่มีต้นไม้ให้ , ขยายให้ย่อยจุดยอด . ในเนอร์น้อยที่สุดต้นไม้ปัญหา จุดแบ่งออกเป็นสองส่วนเทอร์มินัลและ nonterminal จุด . เทอร์มินัลจะกำหนดจุดที่ต้องอยู่ในโซลูชั่น ต้นทุนของ Steiner Tree หมายถึงน้ำหนักที่ขอบทั้งหมด เป็นสไตเนอร์ ต้นไม้อาจประกอบด้วยnonterminal บางจุด เพื่อลดต้นทุน ให้ V เป็นเซตของจุดยอด . โดยทั่วไปเราจะได้รับชุดผม⊂ V ของเทอร์มินัล และตัวชี้วัดการกำหนดระยะห่างระหว่างสองจุดใน V . ที่มีวัตถุประสงค์เพื่อค้นหาการเชื่อมต่อ subgraph ครอบคลุมทุกขั้วของต้นทุนรวมน้อยที่สุด ตั้งแต่ระยะทางทั้งหมด nonnegative ในวัด , โซลูชั่นที่เป็นโครงสร้างต้นไม้ ขึ้นอยู่กับระบุตัวชี้วัด , รุ่นที่สองของ Steiner ต้นไม้ปัญหาได้ถูกศึกษา