OKlibrary  0.2.1.6
Generators.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 24.11.2007 (Swansea) */
00002 /* Copyright 2007, 2008, 2009, 2010 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007
00022 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")\$
00023 oklib_include("OKlib/ComputerAlgebra/Combinatorics/Lisp/Enumeration/Subsets.mac")\$
00024
00025 /* *******************
00026    * Complete graphs *
00027    *******************
00028 */
00029
00030 /* The complete graph for vertex set V: */
00031 complete_g(V) := [V, powerset(V,2)]\$
00032 complete_stdg(n) := complete_g(setn(n))\$
00033
00034
00035 /* ********************
00036    * Paths and cycles *
00037    ********************
00038 */
00039
00040 /* The (standardised, ordered) path graph with n vertices: */
00041 /* Prerequisite: n >= 1: */
00042 pathgraph_og(n) := [create_list(i,i,1,n), create_list({i,i+1},i,1,n-1)]\$
00043 pathgraph_g(n) := og2g(pathgraph_og(n))\$
00044 /* The (standardised, ordered) cycle graph with loops with n vertices: */
00045 /* Prerequisite: n <> 0, 2: */
00046 cyclegraph_ogl(n) := [create_list(i,i,1,n),endcons({n,1},
00047   create_list({i,i+1},i,1,n-1))]\$
00048 cyclegraph_gl(n) := ogl2gl(cyclegraph_ogl(n))\$
00049 /* Remark: cyclegraph_ogl is irreflexiv iff n >= 3. */
00050 /* Now allowing also the case n = 2: */
00051 /* Prerequisite: n >= 1: */
00052 cyclegraph_ogg(n) := [create_list(i,i,1,n), create_list(i,i,1,n),
00053   buildq([n],lambda([e],if e=n then {n,1} else {e,e+1}))]\$
00054 cyclegraph_gg(n) := ogg2gg(cyclegraph_ogg(n))\$
00055
00056
00057 /* **********
00058    * Dipoles *
00059    **********
00060 */
00061
00062 /* The (standardised) general graph with two vertices and n parallel edges
00063    between them: */
00064 dipole_ogg(n) := [[1,2], create_list(i,i,1,n), lambda([e],{1,2})]\$
00065 dipole_gg(n) := ogg2gg(dipole_ogg(n))\$
00066
00067 /* With directed edges, directed from 1 to 2: */
00068 dipole_ogdg(n) := [[1,2], create_list(i,i,1,n), lambda([e],[1,2])]\$
00069 dipole_gdg(n) := ogdg2gdg(dipole_ogdg(n))\$
00070
00071 /* ************
00072    * Bouquets *
00073    ************
00074 */
00075
00076 /* The (standardised) general graph with one vertex and n edges: */
00077 bouquet_ogg(n) := [[1], create_list(i,i,1,n), lambda([e],{1})]\$
00078 bouquet_gg(n) := ogg2gg(bouquet_ogg(n))\$
00079
00080
00081 /* *****************
00082    * Kneser graphs *
00083    *****************
00084 */
00085
00086 /* Kneser-graphs: Vertices are the m-element subsets of {1,..,n}, joined by an
00087    edge if disjoint.
00088    Prerequisites: n >= m >= 1.
00089 */
00090 kneser_g(n,m) := block([sn : setn(n)],
00091  [powerset(sn, m),
00092     map(setify,
00093       lunion(
00094         create_list(cartesian_product({A}, powerset(setdifference(sn, A), m)),
00095                  A, listify(powerset(sn, m)))))])\$
00096 /* A generalisation is kneser_g_hyp(G), namely
00097    kneser_g(n,m) = kneser_g_hyp(complete_stdhg(n,m)).
00098 */
00099
00100
00101
```