graph2 http://www.dse.nl/~postma/graph1.ocd 2006-06-01 experimental 2004-06-27 0 12 This CD defines symbols for handling directed and undirected graphs. Authored by Arjeh---to be merged with version of Erik Postma. automorphism_group This symbol is a unary function whose argument is an undirected graph. When applied to an undirected graph G, it represents the automorphism group of G. The resulting automorphism group is represented as a permutation group on the vertices of the graph G. The automorphism group of a path of length 2 (on three nodes) is the permutation group of order two interchanging the two end nodes. 123 12 23 13 is_homomorphism This symbol is a boolean function with three arguments. The first and arguments are graphs M, N, the third is a map f from the vertex set of M to the vertex set of N. When applied to M, N, and f, it denotes that f is a graph homomorphism from M to N. If is_homomorphism(M,N,f) then, for each pair of vertices x, y of M, we have if {x,y} is an edge of M, then {f(x), f(y)} is an edge of N. is_isomorphism This symbol is a boolean function with three arguments. The first and arguments are graphs M, N, the third is a map f from the element set of M to the element set of N. When applied to M, N, and f, it denotes that f is a graph isomorphism from M to N. This means that f is a homomorphism from M to N, that f is bijective, and that its inverse is a homomorphism from N to M. is_endomorphism This symbol is a boolean function with two arguments. The first argument is a graph M, the second is a map f from the element set of M to the element set of M. When applied to M and f, it denotes that f is a graph endomorphism from M to M. If is_endomorphism(M,f) then is_homomorphism(M,M,f) is_automorphism This symbol is a boolean function with two arguments. The first is a graph M, the second is a map f from the element set of M to the element set of M. When applied to M and f, it denotes a graph automorphism f of M. If is_automorphism(M,f) then is_isomorphism(M,M,f) isomorphic This symbol is a Boolean function with n arguments, n at least 2, which are graphs. When applied to M_1, ..., M_n, it denotes the fact that there is an isomorphism from each M_i to each M_j.