For another perspective on the Königsberg Bridge problem, one can consider the number of edges on each vertex. To visit any vertex in a path once, there needs to be at least one edge going in, and another edge going out, for a total of 2 edges (so that each edge is only travelled once). If a vertex is visited twice, then there needs to be 2 edges in and 2 edges out, for a total of 4 edges. To generalise, any valid path needs an *even* number of edges for each edge to be visited once. There are two exceptions: the start vertex and end vertex. For the start vertex, there doesn’t _need_ to be an edge in, only an edge out, so it can just have one edge. It’s possible that the start edge can be visited another time (in which case we need to add another pair of edges to go in and out). It’s also possible that in a cyclical graph (of say 3 nodes), the start vertex has an even number (2) of edges. Likewise, the end vertex doesn’t _need_ an edge out (although it can!). From these facts, we can come up with a simple heuristic to solve this problem: there can be a maximum of 2 nodes with an odd number of edges. As the Königsberg graph has 3 vertices with an odd number of edges, it can’t be traversed with each edge being travelled only once.
This is the most complete treatment of the 7 bridge problem I have ever seen! I especially enjoyed the historical details that you included. You are right that Euler would have hated the work in tabulating paths, although he did produce about 100 volumes of work. Did they ever finish collecting his material? Thanks again for a great video!
Thanks! I don’t know if they ever finished collecting all of his work. My guess is probably not. Who knows was left in his mind that he never wrote down? I doubt you can be that prolific without a constant stream of ideas coming in…
I enjoyed this quite a bit. I thought the Python could have been a bit more "dumbed down" to be more approachable for others (since you clearly are quite good at it), but that's a minor quibble. I was able to follow it. I also enjoyed the historical details, as another poster mentioned.
I was playing around with the walks_starting_from function and I think there is a bug. I wanted to get all walks from the 5 cycle encoded as C_5 = [ ‘AbB', 'BbC', 'CcD', 'DdE', 'EeA'], walks_starting_from(‘B’, C_5) gave [‘BbA’] where I would expect the answer is [‘BbAeEdDcC’, ‘BbCcDdEeA’] - going round the clock both clockwise and anticlockwise. Seems like you’re missing some walks and need more conditional logic somewhere. Thanks for the great lecture otherwise! Look forward to learning more about how to implement graph theory.
Hey! It’s awesome to see someone is playing around with the code! I tested it out but couldn’t recreate the problem you had. I get both expected walks, one clockwise and one anticlockwise. I made a Google Colab with the modified code (all I did was change the BRIDGES list) which you can see and run here: colab.research.google.com/drive/1_6KPqHiVVVDGv2lfsfyfH6mQvLF_uItY?usp=sharing I’m happy to look at your code, if needed. Feel free to open an issue over at github.com/somacdivad/graph-theory-with-python if you want a second set of eyes 🙂
hii, I am taking a graph course in my university and from now on I'm watching your videos to get along with python etc. I just would like to know why is it necessary to declare a variable in available_bridhes and iterate over it, like: available_bridges = [ bridge for bridge in bridges: ] not simply: available_bridges = [ for bridge in bridges ]
Euler (a Swiss-German gentleman) is pronounced more like eo-ler than it is like oi-ler. The English language doesn't really have a diphthong that matches the eu in Euler. Oi is an approximation but not a good one. Better would be a short soft o-ler. This is a slightly random comment 🙂
For another perspective on the Königsberg Bridge problem, one can consider the number of edges on each vertex.
To visit any vertex in a path once, there needs to be at least one edge going in, and another edge going out, for a total of 2 edges (so that each edge is only travelled once). If a vertex is visited twice, then there needs to be 2 edges in and 2 edges out, for a total of 4 edges. To generalise, any valid path needs an *even* number of edges for each edge to be visited once.
There are two exceptions: the start vertex and end vertex. For the start vertex, there doesn’t _need_ to be an edge in, only an edge out, so it can just have one edge. It’s possible that the start edge can be visited another time (in which case we need to add another pair of edges to go in and out). It’s also possible that in a cyclical graph (of say 3 nodes), the start vertex has an even number (2) of edges. Likewise, the end vertex doesn’t _need_ an edge out (although it can!).
From these facts, we can come up with a simple heuristic to solve this problem: there can be a maximum of 2 nodes with an odd number of edges. As the Königsberg graph has 3 vertices with an odd number of edges, it can’t be traversed with each edge being travelled only once.
This is the most complete treatment of the 7 bridge problem I have ever seen!
I especially enjoyed the historical details that you included.
You are right that Euler would have hated the work in
tabulating paths, although he did produce about 100 volumes of
work. Did they ever finish collecting his material?
Thanks again for a great video!
Thanks! I don’t know if they ever finished collecting all of his work. My guess is probably not. Who knows was left in his mind that he never wrote down? I doubt you can be that prolific without a constant stream of ideas coming in…
Indeed ! Thanks a lot David :)
Hi David.
Its a Theory + Explanation + Programming RIght Mix and Enjoyable Learning that I was looking for Research.
Glad you found it helpful! I'll be adding more videos in the coming weeks!
Every programmer should watch this !
Great content, very good quality and really enjoyable. Thank you :)
Thanks 🙏
Totally thumbsup with possibilities for more :) Thanx :)
Very well done! I found the use of colors especially helpful since I’m a visual learner
Thanks! Glad you liked it 🙂
This is the channel I needed. Great job Danid! Thank you!
Glad to hear it!
Very helpful if you want to get started in solving math problems yourself like I am. Also you showed very well how to include python
I enjoyed this quite a bit. I thought the Python could have been a bit more "dumbed down" to be more approachable for others (since you clearly are quite good at it), but that's a minor quibble. I was able to follow it. I also enjoyed the historical details, as another poster mentioned.
Just discovering this channel, great content/presentation!
Thanks! glad you like the videos!
Fully subscribed to channel. Your mathematical insights will have great applications to data science!
Thanks, Ava! I’m very happy to see you here 🙂
Amazing material!
Well done! Great explanation. I really enjoyed it
I was playing around with the walks_starting_from function and I think there is a bug. I wanted to get all walks from the 5 cycle encoded as C_5 = [ ‘AbB', 'BbC', 'CcD', 'DdE', 'EeA'], walks_starting_from(‘B’, C_5) gave [‘BbA’] where I would expect the answer is [‘BbAeEdDcC’, ‘BbCcDdEeA’] - going round the clock both clockwise and anticlockwise. Seems like you’re missing some walks and need more conditional logic somewhere.
Thanks for the great lecture otherwise! Look forward to learning more about how to implement graph theory.
Hey! It’s awesome to see someone is playing around with the code! I tested it out but couldn’t recreate the problem you had. I get both expected walks, one clockwise and one anticlockwise.
I made a Google Colab with the modified code (all I did was change the BRIDGES list) which you can see and run here: colab.research.google.com/drive/1_6KPqHiVVVDGv2lfsfyfH6mQvLF_uItY?usp=sharing
I’m happy to look at your code, if needed. Feel free to open an issue over at github.com/somacdivad/graph-theory-with-python if you want a second set of eyes 🙂
hii, I am taking a graph course in my university and from now on I'm watching your videos to get along with python etc. I just would like to know why is it necessary to declare a variable in available_bridhes and iterate over it, like:
available_bridges = [
bridge
for bridge in bridges:
]
not simply: available_bridges = [
for bridge in bridges
]
Euler (a Swiss-German gentleman) is pronounced more like eo-ler than it is like oi-ler. The English language doesn't really have a diphthong that matches the eu in Euler. Oi is an approximation but not a good one. Better would be a short soft o-ler. This is a slightly random comment 🙂
Could this be considered a Search Optimization Algorithm?
Hmm, I don't _think_ so... The solution _is_ using a version of depth first search (DFS), though.
Euler was such a badass
legend