Tree

⟩ ⟩ Tree

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

Let $\mathbb{G}$ be a 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)

👉 , Sec. 1.6, Graph

PreviousGraph NextAlgorithms

Last updated 2 years ago

Was this helpful?

// 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)