Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
# cython: binding=True """ Chromatic Polynomial
AUTHORS:
- Gordon Royle - original C implementation - Robert Miller - transplant
REFERENCE:
Ronald C Read, An improved method for computing the chromatic polynomials of sparse graphs. """
#***************************************************************************** # Copyright (C) 2008 Robert Miller # Copyright (C) 2008 Gordon Royle # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
from cysignals.signals cimport sig_check
from sage.libs.gmp.mpz cimport * from sage.rings.integer_ring import ZZ from sage.rings.integer cimport Integer from sage.ext.memory_allocator cimport MemoryAllocator from sage.misc.all import prod
def chromatic_polynomial(G, return_tree_basis=False): """ Compute the chromatic polynomial of the graph G.
The algorithm used is a recursive one, based on the following observations of Read:
- The chromatic polynomial of a tree on n vertices is x(x-1)^(n-1).
- If e is an edge of G, G' is the result of deleting the edge e, and G'' is the result of contracting e, then the chromatic polynomial of G is equal to that of G' minus that of G''.
EXAMPLES::
sage: graphs.CycleGraph(4).chromatic_polynomial() x^4 - 4*x^3 + 6*x^2 - 3*x sage: graphs.CycleGraph(3).chromatic_polynomial() x^3 - 3*x^2 + 2*x sage: graphs.CubeGraph(3).chromatic_polynomial() x^8 - 12*x^7 + 66*x^6 - 214*x^5 + 441*x^4 - 572*x^3 + 423*x^2 - 133*x sage: graphs.PetersenGraph().chromatic_polynomial() x^10 - 15*x^9 + 105*x^8 - 455*x^7 + 1353*x^6 - 2861*x^5 + 4275*x^4 - 4305*x^3 + 2606*x^2 - 704*x sage: graphs.CompleteBipartiteGraph(3,3).chromatic_polynomial() x^6 - 9*x^5 + 36*x^4 - 75*x^3 + 78*x^2 - 31*x sage: for i in range(2,7): ....: graphs.CompleteGraph(i).chromatic_polynomial().factor() (x - 1) * x (x - 2) * (x - 1) * x (x - 3) * (x - 2) * (x - 1) * x (x - 4) * (x - 3) * (x - 2) * (x - 1) * x (x - 5) * (x - 4) * (x - 3) * (x - 2) * (x - 1) * x sage: graphs.CycleGraph(5).chromatic_polynomial().factor() (x - 2) * (x - 1) * x * (x^2 - 2*x + 2) sage: graphs.OctahedralGraph().chromatic_polynomial().factor() (x - 2) * (x - 1) * x * (x^3 - 9*x^2 + 29*x - 32) sage: graphs.WheelGraph(5).chromatic_polynomial().factor() (x - 2) * (x - 1) * x * (x^2 - 5*x + 7) sage: graphs.WheelGraph(6).chromatic_polynomial().factor() (x - 3) * (x - 2) * (x - 1) * x * (x^2 - 4*x + 5) sage: C(x)=graphs.LCFGraph(24, [12,7,-7], 8).chromatic_polynomial() # long time (6s on sage.math, 2011) sage: C(2) # long time 0
By definition, the chromatic number of a graph G is the least integer k such that the chromatic polynomial of G is strictly positive at k::
sage: G = graphs.PetersenGraph() sage: P = G.chromatic_polynomial() sage: min(i for i in range(11) if P(i) > 0) == G.chromatic_number() True
sage: G = graphs.RandomGNP(10,0.7) sage: P = G.chromatic_polynomial() sage: min(i for i in range(11) if P(i) > 0) == G.chromatic_number() True
TESTS:
Check that :trac:`21502` is solved::
sage: graphs.EmptyGraph().chromatic_polynomial() 1 """ return prod([chromatic_polynomial(g) for g in G.connected_components_subgraphs()])
cdef int nverts, nedges, i, j, u, v, top, bot, num_chords, next_v cdef int *queue cdef int *chords1 cdef int *chords2 cdef int *bfs_reorder cdef int *parent cdef mpz_t m, coeff cdef mpz_t *tot cdef mpz_t *coeffs
# Breadth first search from 0: else: else: # bubble sort the chords break except BaseException: for i in range(nverts): mpz_clear(tot[i]) raise # start with the zero polynomial: f(x) = 0
# do this: # f += tot[i]*m*x*(x-1)**(i-1) # an iterative method for binomial coefficients... # coeffs[i-j] += tot[i]*m*coeff cdef Integer c_ZZ
cdef int contract_and_count(int *chords1, int *chords2, int num_chords, int nverts, mpz_t *tot, int *parent) except -1: cdef int i, j, k, x1, xj, z, num, insnum, parent_checked
# contract chord i, and recurse parent_checked = 1 # now try adding {x1, parent[z]} to the list if not parent[x1] == parent[z]: if x1 > parent[z]: ins_list1[insnum] = x1 ins_list2[insnum] = parent[z] else: ins_list1[insnum] = parent[z] ins_list2[insnum] = x1 insnum += 1 else: ins_list1[insnum] = parent[z] ins_list2[insnum] = x1
# now merge new_chords and ins_list else: |