- 1
- 22 927
Grace Wang
Registrace 22. 08. 2021
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/Eulerian_path#Hierholzer's_algorithm)
CREDITS
Other Links
- Thank you to brooksandrew for his work on graph optimization here (used as reference):
brooksandrew.github.io/simpleblog/articles/intro-to-graph-optimization-solving-cpp/#solving-the-chinese-postman-problem
- Cornell Website Visualization: www.cs.cornell.edu/~kt/post/site-graph/
Picture Credits
- Air Flights from www.101computing.net/air-flight-route-planner/
- Bird Migration from www.birdlife.org/worldwide/programmes/migratory-birds
- Penicillin Model by Yikrazuul - Own work, Public Domain, commons.wikimedia.org/w/index.php?curid=7348509
- Junco Photo by Unknown Author is licensed under CC BY-NC-ND
- www.freepnglogos.com/images/plane-9936.html
Music / SFX Used:
czcams.com/video/0hsJ0gMm8OA/video.html
czcams.com/video/h87Nf-Tv1WE/video.html
czcams.com/video/ciogH7VhQsI/video.html
czcams.com/video/OpAmHAMtN-Y/video.html
Sound Effects - www.zapsplat.com
Animations and Visuals - PowerPoint
Video Editing - Lightworks
Audio Editing - Audacity
By Jolie Zhou, Grace Wang, and Melia Guttigoli
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/Eulerian_path#Hierholzer's_algorithm)
CREDITS
Other Links
- Thank you to brooksandrew for his work on graph optimization here (used as reference):
brooksandrew.github.io/simpleblog/articles/intro-to-graph-optimization-solving-cpp/#solving-the-chinese-postman-problem
- Cornell Website Visualization: www.cs.cornell.edu/~kt/post/site-graph/
Picture Credits
- Air Flights from www.101computing.net/air-flight-route-planner/
- Bird Migration from www.birdlife.org/worldwide/programmes/migratory-birds
- Penicillin Model by Yikrazuul - Own work, Public Domain, commons.wikimedia.org/w/index.php?curid=7348509
- Junco Photo by Unknown Author is licensed under CC BY-NC-ND
- www.freepnglogos.com/images/plane-9936.html
Music / SFX Used:
czcams.com/video/0hsJ0gMm8OA/video.html
czcams.com/video/h87Nf-Tv1WE/video.html
czcams.com/video/ciogH7VhQsI/video.html
czcams.com/video/OpAmHAMtN-Y/video.html
Sound Effects - www.zapsplat.com
Animations and Visuals - PowerPoint
Video Editing - Lightworks
Audio Editing - Audacity
By Jolie Zhou, Grace Wang, and Melia Guttigoli
zhlédnutí: 22 931
fart noise xd
Thanks so so so muchhhh ❤👯♂, helped a lot.
Love this video! Thank you
now i know that the problem is Chinese, not the postman.
Thanks for this video. Great intro to the topic.
wow incredible video! Thank you so much. This was extremely helpful
Absolutely loved this
Doesn't D in the first neighborhood have 3 edges connecting to it? i.e. odd no. of edges
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.
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.
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.
Perfect explanation
loved it
I can tell you put a lot of work into this, great job. I wish they would have covered this type of thing back in high school when I was there but they certainly did not. I have added this to a list of all SoME1 videos that I could find. czcams.com/video/MsNQtj3zVs8/video.html
Subscribed! This is a nice video! 😁
this is my favorite video!!