Print Story paging MathGenius
Diary
By garlic (Wed Feb 09, 2005 at 05:20:28 PM EST) (all tags)
Or at least, a math genius.


In my network theory class one of the problems starts with an incidence matrix (non-complete) and asks us to determine if a set of branches constitutes a tree. Piece of cake: if the submatrix of those branches is non-singular then it's a tree. We then do some matrix math from this incidence matrix, A, to get the fundamental loop matrix Bf (Bf = [-(At^-1*Al)' U]) and the fundamental cut-set matrix Qf (Qf = [U At^-1*Al]) where t stands for twig, l stands for link, and U is the nxn identity matrix. All not to tough.

Then, it asks us to determine the number of trees in the graph described by this matrix. From the previous parts of the problem, I'd assume that the goal is to use a mathematical method to determine the number of trees. I know that there's 7 branches and 4 nodes. This means 3 twigs are necessary to make a tree, so 7 choose 3 = 35 possible trees max, but that's an upper bound only. The google searching I've done implies that this is not a problem that has been solved simply. Is there a mathematical way to solve for the number of trees in a graph that doesn't simplify down to "count the trees"?

< Since you axed | BBC White season: 'Rivers of Blood' >
paging MathGenius | 11 comments (11 topical, 0 hidden) | Trackback
WIPO: by ti dave (4.00 / 1) #1 Wed Feb 09, 2005 at 06:15:56 PM EST
ti dave domestic issues

I don't care if people hate my guts; I assume most of them do.
The important question is whether they are in a position to do anything about it. --W.S. Burroughs

you have domestic issues? by Dr H0ffm4n (4.00 / 1) #2 Wed Feb 09, 2005 at 08:16:37 PM EST
who knew?

[ Parent ]
Possibly, my wife and kids. by ti dave (2.00 / 0) #4 Wed Feb 09, 2005 at 08:37:04 PM EST
[conjecture]

I don't care if people hate my guts; I assume most of them do.
The important question is whether they are in a position to do anything about it. --W.S. Burroughs

[ Parent ]
+V2FP by komet (2.00 / 0) #3 Wed Feb 09, 2005 at 08:25:16 PM EST
Best poll evar.

--
<ni> komet: You are functionally illiterate as regards trashy erotica.
Ask an educational professional by Rogerborg (4.00 / 1) #5 Wed Feb 09, 2005 at 08:41:40 PM EST
IME, they will be so surprised and pleased that anyone gives a damn that they'll happily solve it for you.  DO NOT ACCEPT INVITATIONS TO DINNER.

-
Metus amatores matrum compescit, non clementia.
Is "most suck" on the top or bottom? by DesiredUsername (4.00 / 1) #6 Wed Feb 09, 2005 at 11:17:23 PM EST


---
Now accepting suggestions for a new sigline
The user picks the orientation and sticks with it. by garlic (2.00 / 4) #7 Thu Feb 10, 2005 at 12:23:23 AM EST
I don't know. It's not really ordered.


[ Parent ]
wow. by rmg (2.00 / 0) #8 Thu Feb 10, 2005 at 01:12:13 AM EST
actually, this is extremely relevant to something i'm kind of working on, but i don't know all that much about graph theory.

i would like to hear more about these cut and loop matrices. and i had no idea you could detect trees so easily via the adjacency matrix. in fact, i don't really believe it's true because i've seen many graphs with nonzero eigenvalues that were not trees, but maybe there's something here i'm not familiar with. like, maybe networks have some additional qualifications beyond simply being graphs.

what i will say is that if add an edge from the cut set and remove an edge from the loop set of that edge, you'll get another tree. if you translate that into your matrix language, i think you'll have your answer.




[t]rolling retards conversation, period.

stuff by garlic (1.50 / 2) #9 Thu Feb 10, 2005 at 02:12:04 AM EST
The incidence matrix is not the same as an adjacency matrix. An incidence matrix is a node x branch matrix. The adjacency matrix is a node x node matrix. To get the Adjacency matrix from the incidence matrix A = B'*B - 2U, where A is the adjacency matrix, B is the incidence matrix, and U is the appropriately sized identity matrix.

Now my book only gives a proof that a connected graph's incidence matrix sub graph whose columns correspond to a set of twigs (a tree) is nonsingular. It leaves it up to the reader to prove this for a graph with more than 1 part and for the reader to prove the converse: the columns of a nonsingular submatrix of an incidence matrix of order n x n corresponds to a set of twigs (a tree). I haven't done the proof, and am only assuming that the book is correct here. I guess I'm also leaving it as an excercise for the reader to google for a proof or prove it themselves.

It sounds like your correct on determining the number of trees, but this also sounds like it simplifies to "count the number of trees" via an algorithm.


[ Parent ]
no, by rmg (2.00 / 0) #10 Thu Feb 10, 2005 at 04:25:02 AM EST
i think you can interpret it in terms of a trace of the product of two matrices.




[t]rolling retards conversation, period.
[ Parent ]
anyway, there's not enough information here. by rmg (2.00 / 0) #11 Thu Feb 10, 2005 at 04:42:22 AM EST
you give no explanation of a what the twig and link matrices are. without that, there's no way to interpret the the cut-set and loop matrices properly.

i don't think there's much going on here. i think you've just buried the problem in terminology without giving the reader any explanation.




[t]rolling retards conversation, period.

[ Parent ]
paging MathGenius | 11 comments (11 topical, 0 hidden) | Trackback