OCR D1 June 2007 Q6 MST and lower bound cycle
Hello
I do not understand the answer to a part b. Constructing the MST using Prim on the matrix is ok. However, I do not understand the process for deleting the node B then finding a lower bound for the (Hamiltonian?) cycle by adding back the shortest paths from B. What algorithm is this? What has been created as a result of this step? How do I know it must be a lowest bound? I have looked at several textbooks and I cant find this process described – maybe I missed it. I will appreciate any help in explaining this step .
Thanks.
I do not understand the answer to a part b. Constructing the MST using Prim on the matrix is ok. However, I do not understand the process for deleting the node B then finding a lower bound for the (Hamiltonian?) cycle by adding back the shortest paths from B. What algorithm is this? What has been created as a result of this step? How do I know it must be a lowest bound? I have looked at several textbooks and I cant find this process described – maybe I missed it. I will appreciate any help in explaining this step .
Thanks.
Quick Reply
Related discussions
- A-level Exam Discussions 2024
- Edexcel A Level Further Mathematics Paper 3D (9FM0 3D) - 23rd June 2023 [Exam Chat]
- OCR further mechanics a level 16th June 2023
- Is a Oxbridge Mst valuable for someone with non-Oxbridge undergraduate degree?
- OCR A-Level Chemistry B Paper 1 (H433/01) - 12th June 2023 [Exam Chat]
- MSt in Social Innovation at Cambridge Judge Business School
- OCR A GCSE Biology Paper 2 (Foundation Combined) J250/02- 9th June 2023 [Exam Chat]
- ARU medicine apprenticeship information event
- GCSE Exam Discussions 2024
- OCR A-level Further Mathematics A Statistics (Y542) - 14th June 2023 [Exam Chat]
- AQA A Level Biology Paper 3 2019
- OCR A Level PE
- IAL and CIE/CAIE A Level Exams in the UK in November 2023
- Edexcel IGCSE 24th May 2018 Paper 3H Unofficial mark Sceheme
- A-level Chemistry Study Group 2022-2023
- A Level Exam Discussions 2023
- OCR A GCSE Biology Paper 4 Higher Tier [9th June 2023] Exam Chat
- Entry requirements for Physics and Astrophysics degree
- Upper and lower bounds degrees °
- Over 500 questions on AQA Bio Unit 4 + Current Spec and old Spec papers + MS!
Latest
Trending
Last reply 3 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
Trending
Last reply 3 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
