第十三章最小生成树.ppt

Dendrogram of cancers in human Tumors in similar tissues cluster together. 作业 简答题：1～4题 程序设计题：1题 * * Minimum spanning tree This is a bicycle routes in Seattle. And it kind of gives a quick way from downtown out to the suburbs. You can see. This is, the idea of an MST as a model of natural phenomenon. * * * * MST is an important problem that‘s still been studied by theoretical computer scientist and we still dont know the best algorithm. * * if there‘s n points there’s n squared edges because every point‘s connected to every other point. And what we want is, in that graph, to find the subset of edges that connects all the points, that’s minimal.That‘s actually, in a lot of practical problems. The algorithms that we’ve talked about are not useful for this beacause they‘re going to take quadratic time, because e’s quadratic.What is typically done is to build a subgraph, where each point is connected to a certain number of points that are close to it. There‘s a particular graph called the Voronoi diagram, or the Delaunay triangulation. * Take a complete graph on?n?vertices, with edges weighted by i.i.d. random variables uniform on?[0,1].Here is an example, with?100000?nodes.?the minimum spanning tree Build with your favorite algorithm. * Here‘s another application in several scientific studies, there’s the idea of clustering. we have a set of objects and they‘re related by a distance function that specifies how close they are and what we wanna do is divide the objects into a given number k of coherent groups so that objects in different clusters are far apart.here’s a really old example of a application of this, outbreak of cholera deaths in London in the 1850s and, if you plot where all of the deaths happened, scientific study could find that they were clustered around certain places. And, actually they were able to identify well pumps that were leading to the the cholera. * Where you talk about the single length, the distance between two clusters equaling the di