Ask Your Question
0

How to interpret the result of treewidth() function.

asked 2015-02-24 15:04:39 +0100

this post is marked as community wiki

This post is a wiki. Anyone with karma >750 is welcome to improve it.

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!

edit retag flag offensive close merge delete

Comments

Congratulations 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".

slelievre gravatar imageslelievre ( 2015-02-25 10:54:09 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
2

answered 2015-02-24 15:27:12 +0100

Nathann gravatar image

The 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}]
edit flag offensive delete link more

Comments

Got it. Thank you so much! :-)

fetag gravatar imagefetag ( 2015-02-24 16:37:00 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2015-02-24 15:04:39 +0100

Seen: 461 times

Last updated: Feb 24 '15