It couldn't be exactly once, since the graph of the states' connectivity has more than two odd-valence nodes (e.g., California, New Hampshire, West Virginia, North Dakota, Kentucky). --Dan The Traveling Salesman Problem (TSP) is similar, but different: Given that a cost has been assigned to each ordered pair of points of a finite set, find a round trip through all points with the least total cost. The general version doesn't put any conditions on the cost function (it could be asymmetric). Various versions assume the cost is a metric, or that it is Euclidean distance of points in the plane. But this problem seems to be let the U.S. road system define the graph and its cost function, with the requirement being to make a round trip that visits each state (which could be defined as a set of edges) at least once. I suppose it could be called a big generalization of the TSP. --Dan On Jun 4, 2014, at 11:36 AM, Thane Plambeck <tplambeck@gmail.com> wrote:
I thought this was interesting...a Google map allegedly showing how to drive a car through the lower 48 USA states, visiting each state [at least? exactly?] once and minimizing the total distance travelled.
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/ _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun