Trees · Theory Problems

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Advanced Problems.

  1. (20 points) In a tree \(T\) with \(n\) vertices, consider a walk that starts at any vertex, visits every vertex at least once, and may end anywhere (not necessarily where it started). Determine the minimum possible number of edge traversals, expressed in terms of \(n\) and the diameter of \(T\), and prove it.
  2. (20 points) Let \(T\) be a tree on \(n\) vertices. Define the eccentricity of a vertex \(v\) by \[\operatorname{ecc}(v) \coloneqq \max_{u \in V(T)}\operatorname{dist}(u, v).\] Prove that the set of vertices minimizing \(\operatorname{ecc}(\cdot)\) has size \(1\) or \(2\), and if it has size \(2\) then the two vertices are adjacent. Design an \(O(n)\) algorithm to find the center(s).
    Hint:
    Use the notion of a diameter path of a tree, i.e., a longest simple path. Show that for any vertex \(v\), its farthest vertex lies on some diameter.
  3. (20 points) Assume all edge weights are distinct, let \(G=(V,E)\) be a connected weighted graph with at least two spanning trees, and let \(T\) be its MST. For every non-tree edge \(e=(u,v)\in E\setminus E(T)\), let \(f(e)\) be the maximum-weight edge on the unique \(u\)–\(v\) path in \(T\). Design an algorithm to compute the weight of the second-best spanning tree (the lightest spanning tree different from \(T\)) in time \(O((|V| + |E|) \log |V|)\).
    Hint:
    Prove that replacing \(f(e)\) by \(e\) gives the lightest spanning tree that contains \(e\).
  4. (20 points) Let \(T\) be a tree on \(n\) vertices. A centroid is a vertex \(c\) such that every connected component of \(T\setminus\{c\}\) has at most \(n/2\) vertices. Prove that every tree has a centroid, and that there are at most two centroids (and if there are two, they are adjacent). Give a linear-time algorithm to find one.
  5. (20 points) A connected shape made of unit chessboard cells is cut out from an infinite chessboard. The number of black cells in it is exactly three times the number of white cells. Prove that the shape can be partitioned into tetraminoes.
    Hint:
    Consider the adjacency graph of cells (edges between side-adjacent cells) and take a spanning tree.