Решение многокритериальной задачи о назначениях, страница 6

Анализ графов подобия

Цель анализа состоит в разделении вершин графов подобия на группы с использованием бинарных отно­шений.

Выделим в графе подобия вершины, в которые не входят однонаправленные дуги. По сути дела, выде­ленные элементы либо доминируют над всеми или частью остальных, либо несравнимы с ними,т. е. яв­ляются множеством Парето в пространстве критери­ев. Назовем выделенные вершины ядром 1-й степени. Если элементы ядра 1-й степени несравнимы, то им присваивается индекс H₁; если они эквивалентны, то им присваивается индекс D₁.

Удалим из графа подобия вершины, входящие в ядро 1-й степени, и аналогично предыдущему выде­лим среди оставшихся вершин ядро 2-й степени. При числе ядер больше двух и эквивалентности вершин, входящих в ядро 2-й степени, им присваивается ин­декс D2 ,а при несравнимости — индекс H₂.

Процесс выделения ядер продолжается до исчер­пания вершин графа подобия. При числе ядер равном двум вершинам второго ядра присваивается индекс D₂ , если выполняются два условия: а) эти вершины эквивалентны; б) все вершины 1-го ядра доминируют над вершинами 2-го ядра. Если хотя бы одно из этих условий не выполняется, то вершинам 2-го ядра при­сваивается индекс H₂. Легко увидеть, что для всех ядер, кроме последнего, индекс D_i означает факт до­минирования вершин i-го ядра над вершинами (i+1)-го ядра.

Нетрудно убедиться, что при отсутствии циклов в графе этот процесс конечен и заканчивается не более чем за п шагов.

Нетрудно показать справедливость следующей леммы.

Лемма. Графы подобия не содержат циклов.

Доказательство. Допустим, что на вершинах графа подобия имеется цикл

`C<sub>iv</sub> ®`C_kv® . . . `C<sub>fv</sub>®`C_iv(7)

По построению отношения доминирования (3) лю­бая вершина в упорядоченной последовательности `C<sub>iv l</sub> ,`C_kv  , ..., `C<sub>fv</sub> должна иметь по всем критериям не худшие оценки, чем все предыдущие, а хотя бы по одному — лучшую. Следовательно, соотношение `C_fv®`C_iv  невозможно, что