CT Week 10

📚

Representation of Graph as Adjacency Matrix

An adjacency matrix is a way to represent a graph using a square matrix. Each cell in the matrix indicates whether a pair of vertices is connected by an edge. For a graph with V vertices, the adjacency matrix A is a V × V matrix where:

• A[i][j] = 1 if there is an edge between vertex i and vertex j.
• A[i][j] = 0 if there is no edge between vertex i and vertex j.

This representation is particularly useful for dense graphs where the number of edges is large. For example, consider a graph with 4 vertices:

        0 - 1
        |   |
        2 - 3
    

The adjacency matrix for this graph would be:

        0 1 1 0
        1 0 0 1
        1 0 0 1
        0 1 1 0
    

One-Hop Neighbors

One-hop neighbors of a vertex in a graph are the vertices that are directly connected to it by an edge. In terms of the adjacency matrix, if A[i][j] = 1, then vertex j is a one-hop neighbor of vertex i. This concept is crucial for understanding immediate connections and direct relationships in a network.

For example, in the graph represented above, the one-hop neighbors of vertex 0 are vertices 1 and 2.

Two-Hop Neighbors

Two-hop neighbors of a vertex are the vertices that can be reached by traversing exactly two edges. In the adjacency matrix, this can be determined by squaring the matrix A. If (A^2)[i][j] > 0, then vertex j is a two-hop neighbor of vertex i. This helps in analyzing indirect connections and the extended reach of a vertex within the graph.

For example, in the graph represented above, the two-hop neighbors of vertex 0 are vertices 3.