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.

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
      <OMA><OMS cd="relation1" name="eq"/>
           <OMA><OMS cd="graph2" name="automorphism_group"/>
                <OMA><OMS cd="graph1" name="graph"/>
                     <OMA><OMS cd="set1" name="set"/>
                          <OMI>1</OMI><OMI>2</OMI><OMI>3</OMI>
                     </OMA>
                     <OMA><OMS cd="set1" name="set"/>
                          <OMA><OMS cd="set1" name="set"/>
                               <OMI>1</OMI><OMI>2</OMI>
                          </OMA>
                          <OMA><OMS cd="set1" name="set"/>
                               <OMI>2</OMI><OMI>3</OMI>
                          </OMA>
                     </OMA>
                </OMA>
           </OMA>
           <OMA><OMS cd="permgp1" name="group"/>
                <OMS cd="permutation1" name="right_compose"/>
                <OMA><OMS cd="permutation1" name="permutation"/>
                     <OMA><OMS cd="permutation1" name="cycle"/>
                          <OMI>1</OMI><OMI>3</OMI>
                     </OMA>
                </OMA>
           </OMA>
       </OMA>
    </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <apply><csymbol cd="relation1">eq</csymbol>
  <apply><csymbol cd="graph2">automorphism_group</csymbol>
   <apply><csymbol cd="graph1">graph</csymbol>
    <apply><csymbol cd="set1">set</csymbol>
     <cn type="integer">1</cn>
     <cn type="integer">2</cn>
     <cn type="integer">3</cn>
    </apply>
    <apply><csymbol cd="set1">set</csymbol>
     <apply><csymbol cd="set1">set</csymbol>
      <cn type="integer">1</cn>
      <cn type="integer">2</cn>
     </apply>
     <apply><csymbol cd="set1">set</csymbol>
      <cn type="integer">2</cn>
      <cn type="integer">3</cn>
     </apply>
    </apply>
   </apply>
  </apply>
  <apply><csymbol cd="permgp1">group</csymbol>
   <csymbol cd="permutation1">right_compose</csymbol>
   <apply><csymbol cd="permutation1">permutation</csymbol>
    <apply><csymbol cd="permutation1">cycle</csymbol>
     <cn type="integer">1</cn>
     <cn type="integer">3</cn>
    </apply>
   </apply>
  </apply>
 </apply>
</math>

Prefix

eq (automorphism_group (graph (set (1, 2, 3) , set (set (1, 2) , set (2, 3) ) ) ) , group (right_compose, permutation (cycle (1, 3) ) ) )

Popcorn

graph2.automorphism_group(graph1.graph({1 , 2 , 3}, {{1 , 2} , {2 , 3}})) = permgp1.group(permutation1.right_compose, permutation1.permutation(permutation1.cycle(1, 3)))

Rendered Presentation MathML

$$\mathrm{automorphism\_group}\left(\mathrm{graph}(\{1,2,3\},\{\{1,2\},\{2,3\}\})\right)=\mathrm{group}(\mathrm{right\_compose},\mathrm{permutation}\left(\mathrm{cycle}(1,3)\right))$$

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):

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
  <OMA><OMS cd="logic1" name="implies"/>
       <OMA><OMS cd="graph2" name="is_homomorphism"/>
            <OMV name="M"/> <OMV name="N"/>  <OMV name="f"/>
       </OMA>
       <OMBIND><OMS cd="quant1" name="forall"/>
            <OMBVAR><OMV name="x"/><OMV name="y"/>  </OMBVAR>
            <OMA><OMS cd="logic1" name="implies"/>
                 <OMA><OMS cd="logic1" name="and"/>
                      <OMA><OMS cd="set1" name="in"/>
                           <OMV name="x"/>
                           <OMA><OMS cd="graph1" name="vertexset"/>
                                <OMV name="M"/>
                           </OMA>
                      </OMA>
	              <OMA><OMS cd="set1" name="in"/>
                           <OMV name="y"/>
                           <OMA><OMS cd="graph1" name="vertexset"/>
                                <OMV name="M"/>
                           </OMA>
                      </OMA>
	              <OMA><OMS cd="set1" name="in"/>
                           <OMA><OMS cd="set1" name="set"/>
                                <OMV name="x"/><OMV name="y"/>
                           </OMA>
                           <OMA><OMS cd="graph1" name="edgeset"/>
                                <OMV name="M"/>
                           </OMA>
                      </OMA>
                 </OMA>
                 <OMA><OMS cd="set1" name="in"/>
                      <OMA><OMS cd="set1" name="set"/>
                           <OMA><OMV name="f"/>
                                <OMV name="x"/> 
                           </OMA>
                           <OMA><OMV name="f"/>
                                <OMV name="y"/> 
                           </OMA>
                      </OMA>
                      <OMA><OMS cd="graph1" name="edgeset"/>
                           <OMV name="N"/>
                      </OMA>
                 </OMA>
             </OMA>
        </OMBIND>
   </OMA>
</OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <apply><csymbol cd="logic1">implies</csymbol>
  <apply><csymbol cd="graph2">is_homomorphism</csymbol><ci>M</ci><ci>N</ci><ci>f</ci></apply>
  <bind><csymbol cd="quant1">forall</csymbol>
   <bvar><ci>x</ci></bvar>
   <bvar><ci>y</ci></bvar>
   <apply><csymbol cd="logic1">implies</csymbol>
    <apply><csymbol cd="logic1">and</csymbol>
     <apply><csymbol cd="set1">in</csymbol>
      <ci>x</ci>
      <apply><csymbol cd="graph1">vertexset</csymbol><ci>M</ci></apply>
     </apply>
     <apply><csymbol cd="set1">in</csymbol>
      <ci>y</ci>
      <apply><csymbol cd="graph1">vertexset</csymbol><ci>M</ci></apply>
     </apply>
     <apply><csymbol cd="set1">in</csymbol>
      <apply><csymbol cd="set1">set</csymbol><ci>x</ci><ci>y</ci></apply>
      <apply><csymbol cd="graph1">edgeset</csymbol><ci>M</ci></apply>
     </apply>
    </apply>
    <apply><csymbol cd="set1">in</csymbol>
     <apply><csymbol cd="set1">set</csymbol>
      <apply><ci>f</ci><ci>x</ci></apply>
      <apply><ci>f</ci><ci>y</ci></apply>
     </apply>
     <apply><csymbol cd="graph1">edgeset</csymbol><ci>N</ci></apply>
    </apply>
   </apply>
  </bind>
 </apply>
</math>

Prefix

implies (is_homomorphism ( M, N, f) , forall [ x y ] . (implies (and (in ( x, vertexset ( M) ) , in ( y, vertexset ( M) ) , in (set ( x, y) , edgeset ( M) ) ) , in (set ( f ( x) , f ( y) ) , edgeset ( N) ) ) ) )

Popcorn

graph2.is_homomorphism($M, $N, $f) ==> quant1.forall[$x, $y -> set1.in($x, graph1.vertexset($M)) and set1.in($y, graph1.vertexset($M)) and set1.in({$x , $y}, graph1.edgeset($M)) ==> set1.in({$f($x) , $f($y)}, graph1.edgeset($N))]

Rendered Presentation MathML

$$\mathrm{is\_homomorphism}(M,N,f)\Rightarrow \forall \hspace{0.17em}x,y.x\in \mathrm{vertexset}\left(M\right)\wedge y\in \mathrm{vertexset}\left(M\right)\wedge \{x,y\}\in \mathrm{edgeset}\left(M\right)\Rightarrow \{f\left(x\right),f\left(y\right)\}\in \mathrm{edgeset}\left(N\right)$$

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:

OpenMath XML (source)

    <OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
     <OMA><OMS cd="graph2" name="is_isomorphism"/>
          <OMV name="M"/>  <OMV name="N"/> <OMV name="f"/>
     </OMA>
    </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <apply><csymbol cd="graph2">is_isomorphism</csymbol><ci>M</ci><ci>N</ci><ci>f</ci></apply>
</math>

Prefix

is_isomorphism ( M, N, f)

Popcorn

