OpenMath Content Dictionary: graph2

Canonical URL:
http://www.dse.nl/~postma/graph1.ocd
CD Base:
http://www.openmath.org/cd
CD File:
graph2.ocd
CD as XML Encoded OpenMath:
graph2.omcd
Defines:
automorphism_group, is_automorphism, is_endomorphism, is_homomorphism, is_isomorphism, isomorphic
Date:
2004-06-27
Version:
0 (Revision 12)
Review Date:
2006-06-01
Status:
experimental

This CD defines symbols for handling directed and undirected graphs. Authored by Arjeh---to be merged with version of Erik Postma.


automorphism_group

Description:

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.

Example:
The automorphism group of a path of length 2 (on three nodes) is the permutation group of order two interchanging the two end nodes.
automorphism_group ( graph ( { 1 , 2 , 3 } , { { 1 , 2 } , { 2 , 3 } } ) ) = group ( right_compose , permutation ( cycle ( 1 , 3 ) ) )
Signatures:
sts


[Next: is_homomorphism] [Last: isomorphic] [Top]

is_homomorphism

Description:

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.

Commented Mathematical property (CMP):
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.
Formal Mathematical property (FMP):
is_homomorphism ( M , N , f ) x , y . x vertexset ( M ) y vertexset ( M ) { x , y } edgeset ( M ) { f ( x ) , f ( y ) } edgeset ( N )
Signatures:
sts


[Next: is_isomorphism] [Previous: automorphism_group] [Top]

is_isomorphism

Description:

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.

Example:
is_isomorphism ( M , N , f )
Signatures:
sts


[Next: is_endomorphism] [Previous: is_homomorphism] [Top]

is_endomorphism

Description:

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.

Commented Mathematical property (CMP):
If is_endomorphism(M,f) then is_homomorphism(M,M,f)
Formal Mathematical property (FMP):
is_endomorphism ( M , f ) is_homomorphism ( M , M , f )
Example:
is_endomorphism ( M , f )
Signatures:
sts


[Next: is_automorphism] [Previous: is_isomorphism] [Top]

is_automorphism

Description:

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.

Commented Mathematical property (CMP):
If is_automorphism(M,f) then is_isomorphism(M,M,f)
Formal Mathematical property (FMP):
is_automorphism ( M , f ) is_isomorphism ( M , M , f )
Example:
is_automorphism ( M , f )
Signatures:
sts


[Next: isomorphic] [Previous: is_endomorphism] [Top]

isomorphic

Description:

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.

Example:
isomorphic ( M , N )
Signatures:
sts


[First: automorphism_group] [Previous: is_automorphism] [Top]