Сологуб Г.Б. Элементы дискретной математики, страница 2

Окружность единичного радиуса с центром вначалекоординатизображаетбинарноеотношение22ρ = {<x,y> | x +y = 1, x, y – действительные числа}:y101xТ.е., график – это альтернативный способ задания отношений.Кроме того, любое бинарное отношение, заданное намножестве A, можно изобразить в виде т.н.

ориентированногографа G = <A,ρ> следующим образом: произвольным образомотмечают точками элементы множества A и для каждой пары<x,y>∈ρ, x,y∈A проводят стрелку из точки x в точку y. Такимобразом, A будет являться множеством вершин, а ρ - множествомдуг графа G.Пример 14. Отношение из примера 12 можно представить ввиде орграфа:2314Как видно из рисунка, парам вида <x,x>∈ρ, x∈A соответствуетстрелка, замыкающаяся на той же вершине, из которой онавыходит (т.н. петля), а в случае <x,y>∈ρ и <y,x>∈ρ, x,y∈Aстрелка, соединяющая вершины x и y будет двунаправленнойКаждому орграфу G = <A,ρ> ставится в соответствие т.н.матрица смежности S размера n×n, где n – количество вершинграфа, элементы которой вычисляются по следующему правилу:sij = 1, если в G есть дуга из вершины ai в вершину aj; sij = 0 - впротивном случае.

.Очевидно, что любой орграф изображает некотороеотношение, заданное на множестве его вершин, т.о. представлениев виде орграфа или матрицы смежности – это еще дваальтернативных способа задания отношений (правда с помощьюних можно описывать только конечные отношения).Cимметричноеотношениеизображаютввиденеориентированного графа (петли не рисуют, вместодвунаправленных стрелок рисуют линии – т.н. ребра графа).Пример 15. Карта метро является неориентированным графом,который изображает отношение ρ = {<x,y> | идет поезд от x до y},заданное на множестве A станций метрополитена.Если каждому ребру графа (дуге орграфа) поставлено всоответствие некоторое число (т.н.

вес), то такой граф называетсянагруженным графом.Пример 16. Карта автомобильных дорог с отмеченнымирасстояниямимеждунаселеннымипунктамиявляетсянагруженным графом.Теория графов является разделом дискретной математики.Предметом её изучения являются различные виды графов, ихсвойства, алгоритмы построения и методы решения различныхзадач, связанных с графами.Примером оптимизационной задачи на графах является задачапоиска минимального пути в нагруженном графе (т.е. нахождениянабора вершин, связанных ребрами (дугами), сумма весов которыхминимальна).

Такая задача возникает, например, примаршрутизации пакетов сигналов, проходящих по компьютернымсетям.Рассмотрим еще один специальный вид графов – т.н.диаграммы Хассе. Они используются для изображения отношенийчастичного порядка (т.е. отношений обладающих одновременносвойствамирефлексивности,антисимметричностиитранзитивности).Пример 17. Пусть задано множество работников некоторойкомпьютерной фирмы: {«Директор (Д)», «Менеджер проекта(МП)», «Программист (П)», «Начальник отдела продаж (НОП)»,«Менеджер по продажам (МПП)», «Системный администратор(СА)»}, на котором задано отношение «непосредственноподчиняется» = {<МПП, НОП>, <НОП, Д>, <П, МП>, <МП, Д>,<СА, Д>}, которое выражает структуру управления (задаетиерархию в этой фирме).

Это отношение можно изобразить в видеориентированного графа:ДиректорНачальник отделапродажМенеджерпроектаМенеджер попродажамПрограммистСистемныйадминистраторЭто отношение является антисимметричным.В конечном счете, любой работник этой фирмы подчиняетсядиректору. Так что мы можем расширить это отношение, добавивв него пары <МПП, Д> и <П, Д> (дорисовав соответствующиестрелки). Очевидно, что полученное отношение будеттранзитивным.Кроме того, можно сделать это отношение рефлексивным,добавив в него пары <МПП, МПП>, <НОП, НОП>, <П, П>,<МП, МП>, <СА, СА>, <Д, Д> (дорисовав соответствующиепетли).

