Graphs for dummies

What’s a graph?

A graph is a data structure to model networks of interconnected objects.

Yes, that explanation was not for dummies. Let’s try again!

Imagine you want to map the relationship between you and your Twitter followers. You could draw a graph where each vertex represented a persona and each edge represented who follows who.

In graphs, we call vertex or nodes to the objects we are mapping and edges to the relationships between them.

See that some edges have arrows and some don’t? Can you guess why?

Exactly! Arrows represent the direction of the relationship. In this case, edges with no arrows mean both users are following each other. While edges with an arrow means that one user is following the other.

Neighbors

A node can be connected to many other nodes. Those nodes are called neighbors.

Nodes can have in-neighbors or out-neighbors depending on the direction of the edge.

Some Math

Ok, many people out there is going to judge you based on your ability to mathematically represent graphs so let’s dig a bit dipper. But trust me, even can kid can understand this.

A Graph can be defined by the expression $G = (V, E)$ where:

• $G$: is the graph
• $V$: represents a set of vertices
• $E$: represents a set of edges

Easy right?

Just one more thing. Remember we use $\{...\}$ to express sets in Math. A set is a collection of unique values. Also we use $(...)$ to represent tuples. A tuple is finite sequence of ordered elements.

Too technical? Let’s see some examples.

What if we find a graph with mutual edges?

Some key terminology

• Degree of a vertex: number of edges connected to a vertex.

• Path: sequence of connected nodes.
• Path length: number of edges in a path.

• Cycle: path that starts and ends at the same vertex.

• Connected nodes: nodes that are connected by a path.
• Connected graph: a graph where there is a path between every pair of vertices.

Types of graphs

Based on relationship

With all we know now this is going to be easy.

Remember that no arrows means mutual relationship and arrows means one-way relationship.

Ok, so is time to introduce you to the two main types of graphs:

• Directed graphs: edges have a direction represented by arrows.

• Undirected graphs: edges represent connections without any specific direction. Meaning you can go from A to B and from B to A indifferently.

Flavors of graphs

• Simple graphs: no loops or multiple edges between the same pair of vertices.
• Cyclic graphs: contain at least one cycle.
• Acyclic graphs: do not contain cycles.
• Labeled graphs: edges have labels or weights.
• Weighted graphs: subtype of labeled graph, edges have weights or costs associated with them.