A Gentle Introduction To Graph Theory

The post introduces graph theory as the mathematical basis for graph data structures. It explains that graphs are made of a set of vertices and a set of edges, and that unlike trees they do not have a root, hierarchy, or a single direction of flow.

It then separates graphs into directed and undirected forms. Directed edges have a fixed origin and destination, while undirected edges are bidirectional. The post uses the web, Facebook, Twitter, and dev.to to show how real networks can be modeled as graphs.

Reading notes

#

• Graphs come from discrete mathematics and are represented formally as G = (V, E).
• V is a set of vertices and E is a set of edges.
• A tree is a restricted type of graph, but graphs do not follow tree rules.
• Trees have a root, parent-child links, and no cycles.
• Graphs have no root node and can connect nodes in many different ways.
• A graph needs at least one node to count as a graph.
• Directed graphs use ordered edge pairs because direction matters.
• Undirected graphs use unordered edge pairs because travel goes both ways.
• The web is described as a graph because navigation moves between linked pages.
• Facebook fits an undirected graph because friendship is mutual.
• Twitter fits a directed graph because following is one-way.
• The same follow model applies to dev.to authors.