Trees

Definitions

• A graph is said to be circuit-free iff it has no circuits
• A simple graph is called a tree iff it is circuit-free and connected
  • Lemma 10.5.1: A non-trivial tree has at least one vertex of degree 1 (actually, it has at least two vertices of degree 1)
  • Theorem 10.5.2: Any tree with $n$ vertices ($n>0$) has $n-1$ edges.
  • Theorem 10.5.4: If $G$ is a connected graph with $n$ vertices and $n-1$ edges, then $G$ is a tree.
• A trivial tree is a tree that consists of a single vertex
• A simple graph is called a forest iff it is circuit free and not connected
• Terminal vertex or leaf & internal vertex: If tree $T$ has only one or two vertices, then each is called a terminal vertex. If $T$ has at least 3 vertices, then a vertex of degree 1 in $T$ is called a terminal vertex and a vertex of degree greater than 1 is called an internal vertex

Rooted Tree

• A rooted tree is a tree in which there is one vertex that is distinguished from the others and called the root.
• The level of a vertex is the number of deges along the unique path between it and the the root.
• The height of a rooted tree is the maximum level of any vertex of the tree.
• Children, Parents etc.
  • The children of an internal vertex $v$ of a rooted tree are the vertices that are adjacent to $v$ and are one level further away from the root than v
  • If $w$ is a child of $v$ , then $v$ is called the parent of $w$
  • Two distinct vertices that share the same parent are called siblings
  • Given two distinct vertices $v$ and $w$ , if $v$ lies on the unique path between $w$ and the root, then $v$ is an ancestor of $w$ and $w$ is a descendant of $v$

Binary Tree

A binary tree is a rooted tree in which every parent has at most two children. Each child is designated either a left child or a right child. The left subtree of vertex $v$ is the binary tree whose root is the left child, and consists of the left child and its descendants. (same for right subtree)
A full binary tree is a binary tree in which each parent has exactly two children.

• Theorem 10.6.2: For non-negative integers $h$ , if $T$ is any binary tree with height $h$ and $t$ terminal vertices, then $t\le 2^h$ (equivalently, ${\log }_{2}t\le h$)

Full binary tree theorem

If $T$ is a full binary tree with $k$ internal vertices, then $T$ has a total of $2k+1$ vertices and has $k+1$ terminal vertices

Binary Tree Traversal

Breadth-first seach (BFS)

• Visit vertices level-by-level
• At each level, visit vertices from left to right

Depth-first seach (DFS)

• Pre-order
  • Print the data of the root (or current vertex)
  • Traverse the left subtree by recursively (pre-order)
  • Traverse the right subtree by recursively (pre-order)
• In-order
  • Traverse the left subtree recursively (in-order)
  • Print the data of the root (or current vertex)
  • Traverse the right subtree recursively (in-order)
• Post-order
  • Traverse the left subtree recursively (post-order)
  • Traverse the right subtree recursively (post-order)
  • Print the data of the root (or current vertex)
• “Trick”:
  • Pre-order: draw a dot on the left of the vertex, In-order: bottom between the branches, post-order: right
  • Trace a “path” around the “perimeter” of the whole tree counter-clockwise (take the vertices as circles and edges to have thickness)
  • Print the vertex data when we pass a dot

Spanning Trees

A spanning tree for a graph $G$ is a subgraph of $G$ that contains every vertex of $G$ and is a tree

• Proposition 10.7.1:
  • Every connected graph has a spanning tree
  • Any two spanning trees for a graph have the same number of edges

Minimum spanning tree

For a weighted graph (where each edge has a real number weight, and the total weight of all edges is the total weight of the graph), a minimum spanning tree for a connected weighted graph is a spanning tree that has the least possible total weight compared to all other spanning trees for the graph. Note: if $G$ is a weighted graph and $e$ is an edge of $G$ , then $w(e)$ denotes the weight of $e$ and $w(G)$ denotes the total weight of $G$

Kruskal’s Algorithm (to get MST)

1. Go through the edges of a graph in order of increasing weight
2. For each edge, add it to what will become the minimum spanning tree, provided that it will not create a circuit
3. After n-1 edges have been added, where n is the number of vertices of the graph, these edges, together with the vertices of the graph, form a minimum spanning tree for the graph
   Note: If multiple edges have the same weight, then the minimum spanning tree might not be unique

Prim’s Algorithm (to get MST)

1. Pick a vertex to start, and add it to the tree
2. Find the next vertex to add to the tree by finding the vertex that is connected to the current tree by an edge with the lowest weight
   i.e. keep adding the lowest weight vertex to the tree until all vertices have been added