ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 25 Feb 2015 10:54:09 +0100How to interpret the result of treewidth() function.https://ask.sagemath.org/question/25914/how-to-interpret-the-result-of-treewidth-function/ Hi there, I want to generate a random graph and compute the optimal treewidth, also the corresponding decomposition of this graph. Here is my code in sage:
g = graphs.RandomGNM(15, 50)
g.show()
g.treewidth(certificate=True)
The output as follows:
Graph on 7 vertices
I think this result should means in the optimal tree decomposition, there are 7 tree nodes. then my question is how can we get more detail information about which vertex of the graph belongs to which tree node of the decomposition?
Thanks for your attention!Tue, 24 Feb 2015 15:04:39 +0100https://ask.sagemath.org/question/25914/how-to-interpret-the-result-of-treewidth-function/Comment by slelievre for <p>Hi there, I want to generate a random graph and compute the optimal treewidth, also the corresponding decomposition of this graph. Here is my code in sage:</p>
<p>g = graphs.RandomGNM(15, 50)
g.show()
g.treewidth(certificate=True)</p>
<p>The output as follows:
Graph on 7 vertices</p>
<p>I think this result should means in the optimal tree decomposition, there are 7 tree nodes. then my question is how can we get more detail information about which vertex of the graph belongs to which tree node of the decomposition?</p>
<p>Thanks for your attention!</p>
https://ask.sagemath.org/question/25914/how-to-interpret-the-result-of-treewidth-function/?comment=25928#post-id-25928Congratulations for your first question! Here are a few hints. To display code: select lines of code and click the code-formatting button (the one with "101 010"). Or indent each line of code by four spaces. Try editing your question to do that. Also, usually, don't make your question "community wiki".Wed, 25 Feb 2015 10:54:09 +0100https://ask.sagemath.org/question/25914/how-to-interpret-the-result-of-treewidth-function/?comment=25928#post-id-25928Answer by Nathann for <p>Hi there, I want to generate a random graph and compute the optimal treewidth, also the corresponding decomposition of this graph. Here is my code in sage:</p>
<p>g = graphs.RandomGNM(15, 50)
g.show()
g.treewidth(certificate=True)</p>
<p>The output as follows:
Graph on 7 vertices</p>
<p>I think this result should means in the optimal tree decomposition, there are 7 tree nodes. then my question is how can we get more detail information about which vertex of the graph belongs to which tree node of the decomposition?</p>
<p>Thanks for your attention!</p>
https://ask.sagemath.org/question/25914/how-to-interpret-the-result-of-treewidth-function/?answer=25916#post-id-25916The nodes of the tree that you get are sets of vertices
sage: g = graphs.RandomGNM(15, 50)
sage: g.show()
sage: treedec = g.treewidth(certificate=True)
sage: treedec
Graph on 11 vertices
sage: treedec.vertices()
[{0, 3, 4, 7, 8, 9},
{0, 3, 4, 5, 7, 9, 13},
{3, 4, 5, 7, 9, 10, 13},
{0, 1, 3, 4, 6, 7, 8, 9},
{0, 2, 13, 7},
{3, 4, 5, 7, 9, 13},
{0, 2, 13, 14, 7},
{3, 5, 7, 8, 9, 13},
{3, 5, 7, 8, 9, 11, 13},
{0, 2, 3, 4, 5, 7, 9, 12},
{0, 2, 3, 4, 5, 7, 9}]
Tue, 24 Feb 2015 15:27:12 +0100https://ask.sagemath.org/question/25914/how-to-interpret-the-result-of-treewidth-function/?answer=25916#post-id-25916Comment by fetag for <p>The nodes of the tree that you get are sets of vertices</p>
<pre><code>sage: g = graphs.RandomGNM(15, 50)
sage: g.show()
sage: treedec = g.treewidth(certificate=True)
sage: treedec
Graph on 11 vertices
sage: treedec.vertices()
[{0, 3, 4, 7, 8, 9},
{0, 3, 4, 5, 7, 9, 13},
{3, 4, 5, 7, 9, 10, 13},
{0, 1, 3, 4, 6, 7, 8, 9},
{0, 2, 13, 7},
{3, 4, 5, 7, 9, 13},
{0, 2, 13, 14, 7},
{3, 5, 7, 8, 9, 13},
{3, 5, 7, 8, 9, 11, 13},
{0, 2, 3, 4, 5, 7, 9, 12},
{0, 2, 3, 4, 5, 7, 9}]
</code></pre>
https://ask.sagemath.org/question/25914/how-to-interpret-the-result-of-treewidth-function/?comment=25919#post-id-25919Got it.
Thank you so much! :-)Tue, 24 Feb 2015 16:37:00 +0100https://ask.sagemath.org/question/25914/how-to-interpret-the-result-of-treewidth-function/?comment=25919#post-id-25919