лекция


Чтобы посмотреть презентацию с картинками, оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов презентации:

Бинарные отношения. Отношения эквивалентности и разбиения. Отношения частичного порядка. Ирина Борисовна ПросвирнинаБинарные отношения и их свойстваОтношения эквивалентностиРазбиенияОтношения частичного порядкаДиаграммы ХассеАлгоритм топологической сортировки


ОтношенияДекартовым произведением множеств 𝐴 и 𝐵 является множество𝐴×𝐵=(𝑎,𝑏)𝑎∈𝐴, 𝑏∈𝐵Элементы множества 𝐴×𝐵 называются упорядоченными парами. 
ОтношенияОпределение 1Бинарным отношением между множествами 𝐴 и 𝐵 называется подмножество 𝑅 декартова произведения 𝐴×𝐵. Если упорядоченная пара 𝑎,𝑏 принадлежит отношению 𝑅, то пишут 𝒂𝑹𝒃 и говорят, что 𝒂 находится в отношении 𝑹 с 𝒃.В том случае, когда 𝐴=𝐵, мы говорим просто об отношении 𝑅 на 𝐴. 

ОтношенияПример 1 Выписать упорядоченные пары, принадлежащие следующим бинарным отношениям между множествами 𝐴 ={1, 3, 5, 7} и 𝐵 = {2, 4, 6}: 𝑈 ={(𝑥, 𝑦) 𝑥+𝑦=9}; 𝑉 = {(𝑥, 𝑦) х < у}.Решение 𝑈= {3, 6, 5, 4, 7, 2}; 𝑉={(1, 2), (1, 4), (1, 6), (3, 4), (3, 6), (5, 6)}.∎ 



ОтношенияПример 2 Множество 𝑅={(𝑥, у)  𝑥 − делитель 𝑦} определяет отношение на множестве 𝐴= {1, 2, 3, 4, 5, 6}. Найдите все упорядоченные пары, принадлежащие 𝑅.Решение𝑅={ 1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 2, 2, 2, 4, 2, 6, 3, 3, 3, 6, 4, 4, 5, 5, 6, 6}∎ 


ОтношенияИмеется удобный способ перечисления упорядоченных пар, принадлежащих данному отношению.Он основан на понятии ориентированно графа.
ОтношенияПусть 𝐴 и 𝐵 – два конечных множества и пусть 𝑅 – бинарное отношение между этими множествами. Изобразим элементы множеств 𝐴 и 𝐵 точками на плоскости. Для каждой упорядоченной пары отношения 𝑅 нарисуем стрелку, соединяющую точки, представляющие первую и вторую компоненты пары, соответственно. Такой объект называется ориентированным графом или орграфом. Точки, изображающие элементы множеств, принято называть вершинами орграфа.  

