An undirected graph is a fundamental data structure in computer science and mathematics. It is a collection of vertices (also known as nodes) connected by edges. Unlike a directed graph, the edges in an undirected graph have no specific direction, meaning that they can be traversed in both directions.

**Vertices and Edges**

In an undirected graph, vertices represent entities or objects, while edges represent the relationships between these entities. Each edge connects two vertices and denotes that there is a connection or interaction between them. The absence of a direction on the edges implies that the relationship between the vertices is symmetric.

__Example:__

Consider a simple undirected graph representing a social network. The vertices could represent individuals, and the edges could represent friendships between these individuals. Since friendships are usually mutual, an undirected graph accurately models this scenario.

**Adjacency Matrix**

One way to represent an undirected graph is through an adjacency matrix. An adjacency matrix is a square matrix where each row and column correspond to a vertex in the graph. The elements of the matrix indicate whether there is an edge between two vertices.

__Example:__

Let’s consider a small undirected graph with four vertices labeled A, B, C, and D. The adjacency matrix for this graph would be as follows:

A B C D A 0 1 1 0 B 1 0 0 1 C 1 0 0 1 D 0 1 1 0

This matrix tells us that there is an edge between A and B (indicated by “1” at row A, column B), as well as between A and C, B and D, and C and D.

**Adjacency List**

Another way to represent an undirected graph is through an adjacency list. In this representation, each vertex is associated with a list of its adjacent vertices. The adjacency list efficiently captures the connections between vertices.

__Example:__

For the same graph as before, the adjacency list representation would be:

- A: B, C
- B: A, D
- C: A, D
- D: B, C

This list tells us that vertex A is adjacent to vertices B and C, vertex B is adjacent to vertices A and D, and so on.

**Applications of Undirected Graphs**

Undirected graphs have various applications in computer science and beyond. Some common use cases include:

### Social Networks:

Undirected graphs are used to model connections between individuals in social networks like Facebook or LinkedIn.

### Web Page Ranking:

Search engine algorithms like Google’s PageRank use undirected graphs to determine the importance of web pages based on their links.

### Molecular Chemistry:

In chemistry, undirected graphs are used to represent molecules and their bonds.

### Transportation Networks:

Undirected graphs model road networks or flight routes between cities in transportation systems.

**Conclusion**

Undirected graphs play a crucial role in representing relationships between entities or objects. They provide a flexible and intuitive way to analyze connections in various domains. Whether you’re exploring social networks or optimizing web page rankings, understanding undirected graphs is essential for solving complex problems.