Graph Theory

Chapter 3 Trees and Forests

大葉大學 資訊工程系 黃鈴玲

2011.9

Contents

• 3.1 Trees and Some of Their Basic Properties
• 3.2 Characterizations of Trees
• 3.3 Inductive Proofs on Trees
• 3.5 Centers in Trees
• 3.6 Rooted Trees
• 3.7 Binary Trees
• 3.8 Levels in Rooted and Binary Trees

​

2

3.1 Trees and Some of Their Basic Properties

3

Definition 3.1

4

star

Ex 3.3

5

Example 3.2

字典找字的方式：a rooted tree

6

Definition 3.3

Theorem 3.4

Ex 3.18

7

Lemma 3.6

3.2 Characterizations of Trees

8

Theorem 3.7

Proof

3.3 Inductive Proofs on Trees

9

Example 3.8

Proof

Regular binary tree: all vertices have degree 3 or less.

Let d₃(n) denote the maximum number of vertices of degree 3

that such a tree T on n vertices can have. Then

(see Ex3.5)

Let x, y, and z be the number of vertices in T of degree 1, 2, 3.

Then x+y+z=n and x+2y+3z=2n−2,

⇒ y+2z=n−2

⇒ 2z ≤ n−2

⇒ z ≤ ⎣n/2⎦ − 1

3.5 Centers in Trees

10

11

Definition 3.15

G: a graph. For u, v ∈V(G), the distance between u and v,�denoted δ(u,v), is the length of the shortest u, v-path in G.

Question

A model of a street system:

Q: How to place the police station and fire station?

edge: street�vertex: intersection

How to choose the locations?

Minimize the response time between the�facility and the location of a possible emergency�(以出發後能最快到達事故地點為訴求)�(choose x to minimize max{δ(x,v) | v∈ V(G) })

14

Definition 3.18 (離心率及中心)

Example 3.19

Tree中eccentricity值最大的一定發生在leaves

removing all leaves,使ε(u)減少1

15

Theorem 3.20

Theorem 3.21

16

Exercise� Find the distance of u,v, and their eccentricities.

u

v

17

Exercise

Exercise

Find all centers of the graph.

18

Definition (直徑及半徑)

The diameter of a graph G is

diam(G) = max{ δ(u, v) : u, v ∈ V(G) } = max{ε(u) : u ∈ V(G) }

The radius of a graph G is

rad(G) = min{ε(u) : u ∈ V(G) }

​

Exercise

Find the diameters and radii of the graphs in Exercise 3.21 and 3.22.

19

3.6 Rooted Trees

Definition 3.22

Example 3.23

20

Definition 3.24

21

Example 3.25

22

Definition 3.26

Example 3.27

23

3.7 Binary Trees

Definition 3.28

Figure 3.15

24

Definition 3.29

Ex 3.33 Draw the regular binary trees on nine vertices.

25

Theorem 3.31

Pf.

若 tree 有 k 個internal vertex，則� 每個 internal vertex 有 2 個children，� 故 tree 共有 2k 個點是 children � (因每個child只有一個parent，所以只會被計算一次)� root 沒有parent，還沒被計算到

∴tree 共有 2k +1 個點 ⇒ 共有 k +1 個 leaves

26

3.8 Levels in Rooted and Binary Trees

Definition 3.37

27

Observation 3.38

Pf.

(a) If ht(T)= k, then n ≤ 2⁰+2¹+…+2^k = 2^k+1 −1

∴ n+1 ≤ 2^k+1 ⇒ lg(n+1) ≤ k+1 ⇒ ⎡lg(n+1) − 1⎤ ≤ ht(T)

(b) Every vertex except the leaves has exactly two � children, each level (except level 0) must contain � at least two vertices.

​

⇒ n ≥ 2ht(T) + 1

⇒ ht(T) ≤ (n−1)/2

(對照下一頁的圖)

28

Example 3.39

29

Definition 3.41

Observation

(level 0 ~ k−1都全滿, level k 不要求)