Пример 3 Рассмотрим отношение 𝑉 между множествами А={1, 3, 5, 7} и 𝐵= {2, 4, 6} из примера 1, b): 𝑉={(1, 2), (1, 4), (1, 6), (3, 4), (3, 6), (5, 6)}. Соответствующий ориентированный граф показан на рисунке.  1 2 3 4 5 6 7 ОтношенияДля иллюстрации отношения на отдельном множестве 𝐴 чертят орграф, чьи вершины соответствуют одному лишь множеству 𝐴, а стрелки, как обычно, соединяют элементы упорядоченных пар, находящихся в данном отношении.   ОтношенияСвойства отношенийОграничимся изучением бинарных отношений, заданных на одном множестве и рассмотрим некоторый набор их свойств. ОтношенияОпределение 2Отношение 𝑅 на множестве 𝐴 рефлексивно, если 𝑥𝑅𝑥 для всех 𝑥 из 𝐴.В терминах упорядоченных пар данное отношение рефлексивно, если (𝑥, 𝑥) принадлежит 𝑅 для всех возможных значений 𝑥. 
ОтношенияУ ориентированного графа, изображающего рефлексивное отношение, каждая вершина снабжена петлей, то есть стрелкой, начинающейся и заканчивающейся в одной и той же вершине. ОтношенияОпределение 3Отношение 𝑅 на множестве 𝐴 симметрично, если из 𝑥𝑅𝑦 следует 𝑦𝑅𝑥 для всех 𝑥 и 𝑦 из 𝐴. В терминах упорядоченных пар данное отношение симметрично, если из того, что (𝑥, 𝑦) принадлежит 𝑅 следует, что (𝑦, 𝑥) принадлежит 𝑅 для всех возможных значений 𝑥 и 𝑦. 
ОтношенияОрграф симметричного отношения 𝑅 вместе с каждой стрелкой из вершины 𝑥 в вершину 𝑦 имеет стрелку, направленную в обратную сторону: из 𝑦 в 𝑥.   ОтношенияОпределение 4Отношение 𝑅 на множестве 𝐴 антисимметрично, если из 𝑥𝑅𝑦 и 𝑦𝑅𝑥 следует, что 𝑥=𝑦 для всех 𝑥 и 𝑦 из 𝐴.В терминах упорядоченных пар данное отношение антисимметрично, если из того, что (𝑥, 𝑦) принадлежит 𝑅 и (𝑦, 𝑥) принадлежит 𝑅, следует, что 𝑥=𝑦 для всех возможных значений 𝑥 и 𝑦. 
ОтношенияЕсли отношение 𝑅 антисимметрично, то в соответствующем орграфе при наличии стрелки из вершины 𝑥 в несовпадающую с ней вершину 𝑦, стрелка из 𝑦 в 𝑥 будет обязательно отсутствовать.   ОтношенияОпределение 5Отношение 𝑅 на множестве А транзитивно, если из того, что 𝑥𝑅𝑦 и 𝑦𝑅𝑧 следует, что 𝑥𝑅𝑧 для всех 𝑥, 𝑦 и 𝑧 из 𝐴.В терминах упорядоченных пар данное отношение транзитивно, если из того, что (𝑥, 𝑦) принадлежит 𝑅 и (𝑦, 𝑧) принадлежит 𝑅 следует, что (𝑥, 𝑧) принадлежит 𝑅 для всех возможных значений 𝑥, 𝑦 и 𝑧. 
ОтношенияОрграф транзитивного отношения 𝑅 устроен так, что вместе со стрелками из вершины 𝑥 в вершину 𝑦 и из вершины 𝑦 в вершину 𝑧, у него будет стрелка и из вершины 𝑥 в вершину 𝑧.   ОтношенияПример 5 Что можно сказать о свойствах рефлексивности, симметричности, антисимметричности и транзитивности следующих отношений: «𝑥 делит 𝑦» на множестве натуральных чисел; «𝑥 не равно 𝑦» на множестве целых чисел; «возраст 𝑥 совпадает с возрастом 𝑦» на множестве всех людей? 

Отношение эквивалентностиОпределение 1Отношение 𝑅 на множестве 𝑆 называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.Отношения эквивалентности играют важную роль во всех разделах математики! 

Отношение эквивалентностиОпределение 2Два элемента 𝑎 и 𝑏 называют эквивалентными и пишут 𝑎~𝑏, если 𝑎 находится в отношении эквивалентности с 𝑏.  
Примеры отношений эквивалентностиПример 1Пусть 𝑅 – отношение на множестве целых чисел 𝒁, определенное следующим образом:𝑎𝑅𝑏 𝑑𝑒𝑓 𝑎=𝑏 или 𝑎=−𝑏. 𝑅 – отношение эквивалентности, так как оно рефлексивно, симметрично и транзитивно. 


Примеры отношений эквивалентностиПример 2Пусть 𝑅 – отношение на множестве вещественных чисел 𝑹, определенное следующим образом:𝑎𝑅𝑏 𝑑𝑒𝑓 𝑎−𝑏 является целым числом. 𝑅 – отношение эквивалентности, так как оно рефлексивно, симметрично и транзитивно. 


