Chapter 4.1, Problem 51E

Use the technique that we used in Example 7 to do Exercises 51 –54. We do not list duplicate information in the tables.

The table summarizes the Facebook “is a friend of” relationship among eight people.

a. Draw a graph to represent this situation

b. Is the graph connected?

c. Does the graph have any bridges?

d. Would it affect the communication within this group if Caleb and Ben unfriend each other?

Example 7 Using a Graph Theory Model to Schedule Committees

Each member of a city council usually serves on several committees to oversee the operation of various aspects of city government. Assume that council members serve on the following committees: police, parks, sanitation, finance, development, streets, fire department, and public relations. Use Table 4.1, which lists committees having common members, to determine a conflict-free schedule for the meetings. We do not duplicate information in Table 4.1. That is, because police conflicts with fire department, we do not also list that fire department conflicts with police.

Solution: Recall that in building a graph model, we must have two things:

A set of objects—in this case, the set of committees.1. A relationship among the objects. We will say that two committees are related if the two committees have members in common. So we can model the information in Table 4.1 by the graph in Figure 4.19.

This problem is similar to the map-coloring problem. If we color this graph, then all vertices having the same color represent committees that can meet at the same time. We show one possible coloring of the graph in Figure 4.1.

From Figure 4.19, we see that the police, streets, and sanitation committees have no common members and therefore can meet at the same time. Public relations, development, and the fire department can meet at a second time. Finance and parks can meet at a third time.