OKlibrary  0.2.1.6
Representations.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 21.7.2008 (Swansea) */
00002 /* Copyright 2008 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/Graphs/Lisp/Statistics.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00024 
00025 
00026 /* *****************
00027    * Pruefer Codes *
00028    *****************
00029 */
00030 
00031 /* For a given vertex set V of size n >= 1, the "Pruefer code" establishes a
00032    bijection from the set of all trees with vertex set V to the set of
00033    all lists of length max(0,n-2) over V.
00034 */
00035 
00036 /* The Pruefer code for a tree (as an ordered graph): */
00037 tree2pruefercode_og(T) := if length(T[1]) <= 2 then [] else
00038  block([x : min_vertex_degree_v_og(T)[2], y],
00039    y : single_element(disjoin(x, 
00040       for e in T[2] do if elementp(x,e) then return(e))),
00041    return(cons(y, 
00042       tree2pruefercode_og([delete(x,T[1]),delete({x,y},T[2])]) )))$
00043 
00044 /* Given a vertex list and a Pruefer code (as a list of elements from the
00045    vertex set), compute the tree (as an ordered graph) represented by
00046    the given Pruefer code: */
00047 pruefercode2tree_og(V,pc) := 
00048   if pc = [] then (if length(V) = 2 then [V,[setify(V)]] else [V,[]])
00049   else block([x : for v in V do if not member(v,pc) then return(v)],
00050     return([V,cons({x,first(pc)}, 
00051                 pruefercode2tree_og(delete(x,V),rest(pc))[2])]))$
00052 
00053 /* Remark: For a tree T (given as og) let 
00054    T' : pruefercode2tree_og(T[1],tree2pruefercode_og(T)).
00055    Then T[1] = T'[1], and setify(T[2]) = setify(T'[2]).
00056 */
00057 
00058