Примеры отношений эквивалентностиПример 3Пусть 𝑚 – целое число, большее 1. Пусть 𝑎, 𝑏∈𝒁.𝑎≡𝑏(𝑚𝑜𝑑 𝑚)𝑑𝑒𝑓 𝑚(𝑎−𝑏)𝑅=𝑎,𝑏𝑎≡𝑏(𝑚𝑜𝑑 𝑚) – отношение эквивалентности на 𝒁, так как оно рефлексивно: 𝑚(𝑎−𝑎), ∀𝑎∈𝒁, симметрично: 𝑚(𝑎−𝑏)  𝑚(𝑏−𝑎), транзитивно: 𝑚(𝑎−𝑏)∧𝑚(𝑏−𝑐)  𝑚(𝑎−𝑐) 



Примеры отношений эквивалентностиПример 4Пусть 𝑅 – отношение на множестве строк, составленных из букв английского алфавита, определенное следующим образом:𝑎𝑅𝑏 𝑑𝑒𝑓 𝑙𝑎=𝑙(𝑏), где 𝑙𝑥 – длина строки 𝑥.𝑅 – отношение эквивалентности, так как оно рефлексивно, симметрично и транзитивно. 


Примеры отношений эквивалентностиПример 5Пусть 𝑛 – натуральное число и пусть 𝑆 – множество строк, составленных из символов некоторого алфавита 𝐴.Пусть 𝑅𝑛 – отношение на 𝑆, определенное следующим образом:𝑠𝑅𝑛𝑡 𝑑𝑒𝑓 𝑠=𝑡, или 𝑠 и 𝑡 состоят по крайней мере из 𝑛 символов, причем первые 𝑛 символов в строках 𝑠 и 𝑡 совпадают.𝑅𝑛– отношение эквивалентности, так как оно рефлексивно, симметрично и транзитивно. 




«Антипримеры» отношений эквивалентностиПример 6Пусть  – отношение «делит» на множестве натуральных чисел 𝑵.Отношение  не является отношением эквивалентности, так как оно не симметрично:24 , но 4∤2. 

«Антипримеры» отношений эквивалентностиПример 7Пусть 𝑅 – отношение на множестве вещественных чисел 𝑹, определенное следующим образом:𝑥𝑅𝑦 𝑑𝑒𝑓 𝑥−𝑦<1𝑅 не является отношением эквивалентности, так как оно не транзитивно:2,8 𝑅 1,9  ⟺ 2,8−1,9<11,9 𝑅 1,1 ⟺ 1,9−1,1<12,8 𝑅 1,1 ⟺ 2,8−1,1≥1 



Классы эквивалентностиОпределение 3Пусть 𝑅 – отношение эквивалентности на множестве 𝐴 и пусть 𝑎 – элемент множества 𝐴. Множество всех элементов из 𝐴, эквивалентных элементу 𝑎, называется классом эквивалентности элемента 𝑎. Класс эквивалентности элемента 𝑎 относительно 𝑅 обозначается через 𝑎𝑅 или через 𝑎, если из контекста ясно, о каком отношении идет речь.𝑎𝑅=𝑠𝑎,𝑠∈𝑅Если 𝑏∈𝑎𝑅, то 𝑏 называется представителем этого класса эквивалентности. 


Примеры классов эквивалентностиПример 8Пусть 𝑅 – отношение на множестве целых чисел 𝒁, определенное следующим образом:𝑎𝑅𝑏 𝑑𝑒𝑓 𝑎=𝑏 или 𝑎=−𝑏. Найти 𝑎𝑅=𝑎.Решение𝑎=−𝑎,𝑎Например, 5=−5,5, 7=−7,7, 0=0. 




