18.100C Lecture Notes - Lecture 1: Glossary Of Dune Terminology, Travelling Salesman Problem, Greedy Algorithm
Document Summary
Outline: mst (minimum spanning trees, motivations, algorithm for nding them (greedy algorithm, proof of correctness, applications: traveling salesman problem (tsp) Spanning tree: given p = (v, e), a spanning tree is a subgraph p" = (v, e"). Minimum: g = (v, e, w) where w is the weight function and. Laying electrical wires between two points, for which their is a cost for infrastructure. Minimum spanning trees allow us to minimize infrastructure cost while connecting all customers. Greedy algorithm only takes the best decision for its given time step without considering the future implications. Forest: a set of trees with independent edges. Induced forest: if you have g = {abc} and q = {ab}, then the induced forest is (g, q) Maintain a set of edges, a, where a = {e e } We are looking at the forest that a implies on g, meaning g:a. Minimum weight and endpoints of our new edge must be in different components.
