# Tag Info

4

It looks like magic because the proof of Kirchhoff's Matrix Tree Theorem is nontrivial. It relies on several algebraic properties of the matrix constructed in steps 1-3, which is called the Laplacian matrix of the graph. Let $A$ be the adjacency matrix, and let $D$ be the diagonal matrix with the degrees of the nodes on the diagonal. Steps 1-3 build the ...

2

If you have to create the maze: Without boundaries Generated uniformly Generated from a seed It is unfortunately impossible without risking an endless loop, but most times it is good enough to create a really large maze. Daedalus has lots of features and implements all the algorithms on this page. To generate a really big maze in Daedalus, start the ...

1

The maximum spanning tree is about summing weights; maximizing the probability is about multiplying weights. To convert multiplication to sums, take the logarithm. Hopefully that's enough for you to work out an algorithm for this task.

1

You cannot show this since it isn't true. I encourage you to try out some actual numbers (e.g. $n=2$) and see for yourself that the numbers don't match. The problem is that what you should be subtracting is not the number of cycles of length $n-1$, but rather the number of collections of $n-1$ edges which contains at least one cycle. Such a collection need ...

1

I am not aware of any standard name for that kind of tree. One of the wonderful things about language is that we can describe things we don't already have a name for; there are many more interesting concepts than there are pre-existing widely-recognized names. I recommend that, if you find in your writing you need a concise name for it, you choose a name ...

1

The question and this post refers to this answer at its version 2. First of all, what does minimum disagreeing weight mean? The better word should have been "distinguishing". If the set of edges of some fixed weight in $T_1$ is different from that of $T_2$, then $T_1$ and $T_2$ disagree on that weight, i.e., that weight is distinguishing the two minimal ...

1

The maximum leaf spanning tree(MLSPT) is equivalent to the minimum connected dominating set(MCDS), see here. So we just need to prove MCDS is NP-complete. It's easy to verify that the decision version of MCDS is in NP. Similar to proof of NP completeness of dominating set, we perform a reduction from vertex cover(VC), i.e., we prove that $VC \le_p MCDS$: ...

Only top voted, non community-wiki answers of a minimum length are eligible