Алгоритм поиска минимального хроматического разложения графа и его практическое применение

Сухоруков Михаил Андреевич / Suhorukov Mihail Andreevich – студент,

кафедра персональной электроники,

Международный университет природы, общества и человека «Дубна», г. Дубна

Аннотация: в статье рассматривается актуальная проблема регулирования транспортного потока на перекрестках со сложной дорожной инфраструктурой.

Ключевые слова: хроматическое разложение графа, регулирования транспортного потока.

Рассмотрим математическую модель, используемую для управления светофорами на сложном перекрестке дорог. Необходимо описать алгоритм, которому в качестве входных параметров подается множество всех возможных поворотов (продолжение прямой дороги тоже будем рассматривать как «поворот») и который разбивает это множество на несколько групп, так чтобы повороты в группе могли совершаться одновременно. Таким образом, возможно сопоставить каждую группу с режимом работы светофора на перекрестке.

Для того чтобы минимизировать количество режимов работы светофора, необходимо найти минимальное количество разбиений исходного множества. Рассмотрим сложный перекресток на рис. 1.

Рис 1. Рассматриваемый перекресток

Будем учитывать тот факт, что дороги Е и С односторонние, а остальные двухсторонние. Всего на этом перекрестке 13 возможных поворотов. Повороты, такие как AB и DC могут осуществляться одновременно. Трассы других поворотов, например, АС и BD пересекаются, поэтому их нельзя выполнить одновременно. Режимы работы должны учитывать все эти обстоятельства.

Задачу можно представить в виде графа. За вершины графа примем повороты, а ребра графа будут соединять те вершины-повороты, которые нельзя выполнить одновременно. Граф предствлен на рисунке 2.

Рис. 2. Граф, показывающий несовместимые повороты