Graphs are useful for representing real-world data. Many practical problems can be represented by graphs. Therefore, they are becoming increasingly significant as they are applied to other areas of mathematics, science, and technology.

Your first association with the usage of graph theory is most probably social networks—sets of people or groups of people with some pattern of contact or interactions between them, such as Facebook, Twitter, Instagram, LinkedIn, and so on. Here are small graphs illustrating a few users of the first two social networks:

The graph on the left side is undirected and represents connected users as friends from a Facebook point of view, while the graph that illustrates Twitter is a digraph and shows that Miloš Radivojević follows the official account of David Gilmour, but unfortunately, he does not follow him back. Graph theory in social networking is used to implement requests such as friend(s) finder, friends of friends, to find degrees of connectedness, homophily, small-world effects, and to analyze many aspects of relationships between people and people and products or services. Results of such analyses are used by recommendation engines. It is also used to model many to many relations, such as relationships between actors, directors, producers, and movies, for instance, in the IMDb database.

In a computer network, the transmission of data is based on the routing protocol, which selects the best routes between any two nodes or devices. Graph theory is used in computer networking to find the best or least costly path between two nodes (shortest path algorithm).

In information networks, the link structure of a website can be represented by a directed graph, with web pages as nodes and links between them as edges. Web crawlers run graph search algorithms on the web and traverse through web page networks. The Google search engine uses a graph in the PageRank algorithm to rank resulted pages.

There are several biological and medical domains where graph theory techniques are applied: identifying drug targets, and determining the role of proteins and genes of an unknown function. It is being actively used for the modeling of bio-molecular networks, such as protein interaction networks, metabolic networks, as well as transcriptional regulatory networks. Graph theory is also one of the most important factors in generations of genome assembly software. One of the typical examples of usage of graphs is the usage of de Bruijn graphs in the assembly of genomes from DNA sequencing:

Graph theory is also used to study molecules in chemistry and physics. Chemical graph theory (CGT) is a branch of mathematical chemistry which deals with non-trivial applications of graph theory to solve molecular problems.

Finding the shortest path between two points or best possible routes in road networks is one of the oldest problems where graphs are used. Graph theory reduces transport networks to a collection of nodes (cities and road intersections) and edges (roads and rail lines) with the distance between two nodes as weights to help find the optimal route or the list of points that are reachable from the starting point. It is being actively used in airline information systems to optimize flight connections from a distance and cost point of view.

There are many other areas where graph theory is applied: fraud detection, recommendation engines, garbage collectors in programming languages (finding unreachable data), model checking (all possible states and checking if the code is OK), checking mathematical conjunctions, solving puzzles and games, identity and access management, Internet of Things (for modeling the connection between system components and IoT devices), and so on.

Now, as you have learned about graphs and graph theory, let's proceed to graph databases.