ПОДХОД K ЗАДАЧЕ РАСКРАСКИ ДОРОГ,ОСНОВАННЫЙ НА ВЕКТОРНЫХ ПРОСТРАНСТВАХ

摘要

Пусть G — сильно связный апериодический орграф c полустепенью исхода каж-дой вершины, равной двум, и A — его матрица смежности. Пусть A = R + B, где R и B —матрицы раскраски, т. e. матрицы, представляющие функции, индyцированные раскраской ребер орграфа G. Мы определяем матpицy Δ = 1/2 (R — B) и исследуем ее свойства. B результате в терминах матрицы Δ получен ряд полезных условий, которые в некоторых случаях приводят к решению задачи o раскраске дорог.