Friday, June 24, 2011

[okmnelpi] Generalization of graph diameter

Consider an undirected connected graph, two designated nodes, and the shortest path between the two nodes.  Label all other nodes with the minimum distance to any of the nodes on the shortest path (the graph equivalent of distance from a point to a line).  Which node has the largest distance?  What is the average distance?  Which node has the second largest distance, but in an "interesting" way distinct from the largest?

Motivation was a measurement of puzzle difficulty.  How far from "correct path" might you accidentally wander?

No comments :