Think of a social network. You have people (profiles) and the connections between them (friendships). That's a graph in a nutshell. It’s a way to represent relationships between objects.

The objects are called vertices (or nodes), and the connections are called edges.

This visual language of dots and lines allows us to model all sorts of systems, from computer networks and road maps to molecular structures.

Graphs come in a few different flavors depending on the nature of the relationships they represent.

Undirected vs. Directed An undirected graph is like a friendship on Facebook. If person A is friends with person B, person B is also friends with person A. The connection is mutual. The edges are two-way streets.

A directed graph is more like following someone on Twitter. Just because you follow them doesn't mean they follow you back. The relationship has a direction. The edges are one-way streets, represented by arrows.

Unweighted vs. Weighted In an unweighted graph, the edges simply show that a connection exists. The friendship is either there or it isn't.

In a weighted graph, each edge has a numerical value, or "weight," associated with it. This weight can represent anything from distance between cities on a map, to the cost of a flight, or the strength of a social connection.

Drawing a graph is great for visualization, but a computer needs a more structured way to store it. The two most common methods are the adjacency matrix and the adjacency list.

Let's use a simple graph to see how these work. Consider a graph with four vertices: 1, 2, 3, and 4.

Adjacency Matrix An adjacency matrix is a square grid of numbers. If we have $N$ vertices, we create an $N \times N$ matrix. A '1' at the intersection of a row and column means an edge exists between those two vertices. A '0' means there's no edge.

For our example graph, the adjacency matrix would be:

Notice that the matrix is symmetric across the diagonal. This is always true for undirected graphs.

Adjacency List An adjacency list is often more efficient, especially for graphs with few edges. It's a list where each index corresponds to a vertex, and the value is a list of that vertex's neighbors.

For the same graph:

This representation simply says, "Vertex 1 is connected to vertices 2 and 3," and so on. It's a more direct way of listing the connections.

Once we have a graph, we can analyze its properties. These help us understand its structure.

Degree The degree of a vertex is the number of edges connected to it. In our example graph, vertex 3 has a degree of 3, while vertex 4 has a degree of 1.

For directed graphs, we talk about in-degree (number of incoming edges) and out-degree (number of outgoing edges).

Path A path is a sequence of vertices where each adjacent pair in the sequence is connected by an edge. For instance, a path from vertex 1 to 4 in our example is 1-3-4. Another path is 1-2-3-4.

Cycle A cycle is a path that starts and ends at the same vertex. The path 1-2-3-1 forms a cycle in our graph. A graph with no cycles is called an acyclic graph.

Connectivity An undirected graph is connected if there is a path from any vertex to any other vertex. Our example graph is connected. If we couldn't get from one part of the graph to another, it would be disconnected, consisting of multiple separate components.

These basic concepts are the building blocks for the entire field of graph theory. They give us the language to describe and analyze complex networks.