COMPSCI 61B Lecture Notes - Lecture 30: Shortest-Path Tree, Medical Imaging, Dream Evil
28 Aug 2017
School
Department
Course
Professor
Document Summary
Given an undirected graph, a spanning tree t is a subgraph of g where t: A minimum spanning tree is a spanning tree of minimum total weight. Medical imaging (arrangement of nuclei in cancer cells) A shortest path tree can be the mst but not always, so this isn"t the algorithm (you can"t just look at all the spts from all the nodes) Cut property: a useful tool for finding the mst. A cut assignment of a graph"s nodes to two non-empty sets. A crossing edge is an edge which connects a node from one set to a node from the other set. Cut property: given any cut, minimum weight crossing edge is in the mst (let"s assume edge weights are unique for this lecture) Suppose that the minimum crossing edge e were not in the mst. Adding e to the mst creates a cycle. Some other edge f must also be a crossing edge.
