Context Graphs Explained
Introduction to Graph Theory
The Building Blocks of Networks
Think about your social media connections. You're connected to friends, who are connected to their friends, forming a giant web. Or consider a map of a subway system, with stations linked by train lines. Both of these are examples of networks, and in mathematics, we study them using a structure called a graph.
A graph is simply a way of representing relationships between objects.
Graphs have two basic components: vertices and edges. Let's break those down.
vertex
noun
An object or point in a graph. It's also commonly called a node.
edge
noun
A connection or link between two vertices.
Different Kinds of Relationships
Not all relationships are the same, so we have different types of graphs to model them. The distinctions usually come down to two questions: Is the relationship mutual? And does the connection have a value attached to it?
An undirected graph has edges that are two-way streets. If vertex A is connected to vertex B, then B is also connected to A. Think of a friendship on Facebook; it's a mutual connection.
A directed graph has edges with a specific direction, represented by arrows. If an edge goes from A to B, it doesn't automatically mean there's one going from B to A. This is like Twitter (or X), where you can follow someone without them following you back.
An unweighted graph cares only about whether a connection exists. The edges are all equal. It tells you that two stations are connected, but not how far apart they are.
A weighted graph adds more information. Each edge has a numerical value, or "weight," assigned to it. This weight can represent distance, travel time, cost, or the strength of a relationship. A GPS uses a weighted graph to find the fastest route, where edge weights are the time it takes to travel each road.
Describing a Graph
Once we have a graph, we need a language to talk about its features. A few basic properties help us understand a graph's structure.
Degree: The degree of a vertex is the number of edges connected to it. It’s a simple measure of how connected a node is. In a directed graph, we can be more specific: in-degree is the number of incoming edges, and out-degree is the number of outgoing edges.
Path: A path is a sequence of vertices where each adjacent pair is connected by an edge. Think of it as a route you can take through the graph from a starting vertex to an ending one.
Connectivity: An undirected graph is called connected if there is a path between every pair of vertices. If not, the graph is disconnected and is made up of several separate pieces, or components.
These concepts are the foundation of graph theory. By combining them, we can model and analyze all sorts of complex systems, from the internet to the neural networks in our brains.
What are the two fundamental components that make up a graph in mathematics?
A social media platform where friendships are mutual (if you are friends with someone, they are automatically friends with you) is best modeled by what type of graph?