The Chinese Postman Problem (Introduction to Graph Theory)
Vložit
- čas přidán 24. 07. 2024
- This video covers Eulerian, Semi-Eulerian, and regular graphs in the Chinese Postman Problem as well as applications of graph theory. This was made for 3Blue1Brown's Summer of Math Exploration video competition (link: www.3blue1brown.com/blog/some1).
For more information about Eulerian Graphs and perhaps ways to find such trails, this is a good resource on Hierholzer’s Algorithm! (link: en.wikipedia.org/wiki/Euleria...)
CREDITS
Other Links
- Thank you to brooksandrew for his work on graph optimization here (used as reference):
brooksandrew.github.io/simpleb...
- Cornell Website Visualization: www.cs.cornell.edu/~kt/post/s...
Picture Credits
- Air Flights from www.101computing.net/air-flig...
- Bird Migration from www.birdlife.org/worldwide/pr...
- Penicillin Model by Yikrazuul - Own work, Public Domain, commons.wikimedia.org/w/index...
- Junco Photo by Unknown Author is licensed under CC BY-NC-ND
- www.freepnglogos.com/images/p...
Music / SFX Used:
• Sad Emotional and Nost...
• Disappointment - Sound...
• winning triumph (sound...
• The Messenger - Silent...
Sound Effects - www.zapsplat.com
Animations and Visuals - PowerPoint
Video Editing - Lightworks
Audio Editing - Audacity
By Jolie Zhou, Grace Wang, and Melia Guttigoli
Thanks for this video. Great intro to the topic.
wow incredible video! Thank you so much. This was extremely helpful
Absolutely loved this
Perfect explanation
Love this video! Thank you
Subscribed! This is a nice video! 😁
this is my favorite video!!
Thanks so so so muchhhh ❤👯♂, helped a lot.
Thank you for this video. I wanted to know if there were any resources to learn more. I am a delivery driver and this is a topic I am interested in for more efficient routes.
loved it
Doesn't D in the first neighborhood have 3 edges connecting to it? i.e. odd no. of edges
now i know that the problem is Chinese, not the postman.
Nice video! Would be even better with fewer sound-effects. 😅 (Edit: Moreover, the graph in the second half of the video can't come from a real-world example, because the edge lengths violate the triangle inequality (2 + 5 < 8, in particular).)
I don't understand about the Triangle Inequality issue. Couldn't this easily happen with a curved road in a real world example? Imagine a crescent road in the shape of a semicircle with A, D, and C on the flat edge. The path from A to D through C would be shorter than the path from A to D on the crescent road with no intersections.
I'd expect this to happen constantly in suburban neighbourhoods in North America.
At 4:00 you really should be doing ABEFDCA or 340 meters
Doing so will not pass every edge, which contradicts the requirements of the problem.
fart noise xd