二元传递关系计数的上界估计

董永红 郭海林 刘智秉

(1 九江学院理学院; 2 九江学院图书馆 江西九江 332005)

1 预备知识

定义1［1］若S⊆R ×R，则称S为R上的一个二元关系.称S对应的m阶(0，1)矩阵A =(aij)m×m为S的关联矩阵，即(ai，aj)∈S，aij =1;(ai，aj)∉S，aij =0.

定义2［2］给定一个二元关系S，S对应一个有向图Γ，称Γ 为S的对应图.图Γ的顶点集为R ={ai|i =1，2，…，m}，边集为E ={eij=aiaj|(ai，aj)∈S}.

定义3 给定一个二元关系S，记RS ={ai∈R|∃aj∈R，s.t. (ai，aj)∈S}.称|RS|为关系S涉及R的元素个数.一般|RS|≤m =|R|.若|RS|=m称S为二元全涉关系，此时关系对应的矩阵称为全涉矩阵，对应的图为全涉图.依据图论知识，有向图的边集是一个多重子集，而二元关系是单重子集，因此二元关系的对应图是没有重边的.

文献［4］的完全计数是考虑有限集R中元素的次序下，满足某些性质的二元关系的计数.若不考虑有限集R中元素的次序，笔者发现二元关系对应的关联矩阵满足交换行列的合同变换，称为置换合同，即:B=PAPT，其中P为置换矩阵，PT表示P的转置.易见这种合同变换是全体关联矩阵上的一个等价变换，由此本文将关联矩阵合并成等价类，来讨论二元关系的等价类计数.特别是结合关联矩阵与有向图的关系，估计出二元传递关系的等价类计数的一个上界.

2 主要结论

定理2 二元传递关系的等价类计数记为qm，其一个上界为Lm:

其中［x］表示对实数x下取整.

证明定理2 时，需要转化为有向图来讨论，在此处介绍两个命题.

命题1 若二元传递关系对应的图是圈，则涉及n个点的圈是一个有向圈.

证明:如果二元传递关系对应的涉及n个点的圈为a1→a2→a3→…→an→a1，那么对任意的i，j有ai→aj，aj→ai.不妨设i≤j≤n，当i ＜j时，有aij=aji =1;当i=j时，由传递性知……