Примеры отношений эквивалентностиПример 9Найти классы эквивалентности чисел 0 и 1 для отношения сравнимости по модулю 4.Решение04=𝑎𝑎≡0(𝑚𝑜𝑑 4)=…, −8, −4, 0, 4, 8, …14=𝑎𝑎≡1(𝑚𝑜𝑑 4)=…, −7, −3, 1, 5, 9, … 


Примеры отношений эквивалентностиПример 10Построить класс эквивалентности строки 0111 относительно отношения 𝑅3 на множестве всех битовых строк.Решение0111𝑅3==  011, 0110, 0111, 01100, 01101, 01110, 01111, … 

Классы эквивалентности и разбиенияТеорема 1Пусть 𝑅 – отношение эквивалентности на множестве 𝐴. Следующие утверждения для элементов 𝑎 и 𝑏 из множества 𝐴 равносильны: 𝑎𝑅𝑏, 𝑎=𝑏, 𝑎∩𝑏≠∅. 


? 𝑎𝑅𝑏  𝑎=𝑏 ДоказательствоПусть 𝑐∈𝑎  𝑎𝑅𝑐𝑎𝑅𝑏,  𝑅 симметрично  𝑏𝑅𝑎𝑏𝑅𝑎, 𝑎𝑅𝑐, 𝑅 транзитивно  𝑏𝑅𝑐 𝑏𝑅𝑐  𝑐∈𝑏 Итак, 𝑎  𝑏Аналогично доказывается, что 𝑏  𝑎. 




? 𝑎=𝑏  𝑎∩𝑏≠∅  Доказательство Пусть 𝑎=𝑏  𝑎∩𝑏= 𝑎∩𝑎= 𝑎≠∅, так как 𝑎∈𝑎 по рефлексивности отношения 𝑅. 


? 𝑎∩𝑏≠∅  𝑎𝑅𝑏  Доказательство Предположим, что𝑎∩𝑏≠∅  существует элемент 𝑐 со свойством: 𝑐∈𝑎 ∧ 𝑐∈𝑏.𝑎𝑅𝑐 ∧ 𝑏𝑅𝑐𝑎𝑅𝑐 ∧ 𝑐𝑅𝑏𝑎𝑅𝑏 ∎ 




Классы эквивалентности и разбиенияИз теоремы следует, что классы эквивалентности 𝑎𝑅 относительно отношения эквивалентности 𝑅 непустые, попарно не пересекаются и в объединении дают все множество 𝐴.Другими словами классы эквивалентности образуют разбиение множества 𝐴 в смысле следующего определения. 
Классы эквивалентности и разбиенияОпределение 4Разбиением множества 𝐴 называется набор непустых, попарно непересекающихся подмножеств множества 𝐴, объединение которых совпадает с 𝐴. 
Примеры разбиенийПример 11Построить разбиение, соответствующее отношению сравнимости по модулю 4 на множестве целых чисел 𝒁.РешениеРазбиение множества целых чисел 𝒁 состоит из четырех классов вычетов: 04, 14, 24, 34. 

Примеры разбиенийПример 12Построить разбиение, соответствующее отношению эквивалентности 𝑅3 на множестве всех битовых строк.РешениеРазбиение множества всех битовых строк состоит из восьми классов эквивалентности:000𝑅3,   001𝑅3,  010𝑅3,  011𝑅3,100𝑅3,  101𝑅3,   110𝑅3,   111𝑅3.  Отношение частичного порядкаОпределение 5Отношение 𝑅 на множестве 𝑆 называется отношением частичного порядка, если оно рефлексивно, антисимметрично и транзитивно. Множество 𝑆, на котором задано отношение частичного порядка 𝑅, называется частично упорядоченным множеством и обозначается (𝑆,𝑅). 

