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' > |