[go: up one dir, main page]
Scribd
Upload
43 views3 pages

Mathematical Foundations of Computer Science Lecture Outline

The document outlines key concepts in mathematical foundations of computer science including: 1) Spanning trees which are spanning subgraphs that are also trees. Every connected graph contains a spanning tree. 2) Rooted trees which have a distinguished root vertex. Properties like height, children, parents, ancestors and descendants are defined. 3) Binary and full binary trees where internal vertices have at most two or exactly two children respectively. 4) Hamiltonian graphs which contain Hamiltonian cycles where each vertex appears exactly once. Determining if a graph is Hamiltonian is computationally difficult.

Uploaded by

Chenyang Fang
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
43 views3 pages

Mathematical Foundations of Computer Science Lecture Outline

The document outlines key concepts in mathematical foundations of computer science including: 1) Spanning trees which are spanning subgraphs that are also trees. Every connected graph contains a spanning tree. 2) Rooted trees which have a distinguished root vertex. Properties like height, children, parents, ancestors and descendants are defined. 3) Binary and full binary trees where internal vertices have at most two or exactly two children respectively. 4) Hamiltonian graphs which contain Hamiltonian cycles where each vertex appears exactly once. Determining if a graph is Hamiltonian is computationally difficult.

Uploaded by

Chenyang Fang
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Mathematical Foundations of Computer Science

Lecture Outline
October 23, 2018

Spanning Trees
A spanning subgraph of a graph G is a subgraph with vertex set V (G). A spanning tree is
a spanning subgraph that is a tree.

Example. Every connected graph G = (V, E) contains a spanning tree.

Solution. Let T 0 = (V, E 0 ) be a minimally connected spanning subgraph of G. For a


moment assume that such a T 0 always exists. Then, by the equivalence of statements (1)
and (3), T 0 is a tree. Since T 0 is also a spanning subgraph of G, it is a spanning tree of G.
We now show that T 0 , a minimally connected subgraph of G always exists. We will
show this by actually constructing a minimally connected subgraph of G as follows. For
each edge e ∈ E, remove e from E if its removal does not disconnect the graph. Let T 0 be
the resulting subgraph obtained after each edge has been processed once. By construction
and because G is connected, T 0 is connected. Also, by construction, no edge in T 0 can be
removed without disconnecting T 0 . Hence, T 0 is minimally connected.

Rooted Trees
A rooted tree is a tree in which one vertex is distinguished from the others and is called the
root. The level of a vertex, say u, is the number of edges along the unique path between u
and the root. The height of a rooted tree is the maximum level of any vertex in the tree.
Given any vertex of a rooted tree, the children of v are neighbors of v that are one level
away from the root than v. If a vertex v is a child of u, then u is called the parent of v. Two
vertices that are both children of the same parent are called siblings. Given 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. A vertex in a rooted tree is called a leaf if it has no children. Vertices
that have children are called internal vertices. The root is an internal vertex unless it is
the only vertex in the graph, in which case it is a leaf. These definitions are illustrated
in Figure 1. A binary tree is a rooted tree in which every internal vertex has at most two
children. Each child in the binary tree is designated either a left child or a right child (but
not both). A full binary tree is a binary tree in which each internal vertex has exactly two
children.
Given an internal vertex v of a binary tree T , the left subtree of v is the binary tree
whose root is the left child of v, whose vertices consists of the left child of v and all its
descendants, and whose edges consist of all those edges of T that connect the vertices of
the left subtree together. The right subtree of v is defined analogously.
2 Lecture Outline October 23, 2018

root
level 0

u
level 1

v w level 2

level 3

level 4

Figure 1: A rooted tree of height 4. In this tree v is a child of u, u is a parent of v, and v


and w are siblings. All vertices in the marked portion of the tree descendants of u, which
is an ancestor of each vertex.

Example. Prove the following. If k is a positive integer and T is a full binary tree with
k internal vertices then T has a total of 2k + 1 vertices and has k + 1 leaves.

