0 votes 0 votes Algorithms algorithms + – Piyush1way asked Sep 10, 2023 Piyush1way 208 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply parth023 commented Sep 11, 2023 i edited by parth023 Sep 11, 2023 reply Follow Share I’m getting 48 as answer. in graph we have 10 vertices so we need 9 edges to form a MST. Edges AF,EG and DH have to be chosen because of minimum weight and they don’t form a cycle with each other.3 edges done.now we need to choose 6 more edges.now choosing 6 edges can be done in 3 ways. 1) From cycle A-B-C-D-E i choose 4 edges and from the cycle F-G-H-J-I i choose 2 edges.this can be done in $\left(\begin{array}{l}5 \\ 4\end{array}\right)\left(\begin{array}{l}3 \\ 2\end{array}\right)$. 2) from cycle A-B-C-D-E i choose 2 edges and from the cycle F-G-H-J-I i choose 4 edges.this can be done in $\left(\begin{array}{l}3 \\ 2\end{array}\right)\left(\begin{array}{l}5 \\ 4\end{array}\right)$. 3) from cycle A-B-C-D-E i choose 3 edges and from the cycle F-G-H-J-I i choose 3 edges. 1) first select edges AE and GH. and then from the cycle A-B-C-D-E i can select any 2 edges out of AB,BC,CD and similarly you can select any 2 edges out of FI,IJ and JH from the cycle F-G-H-J-I. OR 2) select edges ED and GF and then you can add edges such that you don’t create a cycle. finally we have $\left(\begin{array}{l}5 \\ 4\end{array}\right)\left(\begin{array}{l}3 \\ 2\end{array}\right)$$+$$\left(\begin{array}{l}3 \\ 2\end{array}\right)\left(\begin{array}{l}5 \\ 4\end{array}\right)$$+$$\left(\begin{array}{l}3 \\ 2\end{array}\right)\left(\begin{array}{l}3 \\ 2\end{array}\right)*2$ $=$ $48$ 0 votes 0 votes SankarVinayak commented Sep 11, 2023 reply Follow Share From cycle A-B-C-D-E i choose 4 edges AE-AB-BC-CD and from the cycle F-G-H-J-I i choose 2 edges HG-FG AE-AB-BC-CD-DH-HG-GE is a cycle and hence not MST right 0 votes 0 votes parth023 commented Sep 11, 2023 reply Follow Share I never told that I'll choose 2 edges HG and FG if i selected 4 edges AE-AB-BC-CD from the cycle A-B-C-D-E. what i meant was if we select 4 edges from the cycle A-B-C-D-E, then from the cycle F-G-H-J-I there are 3 ways to select 2 edges. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes AF-EG-DH since they have least weight one of AE,ED,GF,HG from AB,BC,CD,FI,IJ,HJ any 5 (4C1)*(6C5)=24 SankarVinayak answered Sep 11, 2023 SankarVinayak comment Share Follow See all 0 reply Please log in or register to add a comment.