OKlibrary  0.2.1.6
IndependentSets.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 14.2.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/Basic.mac");
00023 
00024 /* Computing the independence number of a graph via the Maxima function */
00025 independence_number_gr_m(G) := length(max_independent_set(g2mg(G)))$
00026 
00027 /* Computing the partition number of a graph via the Maxima function */
00028 partition_number_gr_m(G) := if emptyp(G[2]) then length(G[1]) else
00029  chromatic_number(complement_graph(g2mg(G)))$
00030 
00031