Math Alive

Problem Set. Graph Theory, Part 1.

In this problem set we investigate some concepts in graph theory.

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?

(b) Now if we suppose that each friend of a friend also has the same number of friends, again with only 50% in common with that friend, and none in common with you, how many different people would be friends with you, one of your friends, or a friend of one of your friends?

(c) How many times would you need to continue this before the prediction reached the total number of people in the world? This website might be helpful.

(d) Based on the idea of six degrees of separation, does this mean that you have more or less friends than the average person?!

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.

Problem 4. Avoiding Conflicts

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.
b) What does the greedy coloring theorem allow you to say about the minimum number of cars you can take?

c) What is the actual minimum number of cars you can take? Give an actual assignment of people to cars that resolves the conflicts for this minimum number of cars and explain what prevents you from taking one fewer car than this minimum.