Maths Assignment 8

HANYURWIMFURA DAMIEN LY2008033 COMPUTER SCIENCE AND TECHNOLOGY

DISCRETE MATHEMATICAL STRUCTURES ASSIGNMENT 7 2008/12/26 EXERCISE SET 6.1.

= (V , E , γ ) , where V = { A, B, C.D, E , F , G, H } , E = { e1 , e2 , , e9 } and γ ( e1 ) = { A, C} , γ ( e2 ) = { A, B} , γ ( e3 ) = { D, C} , γ ( e4 ) = { B, D} ,

Q6 Draw a picture of the graph G

γ ( e5 ) = { E , A} , γ ( e6 ) = { E , D} , γ ( e7 ) = { F , E} , γ ( e8 ) = { E , G} and γ ( e9 ) = { F , G} Solution: A

e1 e2

e7

e5

F e9

e3 B

E

C

e4 e6

eee

D

e8

G Q14. Give an example of a regular, connected graph on six vertices that is not complete. Solution:

The graph looks like this : A

B

F

C

E

D

HANYURWIMFURA DAMIEN LY2008033 COMPUTER SCIENCE AND TECHNOLOGY Q17. Let R={(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9), (10,10), (11,11), (12,12), (13,13), (14,14), (15,15), (16,16), (1,10), (10,1), (3,12), (12,3), (5,14), (14,5), (2,11), (11,2), (4,13), (13,4), (6,15), (15,6), (7,16), (16,7), (8,9), (9,8)}. Draw the quotient graph GR. Solution:

{3, 12} {4, 13} {2, 11}

{5, 14}

{1, 10}

{6, 15} {8, 9}

{7, 16}

EXERCISE SET 6.2 Q7. Use Fleury’s algorithm to produce an Euler circuit for the graph in this figure

.

Solution:

One possible

2

answer

3 7

1

6

9

8

4

5

HANYURWIMFURA DAMIEN LY2008033 COMPUTER SCIENCE AND TECHNOLOGY Q10. At the door of an historical mansion, you receive a copy of the floor plan for the house. Is it possible to visit every room in the house by passing through each door exactly once? Explain your reasoning. A

B

F (outside) D C E

Solution: Yes, it is possible to visit every room in the house by passing through each door once. we see that the five rooms A, B, C, D, E and F have 2, 2, 2, 4, 2 and 4 doors (degrees) respectively. Thus, the problem can be solved by Theorem 1, (b). (If G is a connected graph and every vertex has even degree, then there is an Euler Circuit in G) The Euler circuit is: F, A, B, C, D, E, F.

Q13. In this exercise, no Euler circuit is possible for the graph given. For each graph, show the minimum number of edges that would need to be traveled twice in order to travel every edge and return to the starting vertex.

Solution: It is one possible solution.

14

10 13

11

15 51 1

50

48

49

43

35

44

42

28

34

27 36

12

26 29

25

16

30

17

24

18

8 47

45 46

2

41

37

40

38

39

4 3

31 33

32 5

23 22

19 20

21

7 6

9

HANYURWIMFURA DAMIEN LY2008033 COMPUTER SCIENCE AND TECHNOLOGY

EXERCISE SET 6.3

Q12. Find a Hamiltonian circuit of minimal weight for the graph represented by the given figure. B 3

D

3 5

A

6

2

H

2

C

5 5

Solution: C, A, B, D, H, G, F, E, C

E

4 F

6

3 4

G