4 ms·

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 mat

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.

laidoffamazon 2y ago
What is this part of graph theory called, and are there similar insights from doing elementary operations on adjacency matrices?
- kccqzy 2y ago
  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.
- evanb 2y ago
  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.
- FooBarBizBazz 2y ago
  Algebraic graph theory Subfield: Spectral graph theory https://en.m.wikipedia.org/wiki/Algebraic_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 https://pi.math.cornell.edu/~hatcher/AT/AT.pdf
kccqzy 2y ago
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.
- deleted 2y ago
  [deleted]
- meow_catrix 2y ago
  Shows it’s been a while… :)

laidoffamazon 2y ago

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

kccqzy 2y ago
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.
evanb 2y ago
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.
FooBarBizBazz 2y ago
Algebraic graph theory Subfield: Spectral graph theory https://en.m.wikipedia.org/wiki/Algebraic_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 https://pi.math.cornell.edu/~hatcher/AT/AT.pdf

kccqzy 2y ago

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.

deleted 2y ago
[deleted]
meow_catrix 2y ago
Shows it’s been a while… :)