I pose this question as an industrial mathematics practitioner who does not specialize in graph theory: are there specific classes of problems that are only solvable (or best solved) using graph theory? AFAIK, from computation perspective, graph problems are often recasted into linear algebra, in which you have tools of both analysis and algebra. What are some results from graph theory that engender unique insights?
I suppose it depends what you mean by graph theory without linear algebra. Graphs can be represented as matrices without losing anything, so as such you can go from graphs to matrices and do everything you would do with graphs alone.
For describing algorithms sticking with just the notion of graphs is convenient however, as it allows you to speak of edges, nodes, colours etc. keeping things easier to grasp.
Also, there are notions such as planar graphs which probably don't have a nice interpretation in the linear algebra point of view only.
I have been working with homology theory applies to planar graphs this month. A procedure for which I could not see a nice compact algorithm in just graph theory terms reduced to simple matrix multiplication with the help of homology.
I'm certainly not saying linear algebra is useless with planar graphs.
It really depends on what is meant by graph theory vs. linear algebra here. If GT means we can fix an embedding to the space, then we have additional information such as number of crossings. However, it seems like a bit arbitrary restriction.
Network flow optimization and its many particular cases (bipartite matching, transportation problem, nonintersecting paths) are usually defined in terms of directed graphs with arc weights. You can package the arc capacities as a matrix, but you don't do the usual matrix things with it (like multiplying matrices, Gaussian elimination, QR, SVD), except perhaps if you do your matrix algebra over the tropical semiring (but that's often graph theory by another name). So you need new methods even if you shoehorn the problems into matrix language.
Hi, generationP! Excuse me for the unrelated question but it may be the only way to ask you. I've found you comment from a while ago: https://news.ycombinator.com/item?id=30316156
Could you tell a little bit more about thing named "Plato"? It is more a history question and I cannot find any references in the Internet about it. If you are more comfortable with private messages, I can be reached at ultranymous at proton dot me
I know very little about it. I referred to it as "Plato" only because it used to show a picture of Plato sitting on a rock when it downloaded a new paper into its library. My guess is that it used someone's donated account to do that.
Addendum: many algorithms book describe algorithmic solutions to a multitude of graph problems without linear algebra at all, like connected components, network flow, shortest paths, etc, etc
Data is often stored in structures which are based on graphs. And searching within these data structures does not nicely reduce to linear algebra. For instance, I don't think there is any nice way of reducing binary search to linear algebra.
