Trees, rooted trees. Graphs. Lecture 10, презентация

Содержание

Слайд 2

Trees

Trees

 

Слайд 3

Trees Some examples of trees are given in the figure.

Trees
Some examples of trees are given in the figure.

Слайд 4

Trees

Trees

 

Слайд 5

Trees Example 1

Trees

Example 1

 

 

Слайд 6

Trees Theorem 1 Every connected graph contains a spanning tree.

Trees

Theorem 1
Every connected graph contains a spanning tree.

Слайд 7

? Every connected graph contains a spanning tree. Proof

? Every connected graph contains a spanning tree. Proof

 

Слайд 8

? Every connected graph contains a spanning tree. Proof

? Every connected graph contains a spanning tree. Proof

 

Слайд 9

Trees

Trees

 

 

Слайд 10

 

 

Слайд 11

 

 

Слайд 12

 

 

Слайд 13

 

 

Слайд 14

 

Слайд 15

Trees Definition 3 A forest is a (not necessarily connected)

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.

Trees
This is a forest with three connected components.

Слайд 17

Trees

Trees

 

Слайд 18

 

 

Слайд 19

 

 

Слайд 20

 

 

Слайд 21

 

 

Слайд 22

 

 

Слайд 23

 

 

Слайд 24

 

 

Слайд 25

 

 

Слайд 26

 

 

Слайд 27

Weighted graphs

Weighted graphs

 

Слайд 28

Weighted graphs For example, the figure is a diagram of a weighted graph.

Weighted graphs

For example, the figure is a diagram of a weighted

graph.
Слайд 29

Weighted graphs

Weighted graphs

 

Слайд 30

Weighted graphs

Weighted graphs

 

Слайд 31

Weighted graphs

Weighted graphs

 

Слайд 32

Weighted graphs The figure shows a weighted graph with two

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)

An algorithm which produces a minimal spanning tree (Prim’s algorithm)

 

Слайд 34

The construction of a minimal spanning tree using Prim’s algorithm

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

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

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

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

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

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

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

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

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

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

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

Prim’s algorithm

 

Слайд 46

Rooted trees Many of the applications of graph theory, particularly

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.

Rooted trees

For example, family tree are graphs that represent genealogical charts.

Слайд 48

The family tree of the male members of the Bernoulli

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

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

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

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

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

Rooted trees

 

Слайд 54

Rooted trees

Rooted trees

 

Слайд 55

Rooted trees

Rooted trees

 

Слайд 56

Rooted trees

Rooted trees

 

Слайд 57

Rooted trees

Rooted trees

 

Слайд 58

Rooted trees

Rooted trees

 

Слайд 59

Rooted trees

Rooted trees

 

Слайд 60

Rooted trees Determine the level of each vertex of the following rooted tree.

Rooted trees

Determine the level of each vertex of the following rooted

tree.
Слайд 61

Rooted trees

Rooted trees

 

Слайд 62

Rooted trees It is clearly possible to define further terms

Rooted trees

It is clearly possible to define further terms such as

grandparent, grandchild, ancestor, descendant, etc.
Слайд 63

Rooted trees

Rooted trees

 

Слайд 64

Rooted trees

Rooted trees

 

Слайд 65

Rooted trees Rooted trees can be used as models in

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

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

Rooted trees

 

Слайд 68

Rooted trees

Rooted trees

 

Слайд 69

Rooted trees

Rooted trees

 

Слайд 70

Rooted trees

Rooted trees

 

Слайд 71

Rooted trees

Rooted trees

 

Слайд 72

Rooted trees

Rooted trees

 

Имя файла: Trees,-rooted-trees.-Graphs.-Lecture-10,.pptx
Количество просмотров: 160
Количество скачиваний: 0