The Chinese Postman Problem (Introduction to Graph Theory)
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
Пікірлер: 18
wow incredible video! Thank you so much. This was extremely helpful
Thanks for this video. Great intro to the topic.
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.
Absolutely loved this
Perfect explanation
Subscribed! This is a nice video! 😁
Love this video! Thank you
this is my favorite video!!
Thanks so so so muchhhh ❤👯♂, helped a lot.
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).)
@rileynicholson2322
Жыл бұрын
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
@triagolnik
Жыл бұрын
Doing so will not pass every edge, which contradicts the requirements of the problem.
fart noise xd