Minimální rozloha stromu - Minimum degree spanning tree - Wikipedia

v teorie grafů, pro připojený graf ${ displaystyle G}$, a kostra ${ displaystyle T}$ je podgrafem ${ displaystyle G}$ s nejmenším počtem hran, které stále pokrývají ${ displaystyle G}$. Lze dokázat řadu vlastností ${ displaystyle T}$. ${ displaystyle T}$ je acyklický, má (${ displaystyle | V | -1}$) hrany kde ${ displaystyle V}$ je počet vrcholů v ${ displaystyle G}$ atd.

A minimální stupeň překlenující strom ${ displaystyle T '}$ je kostra, která má nejmenší maximální stupeň. Vrchol maximálního stupně v ${ displaystyle T '}$ je nejméně ze všech možných klenutých stromů ${ displaystyle G}$.

Nález minimální stupeň překlenující strom je NP těžké, ale algoritmus místního vyhledávání může dát stromu, jehož maximální stupeň je maximálně maximální stupeň optimálního stromu plus jeden.

Vidět Rozpětí stromu s omezeným stupněm.

tento článek ne uvést žádný Zdroje. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Minimální stupeň překlenující strom"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Duben 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)