Graphs

ABSTRACT

Navigation systems, social networks, and airport connections are all powered by Graphs. By abstracting real-world locations into Nodes and their connections into Edges, we can solve complex problems like finding the “shortest path” between any two points in the world.

1. What is a Graph?

A graph is a mathematical structure used to model relationships between objects. It consists of:

• Nodes (or Vertices): The individual elements or “locations” in the system.
• Edges: The connections between pairs of nodes.

Unlike trees, graphs have no strict hierarchy. They can be:

• Disconnected: Some nodes have no paths between them.

• Sequential: Nodes follow a linear path.

• Hierarchical: Organized like a tree (though trees are actually just a specific type of graph).

• Complex: A mix of connected and disconnected components.

2. Formal Definition

A graph $G$ is formally represented as an ordered pair $G=(V,E)$:

• $V$: A set of vertices $\{v_1,v_2,\dots ,v_n\}$.
• $E$: A set of edges, where each edge $e$ is a pair of vertices $(v,w)$.

Example

$e_1=(a,b)$

The size of a graph is denoted by

• $|V|$ (number of vertices)
• $|E|$ (number of edges).

3. Classifying Graphs

Graphs are categorized based on how their edges behave:

Directed vs. Undirected

• Directed Graph: Edges have a specific direction (one-way). $(v,w)$ means you can go from $v$ to $w$, but not necessarily back.

• Undirected Graph: Edges are bidirectional. $(v,w)$ is equivalent to $(w,v)$.

Weighted vs. Unweighted

• Weighted Graph: Each edge has a “cost” or “weight” $c$ (e.g., distance or travel time).

• Unweighted Graph: All edges are considered equal (effectively having a weight of 1).

4. Paths and Cycles

• Path: A sequence of edges connecting a start node to an end node.

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

• DAG (Directed Acyclic Graph): A directed graph that contains no cycles.

More information can be found here

5. Summary of Properties