Java Web Start Activity:
Run the Java Web Start application below again but this time concentrate on complete graphs Kn. Observe the values of the entries on the leading diagonal and those that are not on the leading diagonal.
We know that the adjacency matrix A of Kn has zeros on the leading diagonal and ones off the leading diagonal. By looking at a few examples you will see that the pattern seems to be that the entries on the leading diagonal of Ap have the same value (we shall call this value dp and the ones off the leading diagonal all have another common value which we shall call ep, different from dp.
Consider K3: Draw the graph K3 and by clicking the + button look at Ap, p=1, 2, ..., 5. Make a table like the one below.
Make similar tables for n=4, 5, and 6.
From your observations, when
- what do you think is the relationship between d p+1 and e p?
- what do you think is the relationship between d p and e p?
- Answer the question above for n=4, 5, and 6.
Prove by induction that your answers to the above
questions continue to hold for all values of n and p. Start your
proof as follows:
Fig 12.2. First part of proof Fig 12.3. Middle part of proof Fig 12.3. End of proof
- Check that the results of your proof above match what you had in your tables if you set n=3, 4, 5, and 6.
You are asked to create a language for some hikers to use to signal messages to one another at night.
The hikers will use colored flash lights to send the messages. They will have three colors, red blue and yellow.
They should not flash the same color twice in a row because it could be mistaken for a flicker of the
flashlight. Words in your language are five flashes long. That way the viewer knows that every five
flashes are a word. To make it unlikely that the receiver loses track of where words begin and end you will
have a long pause between words and will always start with a red flash and end with a yellow flash. So for
instance red blue red blue yellow (written rbrby) would be a valid word but red red blue blue yellow
(rrbby) would not.
- How many words are there in your language? List all of them. [Hint: you will find it easier to list them in lexicographical order]
- How would you change the rules if you wanted a vocabulary of 6 words? List the six words under your new rules.
- How would you change the rules to get a vocabulary of 11 words? List the eleven words under you new rules.
© C. Mawata