OpenMath Content Dictionary: graph1

Canonical URL:
http://www.dse.nl/~postma/graph1.ocd
CD Base:
http://www.openmath.org/cd
CD File:
graph1.ocd
CD as XML Encoded OpenMath:
graph1.omcd
Defines:
arrowset, digraph, edgeset, graph, source, target, vertexset
Date:
2004-06-01
Version:
0 (Revision 13)
Review Date:
2006-06-01
Status:
experimental

This CD defines symbols for handling directed and undirected graphs. Authored by Hans Cuypers and Erik Postma. This version is edited by amc; bugfix JHD after Robbins.


graph

Description:

This symbol represents an undirected graph. It takes two arguments: the vertex set of the graph and the edge set. The vertices can be arbitrary OpenMath objects. Each edge should be a set consisting of two vertices.

Example:
A path of length 2.
graph ( { 1 , 2 , 3 } , { { 1 , 2 } , { 2 , 3 } } )
Signatures:
sts


[Next: vertexset] [Last: target] [Top]

vertexset

Description:

This symbol represents the vertex set of a (directed or undirected) graph. It takes one argument, the graph.

Example:
If Gamma is a graph, the following function tests whether its argument v is a vertex of Gamma.
λ v . v vertexset ( Γ )
Signatures:
sts


[Next: edgeset] [Previous: graph] [Top]

edgeset

Description:

This symbol represents the set of edges of an undirected graph. It takes one argument, the undirected graph.

Example:
Given a graph Gamma and two of its vertices v and w, this predicate asserts that they are adjacent.
{ v , w } edgeset ( Γ )
Commented Mathematical property (CMP):
Every edge in an undirected graph Gamma is a subset of the vertex set of size two.
Formal Mathematical property (FMP):
e , Γ . e vertexset ( Γ ) e vertexset ( Γ ) size ( e ) = 2
Signatures:
sts


[Next: digraph] [Previous: vertexset] [Top]

digraph

Description:

This symbol refers to a digraph. It has two arguments. The first is the set of vertices, the second is the set of arrows. Arrows are represented by lists of length two, where a list represents the arrow from the first element to the second.

Example:
The two-sided infinite directed path.
digraph ( Z , { ( x , x + 1 ) | x Z } )
Signatures:
sts


[Next: arrowset] [Previous: edgeset] [Top]

arrowset

Description:

This symbol represents the set of arrows of a directed graph. It takes one argument, the directed graph.

Example:
The arrow set of the loop consists of one loop.
arrowset ( digraph ( { 1 } , { ( 1 , 1 ) } ) ) = { ( 1 , 1 ) }
Signatures:
sts


[Next: source] [Previous: digraph] [Top]

source

Description:

Given an arrow, this symbol refers to the vertex where the arrow starts. It takes one argument, the arrow.

Example:
The arrow [a, b] starts at a.
source ( ( a , b ) ) = a
Signatures:
sts


[Next: target] [Previous: arrowset] [Top]

target

Description:

Given an arrow, this symbol refers to the vertex the arrow points to. It takes one argument, the arrow.

Example:
The arrow [a, b] points to b.
target ( ( a , b ) ) = b
Signatures:
sts


[First: graph] [Previous: source] [Top]