Естественные расстояния на решетке

Естественные расстояния на решеткеСовершенно очевидно, что на практике часто приходится обходить препятствия и одновременно искать минимальные по длине пути. При этом существует множество различных путей прохождения от Е до F. Рассмотрим в качестве примера четырехугольную решетку Г с естественным расстоянием d, выбрав в качестве базовых окрестностей открытые шары с радиусом 2, представленные на 4-связной решетке.

В этом случае могут быть проложены некоторые дополнительные пути.

Представленная картина интересна тем, что в совокупности приемлемых путей от? до F можно найти некоторые шары или некоторые окрестности, которые наилучшим образом характеризуют картину циркуляции или возможностей доступа к данной конфигурации. Иначе говоря, проложенные пути и свойственные им структуры представляют собой средство для анализа некоторых динамических аспектов данной конфигурации.

Решетка, которая представляет собой разделение плана с помощью модулей или ячеек, обладающих определенными топологическими свойствами, способствует рассмотрению всего многообразия проблем, связанных с топологическими особенностями графов или их носителей. Классической проблемой в теории графов является проблема раскрашивания.

Граф называется rt-раскрашенным, если существует множество и цветов и если каждая вершина рассматриваемого графа будет раскрашена таким образом, что две соседних вершины никогда не будут одного цвета. Хроматическое число графа соответствует минимальному числу различных цветов, с помощью которых можно произвести раскрашивание данного графа.

Известно, что с помощью пяти различных цветов можно раскрасить любой плоский граф.

Предполагается, что данная задача может быть решена и при использовании четырех различных цветов.

Читайте так же:

Комментарии запрещены.