Discrete Mathematics

Erich Prisner

UMUC SG

Spring 2002

- First the teacher informs the student to the left of the bottom row.
- all other calls should be between adjacent students.
- the "closeness" between two adjacent students is expressed by the number of common letters. It is also called the "weight" of the edge.
- The cost of each call equals (30 - closeness), for the corresponding pair of adjacent students.
- The list should minimize the total cost, the sum of the costs of all calls.

**Question: ** What is the expected value of the weight
of an edge for the random names generated above
(look at the Javascript program, and assume that the random numbers
generated there are "random" enough)?

**Probably difficult question: ** What is the expected
value of the weight of a maximum spanning tree
for the random names generated in this way?

The next three questions can not be answered using the applet, but try to think on them anyway:

**Question:** What happens if we add the requirement that each student should
make at most two phone calls, one receiving and one transmitting the information
(the classical phone chain)? Which graph theoretical concept do we get if we still
want to minimize the total cost?

**Question:** What happens if we instead add the requirement that after 10
minutes everybody should be informed. Assume that each call takes exactly 1 minute.

**Question:** What happens if the cost of each call equals (2 - closeness),
i.e. if many calls have negative cost. In that case, adjacent people
with negative call cost should call each other in any case. What would the
structure of the phone chain be then?