Lecture 4: Basics of trees
- Definition and basic properties of trees
tree is a connected acyclic graph; basic equivalent characterizations - minimal connected, maximal acyclic, path uniqueness, number of edges
- Rooted trees and isomorhpism testing
rooted, and planted (i.e. rooted plus ordered) trees, planted tree coding and decoding, tree center, isomorphism testing for trees via coding
- Spanning trees
definition, and enumeration of spanning trees in a graph
The main goal of this lecture is to survey (and prove) some basic theoretical properties of trees, i.e. the simplest graphs from a structural point of view. The numerous presented simple proofs, moreover, show "in action" several powerful proof methods and tools of discrete mathematics. Additionally, a nice and fast method of testing isomorphism between trees is outlined.
Study the whole Sections 5.1, 5.2, and a few words from 5.3 and Chapter 8. Specifically, Section 8.5 gives a (difficult) proof of the determinant formula for the number of spanning trees of a graph.
Unlike in the book, we are pure computer scientists, and thus we depict rooted trees with the root on the top.