[Image 1]
Hey it's a me again @drifter1!
Today we continue with Mathematics, and more specifically the branch of "Discrete Mathematics", in order to get into Common Graph Problems.
So, without further ado, let's get straight into it!
The applications of Graph Theory are basically countless. Many problems (and subproblems) can be solved using the various graph types and representations. With this article a small overview on some of these problems will be made. There are many known algorithms that can be used in order to solve them, which will be mentioned without further explanation...
First and foremost, the most common graph problem is finding the shortest path from one node to another. This of course only makes sense in the context of a weighted graph. The shortest path is the path with the least possible sum of weights.
For example, in the graph below travelling from vertex A to vertex F "costs" 20. On the other, hand if the upper path was taken instead (A → B → D → F) the cost would be 25.
[Image 2]
The two most commonly used algorithms for finding the shortest path from a single source vertex are Dijkstra's algorithm and Bellman-Ford's algorithm. Additionally there are also algorithms like Floyd-Warshall's and Johnson's which solve for shortest paths between all possible pairs.
In many cases, it may be important to know if a path exists from a given node to another. In that case the graph is traversed using either Breadth First Search (BFS) or Depth First Search (DFS) in order to check if the nodes are connected.
The required result in many problems has to be a connected graph, and so a "connectivity check" may have to be applied between all possible node pairs.
An easy to understand problem with lots of real-world applications is TSP. A salesman wants to visit a list of cities. Between each pair of cities there is a travelling cost. Each city is visited once and the first and last city are one and the same. In other words, the problem is about finding the Hamiltonian cycle with the least travelling cost.
The problem may seem simple at first, but finding the optimal solution is computationally complicated. There are many algorithms for solving it such as branch and bound and Held - Karp, which commonly apply estimations and heuristics in order to speed-up the process of finding at least a valid solution.
Another common problem is finding the minimum-cost spanning tree in a given graph. A spanning tree connects all vertices from the original graph, but with the least possible overall cost. The problem can be solved using Kruskal's and Prim's algorithms.
[Image 3]
Let's not forget to mention the problem of maximizing network flow. The weights in the graph may be used to visualize the capacity of each edge. In that sense, maximizing the "grid" and predicting bottlenecks can be very useful. Commonly used algorithms are Fork-Fulkerson's and Edmond-Karp's.
[Image 4]
Lastly, there is also graph coloring. Graphs are basically assigned labels, so that two adjacent vertices don't share one. The chromatic number of a graph is the minimum number of such colorings that has to be assigned. It's more commonly applied on vertices and not edges.
For example, a map can be seen as a graph where different colors are applied to neighboring countries. In that case, there also is no need to apply more than four colors, as a theorem known as the four-color theorem applies in the case of such planar graphs.
[Image 5]
Mathematical equations used in this article, have been generated using quicklatex.
Block diagrams and other visualizations were made using draw.io.
And this is actually it for today's post!
Next time we will talk about Binary Operations...
See ya!
Keep on drifting!
