the 1050 comes from adding all the lengths of the vertices and the shortest distance found so ( 890+160=1050)
@sujoyseal1953 жыл бұрын
You should have explained the ending properly. This is my theory. Someone confirm this. 1050 is obtained as 890 +160. 890 is the original sum of edges of the original graph at the beginning of the problem. From , what it seems we need to have a Euler Path in the graph. So we need to convert the vertices of odd degree into even . So we need to add edges. Now we need determine the edge set given a set { v1 , v2, v3.....} in a greedy manner since it's a minimum weight problem. Now we can't add a Edge E connecting V1 and V2 if either of V1 and V2 is even because then that even vertex becomes odd and the issue persists. Hence we add edges connecting odd vertices from in a manner such that Sum( E1 + E2 + .....) is minimum. Hence we generate all combinations and take the combination having total edge sum minimum . The path can be implemented with a vector in C++ with adjacency list representing the graph. Use next_permutation(v.begin() , v.end()) to generate all paths. Hence the algorithm. It will take exponential time O(n!) . After we have added the edges, we will calculate the original sum of edges and sum of the newly added edges ( 890 +160) which gives the required Chinese Postman Route. This is what I think. Am I making sense?
@osmanhussain67153 жыл бұрын
DO NOT SEE THIS VIDEO! The guy didnt explain the end correctly and youll end up confused
@athego Жыл бұрын
don't understand all the comments, thanks for explaining so well!
@tevian94042 жыл бұрын
5:45 well I believe it is not an Eulerian path but an Eulerian trail since the edges are not repeated but the vertices are?
@randaya5854
Жыл бұрын
An Eulerian path has NO vertices of odd degree, while an Eulerian trail has EXACTLY 2 vertices of odd degree. Since there are 4 vertices of odd degree, which are B, H, F, C, it is NOT an Eulerian trail. The graph is non-Eulerian, overall.
@nguyentuan19909 жыл бұрын
like what? how did you get 1050?
@Suiryuundan
8 жыл бұрын
+Tuan Nguyen with fleury algorithm
@HarishST
7 жыл бұрын
Sum of all edges + The Minimum path discovered (160) = 1050
@mlkstudy2 жыл бұрын
Why didn’t er take BF and FH as the edges to repeat?
@nimisharangarajan6872
Жыл бұрын
because C is not included in that
@ThiNguyen-gd9ny8 жыл бұрын
hello... how to write programs using HEAPSORT to solve Travelling Salesman Problem - TSP on programming language C ... and I need code :( im form Viet Nam...thanks
Пікірлер: 14
the 1050 comes from adding all the lengths of the vertices and the shortest distance found so ( 890+160=1050)
You should have explained the ending properly. This is my theory. Someone confirm this. 1050 is obtained as 890 +160. 890 is the original sum of edges of the original graph at the beginning of the problem. From , what it seems we need to have a Euler Path in the graph. So we need to convert the vertices of odd degree into even . So we need to add edges. Now we need determine the edge set given a set { v1 , v2, v3.....} in a greedy manner since it's a minimum weight problem. Now we can't add a Edge E connecting V1 and V2 if either of V1 and V2 is even because then that even vertex becomes odd and the issue persists. Hence we add edges connecting odd vertices from in a manner such that Sum( E1 + E2 + .....) is minimum. Hence we generate all combinations and take the combination having total edge sum minimum . The path can be implemented with a vector in C++ with adjacency list representing the graph. Use next_permutation(v.begin() , v.end()) to generate all paths. Hence the algorithm. It will take exponential time O(n!) . After we have added the edges, we will calculate the original sum of edges and sum of the newly added edges ( 890 +160) which gives the required Chinese Postman Route. This is what I think. Am I making sense?
DO NOT SEE THIS VIDEO! The guy didnt explain the end correctly and youll end up confused
don't understand all the comments, thanks for explaining so well!
5:45 well I believe it is not an Eulerian path but an Eulerian trail since the edges are not repeated but the vertices are?
@randaya5854
Жыл бұрын
An Eulerian path has NO vertices of odd degree, while an Eulerian trail has EXACTLY 2 vertices of odd degree. Since there are 4 vertices of odd degree, which are B, H, F, C, it is NOT an Eulerian trail. The graph is non-Eulerian, overall.
like what? how did you get 1050?
@Suiryuundan
8 жыл бұрын
+Tuan Nguyen with fleury algorithm
@HarishST
7 жыл бұрын
Sum of all edges + The Minimum path discovered (160) = 1050
Why didn’t er take BF and FH as the edges to repeat?
@nimisharangarajan6872
Жыл бұрын
because C is not included in that
hello... how to write programs using HEAPSORT to solve Travelling Salesman Problem - TSP on programming language C ... and I need code :( im form Viet Nam...thanks
what?