Definition of mst Input: connected, and undirected Graph G=V,E) Each edge (u, v)in e carries a weight w(u, v) Also referred to as cost (length of edge) to connect u and v Output: a subset Tof e that connects all of the vertices in V and whose total weight is minimized Since the total weight is minimized the subset T must be acyclic(no circuit Thus, T'is a tree. We call it a spanning tree The problem of determining the tree t is called the minimum-spanning-tree problem5 Definition of MST • Input: connected, and undirected Graph G=(V,E) – Each edge (u,v) in E carries a weight w(u,v) • Also referred to as cost (length of edge) to connect u and v. • Output: A subset T of E that connects all of the vertices in V and whose total weight is minimized. • Since the total weight is minimized, the subset T must be acyclic (no circuit). – Thus, T is a tree. We call it a spanning tree. • The problem of determining the tree T is called the minimum-spanning-tree problem