11–17 of 17 posts
If you have young kids (6 or 7) who understand multiplication and like math, Gauss's formula is such a magical thing to show them, because it seems like it'd be impossible to shortcut adding up all those numbers that way, on the surface, and it's such an easy thing to prove visually.
A while back I interviewed with a networking company in the bay area and one of the things the interviewer asked me do was to devise an algorithm to walk the fully connected graph without visiting any edge twice if possible. Was a nice problem to discuss, he moved me along nicely in my thought process and we eventually reached a recursive solution. So the length of this walk is basically this formula. He told me they…
A fully connected graph with an even number of vertices will have odd degrees for all of them, and so can't have an Eulerian path.
A while back I interviewed with a networking company in the bay area and one of the things the interviewer asked me do was to devise an algorithm to walk the fully connected graph without visiting any edge twice if possible. Was a nice problem to discuss, he moved me along nicely in my thought process and we eventually reached a recursive solution. So the length of this walk is basically this formula. He told me they…
Isn't the length of the walk the number of edges?
A while back I interviewed with a networking company in the bay area and one of the things the interviewer asked me do was to devise an algorithm to walk the fully connected graph without visiting any edge twice if possible. Was a nice problem to discuss, he moved me along nicely in my thought process and we eventually reached a recursive solution. So the length of this walk is basically this formula. He told me they…
A while back I interviewed with a networking company in the bay area and one of the things the interviewer asked me do was to devise an algorithm to walk the fully connected graph without visiting any edge twice if possible. Was a nice problem to discuss, he moved me along nicely in my thought process and we eventually reached a recursive solution. So the length of this walk is basically this formula. He told me they…
I assume that's only possible in the general case for an odd number of vertices? A fully connected graph with an even number of vertices will have odd degrees for all of them, and so can't have an Eulerian path.
A while back I interviewed with a networking company in the bay area and one of the things the interviewer asked me do was to devise an algorithm to walk the fully connected graph without visiting any edge twice if possible. Was a nice problem to discuss, he moved me along nicely in my thought process and we eventually reached a recursive solution. So the length of this walk is basically this formula. He told me they…
A while back I interviewed with a networking company in the bay area and one of the things the interviewer asked me do was to devise an algorithm to walk the fully connected graph without visiting any edge twice if possible. Was a nice problem to discuss, he moved me along nicely in my thought process and we eventually reached a recursive solution. So the length of this walk is basically this formula. He told me they…
I assume that's only possible in the general case for an odd number of vertices? A fully connected graph with an even number of vertices will have odd degrees for all of them, and so can't have an Eulerian path.