Ctrlk

Tree

tree: an (undirected) connected graph in that any pair of vertices has a unique route between them.
leaf: vertex of degree 1 (has only one edge) in a tree.

Let $\mathbb{G}$ be a connected graph with $n$ vertices, then $\mathbb{G}$ is a tree $\Longleftrightarrow$ $\mathbb{G}$ has exactly $n-1$ edges

Every tree with at least 2 vertices has a leaf. (at least 2 leaves, actually)

General algorithm on a tree T:

// while T is not a trivial tree (with only one vertex)
while T.numberOfVertices > 1 {

    let leaf = T.getLeaf()    // T must have a leaf by theorem
    process(leaf)             // process the leaf
    T.removeLeaf(leaf)        // remove processed leaf with its edge
    
    // ⭐️ after removing the leaf and its edge,
    //    T is still connected and #(edges) = #(vertices) - 1,
    //    so, by theorem, T is still a tree.
}

// finally, T is a trivial tree with only one vertex.
let vertex = T.lastVertex
process(vertex)

👉 First Course in Algorithms Through Puzzles, Sec. 1.6, Graph

PreviousGraph NextAlgorithms

Last updated 3 years ago

Was this helpful?