91Ó°ÊÓ

An adjacency matrix is a fundamental concept in graph theory, representing the graph's structure in a matrix form. It is especially useful when dealing with complex graphs. The matrix is square, with rows and columns corresponding to the vertices (or nodes) of the graph. Each element within the matrix, denoted as \( a_{ij} \), indicates whether there is a direct connection, or edge, from vertex \( i \) to vertex \( j \).

• If \( a_{ij} = 1 \), it signifies there is an edge between vertex \( i \) and vertex \( j \).
• If \( a_{ij} = 0 \), it indicates no direct edge between the two.

This representation allows for a clear and organized way to view all connections within a graph, making it a powerful tool to understand and visualize relationships between different vertices. It's particularly useful for computational tasks like checking connectivity or searching paths.

In graph theory, vertices and edges are the building blocks of any graph. A vertex, or node, represents a singular point in the graph, and an edge represents a connection between two vertices.

• Vertices are often areas of interest or states in problems like networking or mapping.
• Edges can denote relationships or pathways between these areas.

In an adjacency matrix, vertices are represented by the rows and columns. For example, if you encounter a matrix with three rows and columns, the graph has three vertices. The edges in the graph correspond to non-zero values in the matrix.
By analyzing these connections, one can determine the flow of information, transportation routes, or correlations, depending on the graph's purpose.

Graphs can be categorized based on the nature of their edges: undirected or directed. This distinction is crucial because it affects how the adjacency matrix is interpreted. In an **undirected graph**, each edge is bidirectional. This means that if there is a link between vertices \( i \) and \( j \), it works both ways.

• The adjacency matrix of an undirected graph is symmetric, i.e., \( a_{ij} = a_{ji} \).
• These graphs are perfect for modeling mutual relationships, like social connections or partnerships.

In contrast, a **directed graph** has edges with direction, implying that an edge from vertex \( i \) to vertex \( j \) does not necessarily imply a reverse connection.

• For directed graphs, the adjacency matrix does not need to be symmetric.
• These graphs are often used in scenarios like navigation systems, where direction matters.

Understanding whether a graph is directed or undirected is essential as it informs how paths and connectivity are analyzed.