Graph Theory Meets Number Theory
Introduction to Graph Theory
What Is a Graph?
When you hear the word "graph," you might picture a bar chart or a line graph from a math class. In this context, however, a graph is something different. It’s a way of modeling connections between things.
Think about a social network. You have people (the things) and friendships (the connections). A graph is just a formal way to represent this kind of network. It's made up of two simple components: vertices and edges.
Vertex
noun
A point or node in a graph. In our social network example, each person would be a vertex.
Edge
noun
A line that connects two vertices. An edge represents a relationship or connection between the two vertices.
Together, a set of vertices and the edges that connect them form a graph. Let's look at a simple one.
Directed and Undirected Graphs
Edges can have a direction, or they can be neutral. This distinction gives us two main types of graphs.
An undirected graph has edges that are like two-way streets. If there's an edge between vertex A and vertex B, the connection goes both ways. Think of friendships on Facebook: if you are friends with someone, they are also friends with you. The relationship is mutual.
A directed graph, on the other hand, has edges that are like one-way streets. These edges are typically drawn as arrows to show their direction. A connection from vertex A to vertex B doesn't imply a connection from B to A. This is like Twitter (or X): you can follow someone without them following you back.
Key Properties
Graphs have many properties, but two of the most basic are adjacency and connectivity.
Adjacency: Two vertices are adjacent if they are connected by an edge. It’s as simple as that. In the directed graph above, A is adjacent to B, but B is not adjacent to A.
Connectivity describes whether you can get from any vertex to any other vertex in the graph. An undirected graph is connected if there is a path between every pair of distinct vertices. If not, it's disconnected.
A disconnected graph is essentially made of two or more separate smaller graphs. Imagine a social network with two groups of friends that have no connections between them. You couldn't get from a person in the first group to a person in the second group by following friendship links.
For directed graphs, the idea of connectivity is a bit more complex, involving concepts like "strong" and "weak" connectivity, but the basic principle is the same: it's about whether vertices are reachable from one another.
Time to review these core concepts.
Let's see what you've learned.
In the context of computer science, what are the two fundamental components of a graph?
You are modeling a social network where users can 'subscribe' to another user's content feed. This relationship is not necessarily mutual. What type of graph best represents this network?
These building blocks, vertices, edges, and their properties, are the foundation of graph theory. They provide a powerful way to model and analyze relationships in a huge variety of systems.