Diskret matematik A för datateknik
Examination Questions from 1999-08-25

Question 1 (8p)

Choose the correct option(s) for each of the following, giving a short explanation of your choice. You may quote theorems and definitions in your explanation.

1. The number of ways to order the letters in the word MATEMATIK is
   1. 9(7!)
   2. 9!
   3. 9!/(2!2!2!)
   4. none of the above
2. A set X is countable if
   1. it is a subset of .
   2. there is an injection from X to .
   3. there is a bijection from X to .
   4. there is a surjection from X to .
   5. is a subset of X.
   6. none of the above.
3. For integers k 1,

   (

   2k 1

   )

   +

   (

   2k 2

   )

   +

   (

   2k 3

   )

   +

   ...

   +

   (

   2k k

   )

   is equal to
   1. 2^2k-1-2
   2. 2ⁿ
   3. 2^k-1
   4. 2^2k-1-1
   5. none of the above
4. Two graphs G and G' are isomorphic if
   1. they have the same number of vertices.
   2. they have the same number of edges.
   3. their complements are isomorphic.
   4. they contain no triangles
   5. none of the above
5. If two graphs G and G' are isomorphic then
   1. they have the same number of vertices.
   2. they have the same number of edges.
   3. their complements are isomorphic.
   4. they contain no triangles
   5. none of the above
6. In a land far far away, live two types of elves. Each elf is either a light elf or a dark elf. The only difference between the two types of elves is whether they tell the truth all the time, or lie all the time. Unfortunately the situation is further complicated by insanity. A light elf always tells the truth as he sees it. This means that a sane light elf tells the truth, but an insane light elf lies. Similarly a dark elf always lies as he sees it so an insane dark elf always tells the truth and a sane dark elf always lies.
   One of Elvina and Falina is a light elf the other is a dark elf. You have the following information.
   Elvina: We are both insane.
   You: Is that true?
   Falina: Of course not.
   Which of the following are correct?
   1. Elvina is a dark elf and Falina is a light elf.
   2. Falina is a dark elf and Elvina is a light elf.
   3. Both are sane
   4. Both are insane
   5. Both are sane or both are insane
   6. one is sane and one is insane
   7. insufficient information to deduce anything
   8. none of the above
7. For sets X={1,2,3}, Y={4,{5,1}, 2} which of the following are correct?
   1. X Y={1,2}
   2. {5,1} Y
   3. {4, {1,5}} Y
   4. 1 Y
   5. None of the above

Question 2 (4p)

I am going to make a crocheted blanket (afghan). For the afghan, I need two different colours of wool. I have found two that I like, but unfortunately they come in different sized balls. The blue wool comes in 450g balls and the green wool comes in 200g balls. I need a total of 3250g of wool for my project. As there is a limited number of balls of each colour available, and the wool is expensive, I need to know all feasible solutions so that I wont buy too much or too little of each. Only whole balls may be purchased. Can you help?

I need to know all the possible solutions, and how you obtained them - you must convince me that your answer is correct. I don't want to spend hours working on this blanket, to find I have the wrong quantity of wool because you made a mistake!

Question 3 (5p)

1. State and prove a formula which gives a relationship between the number of edges in a graph and the degrees of the vertices.
2. Describe how and why proof by contradiction works.
3. Prove that every tree contains at least one vertex of degree one. (Hint: Let T be a tree on n vertices. Suppose that it does not have a vertex of degree 1. What degrees are possible for the vertices? Why? How many edges does T have?)

Question 4 (4p)

1. Define chromatic index and chromatic number.
2. Find the chromatic number and chromatic index for each of the following graphs. You should prove your results.
   

Question 5 (4p)

Suppose the numbers 1,2,3,...,20 are arranged around a dart board and that we know the sum a+b+c+d of every set {a,b,c,d} of four consecutive numbers around the board. Is it possible that none of these sums is more than 40? Prove your result.

Question 5 (7p)

1. Find a shortest path in the following graph between s and t. You should explain your method.
2. Find a minimum spanning tree in the graph below. Explain your method.
3. Does the minimum spanning tree give a shortest route from s to t? If it does, is this always the case?