CODEWITHSUNDEEP
data-structurestreeminimum-spanning-tree
hysoftwareeng
hysoftwareeng

Reputation: 497

What is a minimum leaf spanning tree?

Could someone explain to be what a minimum leaf spanning tree is? I am confused to what exactly is a leaf in a spanning tree. I understand a spanning tree contains simple paths with no cycles and it spans all vertices in a graph G, but what is a minimum leaf one?

Upvotes: 1

Views: 3210

Answers (2)

DML
DML

Reputation: 544

A leaf is a vertex of degree one in a tree. The degree of a vertex is equal to the number of edges that contain the vertex. A minimum leaf spanning tree is a problem that given a graph G = (V, E) and an integer i, is there a spanning tree T in G that contains at most i leaves?

Upvotes: 1

kraskevich
kraskevich

Reputation: 18566

By definition, a leaf here means a vertex with degree 1. So a minimum leaf spanning tree is a spanning tree with the minimum number of vertices with degree 1.

Upvotes: 1

Related Questions