3 ms·
I haven't thought about this before, but I can't see how this would work. Instead, you'd convert to an adjacency matrix (with edge directions by only populatin
by dekhn 4y ago
I haven't thought about this before, but I can't see how this would work. Instead, you'd convert to an adjacency matrix (with edge directions by only populating the upper rectangular region), then transpose the matrix, then convert back to a graph. The transpose should swap the i, j pair edge directions. Matrix inversion is super-expensive and I think it would produce somethign else entirely, probably not unlike matrix decomposition, which can extract centrality properties of the nodes. But it's super expensive.
- bee_rider 4y agoYep! It was not a serious suggestion, just a joke based on taking a circuitous route through the language.
- dekhn 4y agowhew! I thought I was missing something obvious (I'm a graph/matrix nerd, can't you tell?)
- bee_rider 4y agoIt was a pretty nonsensical joke anyway. Something obvious that I missed which sort of spoils the joke is that if you take a binary tree, look at it as a directed graph, and then take the adjacency matrix of the graph, it is obviously not invertible. Do'h!
- dekhn 4y agoI don't think that's true- at least, I see literature saying that inversting the adjacency matrix of a graph is useful. Is there something about the property of the graph that makes it non-invertible?
- bee_rider 4y agoFor sure they are useful in general. In the case of a binary tree, though -- I guess it depends on how you think of the graph. If it is directed -- a parent only points down to it's children (so, no backwards links up the tree), the adjacency matrix is clearly rank deficient. The row (or column depending on how you want the adjacency matrix to be set up) for edges going in to node 1 is empty. If we think of the graph as undirected, it is still not invertible, but I don't know that there's anything immediately intuitive about it. With 7 nodes we'd have (numbered as in a breadth first traversal): . 1 2 3 4 5 6 7 1 0 1 1 0 0 0 0 2 1 0 0 1 1 0 0 3 1 0 0 0 0 1 1 4 0 1 0 0 0 0 0 5 0 1 0 0 0 0 0 6 0 0 1 0 0 0 0 7 0 0 1 0 0 0 0 Rows 4 and 5, as well as 6 and 7 are clearly degenerate (all the leaf nodes).