Introduction to Graphs: Components and Classification

What is a Graph?

At its core, a graph is a mathematical structure used to model relationships between objects. Think of a city map: the cities are objects, and the roads connecting them are the relationships. In computer science, this abstraction is incredibly powerful, allowing us to represent everything from computer networks to social connections to dependencies in a project.

A graph consists of two key elements:

• Vertices (also called nodes): These are the fundamental objects or entities within the graph.
• Edges: These are the connections or relationships that link pairs of vertices.

To get a clear visual and formal introduction to these concepts, please watch the beginning of the following video from the Reducible channel.

As you saw in the video, we can formally describe a graph $G$ as an ordered pair $G=(V,E)$, where $V$ is the set of all vertices, and $E$ is the set of all edges. This set-based definition is the bedrock upon which all of graph theory is built.

Classifying Graphs: Direction and Weight

Nearly every graph problem you encounter will involve one of four basic types of graphs, derived from two key distinctions. These distinctions are based on the properties of the edges.

1. Directionality: Are the connections one-way or two-way?
2. Weight: Do the connections have an associated cost or value?

Let's explore each of these dimensions.

1. Undirected vs. Directed Graphs

The first classification depends on whether the relationship represented by an edge is symmetric.

Undirected Graphs
In an undirected graph, edges have no orientation. If an edge connects vertex $u$ and vertex $v$, the connection is mutual. It's a two-way street. Mathematically, an edge is an unordered pair of vertices, denoted $\{u,v\}$.

• Analogy: A friendship network on Facebook. If you are friends with someone, they are also friends with you. The relationship is inherently bidirectional.

Directed Graphs (or Digraphs)
In a directed graph, each edge has a specific direction, represented by an arrow. An edge from vertex $u$ to vertex $v$ does not imply an edge from $v$ to $u$. Mathematically, an edge is an ordered pair of vertices, denoted $(u,v)$.

• Analogy: A follower network on Twitter. You can follow someone without them following you back. The relationship is one-way.

The following video from WilliamFiset, a well-known competitive programming educator, provides clear explanations of these two types.

2. Unweighted vs. Weighted Graphs

The second classification depends on whether edges have an associated numerical value.

Unweighted Graphs
In an unweighted graph, the edges simply represent a connection. All connections are treated equally. The primary concern is reachability and the number of hops between vertices, not the "cost" of traversing an edge. In many contexts, unweighted graphs are assumed to have a uniform edge weight of 1.

• Analogy: A simple social network where you are either friends with someone or not. The connection exists, but there's no value attached to it.

Weighted Graphs
In a weighted graph, each edge is assigned a numerical value called a weight. This weight can represent various concepts depending on the problem, such as distance, cost, time, capacity, or any other measurable quantity.

• Analogy: A road map where the edges are roads and the weights are the distances in kilometers or the time it takes to travel between cities. Problems like finding the "shortest path" are central to competitive programming and rely on weighted graphs.

To solidify your understanding, continue with the WilliamFiset video.

Summary and Further Reading

You have now learned the four fundamental graph types that arise from combining these two classifications:

1. Undirected Unweighted Graph: Simple, two-way connections.
2. Undirected Weighted Graph: Two-way connections with a cost/distance.
3. Directed Unweighted Graph (Digraph): One-way connections.
4. Directed Weighted Graph (Weighted Digraph): One-way connections with a cost/distance.

The following image shows these types and hints at other classifications we will explore later in the course, such as cyclic, acyclic, sparse, and dense graphs.

To review and reinforce these definitions, please read through the following sections from the GeeksforGeeks article on graph types.

Conclusion

In this introductory lesson, you've taken the essential first step of learning the fundamental language of graph theory. You can now define a graph and its components (vertices and edges) and classify any given graph based on its directionality and edge weights. These concepts are the building blocks for every algorithm and data structure we will cover.

Key Takeaways:

• A graph is a structure $G=(V,E)$ composed of a set of vertices $V$ and a set of edges $E$.
• Edges in an undirected graph are bidirectional (unordered pairs), while edges in a directed graph are one-way (ordered pairs).
• Edges in an unweighted graph represent simple connections, while edges in a weighted graph each have an associated numerical value.

In our next lesson, we will begin to quantify the properties of graphs. We will define the concept of a vertex's degree (and its directed graph counterparts, in-degree and out-degree) and explore a foundational theorem known as the Handshaking Lemma. This will prepare us for our first explorations of how to represent and traverse graphs in code.