This greedy approach is wrong. e.g: If you would have selected vertex '2' instead of '5', the answer would have been 3 instead of 2. The correct approach is to find all possible subset of vertices that can form vertex cover and select the minimum size set from it.
Vertex Cover Problem is a known NP Complete problem, i.e., there is no polynomial-time solution for this unless P = NP. and you are teaching an polynomial time algorithm. How? problem in the given example: At step 2, if you select node 2 (to remove as we can take anyone according to lecture) the algorithm will give 4 vertices which is not an optimal answer. At step 2 we need to explore all possible paths(which again makes it NP ).
You are going greedy and this approach won't work even in your example. Let's say in your example you remove 2 instead of 5 then you would be forced to remove 2 extra nodes to cover all edges ie 1 and 5. So this time your subset would come out to be {3,2,1,5}. So Better is to check for all subsets and then find the minimum size subset which satisfies our condition.
Great explanation than many youtubers
kya badiya bataya madam apne .....loved it😍
Nice Explanation!
very easy explanation ...💯💯
Great mam
great explanation
Good explaing sum more topics explain THE SET COVERING PROBLEM
how the degree of vertex 6 is 3???
No 2
Degree value of vertex 6 is 2?
Yes
exactly i was finding someone who will ask this
Yes
Thank you so much 🥰💖
Helpful Video mem ❤️
You are golden! :)
Tq
Thank you mam great explanation
very helpful ma'am
Clear mam .tq mam .explain DAA topics mam
Nice mam thank you
good explanation. :)
Mam degree of 2 was 6
Thx mam
Thank you so much maa'm
thank u so much that’s very helpful . could u please solve some proof Questions?
Again thank u :)
Tq mam👍
If you would have chosen vertex 2 instead of 5 in second step (both the vertex had same degree), the ans wouldn't have been correct
yeah but she was not stupid like you, one more thing was there use your common sense.
Mam minor mistake....in the graph degree of 6 is 2...you wrote 3
Once you check again maa
Yeah Now even I have notice it 🙂.
@@geekking638 Yes , degree of 6 is 2
didi apko samja na bas baat khatam
best
Post few more leachers I would like to have Travelling Saleman problem
nice
This greedy approach is wrong. e.g: If you would have selected vertex '2' instead of '5', the answer would have been 3 instead of 2. The correct approach is to find all possible subset of vertices that can form vertex cover and select the minimum size set from it.
This approach is not fully correct as it's a np complete problem , we can do this better by approximate algorithm.
Vertex Cover Problem is a known NP Complete problem, i.e., there is no polynomial-time solution for this unless P = NP.
and you are teaching an polynomial time algorithm. How?
problem in the given example: At step 2, if you select node 2 (to remove as we can take anyone according to lecture) the algorithm will give 4 vertices which is not an optimal answer. At step 2 we need to explore all possible paths(which again makes it NP ).
You are going greedy and this approach won't work even in your example. Let's say in your example you remove 2 instead of 5 then you would be forced to remove 2 extra nodes to cover all edges ie 1 and 5. So this time your subset would come out to be {3,2,1,5}. So Better is to check for all subsets and then find the minimum size subset which satisfies our condition.
💩
Mam explain for tamil I am not anderstand this language
Explain in tamil