4 ms·

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 fu

by phalf 3y ago

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 are using such an algorithm in some of their products and he picks the brain of potential hires to see if they find a more elegant way of doing so. Left a great impression, he really cared about thought processes and communicating! (I didn't end up taking the job for reasons unrelated to the company or the offer.)

a_e_k 3y ago
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.
- phalf 3y ago
  I could be mixing things up here, it's been too long ago. I think this was about a directed graph, so the number of edges is actually N^2 and your walk roughly of that length.
- hgsgm 3y ago
  /r/2IsNotEven
bibanez 3y ago
To walk a fully connected graph with a prime number of vertices you can walk first to x+1, then x+2 then x+3 etc. edges by looping around. This a fun special case to prove (basically if you loop by x+i where i coprime to n, it loops after visiting all the vertices, and if n is prime every i is coprime to it)
dcanelhas 3y ago
Sounds like a traveling salesman problem... Perhaps if you look at a dual graph where the edges are collapsed into nodes and the nodes are stretched out to become edges? Then the problem statement of "visiting each city only once" might become equivalent.
sorokod 3y ago
Isn't the length of the walk the number of edges?
- vince3455 3y ago
  Whenever you visit a node you need one edge to walk in and one to walk out, except for the first and last node. So all K_n with even n , you can walk all the edges. For odd n, you lose one edge per node, except for 2 of them
- JadeNB 3y ago
  I think the parent was agreeing with you, but saying that the number of edges on the fully connected (usually called complete) graph on n vertices is 1 + 2 + 3 + … + n = n(n + 1)/2.

by phalf 3y ago

a_e_k 3y ago

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.

phalf 3y ago
I could be mixing things up here, it's been too long ago. I think this was about a directed graph, so the number of edges is actually N^2 and your walk roughly of that length.
hgsgm 3y ago
/r/2IsNotEven

bibanez 3y ago

To walk a fully connected graph with a prime number of vertices you can walk first to x+1, then x+2 then x+3 etc. edges by looping around. This a fun special case to prove (basically if you loop by x+i where i coprime to n, it loops after visiting all the vertices, and if n is prime every i is coprime to it)

dcanelhas 3y ago

Sounds like a traveling salesman problem... Perhaps if you look at a dual graph where the edges are collapsed into nodes and the nodes are stretched out to become edges? Then the problem statement of "visiting each city only once" might become equivalent.

sorokod 3y ago

Isn't the length of the walk the number of edges?

vince3455 3y ago
Whenever you visit a node you need one edge to walk in and one to walk out, except for the first and last node. So all K_n with even n , you can walk all the edges. For odd n, you lose one edge per node, except for 2 of them
JadeNB 3y ago
I think the parent was agreeing with you, but saying that the number of edges on the fully connected (usually called complete) graph on n vertices is 1 + 2 + 3 + … + n = n(n + 1)/2.