02-地图就是图

4.1　地图就是图

本章不讨论地铁站点图，而要用到一些美国的城市和城市间可能存在的路线。图4-1是美国人口普查局（Census Bureau）估算的美国大陆及其15个最大的都市统计区（metropolitan statistical area，MSA）的地图^[1]。

著名企业家艾伦·马斯克（Elon Musk）已经建议搭建一个新型高速交通网络，该网络由在压力管道中穿梭的胶囊构成。根据马斯克的建议，胶囊将以1126 km/h的速度行进，适合在相距1448 km之内的城市间的经济高效的交通^[2]。他将这种新型交通系统称为“超级高铁”（Hyperloop）。本章将会以搭建此交通网络为背景探讨经典的图问题。

马斯克最初提出的想法是连接Los Angeles和San Francisco的超级高铁。如果要建立一个全国性的超级高铁网络，那么在美国最大的都市区之间实施才会有意义。在图4-2中，去掉了图4-1中的州边界。此外，每个MSA都与另外几个MSA相邻。为了让图增加一些趣味性，这些邻居并不都是离得最近的MSA。

图4-2展示的就是一个图，其中顶点代表美国最大的15个MSA，边代表MSA之间可能存在的超级高铁路线。选择这些路线仅为了用作演示，其他路线当然有可能加入超级高铁网络。

这种对现实世界问题的抽象表示凸显了图的威力。通过这种抽象，我们可以忽略美国的地理信息，而专注于在连接城市的背景下考虑可能实现的超级高铁网络。事实上，只要保持边不变，我们就可以用不同外观的图来考虑问题。例如，在图4-3中Miami的位置就被移动过了。图4-3中的图已经成了一种抽象表示，可以处理与图4-2相同的计算问题，即使Miami不在应有的位置也没关系。不过为了符合情理，这里还是采用图4-2表示。