(a) What is the diameter of this graph?
(b) By adding arrows to turn this into a directed graph, show how the diameter of the graph can be increased. What is the diameter of your new directed graph?
| Math Alive |
Problem 1. Directed and Undirected Graphs.
Consider the following graph:
(a) What is the diameter of this graph?
(b) By adding arrows to turn this into a directed graph, show how the diameter of the graph can be increased. What is the diameter of your new directed graph?
Problem 2. Six degrees of separation
In class, we talked about the idea of everyone being connected through at most six people. Let's test this out. This question is quite wordy so the biggest challenge is to distil the mathematics.
(a) Have a look on your Facebook account and see how many friends you currently have. (If you don't have a Facebook account then you can estimate how many friends you have :) ) Take a quick look at the current news feed to make sure that you aren't missing out on any important news while attempting this problem set. Now suppose that each of your friends also has the same number of friends, and that half of their friends are not friends with you. How many different people does that mean are friends with you or with a friend of yours?Problem 3. The Chinese Postman Problem
In class, we talked about the Chinese Postman Problem. We will now explore this problem.
On his first day on the job, a new postman is given the map below and instructed that he must deliver letters to houses along each of the streets on the map. The postman wants to find the shortest possible route that includes each of the streets on the map at least once and returns him to his starting point at the post office (the intersection in the upper lefthand corner).
a) Draw the graph corresponding to the given map. Vertices in your graph will represent intersections and edges will represent the streets that connect pairs of intersections.
b) In this problem we are also concerned with the length of the streets. Add a weight (i.e., a number) to each edge that represents the length of the corresponding street.
c) Explain why the existence of an Eulerian cycle would be advantageous for the postman.
d) Using the result of Euler discussed in class, explain whether an Eulerian cycle exists for the postman's route.
e) Add a new edge parallel to an existing edge (that is,
connecting the same two vertices as an existing edge) in such a
way that you make an Eulerian cycle possible. Verify that you can
now find an Eulerian cycle in the graph by sketching the cycle.
f) How does your Eulerian cycle correspond to the actual route that the postman will take? In particular, since the postman can't build
new streets, how does he travel along your new edge?
g) In view of your answer to (f), what should the weight of your
new edge be?
h) Find the total distance the postman needs to travel to complete
the route represented by your Eulerian cycle. Is this route
the shortest route that satisfies the postman's constraints? If
yes, explain why. If not, find a shorter route.
i) Now consider the following example: How many ways are there to add 2 parallel edges to this graph so
as to make an Eulerian cycle possible? Which way creates the
shortest possible Eulerian cycle?
j) Using what you've learned, explain how in general a postman can
find the shortest route that includes each street at least once
and ends at his starting point.
You and your friends Amy, Ben, Christine, Dan, and Emily are going to
the movies. You want to take the fewest number of cars possible, but Ben
refuses to be in the same car with any of your female friends and Dan
refuses to be in the same car with Ben or Emily.
a) Draw a graph describing the conflicts.
Problem 4. Avoiding Conflicts
b) What does the greedy coloring theorem allow you to say about the minimum number of cars you can take?