Дискретная математика

157 путь к каждому из колодцев. Так как обитатели домов в ссоре, то желательно, чтобы пути к колодцам не пересекались. См. рис. 5.28. Обозначим дома через Д Л и С, а колодцы - через X, 7 и Z. На рис, 5.29 приведены два варианта возможных расположений тропинок от домов до колодцев. Рис. 5.28 При варианте дорог, изображенных на рис. 5.29, а), имеется много пересечений. В следующем случае, см. рис. 5.29, б) осталось только одно пересечейие. Можно ли сделать так, чтобы пересечений дорог (троп) не б ы л о . Ясно, что задачи, аналогичные этой, возникают не только для перессорившихся соседей. В печатных платах важно научиться проводить соединения без пересечений (без необходимости), также это важно для скоростных автомобильных дорог и т.п. 2 Г X а) Рис. 5.29 б)