This document provides an overview of a course on combinatorial optimization taught by Professor Amin Saberi. It introduces basic concepts in graph theory, including definitions of graphs, vertices, edges, walks, paths, cycles, trees, and forests. It also covers properties of trees, including that the number of edges in a tree of size n is n-1, and that every tree has at least two leaves (vertices of degree 1) if n is greater than or equal to 2. Finally, it discusses counting labeled trees and proves Cayley's theorem that the number of labeled trees with n vertices is n^(n-2) using Prüfer codes.
This document provides an overview of a course on combinatorial optimization taught by Professor Amin Saberi. It introduces basic concepts in graph theory, including definitions of graphs, vertices, edges, walks, paths, cycles, trees, and forests. It also covers properties of trees, including that the number of edges in a tree of size n is n-1, and that every tree has at least two leaves (vertices of degree 1) if n is greater than or equal to 2. Finally, it discusses counting labeled trees and proves Cayley's theorem that the number of labeled trees with n vertices is n^(n-2) using Prüfer codes.
This document provides an overview of a course on combinatorial optimization taught by Professor Amin Saberi. It introduces basic concepts in graph theory, including definitions of graphs, vertices, edges, walks, paths, cycles, trees, and forests. It also covers properties of trees, including that the number of edges in a tree of size n is n-1, and that every tree has at least two leaves (vertices of degree 1) if n is greater than or equal to 2. Finally, it discusses counting labeled trees and proves Cayley's theorem that the number of labeled trees with n vertices is n^(n-2) using Prüfer codes.
This document provides an overview of a course on combinatorial optimization taught by Professor Amin Saberi. It introduces basic concepts in graph theory, including definitions of graphs, vertices, edges, walks, paths, cycles, trees, and forests. It also covers properties of trees, including that the number of edges in a tree of size n is n-1, and that every tree has at least two leaves (vertices of degree 1) if n is greater than or equal to 2. Finally, it discusses counting labeled trees and proves Cayley's theorem that the number of labeled trees with n vertices is n^(n-2) using Prüfer codes.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
You are on page 1/ 5
MS&E 212: Combinatorial Optimization
Instructor: Professor Amin Saberi (saberi@stanford.edu)
Lecture 1 - Monday 1/12/2009
Basic Concepts in Graph Theory
A graph G(V, E) is a set V of vertices and a set E of edges. We usually denote |V | as n,
and |E| as m. In an undirected graph, an edge is an unordered pair of vertices. An ordered pair of vertices is called a directed edge. If we allow multi-sets of edges, i.e. multiple edges between two vertices, this is known as a multigraph. A self-loop or loop is an edge between a vertex and itself. An undirected graph without loops or multiple edges is known as a simple graph. In this class we will assume graphs to be simple unless otherwise stated. If vertices a and b are endpoints of an edge, we say that they are adjacent and write a ∼ b. If vertex a is one of edge e’s endpoints, a is incident to e and we write a ∈ e. The degree of a vertex is the number of edges incident to it, denoted di for vertex vi ∈ V . A walk is a sequence of vertices v1 ....vk such that ∀i ∈ 1..k − 1, vi ∼ vi+1 . A path is a walk where vi 6= vj , ∀i 6= j, i.e. a walk that visits each vertex at most once. A closed walk is a walk where v1 = vk . A cycle is a closed path, i.e. a path combined with the edge (vk , v1 ). A graph is connected if there exists a path between each pair of vertices. A tree is a connected graph with no cycles. A forest is a graph where each connected component is a tree. A node in a forest with degree 1 is called a leaf.
Claim 1 (simple properties of trees)
• The number of edges in a tree of size n is n − 1
• Every tree has at least two leaves (vertices of degree 1),assuming n ≥ 2.
Proof: The first property can be seen by starting a path at an arbitrary node, walking to any neighbor that hasn’t been visited before. After at most n steps, we must reach a vertex v where there are no untraversed neighbors. v must therefore have only one neighbor and is a leaf, otherwise there is a cycle and the graph is not a tree. We can then traverse a path starting at v, and the vertex where the path stops must be a second leaf. We can show the second property by induction. The base case n = 1 is trivial. Any tree of size n > 1 has at least one leaf. Removing a leaf results in a tree with one less node and one less edge. Therefore, a tree with n vertices has one more edge than a tree with n − 1 vertices. Applying this to the base case proves the result. 2 MS&E 212: Combinatorial Optimization - Lecture 1
Graph and Tree Combinatorics
n
How many graphs are there with n vertices? Since there are 2 distinct edges, there are 2( 2 ) graphs. n
We call a graph labeled if the vertex ordering is important. How many labeled trees are there for a given number of vertices n?
Theorem 1 Cayley’s Theorem (19’th century)
The number of labeled trees with n vertices is nn−2 .
The idea of our proof will be to use a bijective mapping between labeled trees and something easier to count. To prove Cayley’s theorem, we will use Prüfer codes. To build the Prüfer code of a tree T (V, E), we use the following iterative procedure. For t = 1, 2, · · · , n − 1,
• Let vertex i be the leaf with smallest label in T at step t, and vertex j its parent.
• Remove i from T .
• Let A′t = j, and let Bt = i.
• Repeat until there are no edges.
We call the two n − 1 length strings A′ and B extended Prüfer code of T . Note that this is just a permuted edge list of T . By construction, the last entry of A′ must be n, since n will never be the leaf with smallest label and there are always at least two leaves. The string A obtained by erasing the last entry of A′ is the Prüfer code of T .
Lemma 1 We can construct B and A′ using only A.
Proof: Given A, we construct A′ by appending n to A. Let A′ = a1 a2 ...an−2 n, we construct B = b1 b2 ...bn−1 as follows: ∀i, bi is the smallest number that hasn’t appeared in {b1 , .., bi−1 } ∪ {ai , ..., an−2 }. This can be seen from the way in which Prüfer codes are constructed by ’pruning’ leaf from the tree. At step i, we have removed nodes {b1 , .., bi−1 }, and it can’t be a parent (so it’s not in MS&E 212: Combinatorial Optimization - Lecture 1 3
{ai , ..., an−2 }). All remaining nodes correspond to precisely the set of leaves, so bi must be the smallest of these as stated.
Proposition 1 The following hold for Prüfer codes:
• The number of Prüfer codes is nn−2 .
• ∀v ∈ V , the degree of v is the number of times it appears in the code plus one.
• Each Prüfer code yields exactly one tree.
Proof: The first statement is obvious from the Prüfer code representation; there are n choices at each n − 2 digit of the code. To see the second statement, simply note that the number of times it appears in the code is the number of “child” vertices it has, then add one for being a leaf at some point to account for the degree. To prove the third statement, note that each tree produces a unique Prüfer code by the deterministic nature of their construction. Also, as shown in lemma 1, we can uniquely construct an edge list from each Prüfer code. All that remains to be shown is that the edge list recovered must be a tree. This is easy to see, as at each stage in the reconstruction of B from lemma 1, starting from the right we are adding nodes of degree one. Since we start with a tree, and adding a node of degree one to a tree produces another tree, the final graph must be a tree. 4 5
