31.1 General Binary Relations

  • IsBinaryRelation( R ) C

    IsBinaryRelation(R) is true precisely when IsEndoGeneralMapping(R) is true.

  • IsSymmetricBinaryRelation( rel ) P
  • IsTransitiveBinaryRelation( rel ) P
  • IsReflexiveBinaryRelation( rel ) P

    Properties of binary relations. Note that a reflexive binary relation is necessarily total.

  • ReflexiveClosureBinaryRelation( Relation ) O
  • SymmetricClosureBinaryRelation( Relation ) O
  • TransitiveClosureBinaryRelation( Relation ) O

    Closure operations for binary relations. TransitiveClosureBinaryRelation is a modified version of the Floyd-Warshall method of solving the all-pairs shortest-paths problem on a directed graph. Its asymptotic runtime is O(n^3) where n is the size of the vertex set. It only assumes there is an arbitrary (but fixed) ordering of the vertex set.

    [Top] [Up] [Next] [Index]

    GAP 4 manual
    February 2000