Week 7

Discrete Mathematics
By Susanna S. Epp

Instructor: Ms. Maryam bibi

CS Department
Bahria University
Islamabad Campus
Introduction
to Tree
 Minimal
Spanning Tree
Example – (45 - 17)

Discrete Mathematics - BSCS 4

Example – (45 – 17a)

Discrete Mathematics - BSCS 5

Solution – (45 – 18)

Discrete Mathematics - BSCS 6

Weighted Graph – (19)

Discrete Mathematics - BSCS 7

Example – (45 – 19a)

Discrete Mathematics - BSCS 8

Minimal Spanning Tree – (45 - 20)

Discrete Mathematics - BSCS 9

Example – (45 - 21)

Discrete Mathematics - BSCS 10

Example – (45 – 21a)

Discrete Mathematics - BSCS 11

Example – (45 – 21b)

Discrete Mathematics - BSCS 12

Example – (45 – 21c)

Discrete Mathematics - BSCS 13

Example – (45 - 22)

Discrete Mathematics - BSCS 14

Kruskal’s Algorithm – (45 - 23)

Discrete Mathematics - BSCS 15

Kruskal’s Algorithm – (45 – 23a)

Discrete Mathematics - BSCS 16

Kruskal’s Algorithm – (45 – 23b)

Discrete Mathematics - BSCS 17

Example – (45 – 24)

Discrete Mathematics - BSCS 18

Solution – (45 – 24a)

Discrete Mathematics - BSCS 19

Solution – (45 – 24b)

Discrete Mathematics - BSCS 20

Solution – (45 – 24c)

Discrete Mathematics - BSCS 21

Solution – (45 – 24e)

Discrete Mathematics - BSCS 22

Solution – (45 – 24f)

Discrete Mathematics - BSCS 23

Solution – (45 – 24g)

Discrete Mathematics - BSCS 24

Solution – (45 – 24h)

Discrete Mathematics - BSCS 25

Solution – (45 -24i)

Discrete Mathematics - BSCS 26

Prim’s Algorithm – (45 - 25)

Discrete Mathematics - BSCS 27

Prim’s Algorithm – (45 – 25a)

Discrete Mathematics - BSCS 28

Example – (45 - 26)

Discrete Mathematics - BSCS 29

Solution – (45 – 26a)

Discrete Mathematics - BSCS 30

Solution – (45 – 26b)

Discrete Mathematics - BSCS 31

Solution – (45 – 26c)

Discrete Mathematics - BSCS 32

Solution – (45 – 26d)

Discrete Mathematics - BSCS 33

Solution – (45 – 26e)

Discrete Mathematics - BSCS 34

Solution – (45 – 26f)

Discrete Mathematics - BSCS 35

Example – (45 - 27)

Discrete Mathematics - BSCS 36

Solution – (45 - 28)

Discrete Mathematics - BSCS 37

Solution – (45 – 28a)

Discrete Mathematics - BSCS 38

Solution – (45 – 28b)

Discrete Mathematics - BSCS 39

Solution – (45 – 28d)

Discrete Mathematics - BSCS 40

Solution – (45 – 28e)

Discrete Mathematics - BSCS 41

Solution – (45 – 29b)

Discrete Mathematics - BSCS 42

 Minimum Connector Algorithms

Kruskal’s algorithm Prim’s algorithm

1. Select the shortest edge in a 1. Select any vertex

network
2. Select the shortest edge
2. Select the next shortest edge connected to that vertex
which does not create a cycle
3. Select the shortest edge
3. Repeat step 2 until all vertices connected to any vertex
have been connected already connected

4. Repeat step 3 until all

vertices have been
connected
Example
A cable company want to connect five villages to their network which
currently extends to the market town of Avonford. What is the minimum
length of cable needed?

Brinleigh 5 Cornwell

3
4
8 6
8
Avonford Fingley Donster
7
5
4 2

Edan
We model the situation as a network, then the problem
is to find the minimum connector for the network

B 5 C

3
4
8 6
8
A F D
7
5
4 2

E
 Kruskal’s Algorithm
List the edges in
order of size:
B 5 C ED 2
AB 3
3 AE 4
4
8 6 CD 4
BC 5
8 EF 5
A D CF 6
7 F
AF 7
5 BF 8
4 CF 8
2

E
 Kruskal’s Algorithm

Select the shortest

edge in the network
B 5 C
ED 2
3
4
8 6

8
A D
7 F

5
4 2

E
 Kruskal’s Algorithm
Select the next shortest
edge which does not
B 5 create a cycle
C
ED 2
3 AB 3
4
8 6

8
A D
7 F

5
4 2

E
 Kruskal’s Algorithm
Select the next shortest
edge which does not
B 5 create a cycle
C
ED 2
3 AB 3
4
8 6 CD 4 (or AE 4)

8
A D
7 F

5
4 2

E
 Kruskal’s Algorithm
Select the next shortest
edge which does not
B 5 create a cycle
C
ED 2
3 AB 3
4
8 6 CD 4
AE 4
8
A D
7 F

5
4 2

E
 Kruskal’s Algorithm
Select the next shortest
edge which does not
B 5 create a cycle
C
ED 2
3 AB 3
4
8 6 CD 4
AE 4
8 BC 5 – forms a cycle
A D EF 5
7 F

5
4 2

E
 Kruskal’s Algorithm
All vertices have been
connected.
B 5 C The solution is
3 ED 2
4
8 6 AB 3
CD 4
8 AE 4
A D EF 5
7 F

5
4 Total weight of tree: 18
2

E
 Prim’s Algorithm
Select any vertex

B 5 A
C
Select the shortest
3 edge connected to
4
8 6 that vertex

8 AB 3
A D
7 F

5
4 2

E
 Prim’s Algorithm
Select the shortest
edge connected to
B 5 any vertex already
C connected.
3 AE 4
4
8 6

8
A D
7 F

5
4 2

E
 Prim’s Algorithm
Select the shortest
edge connected to
B 5 any vertex already
C connected.
3 ED 2
4
8 6

8
A D
7 F

5
4 2

E
 Prim’s Algorithm
Select the shortest
edge connected to
B 5 any vertex already
C connected.
3 DC 4
4
8 6

8
A D
7 F

5
4 2

E
 Prim’s Algorithm
Select the shortest
edge connected to
B 5 any vertex already
C connected.
3 EF 5
4
8 6

8
A D
7 F

5
4 2

E
 Prim’s Algorithm
All vertices have been
connected.
B 5 C The solution is
3 AB 3
4
8 6 AE 4
ED 2
8 DC 4
A D EF 5
7 F

5
4 Total weight of tree: 18
2

E
 Some points to note

•Both algorithms will always give solutions with

the same length.

•They will usually select edges in a different order

– you must show this in your workings.

•Occasionally they will use different edges – this

may happen when you have to choose between
edges with the same length. In this case there is
more than one minimum connector for the
network.