centroid#

Return the centroid of an unweighted tree.

The centroid of a tree is the set of nodes such that removing any one of them would split the tree into a forest of subtrees, each with at most N / 2 nodes, where N is the number of nodes in the original tree. This set may contain two nodes if removing an edge between them results in two trees of size exactly N / 2.

Parameters:

GNetworkX graph: A tree.

Returns:

clist: List of nodes in centroid of the tree. This could be one or two nodes.

Raises:

NotATree: If the input graph is not a tree.
NotImplementedException: If the input graph is directed.
NetworkXPointlessConcept: If G has no nodes or edges.

See also

barycenter()
center()
center: tree center

Notes

This algorithm’s time complexity is O(N) where N is the number of nodes in the tree.

In unweighted trees the centroid coincides with the barycenter, the node or nodes that minimize the sum of distances to all other nodes. However, this concept is different from that of the graph center, which is the set of nodes minimizing the maximum distance to all other nodes.

Examples

>>> G = nx.path_graph(4)
>>> nx.tree.centroid(G)
[1, 2]

A star-shaped tree with one long branch illustrates the difference between the centroid and the center. The center lies near the middle of the long branch, minimizing maximum distance. The centroid, however, limits the size of any resulting subtree to at most half the total nodes, forcing it to remain near the hub when enough short branches are present.

>>> G = nx.star_graph(6)
>>> nx.add_path(G, [6, 7, 8, 9, 10])
>>> nx.tree.centroid(G), nx.tree.center(G)
([0], [7])