Redo Example, but this time assume that you are based in Memphis and must visit each of th...

Redo Example, but this time assume that you are based in Memphis and must visit each of the other four cities. Again, use the nearest neighbor algorithm to find a Hamilton circuit and state its weight.

Solving the Four-Color Problem for South America

Model the map of South America by a graph and use this graph to color the map using at most four colors.

SOLUTION:

In this problem, we have a set of countries, some of which are related in that they share a common border. Therefore, we can model this situation by a graph.

Graph model of map of South America.

Coloring of graph of South America.

We will represent each country by a vertex; if two countries share a common border, we draw an edge between the corresponding vertices. This graph appears in Figure

Note that we connect the vertices representing Peru and Colombia with an edge because they share a common boundary. We do not connect the vertices representing Argentina and Peru, because they have no boundary in common.

We can rephrase the map-coloring question now as follows: Using four or fewer colors, can we color the vertices of a graph so that no two vertices of the same edge receive the same color? It is easier to think about coloring a graph than it is to think about coloring the original map.

There are several ways to color the graph in Figure. However, unlike tracing graphs, there is no particular procedure for accomplishing this coloring except trial and error. One possible coloring for the graph appears in Figure. You may want to color this graph in a different way; however, notice that you cannot do it using fewer than four colors.

If Cameron hears a rumor first, who in Example will not hear the rumor from anyone in the group?

Assume that we have gathered the following information about how rumors spread in the Pritchett family:

---

1. If Manny hears a rumor, he will communicate it to Gloria and Jay, but Gloria and Jay will not tell rumors they hear to Manny.

---

2. Gloria and Jay will tell rumors they hear to each other.

---

3. Gloria tells rumors she hears to Cameron, but Cameron does not relay rumors he hears to Gloria but he does tell them to Jay.

Model this situation with a directed graph.

SOLUTION:

Because rumors do not always flow in both directions, we will model this situation with the directed graph in Figure. The arrows on the edges show the direction in which the rumors travel.

For example, the directed edge from M to G shows that Manny communicates rumors to Gloria. Likewise, the absence of a directed edge from G to M indicates that Gloria does not tell rumors to Manny.

A directed graph modeling the spread of rumors.