graph2.is_isomorphism($M, $N, $f)

Rendered Presentation MathML

$$\mathrm{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):

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
  <OMA><OMS cd="logic1" name="implies"/>
       <OMA><OMS cd="graph2" name="is_endomorphism"/>
            <OMV name="M"/>  <OMV name="f"/>
       </OMA>
       <OMA><OMS cd="graph2" name="is_homomorphism"/>
            <OMV name="M"/> <OMV name="M"/>  <OMV name="f"/>
       </OMA>
  </OMA>
</OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <apply><csymbol cd="logic1">implies</csymbol>
  <apply><csymbol cd="graph2">is_endomorphism</csymbol><ci>M</ci><ci>f</ci></apply>
  <apply><csymbol cd="graph2">is_homomorphism</csymbol><ci>M</ci><ci>M</ci><ci>f</ci></apply>
 </apply>
</math>

Prefix

implies (is_endomorphism ( M, f) , is_homomorphism ( M, M, f) )

Popcorn

graph2.is_endomorphism($M, $f) ==> graph2.is_homomorphism($M, $M, $f)

Rendered Presentation MathML

$$\mathrm{is\_endomorphism}(M,f)\Rightarrow \mathrm{is\_homomorphism}(M,M,f)$$

Example:

OpenMath XML (source)

    <OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
     <OMA><OMS cd="graph2" name="is_endomorphism"/>
          <OMV name="M"/> <OMV name="f"/>
     </OMA>
    </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML"><apply><csymbol cd="graph2">is_endomorphism</csymbol><ci>M</ci><ci>f</ci></apply></math>

Prefix

is_endomorphism ( M, f)

Popcorn

graph2.is_endomorphism($M, $f)

Rendered Presentation MathML

$$\mathrm{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):

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
  <OMA><OMS cd="logic1" name="implies"/>
       <OMA><OMS cd="graph2" name="is_automorphism"/>
            <OMV name="M"/>  <OMV name="f"/>
       </OMA>
       <OMA><OMS cd="graph2" name="is_isomorphism"/>
            <OMV name="M"/> <OMV name="M"/>  <OMV name="f"/>
       </OMA>
  </OMA>
</OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <apply><csymbol cd="logic1">implies</csymbol>
  <apply><csymbol cd="graph2">is_automorphism</csymbol><ci>M</ci><ci>f</ci></apply>
  <apply><csymbol cd="graph2">is_isomorphism</csymbol><ci>M</ci><ci>M</ci><ci>f</ci></apply>
 </apply>
</math>

Prefix

implies (is_automorphism ( M, f) , is_isomorphism ( M, M, f) )

Popcorn

graph2.is_automorphism($M, $f) ==> graph2.is_isomorphism($M, $M, $f)

Rendered Presentation MathML

$$\mathrm{is\_automorphism}(M,f)\Rightarrow \mathrm{is\_isomorphism}(M,M,f)$$

Example:

OpenMath XML (source)

<OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
     <OMA><OMS cd="graph2" name="is_automorphism"/>
          <OMV name="M"/> <OMV name="f"/>
     </OMA>
</OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML"><apply><csymbol cd="graph2">is_automorphism</csymbol><ci>M</ci><ci>f</ci></apply></math>

Prefix

is_automorphism ( M, f)

Popcorn

graph2.is_automorphism($M, $f)

Rendered Presentation MathML

$$\mathrm{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:

OpenMath XML (source)

    <OMOBJ xmlns="http://www.openmath.org/OpenMath" version="2.0">
     <OMA><OMS cd="graph2" name="isomorphic"/>
          <OMV name="M"/>  <OMV name="N"/> 
     </OMA>
    </OMOBJ>

Strict Content MathML

<math xmlns="http://www.w3.org/1998/Math/MathML"><apply><csymbol cd="graph2">isomorphic</csymbol><ci>M</ci><ci>N</ci></apply></math>

Prefix

isomorphic ( M, N)

Popcorn

graph2.isomorphic($M, $N)

Rendered Presentation MathML

$$\mathrm{isomorphic}(M,N)$$

Signatures:

sts

---

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