Содержание к диссертации
Введение
ГЛАВА 1. Анализ подходов к формированию моделей и методов принятия решений на основе нечетких отно шений предпочтения 12
1.1. Анализ методов и подходов к проблеме принятия решений 12
1.2. Способы оценки предпочтений на множестве рассматриваемых объектов 16
1.3. Классификация методов принятия решений в условиях неопределенности 20
1.4. Цель работы и задачи исследования 33
ГЛАВА 2. Нечеткие отношения как модель представле ния экспертных знаний в задаче принятия решений . 35
2.1. Нечеткие бинарные отношения: операции, свойства и типы 35
2.2. Композиция нечетких отношений 45
2.3. Транзитивность как особое свойство нечетких отношений . 60
2.4. Транзитивное замыкание нечеткого бинарного отношения . 64
ГЛАВА 3. Задача нечеткой классификации 76
3.1. Свойства отношения различия и подобия 76
3.2. Транзитивные расстояния 81
3.3. Алгоритм нечеткой классификации 85
ГЛАВА 4. Ранжирование альтернатив заданного множе ства на основе нечетких отношений предпочтения . 91
4.1. Свойства нечетких отношений и порядковая функция . 91
4.2. Графы нечетких отношений порядка 107
4.3. Алгоритм ранжирования альтернатив на основе нечеткого отношения предпочтения 114
ГЛАВА 5. Анализ результатов вычислительного экспери мента 121
5.1. Влияние различных типов транзитивности на нечеткую классификацию 121
5.2. Влияние различных типов транзитивности на иерархическое представление ранжирования альтернатив структуру диаграммы Хассе 125
Заключение 138
Литература
- Способы оценки предпочтений на множестве рассматриваемых объектов
- Транзитивность как особое свойство нечетких отношений .
- Алгоритм нечеткой классификации
- Графы нечетких отношений порядка
Введение к работе
В самой общей постановке задача принятия решений (ЗПР) заключается в выборе лучшей (наиболее предпочтительной, оптимальной) альтернативы из множества заданных в соответствии с предпочтениями эксперта или лица, принимающего решения (ЛПР). Предпочтение - это оценка полезности или качества варианта решения, которая основывается на субъективном понимании ценности, эффективности решений. Именно поэтому эксперт является центральной фигурой процесса принятия решений, а разработка моделей представления экспертных знаний и процедур, ориентированных на эти модели, является одной из важнейших проблем теории принятия решений. Существуют различные процедуры экспертного оценивания, в рамках которых используется тот или иной тип экспертных оценок: ранжирование, парные сравнения, непосредственная оценка, классификация. Метод парных сравнений занимает особое место, поскольку имеет целый ряд преимуществ: в сравнении участвует только пара альтернатив заданного множества, что существенно повышает объективность оценки; процедура легко обобщается на случай векторного критерия; в настоящее время существуют специальные шкалы для оценивания предпочтений разной чувствительности, что позволяет учитывать степень компетентности эксперта; метод оценки не навязывает эксперту априорных условий, в отличии от других подходов (например, не требует транзитивности предпочтений). Результатом метода парных сравнений является матрица парных сравнений А = {aij}nxm элементы которой а^ могут а) иметь количественное представление (в одной из шкал, например, индикаторной, Саати); б) лингвистическое представление (в этом случае А задает лингвистическое отношение предпочтения) или в) соответствовать нечеткому отношению предпочтения (ау задает степень предпочтения числом из [0, 1]). Нечеткие отношения предпочтения позволяют, в отличие от обычных, учитывать интенсивность, силу предпочтения одних вариантов над другими, поэтому использование нечеткого отношения в качестве модели представления экс-
пертной информации позволяет повысить адекватность описания системы предпочтений ЛПР, повышает ее чувствительность.
Подходы к обработке матрицы А в виде нечеткого отношения предпочтения исследовались А.Н. Борисовым, А.В. Алексеевым, О.А. Крумбер-гом, В.Е. Жуковиным, С.А. Орловским. Классическим считается подход С.А. Орловского к решению задачи ранжирования, основанный на вычислении степеней доминирования и недоминирования для каждой альтернативы. Эти исследования обобщаются F. Herrera, Е. Herrera-Viedma, М. Del-gado, L. Martinez, J.L. Verdegay на лингвистические отношения предпочтения. Задачи нечеткой классификации рассматриваются в работах А. Коф-мана.
Заметим, что в перечисленных подходах учитывается только (тах-тіп)-транзитивность нечетких предпочтений. Вместе с тем, использование треугольных норм и конорм для формализации нечетких логических связок позволяет обобщить это важное свойство и, тем самым, придать моделям принятия решений такие качества, как универсальность, гибкость, возможность адаптации к информационной среде конкретной задачи.
Таким образом, актуальность диссертационной работы обусловлена необходимостью обобщения понятия транзитивности нечетких отношений и исследования влияния этого свойства на результаты решения основных задач принятия решений - классификации и ранжирования.
Связь с планом. Исследования по теме диссертационной работы проводилось в соответствии с научным направлением Воронежского государственного технического университета «Вычислительные системы и программно-аппаратные комплексы».
Цель работы Цель работы заключается в обобщении свойства транзитивности нечетких отношений и его всестороннем исследовании, а также разработке моделей принятия решений, учитывающих это свойство.
Достижение поставленной цели требует решения следующих основных задач:
Анализ подходов к построению процедур принятия решений на основе нечетких отношений, учитывающих свойство транзитивности.
Обобщение понятия транзитивности нечетких отношений на основе композиций, определяемых с помощью треугольных Т-норм и 5-конорм и исследование влияния транзитивного замыкания на основные свойства нечетких отношений.
Разработка моделей и методов для решения задачи нечеткой классификации с учетом различных типов транзитивности и исследование структуры декомпозиционного дерева.
Разработка моделей и методов для решения задачи ранжирования на основе нечеткого отношения предпочтения и исследование соответствующих иерархических структур.
Экспериментальное исследование влияния выбора типов транзитивности на результаты задачи классификации и ранжирования альтернатив заданного множества и разработка практических рекомендаций для выбора типа транзитивного замыкания при переходе от исходного отношения к соответствующему транзитивному.
Методы исследования. В диссертационной работе использованы методы теории принятия решений, теории нечетких множеств и отношений, дискретной математики, теории графов, теории исследования операций, а также системного анализа.
Научная новизна работы. В диссертации получены следующие результаты, характеризующиеся научной новизной.
На основе треугольных Г-норм и 5-конорм определены операции композиции, позволяющие обобщить свойство транзитивности и установить взаимосвязи между (тах-Т)- и (тіп-5)-транзитивньіми отношениями.
Впервые сформулирована и доказана теорема о декомпозиции для отношения различия, позволяющая предложить альтернативный вариант нечеткой классификации без использования отношения подобия.
Для различных типов транзитивности сформулировано условие пе-
рехода от отношения предпорядка к отношению нестрого порядка, позволяющее построить порядковую функцию и на ее основе получить ранжирование альтернатив заданного множества.
Обобщен алгоритм нечеткой классификации на основе использования различных типов транзитивности, позволяющий повысить чувствительность классификации к параметрам - порогу и/или уровню достоверности.
Предложен алгоритм ранжирования альтернатив на основе нечеткого отношения предпочтения, отличающийся тем, что за счет выбора типа транзитивности можно управлять степенью детализации иерархической структуры, определяющей упорядочение альтернатив заданного множества.
Практическая значимость работы. Развиваемая теоретическая база и выводы, полученные на основе вычислительного эксперимента, создают основу для разработки систем поддержки принятия решений, ориентированных на обработку экспертной информации в виде нечетких отношений предпочтения. Предложены алгоритмы, учитывающие тип транзитивности нечеткого отношения. Разработаны рекомендации, позволяющие обосновать выбор типа транзитивности, наделяя декомпозиционную структуру тем или иным уровнем чувствительности.
Теоретические результаты диссертации используются в учебном процессе Воронежского государственного университета при чтении спецкурсов, выполнении дипломных и курсовых работ.
Апробация работы. Основные результаты, полученные в диссертационной работе, докладывались и обсуждались на Международных школах-семинарах «Современные проблемы механики и прикладной математики» (Воронеж, 2004, 2005), на конференции «Экономическое прогнозирование: модели и методы» (Воронеж, 2007), на научно-технических конференциях профессорско-преподавательского состава, аспирантов и студентов Воронежского государственного университета и научных конференциях Воро-
нежского государственного технического университета.
Публикации. Основные результаты диссертации опубликованы в 7 научных работах, в том числе 3 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, лично соискателю принадлежит в [1, 3, 5] - теоретические исследования влияния типа композиции на свойства отношений, [2, 4] - проведение расчетов и численных исследований моделей.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 117 наименований, и приложения. Основная часть работы изложена на 169 страницах текста и содержит 32 рисунка и 8 таблиц.
Структура и краткое содержание работы. Во введении обоснована актуальность темы диссертационной работы, определены цель и задачи исследования, охарактеризованы используемые методы, описаны структура работы, взаимосвязь и краткое содержание ее разделов.
В первой главе рассмотрены общие проблемы задач принятия решений. Приведена классификация ЗПР по виду отображения множества допустимых альтернатив в множество критериальных оценок; по мощности множества критериальных оценок и по типу системы предпочтений решающего элемента.
В разделе 1.2 описаны виды экспертных оценок оценок, среди которых выделен метод парного сравнения альтернатив как наиболее точно отражающий субъективное предпочтение, на который налагаются меньшие ограничения, чем при других видах оценки. Метод парного сравнения не навязывает эксперту априорных условий (не требует транзитивности предпочтений).
Способы оценки предпочтений на множестве рассматриваемых объектов
1. Количественные показатели. Пусть рассматриваемая система имеет множество состояний А, причем «качество» каждого состояния аєА описывается различными показателями /Да) (г = 1,..., п).
Функция (р(х) называется допустимым преобразованием признака f(a) (а Є А), если функция (p(f(a)) (а Є А) задает тот же признак. Обычно оценки / данного показателя определены вместе с множеством всех допустимых преобразований Ф. В этом случае говорят, что измерения произведены в шкале типа Ф.
О количественном выражении показателя (или предпочтения) обычно говорят в том случае, когда его значения (оценки) можно сравнивать -на сколько или во сколько раз одна оценка больше другой.
Чаще всего на практике количественные показатели используются для прогноза значений параметров, соотношения между которыми слиш ком очевидны, чтобы называть их теоретическими.
Если не известно, как количественный показатель связан с другими, что очень типично, например, для психологических показателей, класс допустимых преобразований можно попытаться выяснить из анализа свойств эмпирических отношений между объектами [59].
2. Оценки в бальной и ранговой шкалах. В отличие от количественных оценок, соответствующих, как правило, объективным измерениям объективных показателей, балльные оценки обычно характеризуют субъективные мнения. Экспертные оценки часто производятся в бальных шкалах.
Значения (градации) балльной шкалы представляют собой ограниченный дискретный ряд чисел, отстоящих друг от друга на одинаковом расстоянии. Обычно при экспертных оценках в качестве значений шкалы берут начальный отрезок натурального ряда или часть ряда целых чисел, симметричную относительно нуля (0, ±1, ±2,..., ±т).
Различают два вида балльных оценок.
В первом случае оценка производится по объективному критерию, так что индивидуальные оценки являются некоторыми флуктуациями реальных значений. Обычно при этом имеются некоторые общепринятые эталоны, соответствующие градациям шкалы, с которыми и сравниваются рассматриваемые объекты. Чем более точно охарактеризованы и оценены возможные отклонения от эталонов, тем меньше флуктуации в оценках, тем больше доверия к ним.
Знание эталонов позволяет установить соответствие между значениями многих признаков, характеризующих объект, и на основе этого прогнозировать значения других признаков по балльным оценкам объектов.
Вопрос о типе балльных шкал такого рода довольно сложен. При некоторых условиях они могут рассматриваться как количественные [59].
В практических же ситуациях оценки, даже даваемые одним и тем же экспертом, характеризуются большими отклонениями.
Балльная оценка второго вида производится, когда не только нет общепринятых эталонов, но и сомнительно даже наличие некоего единственного объективного критерия, субъективными отражениями которого являются оценки, так что бессмысленным является сам вопрос о количественном соотношении оценок.
В этом случае часто оценки рассматриваются выполненными в так называемой ранговой или порядковой шкале. Говорят, что измерение выполнено в порядковой (ранговой) шкале, если множество допустимых преобразований Ф состоит из всех монотонно возрастающих функций.
Ранговые оценки имеет смысл сравнивать только по отношению «больше - меньше»: оно сохраняется при монотонных преобразованиях. Поскольку ранговые оценки имеют смысл только с точностью до упорядочения по величине, их можно давать не только в числовых терминах, но в качестве градаций использовать символы любого упорядоченного множества (алфавита). Это равносильно сопоставлению чисел, чье упорядочение по величине совпадает с упорядочением символов множества.
3. Ранжирование. Под ранжированием [59] понимается представ ление объектов в виде последовательности в соответствии с убыванием их предпочтительности. При этом допускается указание на равноценность некоторых рядом расположенных объектов.
Ранжирование легко представить как оценку в ранговой шкале: рангом объекта а (т. е. значением /(a)) можно считать номер места, которое он занимает в ранжировании при обратной нумерации мест. При этом считается, что равноценные объекты находятся на одном и том же месте. Упорядоченные места, на которых расположены объекты, могут рассматриваться как символы упорядоченного множества значений ранговой шкалы.
4. Попарное сравнение. Этот способ оценки состоит в указании предпочтительного объекта в каждой паре объектов. Объекты могут также быть равноценными или несравнимыми.
Транзитивность как особое свойство нечетких отношений .
Практическое значение теоремы 2.6 заключается в том, что она позволяет перейти от нетранзитивного отношения к транзитивному с помощью операции транзитивного замыкания. Так как в основе транзитивного замыкания лежит определенный тип композиции, то R является транзитивным отношением с определенным типом транзитивности. При решении прикладных задач требуется исследование, направленное на выявление необходимой транзитивности.
Теорема 2.7. Транзитивное замыкание R является наименьшим транзитивным отношением, включающим R, т. е. R С І?, и для любого транзитивного отношения Q, такого, что RC Q, следует RCQ.
Как следствие данной теоремы получаем, что R транзитивно тогда и только тогда, когда R = R. При транзитивном замыкании нечеткого отношения R в общем случае сохраняются лишь некоторые свойства отношения R. Теорема доказана.
Из данной теоремы следует, что при определении транзитивного замыкания степень отношения Rk вычисляется до тех пор, пока не найдется такого к, что Rk = Rk+1. В общем случае, если R С X х X, где X - конечное универсальное множество и Х = п, то R = RUR2U---URn (Я = ЯПЯ2П---ПЯП) и существует к, определяемое (2.10), такое, что к п. В случае, когда R рефлексивно, имеем R С R2 С С Rn l = Rn = Rn+1 = . Теорема 2.11. Пусть R есть (тах-Т)-транзитивное замыкание некоторого нечеткого отношения R С X х X, и R есть (min-S)-транзитивное замыкание R. Тогда R = R.
Доказательство. Так как R есть транзитивное замыкание некоторого нечеткого отношения R, то имеем R = R U R2 U Я3 U .... Найдем дополнение R: R = RURoR\jR2oRU... = Rr\RoRnR2oRn...@ Согласно утверждению 1 имеем Ro R = J? R. @RnR»RnR2»Rn... = R. Теорема доказана.
Заметим, что утверждение данной теоремы распространяется на все типы двойственных операций, рассмотренных в данной работе.
Утверждение 2.12. а-уровенъ транзитивного замыкания нечеткого отношения R совпадает с транзитивным замыканием соответствующего а-уровня: (R)a = (Ral Va O.
Условия транзитивности устанавливают силу связи для различных пар объектов в нечетком отношении. Эта связь может быть как очень слабой, так и достаточно сильной.
Связь нечеткого отношения с понятием конечного графа
Рассмотрим в конечном графе G С X х X упорядоченную r-ку (т.е. упорядоченный набор из г элементов) с повторениями или без повторений1 о = [Xit1 ХІ2, ..., Xjr), где Xik Є X, k = 1,2,..., г, при условии V{xik xik+i) PR(xik xik+i) 0 fc = l,2,...,r-l.
Определение 2.24. Упорядоченная г-ка называется путем из х в Х{г в графе G (или в отношении R). Другими словами, г в зависимости от случая может быть меньше, равно или больше С каждым путем (х , Х{2, ..., ХІГ) будем связывать величину, определяемую выражением l{xivxi2,...,xir) = fiR(xh,xi2) Л fiR{xit,хіз) Л Л linixir Xir). (2.11) Теперь рассмотрим все возможные пути, существующие между Xi и Xj - двумя произвольными элементами из X. Пусть С(ХІ, Xj) - обычное множество всех таких путей: L {Xi,Xj) = [L/[Xi,Xj)\L [Xj, Xj) = [Хц = Х(, Х{2, . . . , Х{т_х) Х{т =Xj)j. Определим сильнейший путь C {xi,Xj) из Х{ в Xj как I [Х%} Xj) = у 1 \%ц == %ii Я-г 2) J %iT-и %ir = xj) [Z.iZ) C{xuxj) Длиной пути будем называть число, на единицу меньшее числа элементов, определяющих путь.
Рассмотрим несколько теорем, отражающих связь пути в нечетком графе с понятием нечеткого бинарного отношения, свойством транзитивности и понятием транзитивного расстояния.
Алгоритм нечеткой классификации
Пусть задано множество нечетких подмножеств {А\, Лг,..., Ап} на универсальном множестве X = (х\, Х2, хт). Требуется определить транзитивно ближайшие подмножества, т.е. какие подмножества попадут в один класс эквивалентности, если в качестве расстояния между подмножествами использовать транзитивные расстояния, определенные с помощью различных типов композиций нечетких отношений.
Решение поставленной задачи осуществляется с помощью алгоритма нечеткой классификации. Нечеткую классификацию можно осуществить несколькими способами (схема, представленная на рис. 3.1). В данной работе рассматривается один из вариантов нечеткой классификации.
Для перехода от отношения сходства R к отношению подобия R используется операция транзитивного замыкания. Так как в основе транзи-тивного замыкания лежит определенный тип композиции, то R является транзитивным отношением с определяемой этой транзитивностью принципом рационального выбора оптимального решения, и необходимо исследование, направленное на выявление необходимой транзитивности для конкретной ситуации.
Для перехода от отношения подобия к отношению различия или наоборот используется операция дополнения. Однако переход к отношению различия возможен и от отношения несходства с помощью двойственного транзитивного замыкания. Очевидно, что путь к отношению различия зависит от того, какая интерпретация при сравнении двух альтернатив является более естественной и что стоит за условием транзитивности. Несмотря на различные условия формирования входной информации, получим одно и то же отношение различия. Матрица отношения различия задает матрицу транзитивных расстояний. Тип транзитивного расстояния зависит от того, с помощью какой операции было получено транзитивное замыкание.
Затем, в соответствии с теоремой о декомпозиции нечеткое отношение подобия или различия представляется в виде иерархической структуры обычных отношений эквивалентности (толерантности), упорядоченных по включению в соответствии со значением уровня а.
Алгоритм нечеткой классификации Шаг 1. Для каждой пары подмножеств (Д-,А/) найти расстояние Хемминга 1 п 8(Ai, А]) = - 2 \VAiiXk) - ЦА,{хк)\ п к=1 (или другое расстояние в зависимости от решаемой проблемы), которое задает отношение несходства R (антирефлексивное и симметричное нечеткое отношение).
Шаг 2. Вычислить (min —5)-транзитивное замыкание R отношения несходства R. Отношение R будет нечетким отношением различия (антирефлексивное, (min — 5)-транзитивное, симметричное нечеткое отношение), которое задает матрицу (min — 5)-расстояний между нечеткими подмножествами.
Шаг 3. Для отношения различия R построить отношение подобия (толерантности) R (рефлексивное, (max —Т)-транзитивное, симметричное нечеткое отношение) следующим образом:
Шаг 4. К отношению подобия (толерантности) применить теорему о декомпозиции. При этом получим класс подмножеств, расстояние между которыми равно ао, затем класс подмножеств, расстояние между которыми равно #1, ао а\ и т.д., где ао а\ аг.
Шаг 5. Построить декомпозиционное дерево, которое отражает группировки элементов, полученные с помощью (тіп-5)-расстояния.
Графы нечетких отношений порядка
Упорядочение объектов по степени проявления ими некоторого количественного или качественного признака называется ранжированием.
Ранжирование объектов на основе количественного признака опирается на сравнение чисел между собой. Такие сравнения можно выполнить без участия человека.
Упорядочение объектов, сравниваемых по качественному признаку, невозможно без участия человека - эксперта. Такое ранжирование называется экспертным ранжированием.
Обычно ранжируют либо сложные реальные объекты - проекты, образцы продукции, уровни мастерства и т. п., либо ожидаемые результаты возможных управленческих решений - альтернативы. Все эти объекты характеризуются общим качественным признаком - важностью, полезностью, привлекательностью и др. Пусть ранжируемые объекты заданы некоторым списком. Задача состоит в том, чтобы перейти от исходного, чаще всего случайного упорядочения объектов к их правильному (по мнению эксперта) упорядочению. Список правильно упорядоченных объектов называется конечным списком.
Пусть имеется совокупность объектов (альтернатив) А и требуется сравнить их по предпочтительности, т. е. задать отношение предпочтения на множестве А и определить наилучшие объекты (альтернативы). Отношение предпочтения Р, которое можно определить как aPb, а,Ь Є А (объект а не менее предпочтителен, чем объект Ь) должно быть рефлексивным и антисимметричным, так как каждый объект не хуже самого себя, и, если объект а не хуже Ь и b не хуже а, то они одинаковы по предпочтительности. Отношение Р должно быть также транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами это свойство может быть нарушено), т. е. Р будет отношением частичного порядка.
Определяя в Р наибольшие элементы (а они равноценны по предпочтительности), мы находим «наилучшие» с точки зрения отношения предпочтения элементы. Однако если Р не является отношением линейного порядка, множество наибольших элементов может быть пустым. В этом случае для выбора используется более слабое понятие максимального элемента и множество максимальных элементов определяет «неулучшаемые» с точки зрения этого отношения предпочтения элементы.
Один из возможных способов решения задачи сравнения объектов по предпочтительности - ранжирование, т.е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделим «наилучшие» «или наихудшие» с точки зрения отношения предпочтения объекты.
Проблема выбора наилучших объектов - ключевая в теории принятия решений, разделе прикладной математики, имеющем многочисленные приложения в экономике, социологии, технике.
Рассмотрим следующую задачу. Пусть задано множество альтернатив X = {хі,... ,хп}, каждая из которых возможно характеризуется набором показателей (критериев). Для сравнения альтернатив привлекается эксперт (или группа экспертов), который в результате парного сравнения оценивает предпочтение альтернатив в паре (xi,Xj) числом из [0,1]. Тем самым, формируется некоторое нечеткое отношение R с матрицей [R] = {rij}nxn, где тц Є [0,1]. Требуется получить полный или частичный порядок заданного множества альтернатив.
Формально под нечетким отношением предпочтения подразумевается любое рефлексивное и транзитивное отношение, т. е. предпорядок. Заметим, что оба свойства вполне естественны, поскольку каждая альтернатива не хуже самой себя и если Х{ не хуже Xj, a Xj не хуже Хк, то целесообразно потребовать, чтобы xi была не хуже хь. Однако, на практике свойство транзитивности нарушается в 30% случаев, что обусловлено сложностью и субъективным фактором процедуры сравнения. В некоторых случаях рассматривается также свойство антисимметричности и тогда отношение предпочтения - это нестрогий порядок [42]. В [73] к отношению предпочтения предъявляется лишь свойство рефлексивности. Такая неоднозначность в определении нечеткого отношения предпочтения возникает потому, что кроме рефлексивности (выполнение которой можно обеспечить автоматически), все остальные свойства могут нарушаться и потому требуется специальная обработка матрицы парных сравнений, чтобы ее можно было рассматривать как матрицу нечеткого отношения предпочтения. В основу такого преобразования могут быть положены теоремы 2.2 и 2.6. В результате получим рефлексивное, транзитивное отношение, обладающее свойством совершенной антисимметрии - нечеткое отношение совершенного нестрогого порядка R, соответствующее исходному отношению R.
Так как любое нечеткое отношение можно представить через совокупность обычных отношений, то, применяя к отношению R теорему декомпозиции 4.5, получим его представление через совокупность обычных отношений, обладающих свойством рефлексивности, транзитивности и совершенной антисимметрии. Для каждого а отношение Ra представляет собой нестрогий совершенный порядок, а, следовательно, соответствующий граф Gfi не имеет контуров, отличных от петель (это следует из свойства транзитивности [43]), поэтому граф G допускает разложение на уровни.
