Полупорядок: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Полупорядок''' (''[[Semiorder]]'') -
'''Полупорядок''' (''[[Semiorder]]'')
[[антирефлексивное отношение|антирефлексивное]] [[бинарное отношение]] <math>P</math>, удовлетворяющее условиям:
[[антирефлексивное отношение|антирефлексивное]] [[бинарное отношение]] <math>\,P,</math> удовлетворяющее условиям:


(1) <math>aPb, \, cPd</math> влекут за собой <math>aPd</math> или <math>cPb</math>;
(1) <math>aPb, \, cPd</math> влекут за собой <math>\,aPd</math> или <math>\,cPb;</math>


(2) <math>aPb</math> и <math>bPc</math> влекут за собой <math>aPd</math> или <math>dPc</math>,
(2) <math>\,aPb</math> и <math>\,bPc</math> влекут за собой <math>\,aPd</math> или <math>\,dPc,</math>


где <math>a,b,c,d \in V</math> --- произвольные (необязательно различные) элементы.
где <math>\,a,b,c,d \in V</math> произвольные (необязательно различные) элементы.


Полупорядок можно также определить как бинарное отношение <math>P</math>, для
Полупорядок можно также определить как бинарное отношение <math>\,P,</math> для
которого найдется вещественнозначная функция <math>f</math> такая, что <math>uPv</math>
которого найдется вещественнозначная функция <math>\,f</math> такая, что <math>\,uPv</math>
имеет место
имеет место
тогда и только тогда, когда <math>f(u) > f(v) + \delta</math> для некоторой
тогда и только тогда, когда <math>\,f(u) > f(v) + \delta</math> для некоторой
константы <math>\delta</math> (возможно, равной единице).
константы <math>\,\delta</math> (возможно, равной единице).
==Литература==
==Литература==
[J. Graph Theory]
[J. Graph Theory]

Текущая версия от 12:31, 17 июня 2011

Полупорядок (Semiorder) — антирефлексивное бинарное отношение [math]\displaystyle{ \,P, }[/math] удовлетворяющее условиям:

(1) [math]\displaystyle{ aPb, \, cPd }[/math] влекут за собой [math]\displaystyle{ \,aPd }[/math] или [math]\displaystyle{ \,cPb; }[/math]

(2) [math]\displaystyle{ \,aPb }[/math] и [math]\displaystyle{ \,bPc }[/math] влекут за собой [math]\displaystyle{ \,aPd }[/math] или [math]\displaystyle{ \,dPc, }[/math]

где [math]\displaystyle{ \,a,b,c,d \in V }[/math] — произвольные (необязательно различные) элементы.

Полупорядок можно также определить как бинарное отношение [math]\displaystyle{ \,P, }[/math] для которого найдется вещественнозначная функция [math]\displaystyle{ \,f }[/math] такая, что [math]\displaystyle{ \,uPv }[/math] имеет место тогда и только тогда, когда [math]\displaystyle{ \,f(u) \gt f(v) + \delta }[/math] для некоторой константы [math]\displaystyle{ \,\delta }[/math] (возможно, равной единице).

Литература

[J. Graph Theory]