2. You may know that, at the end of the Lord of the Rings, Frodo leaves Middle-earth by boat with Bilbo, Celeborn, Elron
Posted: Wed May 04, 2022 1:39 pm
2. You may know that, at the end of the Lord of the Rings, Frodo
leaves Middle-earth by boat with Bilbo, Celeborn, Elrond, Gandalf,
and Galandriel. Their destination is the Undying Lands, but they
get lost enroute and dock in Charleston, South Carolina. They
marvel at the city’s complex geography and ask for your help.
Luckily, you know graph theory ...
Downtown Charleston is connected to Mount Pleasant by one
bridge, to West Ashley by two bridges, and to North Charleston and
James Island by one bridge each. (We count I-26— linking Downtown
to North Charleston—as a bridge.) West Ashley is connected to James
Island by a bridge, and to North Charleston by two bridges. Mount
Pleasant is connected by bridges (one to each town) to North
Charleston, to Sullivan’s Island and to the Isle of Palms, and
those two islands are also connected to each other by a bridge.
(a) Draw a graph showing the information. (Your graph model
should have 7 vertices and 12 edges. Please label the
vertices.)
(b) Is it possible to cross all 12 bridges without going over
the same bridge twice? If not, explain why. If so, where would such
trip start and end?
(c) How would your answer to part (b) change if I-26 we not
counted among bridges? Explain.
leaves Middle-earth by boat with Bilbo, Celeborn, Elrond, Gandalf,
and Galandriel. Their destination is the Undying Lands, but they
get lost enroute and dock in Charleston, South Carolina. They
marvel at the city’s complex geography and ask for your help.
Luckily, you know graph theory ...
Downtown Charleston is connected to Mount Pleasant by one
bridge, to West Ashley by two bridges, and to North Charleston and
James Island by one bridge each. (We count I-26— linking Downtown
to North Charleston—as a bridge.) West Ashley is connected to James
Island by a bridge, and to North Charleston by two bridges. Mount
Pleasant is connected by bridges (one to each town) to North
Charleston, to Sullivan’s Island and to the Isle of Palms, and
those two islands are also connected to each other by a bridge.
(a) Draw a graph showing the information. (Your graph model
should have 7 vertices and 12 edges. Please label the
vertices.)
(b) Is it possible to cross all 12 bridges without going over
the same bridge twice? If not, explain why. If so, where would such
trip start and end?
(c) How would your answer to part (b) change if I-26 we not
counted among bridges? Explain.