Примеры частично упорядоченных множествПример 1Отношение «больше или равно» (≥) на множестве целых чисел 𝒁 является отношением частичного порядка. 
Примеры частично упорядоченных множествПример 2Отношение «делит» () на множестве натуральных чисел 𝑵 является отношением частичного порядка. 
Примеры частично упорядоченных множествПример 3Отношение «содержится в» () на множестве всех подмножеств 𝑃(𝑆) множества 𝑆 является отношением частичного порядка. 
«Антипример» частично упорядоченного множестваПример 4Отношение «𝑥 старше 𝑦», определенное на множестве всех людей, не является отношением частичного порядка.Действительно, это отношение не является рефлексивным. 
Отношение частичного порядкаОпределение 6Пусть (𝑆,≺) – частично упорядоченное множество. Два элемента 𝑎 и 𝑏 из 𝑆 называются сравнимыми, если 𝑎 ≺ 𝑏 или 𝑏 ≺ 𝑎. 
Отношение частичного порядкаОпределение 7Если (𝑆,≺) – частично упорядоченное множество, любые два элемента которого сравнимы, то 𝑆 называется линейно упорядоченным множеством или цепью, а отношение ≺ называется линейным порядком.  
Пример линейно упорядоченного множестваПример 5Частично упорядоченное множество(𝒁,≤) является цепью. 
«Антипример» линейно упорядоченного множестваПример 6Частично упорядоченное множество (𝑵,) не является цепью, так как 5 и 7 несравнимы. 
Построение диаграммы Хассе для 𝑺=𝟏, 𝟐, 𝟑, 𝟒, ≤  Построим ориентированный граф отношения ≤, определенного на множестве 1, 2, 3, 4. 3421 Построение диаграммы Хассе для 𝟏, 𝟐, 𝟑, 𝟒, ≤.  Удалим все петли.3421 Построение диаграммы Хассе для 𝟏, 𝟐, 𝟑, 𝟒, ≤.  Удалим все петли.3421 Построение диаграммы Хассе для 𝟏, 𝟐, 𝟑, 𝟒, ≤.  Удалим все ребра (𝑥,𝑦), для которых существует элемент 𝑧∈𝑆 такой, что 𝑥≤𝑧 и 𝑧≤𝑦. 3421 Построение диаграммы Хассе для 𝟏, 𝟐, 𝟑, 𝟒, ≤.  Удалим все ребра (𝑥,𝑦), для которых существует элемент 𝑧∈𝑆 такой, что 𝑥≤𝑧 и 𝑧≤𝑦. 3421 Построение диаграммы Хассе для 𝟏, 𝟐, 𝟑, 𝟒, ≤.  Удалим все стрелки.3421 Построение диаграммы Хассе для 𝟏, 𝟐, 𝟑, 𝟒, ≤.  Удалим все стрелки.3421 Построить диаграмму Хассе для частичного порядка 𝒂,𝒃𝒃⋮𝒂, определенного на 𝟏,𝟐,𝟑,𝟒,𝟔,𝟖,𝟏𝟐. 1263181242 Построить диаграмму Хассе для частично упорядоченного множества 𝑷𝒂,𝒃,𝒄, . 𝑎,𝑏,𝑐 𝑏,𝑐 𝑎,𝑐 𝑎 ∅ 𝑐 𝑎,𝑏 𝑏  Максимальные и минимальные элементыОпределение 8Пусть (𝑆,≺) – частично упорядоченное множество. Элемент 𝑎 из 𝑆 называется максимальным, если не существует элемента 𝑏∈𝑆 со свойством: 𝑎≺𝑏.Элемент 𝑎 из 𝑆 называется минимальным, если не существует элемента 𝑏∈𝑆 со свойством: 𝑏≺𝑎. 

