4 ms·
What is this part of graph theory called, and are there similar insights from doing elementary operations on adjacency matrices?
by 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 agoI 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 agoIf 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 agoAlgebraic 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