1. **Problem Statement:** Find the minimum spanning tree (MST) of the given weighted graph using Prim's algorithm. 2. **Prim's Algorithm Overview:** Prim's algorithm builds the MST by starting from an arbitrary vertex and repeatedly adding the smallest edge that connects a vertex in the MST to a vertex outside it. 3. **Step-by-step Application:** **Graph vertices:** a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p **Start at vertex a.** - Initialize MST with vertex a. - Edges from a: ab=1, ad=4, am=2 (circle edge) - Choose smallest edge: ab=1 **MST vertices:** a,b - Edges from MST to outside: bc=4, be=3, ad=4, am=2 - Choose smallest edge: am=2 **MST vertices:** a,b,m - Edges from MST to outside: bc=4, be=3, mn=2, ad=4 - Choose smallest edge: mn=2 **MST vertices:** a,b,m,n - Edges from MST to outside: bc=4, be=3, no=2, ad=4 - Choose smallest edge: no=2 **MST vertices:** a,b,m,n,o - Edges from MST to outside: bc=4, be=3, op=3, ad=4 - Choose smallest edge: be=3 **MST vertices:** a,b,m,n,o,e - Edges from MST to outside: bc=4, ef=1, op=3, ad=4 - Choose smallest edge: ef=1 **MST vertices:** a,b,m,n,o,e,f - Edges from MST to outside: bc=4, fg=4, op=3, ad=4 - Choose smallest edge: op=3 **MST vertices:** a,b,m,n,o,e,f,p - Edges from MST to outside: bc=4, fg=4, dp=2, ad=4 - Choose smallest edge: dp=2 **MST vertices:** a,b,m,n,o,e,f,p,d - Edges from MST to outside: bc=4, fg=4, gh=8, ad=4 - Choose smallest edge: ad=4 **MST vertices:** a,b,m,n,o,e,f,p,d - Edges from MST to outside: bc=4, fg=4, gh=8 - Choose smallest edge: bc=4 **MST vertices:** a,b,m,n,o,e,f,p,d,c - Edges from MST to outside: cf=6, fg=4, gh=8 - Choose smallest edge: fg=4 **MST vertices:** a,b,m,n,o,e,f,p,d,c,g - Edges from MST to outside: gh=8, hi=2 - Choose smallest edge: hi=2 **MST vertices:** a,b,m,n,o,e,f,p,d,c,g,h,i - Edges from MST to outside: jn=4, kl=3, jk=4, lm=2 - Choose smallest edge: jn=4 **MST vertices:** a,b,m,n,o,e,f,p,d,c,g,h,i,j - Edges from MST to outside: kl=3, jk=4, lm=2 - Choose smallest edge: lm=2 **MST vertices:** a,b,m,n,o,e,f,p,d,c,g,h,i,j,l - Edges from MST to outside: kl=3, jk=4 - Choose smallest edge: kl=3 **MST vertices:** a,b,m,n,o,e,f,p,d,c,g,h,i,j,l,k - Edges from MST to outside: jk=4 - Choose smallest edge: jk=4 **MST vertices:** a,b,m,n,o,e,f,p,d,c,g,h,i,j,l,k - All vertices connected. 4. **Final MST edges:** $\{ab=1, am=2, mn=2, no=2, be=3, ef=1, op=3, dp=2, ad=4, bc=4, fg=4, hi=2, jn=4, lm=2, kl=3, jk=4\}$ This set connects all vertices with minimum total weight.