1 ) How to use the math functions over graphs that are not in the data graph of Mathematica?
2 ) How to compute Chromatic Poynomials for a graph introduced by myself ?
Could you provide an example of each?
Bruce is right, it is not at all clear what do you need. Please give details and example. Also take a look at this MathWorld article. There is a link to an attached Mathematica notebook with code right below the tittle of the page.
Example where does not work
In this example does not work the Chromatic Polynomial
AdjacencyGraph[({{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}, {0,
0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1,
0, 0}, {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 0,
0, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 0,
1, 0, 0, 1, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0,
0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0,
0, 0, 1, 0}})]
I need the Chromatic Polynomial of graph defined by the following matrix, may you give the pass to get it.
Sincerely,
Reinaldo Giudici
{{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0},
{1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
{0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1},
{0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}}
Hi Reinaldo:
Did you look at the function ChromaticPolynomial ? it is from the Combinatorica package.
Dear Sander, Yes I did it
my example:
In this example does not work the Chromatic Polynomial
g = AdjacencyGraph[({{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}, {0,
0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1,
0, 0}, {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 0,
0, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 0,
1, 0, 0, 1, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0,
0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0,
0, 0, 1, 0}})]
ChromaticPolynomial[g]
This uses the old Graph specification, all from the combinatorica package:
You probably have to use FromAdjacencyMatrix, and related functions from:
Combinatorica/guide/GraphConstructionAndRepresentations
^^ Look that up in the help.
Could you please read carefully about package usage in Mathematica and especially this tutorial: Combinatorica. Please note Combinatorica package functionality is being in the process of transfer to built in Graph functionality. But do not confuse their syntax - they do not match.
It all works:
<< Combinatorica`
m = {{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0},
{1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
{0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1},
{0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}};
In[] = ChromaticPolynomial[FromAdjacencyMatrix[m], z]
Out[] = -3210 z + 13675 z^2 - 26877 z^3 + 32819 z^4 - 28015 z^5 + 17680 z^6 -
8444 z^7 + 3052 z^8 - 816 z^9 + 153 z^10 - 18 z^11 + z^12
FromAdjacencyMatrix[m] // ShowGraph
Dear Vitaly Kaurov
Your suggestion works pretty good. I am happy and I am continuing my research.
Thanks a lot,
Reinaldo Giudici
Dear Vitaly Kaurov,
I have been working on graphs up to 16 vertices and the program to compute works fine (it takes about 5 hours on my Sony Laptop), however when I try a graph with 18 vertices does not work, ever after 26 hours (I aborted de computations). For intance, the following graph :
g= {{0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {1, 0, 1, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0,
0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1}, {0,
1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,
1}, {0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {1, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0,
1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0,
1, 0, 0, 0}, {0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}};
Another question, the comand Constraction
Contract[g,{x,y}]
is not working for us, or I do not how to used it.
g = {{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 1, 0, 1,
0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0}, {1, 0,
0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0,
0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0,
0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 0,
0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}};
FromAdjacencyMatrix // ShowLabeledGraph
The graph is shown but the contract graph no
Contract[g, {1, 2}]
Thanks a lot in advance,
Your sincerely
Reinaldo Giudici
Dear Reinaldo, please take a few minutes to learn how to make proper posts with this tutorial:
How to type up a post: editor tutorial & general tips
- especially posting code. You can see other people on the thread use proper tools for posting code. It seems that because you pasted code as plain text some parts of it are missing.
Dear Vitaly Kaurov,
I have been working on graphs up to 16 vertices and the program to compute works fine (it takes about 5 hours on my Sony Laptop), however when I try a graph with 18 vertices does not work, ever after 26 hours (I aborted de computations). For intance, the following graph :
g={{0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {1, 0, 1, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0,
0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1}, {0,
1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,
1}, {0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {1, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0,
1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0,
1, 0, 0, 0}, {0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}};
ChromaticPolynomial[FromAdjacencyMatrix[g], z]
Another question, the Combinatorica command Contract[g,{x,y}] is not working for us, or I do not how to used it.
h={{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 1,0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0}, {1, 0,0, 0, 0, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}};
The graph is shown but the contract graph no Contract[g, {1, 2}]
We tried to enter the matrix for the suggested method, but had no luck.
Thanks a lot in advance,Your sincerely
Reinaldo Giudici
Another question, the command Contract[g,{x,y}]i s not working for us, or I do not how to used it.
h={{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 1,0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0}, {1, 0,0, 0, 0, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}};
The graph is shown but the contract graph Contract[h, {1, 2}]
We tried to enter the matrix for the suggested method, but had no luck.
Thanks a lot in advance,Your sincerely
Reinaldo Giudici
I have been working on graphs up to 16 vertices and the program to compute works fine (it takes about 5 hours on my Sony Laptop), however when I try a graph with 18 vertices does not work, ever after 26 hours (I aborted de computations). For intance, the following graph.
g={{0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {1, 0, 1, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0,
0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1}, {0,
1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,
1}, {0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {1, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0,
1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0,
1, 0, 0, 0}, {0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}};
In[] = ChromaticPolynomial[FromAdjacencyMatrix[m], z]
Another question, the command Contract[g,{x,y}]i s not working for us, or I do not how to used it.
h={{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 1,0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0}, {1, 0,0, 0, 0, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}};
The graph is shown but the contract graph no Contract[g, {1, 2}]
We tried to enter the matrix for the suggested method, but had no luck.
Thanks a lot in advance,Your sincerely
Reinaldo Giudici
you need to convert h to combinatorica graph like you did for chromatic polynomial:
Contract[FromAdjacencyMatrix[h], {1, 2}]
Dear Jaebum,
I have already done as I did for chromatical polynonial and did not work as I show you:
h={{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 1,0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0}, {1, 0,0, 0, 0, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}};
Contract[FromAdjacencyMatrix[h], {1, 2}]
Graph : < 17, 11, Undirected >
that the answer I GOT
Dear Reinaldo,
Chromatic polynomials are typically calculated using a deletion-contraction recursion, which is a very lengthy and awkward procedure to perform. The problem of computing such polynomials (which are a specialization of the Tutte polynomial) is \#P-hard in general, so one can not expect miracles of the “d-c” recursion, which I assume is the built-in method of Combinatorica.
Determinining whether a graph admits a k-coloring is known to be NP-complete for k\geq 3, but there exist various approximation algorithms for performing graph colorings that are somewhat optimal. In [1], Bonnie Berger and John Rompel developed an algorithm with a performance guarantee of O(n(log~log~n)^3/(log~n)^3) and MagnĂşs HalldĂłrsson improved this result to O(n(log~log~n)^2/(log~n)^3) in [2].
In 2009, a research group from New Zealand calculated the Tutte polynomial of the truncated icosahedron and, as their website explains, this took about one week to compute in a cluster of 150 computers [3]. So yes, computing the chromatic polynomial (more generally Tutte polynomial) of large graphs can be a complete nightmare as you already experienced. This is probably why finding efficient coloring algorithms remains one of the most exciting open challenges in combinatorics and computer science.
I hope this helps!
References:
[1] B. Berger and J. Rompel. A better performance guarantee for approximate graph coloring. Algorithmica, 1988.
[2] M. M. HalldĂłrsson. A still better performance guarantee for approximate graph coloring. Information Processing Letters, 1993.
[3] “Code for Computing Tutte Polynomials” (http://homepages.ecs.vuw.ac.nz/~djp/tutte/)
I don’t think that the chromatic polynomials functionality of Mathematica and the cited 2009 paper define the possible limits for performance. See for example https://www.hackerrank.com/contests/projecteuler/challenges/euler194 and specifically the constraints on the graph size. It implies that with proper optimization techniques the chromatic polynomials for planar graphs up to 60 vertices can be calculated within seconds.
Dear Oleg,
Thank you very much for your response and the interesting PE problem.
What really defines the limits for performance is the fact that the running time of the deletion-contraction algorithm that is normally used to compute the Tutte - and chromatic - polynomial is O((\frac{1+\sqrt{5}}{2})^{n+m}) for a graph on n vertices and m edges (See Chapter 2 of [1]). This recursion is most probably the calculation method in Combinatorica.
It has been found that evaluating the Tutte polynomial is \#P-hard at any point (a,b) except when (a,b) lies on the hyperbola H_1:=(x-1)(y-1)=1 and eight special points [2]. In such cases the computation can be done in polynomial time.
The Tutte polynomial of any planar graph along the special hyperbola H_2:=(x-1)(y-1)=2 can also be computed in polynomial time; maybe this is the case in the problem you mention.
Best regards,
Allan
References:
[1] H. S. Wilf, Algorithms and complexity, vol. 986, Prentice-Hall Englewood Cliffs, NJ, 1986.
[2] F. Jaeger, D. L. Vertigan, D. J. Welsh, On the computational complexity of the Jones and Tutte polynomials, in:
Mathematical Proceedings of the Cambridge Philosophical Society, vol. 108, Cambridge University Press, 35–53,
1990.