Главная | Случайная
Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Бинарные отношения и графы




 

Бинарное отношение R на конечном множестве V может быть представлено ориентированным графом G(R), называемым графом отношения R. Вершинами графа служат элементы множества V; вершины x и y соединены направленной дугой с началом x и концом y, если (x,y)∈R. Обратно, всякий ориентированный граф без параллельных дуг G задает бинарное отношение R(G) на множестве своих вершин, чьим графом он и


 

 

является: вершины x и y связаны отношением R(G), если они соединены направленной дугой с началом x и концом y. Если R

– бинарное отношение на конечном множестве V = {1, 2, …, n}, а G – граф c вершинами V = {1, 2, …, n}, то матрица смежности графа G совпадает с характеристической матрицей отношения R в том и только том случае, когда G = G(R) или, что равносильно, R = R(G).

Рассмотрим, как связаны свойства отношения R и соответствующего ему графа G = G(R).

Отношение R симметрично, если для любых x, yV из xRy следует yRx. Иными словами, если на ориентированном графе G имеется дуга из x в y, то имеется также и дуга из y в x. В этом случае матрица смежности графа G симметрична. По существу, граф G оказывается неориентированным. Можно считать, что симметричным отношениям отвечают неориентированные графы. Антисимметричность отношения R означает, что xRy и yRx влечет x = y и равносильна тому, что две различные вершины графа G могут быть связаны дугой лишь в одном направлении. Если отношение R асимметрично, то есть xRy влечет yRx, то, кроме того, граф G не должен иметь петель.

Если R рефлексивное отношение, то есть xRx для любого

 

xV, то граф G имеет петлю в каждой вершине, а диагональ матрицы смежности состоит из одних единиц. Соответственно отношение R антирефлексивно тогда и только тогда, когда граф G не имеет петель.


 

 

Отношение R транзитивно, если из xRy и yRz следует xRz. Для графа G это означает, что если G содержит дуги из x в y и из y в z, то он содержит и дугу из x в z. Более того, если существует путь из вершины x в вершину y, то имеется и дуга из x в y.

В терминах графа G = G(R) простую интерпретацию получает понятие транзитивного замыкания отношения R. На множестве вершин графа G определим отношение достижимости R^, полагая xR^y тогда и только тогда, когда вершина y достижима из вершины x (в графе G имеется путь из x в y). Отношение достижимости R^ является транзитивным замыканием отношения R, то есть R^ – это наименьшее транзитивное отношение, содержащее R. Матрицей отношения R^ служит матрица E A A[k] ∨…∨ A[n–1], где A – матрица

смежности графа G.

 

Отношение R называется ацикличным, если граф G(R) не содержит нетривиальных циклов. Если вершины x и y на графе ацикличного отношения R соединены некоторым путем, то в этом графе нет дуги из y в x.

 

Теорема.Отношение R на конечном множестве V ациклично тогда и только тогда, когда существует отображение ϕ:VN такое, что xRy влечет ϕ(x) < ϕ(y) для любых x,yV.


 

 

До каз а тельст во . Достаточность. Предположим, что отображение ϕ обладает указанным свойством. Тогда для любого цикла v0, v1, …,vn, v0 = vn, в графе G(R) имеем:

ϕ(v0) < ϕ(v1) <…< ϕ(vn) = ϕ(v0),

 

что невозможно при n > 0.

 

Необходимость. Пусть n = |V| – число элементов множества V. Для произвольного xV рассмотрим множество всевозможных простых цепей в графе G(R), заканчивающихся в вершине x. Ни одна из этих цепей не содержит более чем n вершин, так что их длины ограничены в совокупности. Положим ϕ(x) = k, где k – максимальная из длин простых цепей, заканчивающихся в вершине x. Если нет ни одной цепи, ведущей в x, то есть ни одна дуга не заканчивается в x, полагаем ϕ(x)=0. Покажем, что так определенное отображение ϕ обладает нужным свойством. Предположим, что xRy. Пусть ϕ(x)=k. Тогда в графе G(R) имеется простая цепь v0, v1, …,vk = x. Добавив к этой цепи дугу из x в y, мы получим маршрут v0, v1, …,vk = x, y (длины k+1). Этот маршрут является простой цепью. В самом деле, так как цепь v0, v1, …, vk простая, все вершины в ней различны. Если y совпадает с одной из вершин этой цепи, скажем y = vi, получается цикл y = vi, v1, …,vk = x, y, что противоречит ацикличности отношения R. Следовательно, имеется простая цепь длины k+1, заканчивающаяся в y. Значит, ϕ(y) ≥ k+1 и потому ϕ(y) > ϕ(x).


 

 

Пример.Рассмотрим бинарное отношение R, граф которого

 

G(R) представлен на рис 9.

 

 

1 2

 

 

4 3

 

Рис. 9

 

В соответствии с определением отображения ϕ находим:

 

ϕ(1) = 0; ϕ(2) = 1; ϕ(3) = 2; ϕ(4) = 3.

 

 

Из предыдущей теоремы следует, что функция выбора CR (блокировка), построенная по ацикличному отношению R, является расширением некоторой функции выбора по скалярному критерию. В самом деле, пусть Ω = {1, 2, …, n} – множество альтернатив, а R – ацикличное бинарное отношение на Ω. Тогда, по предыдущей теореме, на множестве Ω существует числовая функция ϕ :{1, 2, …, n}→N такая, что iRj влечет ϕ(i) < ϕ(j). Зададим функцию f (скалярный критерий), полагая f(i) = n – ϕ(i). Ясно, что iRj влечет f(i) > f(j). Следовательно, f(i) ≤ f(j) влечет iRj. Обозначим через C функцию выбора по скалярному критерию f. Тогда

xC(X) ⇔ ∀yX f(x) ≥ f(y).


 

 

С другой стороны, в соответствии с определением функции

 

выбора CR имеем:

 


 

 

Следовательно,


xCR(X)⇔ ∀yX (yRx)}.

 

 

xC(X) ⇒xCR(X),


 

то есть C(X) ⊂ CR(X).


 

 

Деревья

 




Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2019 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных