可实现布尔矩阵与传递关系计数

传递关系的计数问题是一个开问题。本文建立了对称传递关系与可实现布尔矩阵的联系,并通过该联系,给出了对称传递关系的计数。

布尔矩阵的可实现问题及其与色数问题的关系

讨论了布尔矩阵的可实现问题及其与色数问题的关系.首先给出布尔矩阵可实现的一些充要条件,讨论可实现布尔矩阵的性质,其次证明可实现布尔矩阵的容度等于该矩阵所生成的图的色数;简单图的邻接矩阵的对偶阵是可实现的,且其容度就是简单图的色数的一个上界.

可实现布尔矩阵的容度与无向图的团覆盖数

讨论了可实现布尔矩阵的容度问题。将可实现布尔矩阵看成是无向图,我们证明了可实现布尔矩阵的容度等于其相应无向图的团覆盖数与孤立点数之和,并给出了通过计算容度来计算团覆盖数,以及通过计算团覆盖数来计算容度的算法框架。