[meow_catrix]

Make a connectedness matrix of airports x airports with 1 marking a connection and 0 marking no connection. You can now iterate over legs by multiplying the matrix with itself. Do this until all values in the matrix are zero. The previous iteration shows a 1 where the longest routes are.

[kccqzy]

Great idea but two typos.

Multiplying the adjacency matrix by itself gives the number of walks of a specified length. Therefore you would keep multiplying the matrix by itself until all values are nonzero. Then the previous iteration shows a zero where the longest routes are.

[meow_catrix]

Shows it’s been a while… :)

[laidoffamazon]

What is this part of graph theory called, and are there similar insights from doing elementary operations on adjacency matrices?

[kccqzy]

I don't know what this part of graph theory is called but I noticed in college that this is taught in the graph theory class from the mathematics department but not in the graph theory class from the computer science department.

[FooBarBizBazz]

Algebraic graph theory

Subfield: Spectral graph theory

https://en.m.wikipedia.org/wiki/Algebraic_graph_theory

As for adjacency matrices -- consider the (oriented) vertex-edge incidence matrix D (vertices x edges, each edge is a column, head is +1 and tail is -1, other entries are zero). Then D and D' (transpose) both have interpretations (stop and think about them; they're like gradient and divergence), as does L = D D' (graph Laplacian).

This also generalizes from graphs to simplicial complexes (triangles, tetrahedra). And "connected components" of graphs generalize to higher homology groups (loops, voids):

https://pi.math.cornell.edu/~hatcher/AT/AT.pdf

[evanb]

If the graph is an undirected graph the adjacency matrix is symmetric. People study the eigenvalue spectrum; the largest eigenvalue is bounded by the highest degree of a vertex in the graph.