A morphism of graphs f:G→ H (Also known as homomorphisms) is a function from the vertex set of one graph to the vertex set of another, f:V(G)→ V(H), such that some properties (adjacency for instance) are preserved. In YAGS such a function is represented by a list F=[f(1),f(2),...f(n)]. For instance, the list F=[2,3,4,3] represents a morphism that maps vertex 1 of G onto vertex 2 of H and also maps 2 to 3, 3 to 4 and 4 to 3. In this example, F implicitly says that G has exactly 4 vertices and that H has at least 4 vertices.
YAGS has a very rich and flexible set of operations to deal with graph morphisms which we describe in the next sections. All these operations report progress at InfoLevel 3 (see B.24-3 and Section 6.4).
Here we describe only the most used ones. The operations dealing with morphisms are organized in triplets, like the following one:
FullMonoMorphism(G,H) |
FullMonoMorphisms(G,H) |
NextFullMonoMorphism(G,H,F) |
All three of these operations refer to the same kind of morphisms, f, which are Morphisms (the image of an edge is an edge), Mono (vertex-injective) and Full (i.e. f(x)f(y) ∈ E(H) ⇒ ∃ x'y'∈ E(G) with f(x'y')=f(x)f(y)). The first two operations simply return either one or all the morphisms between two given graphs:
gap> p3:=PathGraph(3);c4:=CycleGraph(4); Graph( Category := SimpleGraphs, Order := 3, Size := 2, Adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ] ) Graph( Category := SimpleGraphs, Order := 4, Size := 4, Adjacencies := [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ] ) gap> FullMonoMorphism(p3,c4); [ 1, 2, 3 ] gap> FullMonoMorphisms(p3,c4); [ [ 1, 2, 3 ], [ 1, 4, 3 ], [ 2, 1, 4 ], [ 2, 3, 4 ], [ 3, 2, 1 ], [ 3, 4, 1 ], [ 4, 1, 2 ], [ 4, 3, 2 ] ]
The third operation, NextFullMonoMorphism receives as parameters, besides the two given graphs, a partial morphism F. As you may have guessed a partial morphism is any prefix of a morphism, so in case [ 1, 2, 3 ] is a morphism, it follows that [ 1, 2, 3 ], [ 1, 2 ], [ 1 ] and [ ] are partial morphisms.
Our operation NextFullMonoMorphism then, returns the next morphism, then one following the given partial morphism F in lexicographic order. It also stores this next morphism in the variable F so we can iteratively call NextFullMonoMorphism to obtain all morphisms one by one:
gap> p3:=PathGraph(3);;c4:=CycleGraph(4);; gap> f:=[3,4];;NextFullMonoMorphism(p3,c4,f); [ 3, 4, 1 ] gap> f; [ 3, 4, 1 ] gap> NextFullMonoMorphism(p3,c4,f); [ 4, 1, 2 ] gap> f; [ 4, 1, 2 ] gap> NextFullMonoMorphism(p3,c4,f); [ 4, 3, 2 ] gap> NextFullMonoMorphism(p3,c4,f); fail gap> f; [ fail ] gap> NextFullMonoMorphism(p3,c4,f); [ 1, 2, 3 ] gap> NextFullMonoMorphism(p3,c4,f); [ 1, 4, 3 ] gap> f:=[]; [ ] gap> NextFullMonoMorphism(p3,c4,f); [ 1, 2, 3 ] gap> NextFullMonoMorphism(p3,c4,f); [ 1, 4, 3 ]
Note that f:=[ ] and f:=[ fail ] are always considered partial morphisms; these are useful to compute the first morphism and to report when there are no more morphisms to find. Please note that NextFullMonoMorphism will not check whether the given partial morphism is actually a partial morphism. This is done this way for efficiency, since actually both FullMonoMorphism and FullMonoMorphisms are implemented in terms of NextFullMonoMorphism.
NextFullMonoMorphism is useful when the set of all morphisms from G to H is too big: This way, given enough time, we can process all of the morphisms one by one even if the set of all morphisms does not fit in memory.
The reader, may have noticed that these operations are precisely what is needed to implement IsInducedSubgraph:
gap> IsInducedSubgraph:=function(h,g) > return FullMonoMorphism(h,g)<>fail; end; function( h, g ) ... end gap> IsInducedSubgraph(PathGraph(3),CycleGraph(4)); true gap> IsInducedSubgraph(PathGraph(4),CycleGraph(4)); false
If your morphisms of choice are not Full nor Mono, you can simply use:
Morphism(G,H) |
Morphisms(G,H) |
NextMorphism(G,H,F) |
just like we did with the previous triplet of operations.
gap> Morphism(PathGraph(3),CycleGraph(4)); [ 1, 2, 1 ] gap> Morphisms(PathGraph(3),CycleGraph(4)); [ [ 1, 2, 1 ], [ 1, 2, 3 ], [ 1, 4, 1 ], [ 1, 4, 3 ], [ 2, 1, 2 ], [ 2, 1, 4 ], [ 2, 3, 2 ], [ 2, 3, 4 ], [ 3, 2, 1 ], [ 3, 2, 3 ], [ 3, 4, 1 ], [ 3, 4, 3 ], [ 4, 1, 2 ], [ 4, 1, 4 ], [ 4, 3, 2 ], [ 4, 3, 4 ] ] gap> f:=[4,3];NextMorphism(PathGraph(3),CycleGraph(4),f); [ 4, 3 ] [ 4, 3, 2 ] gap> NextMorphism(PathGraph(3),CycleGraph(4),f); [ 4, 3, 4 ] gap> NextMorphism(PathGraph(3),CycleGraph(4),f); fail gap> NextMorphism(PathGraph(3),CycleGraph(4),f); [ 1, 2, 1 ]
Also, this particular type of morphisms is what we need to implement IsKColorable:
gap> IsKColorable:=function(g,k) > return Morphism(g,CompleteGraph(k))<>fail; end; function( g, k ) ... end gap> IsKColorable(CycleGraph(6),2); true gap> IsKColorable(CycleGraph(5),2); false gap> IsKColorable(CycleGraph(5),3); true
The full list of predefined types of morphisms that YAGS knows about is explained in the next section.
Following the same organization of operations in triplets as explained in the previous section, we present now the full list of YAGS's operations for predefined types of morphisms. The operations that start with a hash mark (#) are not yet implemented, but they are there as a place holders for a future implementation.
NextMetricMorphism(G,H,F) NextEpiMetricMorphism(G,H,F) NextMonoMorphism(G,H,F) NextFullMonoMorphism(G,H,F) NextBiMorphism(G,H,F) NextFullBiMorphism(G,H,F) NextCompleteEpiWeakMorphism(G,H,F) NextCompleteEpiMorphism(G,H,F) NextCompleteWeakMorphism(G,H,F) NextCompleteMorphism(G,H,F) #NextFullEpiWeakMorphism(G,H,F) #NextFullEpiMorphism(G,H,F) #NextFullWeakMorphism(G,H,F) #NextFullMorphism(G,H,F) NextEpiWeakMorphism(G,H,F) NextEpiMorphism(G,H,F) NextWeakMorphism(G,H,F) NextMorphism(G,H,F) MetricMorphism(G,H) EpiMetricMorphism(G,H) MonoMorphism(G,H) FullMonoMorphism(G,H) BiMorphism(G,H) FullBiMorphism(G,H) CompleteEpiWeakMorphism(G,H) CompleteEpiMorphism(G,H) CompleteWeakMorphism(G,H) CompleteMorphism(G,H) #FullEpiWeakMorphism(G,H) #FullEpiMorphism(G,H) #FullWeakMorphism(G,H) #FullMorphism(G,H) EpiWeakMorphism(G,H) EpiMorphism(G,H) WeakMorphism(G,H) Morphism(G,H) MetricMorphisms(G,H) EpiMetricMorphisms(G,H) MonoMorphisms(G,H) FullMonoMorphisms(G,H) BiMorphisms(G,H) FullBiMorphisms(G,H) CompleteEpiWeakMorphisms(G,H) CompleteEpiMorphisms(G,H) CompleteWeakMorphisms(G,H) CompleteMorphisms(G,H) #FullEpiWeakMorphisms(G,H) #FullEpiMorphisms(G,H) #FullWeakMorphisms(G,H) #FullMorphisms(G,H) EpiWeakMorphisms(G,H) EpiMorphisms(G,H) WeakMorphisms(G,H) Morphisms(G,H)
Here, several name fragments are used in a uniform way:
Morphism: The images of adjacent vertices are adjacent (except with prefix Weak).
Weak: Weakens the notion of morphism so that it is allowed that adjacent vertices go to equal ones. That is, a WeakMorphism is one where the images of adjacent-or-equal vertices are also adjacent-or-equal.
Epi: The morphism is vertex-surjective.
Mono: The morphism is vertex-injective.
Bi: The morphism is vertex-bijective.
Full: f(x)f(y) ∈ E(H) ⇒ ∃ x'y'∈ E(G) with f(x'y')=f(x)f(y).
Complete: Whenever a pair of vertices x, y are mapped onto an edge of H, the pair [x, y] is also an edge (of G).
Metric: The image of any pair of vertices are at the same distance from each other as the original pair of vertices.
All meaningful combinations of these name fragments are present in the full list of operations for predefined types of morphisms. But note that some combinations are, by mathematical reasons, necessarily synonyms like FullBiMorphism = CompleteBiMorphism = MetricBiMorphism; in such cases, only one of those names is selected for use in YAGS. Note also that a FullBiMorphism is most commonly known as an isomorphism.
Indeed, YAGS knows about FullBiMorphisms and also about IsoMorphisms: the former is implemented together with all the other operations listed in this section, using the general schema explained in the next section, while the latter is implemented with different, more efficient, ad-hoc methods. IsoMorphism is faster than FullBiMorphism, but FullBiMorphism is part of a bigger, more flexible schema.
All the morphism operations listed in the previous section are implemented in a uniform, semi-automatic way by means of the following triplet of operations, which are explained in their indicated sections of the manual:
In short, the relation of this triplet and the previous ones is best explained by a few examples:
| This operation: | Is the same as: |
BiMorphism(G,H) |
PropertyMorphism(G,H,[CHK_MONO,CHK_EPI,CHK_MORPH]) |
MetricMorphism(G,H) |
PropertyMorphism(G,H,[CHK_METRIC,CHK_MORPH]) |
CompleteWeakMorphisms(G,H) |
PropertyMorphisms(G,H,[CHK_CMPLT,CHK_WEAK]) |
NextEpiMorphism(G,H,F) |
NextPropertyMorphism(G,H,F,[CHK_EPI,CHK_MORPH]) |
In the previous table, there are several predefined property-checking functions: CHK_METRIC, CHK_CMPLT, CHK_MONO, CHK_EPI, CHK_WEAK and CHK_MORPH. These are functions that receive, two graphs (G and H) and a partial morphism (F) as parameters and they return true whenever F is a valid (feasible) partial morphism from G to H satisfying the required property (i.e. metric, complete, mono, etc.); they all return false otherwise.
gap> CHK_MORPH; function( g1, g2, morph ) ... end gap> Print(CHK_MONO,"\n"); function ( g1, g2, morph ) local x, y; x := Length( morph ); y := morph[x]; if y in morph{[ 1 .. x - 1 ]} then return false; fi; return true; end gap> Print(CHK_EPI,"\n"); function ( g1, g2, morph ) return Order( g2 ) - Length( Set( morph ) ) <= Order( g1 ) - Length( morph ); end
Note that CHK_MONO assumes that only the last element in the partial morphism needs to be verified for the sought property. This is correct in general since what NextPropertyMorphism does is to continually try to construct a new (longer) partial morphism from an existing one, so the sought property was already checked in all prefixes of the current partial morphism (The precise technique used by NextPropertyMorphism is known as backtracking, and it is described in the next chapter).
It is usually required to include at least one of CHK_WEAK or CHK_MORPH in the list of properties to check used by the PropertyMorphism triplet, since otherwise, no adjacency-preserving function is ever verified and then the resulting maps are more properly named "functions" rather than "morphisms":
gap> k2:=CompleteGraph(2);;I2:=DiscreteGraph(2);; gap> PropertyMorphisms(k2,I2,[]); [ [ 1, 1 ], [ 1, 2 ], [ 2, 1 ], [ 2, 2 ] ]
There is nothing special about YAGS predefined property-checking functions and the user may write new ones. For example, if we would like to create a new type of weak morphism restricting the mapping so that the image of a vertex always has a degree greater than or equal to that of the vertex, then we could write:
gap> checkdegree:=function(G,H,f) > local x,fx; > x:=Length(f);fx:=f[x]; > return VertexDegree(G,x)<=VertexDegree(H,fx); > end; function( G, H, f ) ... end gap> NextSpecialMorphism:=function(G,H,F) > return NextPropertyMorphism(G,H,F,[CHK_WEAK,checkdegree]); > end; function( G, H, F ) ... end gap> c4:=CycleGraph(4);;p4:=PathGraph(4);;F:=[];; gap> NextSpecialMorphism(c4,p4,F); [ 2, 2, 2, 2 ] gap> NextSpecialMorphism(c4,p4,F); [ 2, 2, 2, 3 ] gap> NextSpecialMorphism(c4,p4,F); [ 2, 2, 3, 2 ] gap> NextSpecialMorphism(c4,p4,F); [ 2, 2, 3, 3 ] gap> SpecialMorphisms:=function(G,H) > return PropertyMorphisms(G,H,[CHK_WEAK,checkdegree]); > end; function( G, H ) ... end gap> SpecialMorphisms(c4,p4); [ [ 2, 2, 2, 2 ], [ 2, 2, 2, 3 ], [ 2, 2, 3, 2 ], [ 2, 2, 3, 3 ], [ 2, 3, 2, 2 ], [ 2, 3, 2, 3 ], [ 2, 3, 3, 2 ], [ 2, 3, 3, 3 ], [ 3, 2, 2, 2 ], [ 3, 2, 2, 3 ], [ 3, 2, 3, 2 ], [ 3, 2, 3, 3 ], [ 3, 3, 2, 2 ], [ 3, 3, 2, 3 ], [ 3, 3, 3, 2 ], [ 3, 3, 3, 3 ] ]
Note that the property-checking functions must receive three parameters (namely, two graphs G,H and a partial morphism F) and it is OK (and better for efficiency), if the function assumes that all prefixes of the current partial morphism, already passed the test.
Since all morphism-related operations in YAGS use Backtrack (B.2-1), they all report progress at InfoLevel 3 (see B.24-3 and Section 6.4). This is useful to have an idea of how much additional time is needed for the current computation to finish and it is also useful for debugging user-defined property-checking functions.
generated by GAPDoc2HTML