The Colored Bridges Problem: In Memory of Frank Harary (1921–2005)

A town has a network of walkways running through it, each colored gray. A red bridge is constructed between every two walkway intersections that are two blocks apart, and a blue bridge is constructed between every two intersections that are three blocks apart. The colored bridges problem asks whether it is possible to take a round‐trip about the town passing through each of its intersections exactly once such that during this trip the walkway or bridge used to enter every intersection is of a different color than that used to exit it. With the aid of graph theory, we show that such a round‐trip is always possible when the walkways of the town form a grid. Conditions are determined under which no blue bridges are needed. Una ciudad tiene una red de caminos de color gris que la atraviesan. Un puente rojo se construye entre cada dos intersecciones de caminos separados por dos manzanas y un puente azul se construye entre cada dos intersecciones que están a tres manzanas de distancia. El problema de los puentes de colores se pregunta si es posible hacer un viaje alrededor de la ciudad pasando por cada una de las intersecciones exactamente una sola vez de modo que durante este viaje el camino o puente utilizado para entrar en cada intersección es de color distinto al que se utiliza para salir. Con la ayuda de la teoría de grafos, mostramos que tal viaje es siempre posible cuando los caminos de la ciudad forman una cuadrícula. Se determinan las condiciones bajo las cuales no son necesarios los puentes azules. 城镇中贯穿于其中的通道构成的网络标记为灰色。任意两个分离区域的通道交叉处构建一个红色的桥，而三个分离区域的两两交叉处则构建一个蓝色的桥。有色桥问题是关于能否对任意交叉处仅通过一次就能遍历整个城镇，也就是在该旅程中在进入和走出每个交叉点的道路或桥是不同颜色的问题。借助于图论，本文显示了当城镇道路网络构建格网时，上述路径总是存在的。当不需要蓝色的桥时，条件是完全确定的。