Слайд 2
![Trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-1.jpg)
Слайд 3
![Trees Some examples of trees are given in the figure.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-2.jpg)
Trees
Some examples of trees are given in the figure.
Слайд 4
![Trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-3.jpg)
Слайд 5
![Trees Example 1](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-4.jpg)
Слайд 6
![Trees Theorem 1 Every connected graph contains a spanning tree.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-5.jpg)
Trees
Theorem 1
Every connected graph contains a spanning tree.
Слайд 7
![? Every connected graph contains a spanning tree. Proof](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-6.jpg)
? Every connected graph contains a spanning tree.
Proof
Слайд 8
![? Every connected graph contains a spanning tree. Proof](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-7.jpg)
? Every connected graph contains a spanning tree.
Proof
Слайд 9
![Trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-8.jpg)
Слайд 10
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-9.jpg)
Слайд 11
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-10.jpg)
Слайд 12
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-11.jpg)
Слайд 13
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-12.jpg)
Слайд 14
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-13.jpg)
Слайд 15
![Trees Definition 3 A forest is a (not necessarily connected)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-14.jpg)
Trees
Definition 3
A forest is a (not necessarily connected) graph each of
whose components is a tree.
Слайд 16
![Trees This is a forest with three connected components.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-15.jpg)
Trees
This is a forest with three connected components.
Слайд 17
![Trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-16.jpg)
Слайд 18
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-17.jpg)
Слайд 19
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-18.jpg)
Слайд 20
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-19.jpg)
Слайд 21
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-20.jpg)
Слайд 22
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-21.jpg)
Слайд 23
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-22.jpg)
Слайд 24
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-23.jpg)
Слайд 25
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-24.jpg)
Слайд 26
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-25.jpg)
Слайд 27
![Weighted graphs](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-26.jpg)
Слайд 28
![Weighted graphs For example, the figure is a diagram of a weighted graph.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-27.jpg)
Weighted graphs
For example, the figure is a diagram of a weighted
graph.
Слайд 29
![Weighted graphs](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-28.jpg)
Слайд 30
![Weighted graphs](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-29.jpg)
Слайд 31
![Weighted graphs](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-30.jpg)
Слайд 32
![Weighted graphs The figure shows a weighted graph with two](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-31.jpg)
Weighted graphs
The figure shows a weighted graph with two minimal spanning
trees, both of weight 22.
Слайд 33
![An algorithm which produces a minimal spanning tree (Prim’s algorithm)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-32.jpg)
An algorithm which produces a minimal spanning tree (Prim’s algorithm)
Слайд 34
![The construction of a minimal spanning tree using Prim’s algorithm](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-33.jpg)
The construction of a minimal spanning tree using Prim’s algorithm
1
9
2
6
3
8
6
4
9
Слайд 35
![The construction of a minimal spanning tree using Prim’s algorithm](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-34.jpg)
The construction of a minimal spanning tree using Prim’s algorithm
1
9
2
6
3
8
6
4
9
1
9
2
6
3
8
6
4
9
Слайд 36
![The construction of a minimal spanning tree using Prim’s algorithm](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-35.jpg)
The construction of a minimal spanning tree using Prim’s algorithm
1
9
2
6
3
8
6
4
9
1
9
2
6
3
8
6
4
9
Слайд 37
![The construction of a minimal spanning tree using Prim’s algorithm](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-36.jpg)
The construction of a minimal spanning tree using Prim’s algorithm
1
9
2
6
3
8
6
4
9
1
9
2
6
3
8
6
4
9
Слайд 38
![The construction of a minimal spanning tree using Prim’s algorithm](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-37.jpg)
The construction of a minimal spanning tree using Prim’s algorithm
1
9
2
6
3
8
6
4
9
1
9
2
6
3
8
6
4
9
Слайд 39
![The construction of a minimal spanning tree using Prim’s algorithm](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-38.jpg)
The construction of a minimal spanning tree using Prim’s algorithm
1
9
2
6
3
8
6
4
9
1
9
2
6
3
8
6
4
9
Слайд 40
![The construction of a minimal spanning tree using Prim’s algorithm](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-39.jpg)
The construction of a minimal spanning tree using Prim’s algorithm
1
9
2
6
3
8
6
4
9
1
9
2
6
3
8
6
4
9
Слайд 41
![The construction of a minimal spanning tree using Prim’s algorithm](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-40.jpg)
The construction of a minimal spanning tree using Prim’s algorithm
1
9
2
6
3
8
6
4
9
1
9
2
6
3
8
6
4
9
Слайд 42
![The construction of a minimal spanning tree using Prim’s algorithm](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-41.jpg)
The construction of a minimal spanning tree using Prim’s algorithm
1
9
2
6
3
8
6
4
9
1
9
2
6
3
8
6
4
9
Слайд 43
![The construction of a minimal spanning tree using Prim’s algorithm](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-42.jpg)
The construction of a minimal spanning tree using Prim’s algorithm
1
9
2
6
3
8
6
4
9
1
9
2
6
3
8
6
4
9
Слайд 44
![The construction of a minimal spanning tree using Prim’s algorithm](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-43.jpg)
The construction of a minimal spanning tree using Prim’s algorithm
1
9
2
6
3
8
6
4
9
1
9
2
6
3
8
6
4
9
Слайд 45
![Prim’s algorithm](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-44.jpg)
Слайд 46
![Rooted trees Many of the applications of graph theory, particularly](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-45.jpg)
Rooted trees
Many of the applications of graph theory, particularly in computing,
use a certain kind of tree, called a ‘rooted tree’.
This is simply a tree where a particular vertex has been distinguished or singled out from the rest.
Слайд 47
![Rooted trees For example, family tree are graphs that represent genealogical charts.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-46.jpg)
Rooted trees
For example, family tree are graphs that represent genealogical charts.
Слайд 48
![The family tree of the male members of the Bernoulli](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-47.jpg)
The family tree of the male members of the Bernoulli family
of Swiss mathematicians is shown in the figure.
Слайд 49
![Rooted trees Family trees use vertices to represent the members](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-48.jpg)
Rooted trees
Family trees use vertices to represent the members of a
family and edges to represent parent – child relationships.
The undirected graph representing a family tree (restricted to people of just one gender and with no inbreeding) is an example of a rooted tree.
Слайд 50
![Rooted trees The undirected graph representing the family tree of](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-49.jpg)
Rooted trees
The undirected graph representing the family tree of the male
members of the Bernoulli family of Swiss mathematicians is an example of a rooted tree.
Слайд 51
![Rooted trees Rooted trees are perhaps most familiar in computing](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-50.jpg)
Rooted trees
Rooted trees are perhaps most familiar in computing as models
for the structure of file directories.
Слайд 52
![Rooted trees Some of the other important uses of rooted](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-51.jpg)
Rooted trees
Some of the other important uses of rooted trees in
computing include the representation of data and the representation of algebraic expressions.
Слайд 53
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-52.jpg)
Слайд 54
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-53.jpg)
Слайд 55
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-54.jpg)
Слайд 56
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-55.jpg)
Слайд 57
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-56.jpg)
Слайд 58
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-57.jpg)
Слайд 59
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-58.jpg)
Слайд 60
![Rooted trees Determine the level of each vertex of the following rooted tree.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-59.jpg)
Rooted trees
Determine the level of each vertex of the following rooted
tree.
Слайд 61
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-60.jpg)
Слайд 62
![Rooted trees It is clearly possible to define further terms](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-61.jpg)
Rooted trees
It is clearly possible to define further terms such as
grandparent, grandchild, ancestor, descendant, etc.
Слайд 63
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-62.jpg)
Слайд 64
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-63.jpg)
Слайд 65
![Rooted trees Rooted trees can be used as models in](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-64.jpg)
Rooted trees
Rooted trees can be used as models in such diverse
areas as
computer science,
biology,
management.
Слайд 66
![Rooted trees Of particular importance in applications in computing are](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-65.jpg)
Rooted trees
Of particular importance in applications in computing are binary rooted
trees.
A binary rooted tree has a property that each vertex has at most two children.
In a binary rooted tree the two subtrees of a vertex are referred to as the left-subtree and the right-subtree of the vertex.
If a vertex has no left child its left-subtree is said to be the null tree (i.e. a tree with no vertices).
Similarly, if a vertex has no right child its right-subtree is said to be the null tree.
Слайд 67
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-66.jpg)
Слайд 68
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-67.jpg)
Слайд 69
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-68.jpg)
Слайд 70
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-69.jpg)
Слайд 71
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-70.jpg)
Слайд 72
![Rooted trees](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/197328/slide-71.jpg)