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