Это разумно, ведь можно сказать, что каждый изработников подчиняется сам себе (предполагаем, что все онивменяемы ☺).В итоге, получим отношение частичного порядка, котороеможно было бы изобразить орграфом с кучей стрелок и петель.Однако принято изображать такие отношения с помощьюдиаграммы Хассе.

Для этого отношения она такова:ДиректорНачальник отделапродажМенеджерпроектаМенеджер попродажамПрограммистСистемныйадминистраторЭто уже неориентированный граф, в нем исходные стрелкизаменены на линии, петли не нарисованы, стрелки, добавленныепо транзитивности, – тоже, но при этом неявно предполагается,что они есть.Особенностью диаграмм Хассе является то, что в них имеетсущественное значение высота, на которой расположен элемент:из двух соединенных линией элементов один обязательнорасполагается ниже другого – это значит, что он «меньше»(«хуже», «подчиняется» и т.п., в зависимости от содержательногосмысла отношения).Пусть на множестве A задано “≤” - отношение частичногопорядка.

Вводятся следующие определения.Элемент m∈A называется минимальным, если в A нетэлементов x ≠ m таких, что x ≤ m.Элемент m∈A называется максимальным, если в A нетэлементов x ≠ m таких, что m ≤ x.Элемент m∈A называется наименьшим, если m ≤ x ∀x∈A.Элемент m∈A называется наибольшим, если x ≤ m ∀x∈A.Если в частично упорядоченном множестве A все элементысравнимы, т.е. ∀x≠y∈A одна из двух пар <x, y> или <y, x>обязательно принадлежит отношению порядка, то это отношениеназывается линейным порядком.Пример 18.

В частично упорядоченном множестве работниковфирмы из примера 17 минимальных элементов будет несколько –это МПП, П и СА; Д является максимальным и наибольшим;наименьшего элемента нет.gПример19.ПустьнамножествеA = {a, b, c, d, e, f, g} задано отношение частичногоefпорядка с помощью диаграммы Хассе.dВыпишем содержащиеся в нем пары.Это отношение будет содержать, исходя изbcрефлексивности, пары: <a, a>, <b, b>, <c, c>, <d, d>,<e, e>, <f, f>, <g, g>.aДалее, для каждой линии на диаграмме запишемсоответствующую ей пару, учитывая высоту, на которойрасположены соединенные этой линией элементы: <a, b>, <a, d>,<a, c>, <b, e>, <c, f>, <d, e>, <d, f>, <e, g>.Кроме того, по транзитивности, добавим пары: <a, e>, <a, f>,<b, g>, <d, g>.Ну и, с учетом уже добавленных, добавляем также, потранзитивности, пару <a, g>.Итак, заданное отношение имеет вид: “≤” = {<a, a>, <b, b>,<c, c>, <d, d>, <e, e>, <f, f>, <g, g>, <a, b>, <a, d>, <a, c>, <b, e>,<c, f>, <d, e>, <d, f>, <e, g>, <a, e>, <a, f>, <b, g>, <d, g>, <a, g>}.a – минимальный и наименьший элемент множества A,наибольшего нет, g и f – максимальные.“≤” не является отношением линейного порядка, так какнесравнимы элементы b и c, e и f, g и f, b и f, с и e, с и g, b и d,c и d.Можно дополнить это отношение до линейного порядка,упорядочив произвольным образом эти элементы, не нарушая приэтом транзитивность.Например, добавим в это отношение пары <b, c>, <f, e>, <c,d>.По транзитивности, в него войдут также пары <b, d>, <b, f>,<c, e>, <c, g>, <f, g>.Таким образом, получим отношение линейного порядка{<a, a>, <b, b>, <c, c>, <d, d>, <e, e>, <f, f>, <g, g>, <a, b>, <a, d>,<a, c>, <b, e>, <c, f>, <d, e>, <d, f>, <e, g>, <a, e>, <a, f>, <b, g>,<d, g>, <a, g>, <b, c>, <f, e>, <c,d>, <b, d>, <b, f>, <c, e>, <c, g>,<f, g>}.gДиаграмма Хассе этого отношения будет иметь вид:efdcba.