Solution. Suppose T is a full binary tree with k internal vertices. Observe that the set
of all vertices of T can be partitioned into two disjoint subsets: the set of all vertices in T
that have a parent and the set of vertcies in T that do not have a parent. The root of T is
the only vertex in T that does not have a parent. Also, every internal vertex of a full binary
tree has exactly two children. Thus, the total number of children of all internal vertices
equals 2k. This is also the number of vertices that have a parent. Adding one for the root
to this number gives us the total number of vertices in T to be 2k + 1.
Also, the total number of vertices in T is the sum of the number of internal vertices in T
and the number of leaves in T . Hence, the number of leaves in T equals 2k + 1 − k = k + 1.

Example. Any binary tree of height at most h has at most 2h leaves.

Solution. We will prove the claim by doing induction on h. Let P (h) be the property
that a binary tree of height at most h has at most 2h leaves.

Induction Hypothesis: Assume that P (k) is true for some k ≥ 0.


Base Case: P (0) is clearly true as there is only one tree of height at most zero. This tree
has only one vertex which is a leaf. This equals 20 = 1.
Induction Step: We want to prove that P (k + 1) is true. Consider any binary tree T having
height at most k + 1, and root r. Since we have already proven the claim for trees with
height zero in the base case, we will assume that the height of T is at least one. The root
r has at least one and at most two children. Each subtree rooted at a child of r is a rooted
binary tree of height at most k. By induction hypothesis, the number of leaves in these
subtrees is at most 2k . Since r has at most two subtrees rooted at its children, the total
October 23, 2018 Lecture Outline 3

number of leaves in T is at most 2 × 2k = 2k+1 . This proves that P (k + 1) is true and hence
completes the proof.

Hamiltonian Graphs
A Hamiltonian cycle in a graph G is a cycle in which each vertex of G appears exactly
once. A graph is Hamiltonian if it contains a Hamiltonian cycle.

To determine whether a graph is Hamiltonian or not is a very hard problem.

Example. For any integer n ≥ 3, let G be a simple graph on n vertices, and assume that
all vertices in G are of degree at least n/2. Prove that G has a Hamiltonian cycle.

Solution. Assume for contradiction that G does not have a Hamiltonian cycle. Add new
edges to G one-by-one, until we come to a point where adding an edge, say (x, y), creates a
Hamiltonian cycle. Let G0 be the graph in which all vertices have degree at least n/2 and
G0 does not have a Hamiltonian cycle, but adding (x, y) will make G0 Hamiltonian. Since
adding edge (x, y) creates a Hamiltonian cycle in G0 , it must be that G0 has a Hamiltonian
path that begins at x and ends at y. Let the path be x = v1 , v2 , . . . , vn−1 , vn = y. We
now apply the pigeon-hole principle as follows. Let the pigeons be the edges incident on
the vertices x and y, and let the holes be the (n − 1) edges of the form (vi , vi+1 ), where
1 ≤ i ≤ n−1. An edge (pigeon) of the form (x, vi ) is assigned to the “hole” (vi−1 , vi ) and an
edge (pigeon) of the form (y, vi ) is assigned to the “hole” (vi , vi+1 ). Since deg(x) ≥ n/2 and
deg(y) ≥ n/2 and at most one edge incident on x (or y) is assigned to a hole, by the pigeon-
hole principle, there must be i such that 3 ≤ i ≤ n − 1 and there is an edge (x, vi ) and an
edge (y, vi−1 ) (see figure below). Note that since the edge (x, y) does not exist in G0 , the hole
corresponding to (v1 , v2 ) only has one edge, namely (x, v2 ). Similarly, the hole (vn−1 , vn )
will only contain the edge (y, vn−1 ). But this would mean that xv2 v3 · · · vi−1 yvn−1 vn−2 · · · vi
is a Hamiltonian cycle, a contradiction.

v2 vi−1 vi vn−1
x y

You might also like