Диаграмма Хассе для частичного порядка 𝒂,𝒃𝒃⋮𝒂, определенного на 𝐒=𝟏,𝟐,𝟑,𝟒,𝟔,𝟖,𝟏𝟐. 1 – минимальный элемент (𝑆,⋮);8, 12 – максимальные элементы 𝑆,⋮. 1263181242 Диаграмма Хассе для частично упорядоченного множества 𝑷𝒂,𝒃,𝒄, . 𝑎,𝑏,𝑐  максимальный элемент 𝑷𝒂,𝒃,𝒄, ;∅  минимальный элемент 𝑷𝒂,𝒃,𝒄, . 𝑎,𝑏,𝑐 𝑏,𝑐 𝑎,𝑐 𝑎 ∅ 𝑐 𝑎,𝑏 𝑏  Топологическая сортировкаПредположим, что разрабатывается проект, состоящий из 20 различных заданий.Выполнение части заданий проекта может быть начато только после того, как другие задания проекта будут полностью завершены.В какой очередности должны выполняться задания проекта?Зададим на множестве всех заданий проекта частичный порядок, положив для заданий 𝑎 и 𝑏:𝑎≺𝑏𝑑𝑒𝑓 𝑏 не может быть начато, пока не завершено 𝑎 


Топологическая сортировкаОпределение 9 Линейный порядок ≺ называется согласованным с частичным порядком 𝑅, если из того, что 𝑎𝑅𝑏 следует, что 𝑎≺𝑏.Построение линейного порядка, согласованного с данным частичным порядком, называется топологической сортировкой. 
Топологическая сортировкаЛемма Любое конечное частично упорядоченное множество (𝑆, ≺) имеет хотя бы один минимальный элемент.ДоказательствоВыберем в множестве 𝑆 элемент 𝑎0.Если 𝑎0 не минимальный, то найдется такой элемент 𝑎1 в 𝑆, что 𝑎1≺ 𝑎0.Если 𝑎1 не минимальный, то найдется такой элемент 𝑎2 в 𝑆, что 𝑎2≺𝑎1.Продолжим этот процесс.Так как 𝑆 – конечное множество, то процесс должен закончиться построением минимального элемента 𝑎𝑛 множества 𝑆.∎ 



Алгоритм топологической сортировкиПусть (𝐴,≺) – конечное частично упорядоченное множество.Выберем в 𝐴 минимальный элемент 𝑎1. Он существует по лемме. (𝐴−𝑎1,≺) – тоже конечное частично упорядоченное множество.Если 𝐴−𝑎1≠∅, то выберем в частично упорядоченном множестве 𝐴−𝑎1 минимальный элемент 𝑎2. Он существует по лемме. Если 𝐴−𝑎1,𝑎2≠∅, то выберем в частично упорядоченном множестве 𝐴−𝑎1,𝑎2 минимальный элемент 𝑎3.Продолжим этот процесс, выбрав в 𝐴−𝑎1,…,𝑎𝑘 минимальный элемент 𝑎𝑘+1.Так как 𝐴 – конечное множество, процесс должен закончиться. 



Алгоритм топологической сортировкиИтак, для частично упорядоченного множества (𝐴,≺) построен линейный порядок ≺𝑙:𝑎1 ≺𝑙 𝑎2 ≺𝑙 … ≺𝑙 𝑎𝑛Этот линейный порядок согласован с исходным частичным порядком.∎ 

