Minimum degree spanning tree
In graph theory, for a connected graph [math]\displaystyle{ G }[/math], a spanning tree [math]\displaystyle{ T }[/math] is a subgraph of [math]\displaystyle{ G }[/math] with the least number of edges that still spans [math]\displaystyle{ G }[/math]. A number of properties can be proved about [math]\displaystyle{ T }[/math]. [math]\displaystyle{ T }[/math] is acyclic, has ([math]\displaystyle{ |V|-1 }[/math]) edges where [math]\displaystyle{ V }[/math] is the number of vertices in [math]\displaystyle{ G }[/math] etc. A minimum degree spanning tree [math]\displaystyle{ T' }[/math] is a spanning tree which has the least maximum degree. The vertex of maximum degree in [math]\displaystyle{ T' }[/math] is the least among all possible spanning trees of [math]\displaystyle{ G }[/math].
Finding minimum degree spanning tree is NP hard, but a local search algorithm can give a tree which its maximum degree is at most the maximum degree of optimal tree plus one.
See Degree-Constrained Spanning Tree.
This article does not cite any external source. HandWiki requires at least one external source. See citing external sources. (2021) (Learn how and when to remove this template message) |
Original source: https://en.wikipedia.org/wiki/Minimum degree spanning tree.
Read more |