Sunday, January 07, 2007
A practical application of graph theory
I created a directed graph out of the 32 NFL teams, with an edge going from Team A to Team B if Team A defeated Team B during the regular season. So there are 2 edges coming out of Oakland (Arizona and Pittsburgh), and 2 edges coming in to San Diego (Baltimore and Kansas City). Given this season, it is not at all surprising that there is path leading from any team to any other team. (For instance, to get from Oakland to San Diego, you need a three-step path, Pittsburgh, Kansas City, San Diego.) What might be surprising is that you can get from any team to any other team in just four steps. (The six pairs that require four steps are: OAK-HOU, OAK-IND, TEN-SD, ARI-SD, CHI-SD, and DET-SD.) There's an extra credit assignment in here somewhere.