gap-online-help 4r8p8-3 / usr / share / gap / doc / ref / chap33.txt

  
  33 Relations
  
  A  binary  relation R on a set X is a subset of X × X. A binary relation can
  also  be thought of as a (general) mapping from X to itself or as a directed
  graph where each edge represents an element of R.
  
  In  GAP,  a relation is conceptually represented as a general mapping from X
  to   itself.  The  category  IsBinaryRelation  (33.1-1)  is  a  synonym  for
  IsEndoGeneralMapping  (32.13-3).  Attributes  and properties of relations in
  GAP  are supported for relations, via considering relations as a subset of X
  × X, or as a directed graph; examples include finding the strongly connected
  components  of  a  relation,  via  StronglyConnectedComponents  (33.4-5), or
  enumerating the tuples of the relation.
  
  
  33.1 General Binary Relations
  
  This section lists general constructors of relations.
  
  33.1-1 IsBinaryRelation
  
  IsBinaryRelation( R )  property
  
  is  exactly  the  same category as (i.e. a synonym for) IsEndoGeneralMapping
  (32.13-3).
  
  33.1-2 BinaryRelationByElements
  
  BinaryRelationByElements( domain, elms )  function
  
  is  the binary relation on domain and with underlying relation consisting of
  the    tuples   collection   elms.   This   construction   is   similar   to
  GeneralMappingByElements  (32.2-1)  where  the source and range are the same
  set.
  
  
  33.1-3 IdentityBinaryRelation
  
  IdentityBinaryRelation( degree )  function
  IdentityBinaryRelation( domain )  function
  
  is  the binary relation which consists of diagonal pairs, i.e., pairs of the
  form (x,x). In the first form if a positive integer degree is given then the
  domain  is  the  set of the integers { 1, ..., degree }. In the second form,
  the objects x are from the domain domain.
  
  33.1-4 EmptyBinaryRelation
  
  EmptyBinaryRelation( degree )  function
  EmptyBinaryRelation( domain )  function
  
  is  the  relation with R empty. In the first form of the command with degree
  an  integer,  the  domain  is  the  set of points { 1, ..., degree }. In the
  second form, the domain is that given by the argument domain.
  
  
  33.2 Properties and Attributes of Binary Relations
  
  33.2-1 IsReflexiveBinaryRelation
  
  IsReflexiveBinaryRelation( R )  property
  
  returns true if the binary relation R is reflexive, and false otherwise.
  
  A binary relation R (as a set of pairs) on a set X is reflexive if for all x
  ∈ X, (x,x) ∈ R. Alternatively, R as a mapping is reflexive if for all x ∈ X,
  x is an element of the image set R(x).
  
  A  reflexive  binary  relation  is  necessarily  a total endomorphic mapping
  (tested via IsTotal (32.3-1)).
  
  33.2-2 IsSymmetricBinaryRelation
  
  IsSymmetricBinaryRelation( R )  property
  
  returns true if the binary relation R is symmetric, and false otherwise.
  
  A binary relation R (as a set of pairs) on a set X is symmetric if (x,y) ∈ R
  then (y,x) ∈ R. Alternatively, R as a mapping is symmetric if for all x ∈ X,
  the preimage set of x under R equals the image set R(x).
  
  33.2-3 IsTransitiveBinaryRelation
  
  IsTransitiveBinaryRelation( R )  property
  
  returns true if the binary relation R is transitive, and false otherwise.
  
  A  binary  relation R (as a set of pairs) on a set X is transitive if (x,y),
  (y,z)  ∈ R implies (x,z) ∈ R. Alternatively, R as a mapping is transitive if
  for  all x ∈ X, the image set R(R(x)) of the image set R(x) of x is a subset
  of R(x).
  
  33.2-4 IsAntisymmetricBinaryRelation
  
  IsAntisymmetricBinaryRelation( rel )  property
  
  returns  true  if  the  binary  relation  rel  is  antisymmetric,  and false
  otherwise.
  
  A  binary  relation  R  (as  a  set of pairs) on a set X is antisymmetric if
  (x,y),  (y,x)  ∈  R  implies  x  =  y.  Alternatively,  R  as  a  mapping is
  antisymmetric  if  for  all x ∈ X, the intersection of the preimage set of x
  under R and the image set R(x) is { x }.
  
  33.2-5 IsPreOrderBinaryRelation
  
  IsPreOrderBinaryRelation( rel )  property
  
  returns true if the binary relation rel is a preorder, and false otherwise.
  
  A preorder is a binary relation that is both reflexive and transitive.
  
  33.2-6 IsPartialOrderBinaryRelation
  
  IsPartialOrderBinaryRelation( rel )  property
  
  returns  true  if  the  binary  relation  rel  is a partial order, and false
  otherwise.
  
  A partial order is a preorder which is also antisymmetric.
  
  33.2-7 IsHasseDiagram
  
  IsHasseDiagram( rel )  property
  
  returns  true  if  the  binary  relation rel is a Hasse Diagram of a partial
  order, i.e., was computed via HasseDiagramBinaryRelation (33.4-4).
  
  33.2-8 IsEquivalenceRelation
  
  IsEquivalenceRelation( R )  property
  
  returns  true if the binary relation R is an equivalence relation, and false
  otherwise.
  
  Recall,  that  a  relation  R is an equivalence relation if it is symmetric,
  transitive, and reflexive.
  
  33.2-9 Successors
  
  Successors( R )  attribute
  
  returns  the list of images of a binary relation R. If the underlying domain
  of  the  relation is not { 1, ..., n }, for some positive integer n, then an
  error is signalled.
  
  The  returned  value  of  Successors  is a list of lists where the lists are
  ordered  as the elements according to the sorted order of the underlying set
  of  R.  Each  list  consists of the images of the element whose index is the
  same as the list with the underlying set in sorted order.
  
  The  Successors  of  a  relation is the adjacency list representation of the
  relation.
  
  33.2-10 DegreeOfBinaryRelation
  
  DegreeOfBinaryRelation( R )  attribute
  
  returns  the size of the underlying domain of the binary relation R. This is
  most natural when working with a binary relation on points.
  
  33.2-11 PartialOrderOfHasseDiagram
  
  PartialOrderOfHasseDiagram( HD )  attribute
  
  is  the  partial order associated with the Hasse Diagram HD i.e. the partial
  order generated by the reflexive and transitive closure of HD.
  
  
  33.3 Binary Relations on Points
  
  We  have  special construction methods when the underlying X of our relation
  is the set of integers { 1, ..., n }.
  
  33.3-1 BinaryRelationOnPoints
  
  BinaryRelationOnPoints( list )  function
  BinaryRelationOnPointsNC( list )  function
  
  Given  a  list of n lists, each containing elements from the set { 1, ..., n
  },  this  function  constructs  a  binary relation such that 1 is related to
  list[1],  2  to list[2] and so on. The first version checks whether the list
  supplied is valid. The the NC version skips this check.
  
  33.3-2 RandomBinaryRelationOnPoints
  
  RandomBinaryRelationOnPoints( degree )  function
  
  creates a relation on points with degree degree.
  
  
  33.3-3 AsBinaryRelationOnPoints
  
  AsBinaryRelationOnPoints( trans )  function
  AsBinaryRelationOnPoints( perm )  function
  AsBinaryRelationOnPoints( rel )  function
  
  return   the  relation  on  points  represented  by  general  relation  rel,
  transformation  trans  or  permutation  perm.  If  rel  is  already a binary
  relation on points then rel is returned.
  
  Transformations  and  permutations  are special general endomorphic mappings
  and have a natural representation as a binary relation on points.
  
  In  the last form, an isomorphic relation on points is constructed where the
  points are indices of the elements of the underlying domain in sorted order.
  
  
  33.4 Closure Operations and Other Constructors
  
  33.4-1 ReflexiveClosureBinaryRelation
  
  ReflexiveClosureBinaryRelation( R )  operation
  
  is  the  smallest  binary relation containing the binary relation R which is
  reflexive.  This  closure  inherits  the properties symmetric and transitive
  from R. E.g., if R is symmetric then its reflexive closure is also.
  
  33.4-2 SymmetricClosureBinaryRelation
  
  SymmetricClosureBinaryRelation( R )  operation
  
  is  the  smallest  binary relation containing the binary relation R which is
  symmetric.  This  closure  inherits  the properties reflexive and transitive
  from R. E.g., if R is reflexive then its symmetric closure is also.
  
  33.4-3 TransitiveClosureBinaryRelation
  
  TransitiveClosureBinaryRelation( rel )  operation
  
  is  the  smallest  binary relation containing the binary relation R which is
  transitive.  This  closure  inherits  the properties reflexive and symmetric
  from R. E.g., if R is symmetric then its transitive closure is also.
  
  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.
  
  33.4-4 HasseDiagramBinaryRelation
  
  HasseDiagramBinaryRelation( partial-order )  operation
  
  is  the smallest relation contained in the partial order partial-order whose
  reflexive and transitive closure is equal to partial-order.
  
  33.4-5 StronglyConnectedComponents
  
  StronglyConnectedComponents( R )  operation
  
  returns an equivalence relation on the vertices of the binary relation R.
  
  33.4-6 PartialOrderByOrderingFunction
  
  PartialOrderByOrderingFunction( dom, orderfunc )  function
  
  constructs  a  partial  order whose elements are from the domain dom and are
  ordered using the ordering function orderfunc. The ordering function must be
  a  binary  function returning a boolean value. If the ordering function does
  not describe a partial order then fail is returned.
  
  
  33.5 Equivalence Relations
  
  An  equivalence  relation  E  over  the  set  X  is a relation on X which is
  reflexive, symmetric, and transitive. A partition P is a set of subsets of X
  such  that  for  all  R,  S  ∈  P,  R  ∩  S is the empty set and ∪ P = X. An
  equivalence  relation  induces  a partition such that if (x,y) ∈ E then x, y
  are in the same element of P.
  
  Like  all  binary  relations  in  GAP  equivalence relations are regarded as
  general  endomorphic mappings (and the operations, properties and attributes
  of general mappings are available). However, partitions provide an efficient
  way  of representing equivalence relations. Moreover, only the non-singleton
  classes  or blocks are listed allowing for small equivalence relations to be
  represented  on  infinite  sets.  Hence  the  main  attribute of equivalence
  relations   is  EquivalenceRelationPartition  (33.6-1)  which  provides  the
  partition induced by the given equivalence.
  
  33.5-1 EquivalenceRelationByPartition
  
  EquivalenceRelationByPartition( domain, list )  function
  EquivalenceRelationByPartitionNC( domain, list )  function
  
  constructs  the  equivalence  relation over the set domain which induces the
  partition  represented  by  list.  This  representation  includes  only  the
  non-trivial blocks (or equivalent classes). list is a list of lists, each of
  these lists contain elements of domain and are pairwise mutually exclusive.
  
  The  list of lists do not need to be in any order nor do the elements in the
  blocks  (see  EquivalenceRelationPartition  (33.6-1)). a list of elements of
  domain  The  partition  list  is a list of lists, each of these is a list of
  elements  of  domain that makes up a block (or equivalent class). The domain
  is  the  domain  over  which  the relation is defined, and list is a list of
  lists,  each  of  these is a list of elements of domain which are related to
  each other. list need only contain the nontrivial blocks and singletons will
  be  ignored.  The NC version will not check to see if the lists are pairwise
  mutually exclusive or that they contain only elements of the domain.
  
  33.5-2 EquivalenceRelationByRelation
  
  EquivalenceRelationByRelation( rel )  function
  
  returns  the  smallest  equivalence  relation containing the binary relation
  rel.
  
  33.5-3 EquivalenceRelationByPairs
  
  EquivalenceRelationByPairs( D, elms )  function
  EquivalenceRelationByPairsNC( D, elms )  function
  
  return  the  smallest  equivalence  relation on the domain D such that every
  pair in elms is in the relation.
  
  In the NC form, it is not checked that elms are in the domain D.
  
  33.5-4 EquivalenceRelationByProperty
  
  EquivalenceRelationByProperty( domain, property )  function
  
  creates  an equivalence relation on domain whose only defining datum is that
  of having the property property.
  
  
  33.6 Attributes of and Operations on Equivalence Relations
  
  33.6-1 EquivalenceRelationPartition
  
  EquivalenceRelationPartition( equiv )  attribute
  
  returns a list of lists of elements of the underlying set of the equivalence
  relation equiv. The lists are precisely the nonsingleton equivalence classes
  of  the  equivalence.  This  allows  us  to  describe  small equivalences on
  infinite sets.
  
  33.6-2 GeneratorsOfEquivalenceRelationPartition
  
  GeneratorsOfEquivalenceRelationPartition( equiv )  attribute
  
  is a set of generating pairs for the equivalence relation equiv. This set is
  not  unique. The equivalence equiv is the smallest equivalence relation over
  the underlying set which contains the generating pairs.
  
  33.6-3 JoinEquivalenceRelations
  
  JoinEquivalenceRelations( equiv1, equiv2 )  operation
  MeetEquivalenceRelations( equiv1, equiv2 )  operation
  
  JoinEquivalenceRelations   returns   the   smallest   equivalence   relation
  containing both the equivalence relations equiv1 and equiv2.
  
  MeetEquivalenceRelations  returns  the  intersection  of the two equivalence
  relations equiv1 and equiv2.
  
  
  33.7 Equivalence Classes
  
  33.7-1 IsEquivalenceClass
  
  IsEquivalenceClass( obj )  Category
  
  returns true if the object obj is an equivalence class, and false otherwise.
  
  An  equivalence class is a collection of elements which are mutually related
  to  each  other  in  the  associated  equivalence  relation. Note, this is a
  special category of objects and not just a list of elements.
  
  33.7-2 EquivalenceClassRelation
  
  EquivalenceClassRelation( C )  attribute
  
  returns the equivalence relation of which C is a class.
  
  33.7-3 EquivalenceClasses
  
  EquivalenceClasses( rel )  attribute
  
  returns  a  list of all equivalence classes of the equivalence relation rel.
  Note  that  it  is  possible  for  different  methods  to  yield the list in
  different  orders,  so  that  for two equivalence relations c1 and c2 we may
  have c1 = c2 without having EquivalenceClasses( c1 ) =EquivalenceClasses( c2
  ).
  
  33.7-4 EquivalenceClassOfElement
  
  EquivalenceClassOfElement( rel, elt )  operation
  EquivalenceClassOfElementNC( rel, elt )  operation
  
  return the equivalence class of elt in the binary relation rel, where elt is
  an  element  (i.e.  a  pair) of the domain of rel. In the NC form, it is not
  checked that elt is in the domain over which rel is defined.