Алгоритм топологической сортировки. ПримерыПример 1Построить согласованный линейный порядок для частично упорядоченного множества 1, 2, 4, 5, 12, 20, . 2025201241 Алгоритм топологической сортировки. ПримерыПример 1Построить согласованный линейный порядок для частично упорядоченного множества 1, 2, 4, 5, 12, 20, .Решение1 2025201241 Алгоритм топологической сортировки. ПримерыПример 1Построить согласованный линейный порядок для частично упорядоченного множества 1, 2, 4, 5, 12, 20, .Решение1 202520124 Алгоритм топологической сортировки. ПримерыПример 1Построить согласованный линейный порядок для частично упорядоченного множества 1, 2, 4, 5, 12, 20, .Решение1≺5 202520124 Алгоритм топологической сортировки. ПримерыПример 1Построить согласованный линейный порядок для частично упорядоченного множества 1, 2, 4, 5, 12, 20, .Решение1≺5 20220124 Алгоритм топологической сортировки. ПримерыПример 1Построить согласованный линейный порядок для частично упорядоченного множества 1, 2, 4, 5, 12, 20, .Решение1≺5≺2 20220124 Алгоритм топологической сортировки. ПримерыПример 1Построить согласованный линейный порядок для частично упорядоченного множества 1, 2, 4, 5, 12, 20, .Решение1≺5≺2 2020124 Алгоритм топологической сортировки. ПримерыПример 1Построить согласованный линейный порядок для частично упорядоченного множества 1, 2, 4, 5, 12, 20, .Решение1≺5≺2 ≺4 2020124 Алгоритм топологической сортировки. ПримерыПример 1Построить согласованный линейный порядок для частично упорядоченного множества 1, 2, 4, 5, 12, 20, .Решение1≺5≺2 ≺4 202012 Алгоритм топологической сортировки. ПримерыПример 1Построить согласованный линейный порядок для частично упорядоченного множества 1, 2, 4, 5, 12, 20, .Решение1≺5≺2 ≺4 ≺20 202012 Алгоритм топологической сортировки. ПримерыПример 1Построить согласованный линейный порядок для частично упорядоченного множества 1, 2, 4, 5, 12, 20, .Решение1≺5≺2 ≺4 ≺20 12 Алгоритм топологической сортировки. ПримерыПример 1Построить согласованный линейный порядок для частично упорядоченного множества 1, 2, 4, 5, 12, 20, .Решение1≺5≺2 ≺4 ≺20 ≺12∎ 12 Алгоритм топологической сортировки. ПримерыПример 2Проект развития компьютерной компании предполагает выполнение семи этапов.Выполнение некоторых этапов проекта развития может быть начато только после того, как другие этапы проекта будут полностью завершены.В какой очередности должны выполняться этапы проекта развития компании?Зададим на множестве всех этапов проекта частичный порядок, положив для этапов 𝑋 и 𝑌:𝑋𝑌𝑑𝑒𝑓 𝑌 не может быть начат, пока не завершен 𝑋 


Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.𝐷 𝐺 𝐹 𝐵 𝐸 12𝐴 𝐶  Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.Решение𝐴 𝐷 𝐺 𝐹 𝐵 𝐸 12𝐴 𝐶  Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.Решение𝐴 𝐷 𝐺 𝐹 𝐵 𝐸 12𝐶  Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.Решение𝐴 ≺𝐶 𝐷 𝐺 𝐹 𝐵 𝐸 12𝐶  Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.Решение𝐴  𝐶 𝐷 𝐺 𝐹 𝐵 𝐸 12 Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.Решение𝐴  𝐶  𝐵 𝐷 𝐺 𝐹 𝐵 𝐸 12 Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.Решение𝐴  𝐶  𝐵 𝐷 𝐺 𝐹 𝐸 12 Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.Решение𝐴 ≺𝐶 ≺𝐵 ≺ 𝐸 𝐷 𝐺 𝐹 𝐸 12 Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.Решение𝐴 ≺𝐶 ≺𝐵 ≺ 𝐸 𝐷 𝐺 𝐹 12 Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.Решение𝐴 ≺𝐶 ≺𝐵 ≺ 𝐸 ≺ 𝐹 𝐷 𝐺 𝐹 12 Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.Решение𝐴 ≺𝐶 ≺𝐵 ≺ 𝐸 ≺ 𝐹 𝐷 𝐺 12 Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.Решение𝐴 ≺𝐶 ≺𝐵 ≺ 𝐸 ≺ 𝐹≺ 𝐷 𝐷 𝐺 12 Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.Решение𝐴 ≺𝐶 ≺𝐵 ≺ 𝐸 ≺ 𝐹≺ 𝐷 𝐺 12 Алгоритм топологической сортировки. ПримерыПример 2Построить согласованный линейный порядок для частично упорядоченного множества проектов.Решение𝑨≺𝑪 ≺𝑩 ≺ 𝑬 ≺𝑭≺𝑫 ≺ 𝑮∎ 𝐺 12

Приложенные файлы


Добавить комментарий