Graphs

Graphs

Your friends have friends of their own. Many users together form a many-to-many relationship network, which can be modeled as a graph.

Map navigation is another example: a network of metro stations can be represented as a graph to plan a route between a source and a destination.

Graphs are more complex than trees. A tree organizes one-to-many relationships into parent and child levels. A graph supports many-to-many relationships, without a required parent–child hierarchy.

Its basic units are vertices, corresponding to nodes in a tree. Their relationships are edges. Let $V$ be the vertex set and $E$ the edge set. An edge connects a pair: $(v,w)\in E$, with $v,w\in V$.

Edges may have different weights. For example, distances between stations vary. A graph with edge weights is a weighted graph, also called a network.

Some relationships are asymmetric: an account may follow another account without being followed back.

Such edges have a direction. A directed graph distinguishes $\langle v,w\rangle$, an edge from $v$ to $w$, from the reverse direction.

For a mutual relationship, either endpoint is connected to the other. Such relationships can be modeled by an undirected graph.