[Math] Calculating Adjacency Matrix

graph theorylinear algebramatrices

I'm having trouble understanding the concept, I know it is pretty simple but could someone help me out.

Assume that I have the following:

$V = \begin{bmatrix}
0&0&1 \\
0&0&1 \\
1&0&0
\end{bmatrix}$

This is an undirected graph, now I want to find the Adjacency matrix, which, is all the elements that are in the set.

So I will have

$V \in V =
\left\{\begin{matrix}(v1, v1), (v1, v2), (v1, v3), (v2, v2), (v2, v1) ……
\end{matrix}\right.$

I don't understand this however, in the formula, it says to put a "1" it's in the subset.. However, do I put a 1 if it's in the subset WHERE the value is "1" in the matrix $V$ or is "1" put where only the subset can exist.. I.e. $(v1, v1)$ would therefore have "0"?

Thanks

EDIT:

In this example, the following is given:

G = [0, 0, 1; 0, 0, 1; 1, 1, 0]; xy = [1 1; 0 0 ; 2 0];

Therefore, what does xy represent in this example, if G is the adjacency matrix? I'm guessing that it represents the edges, but, I don't know how to calculate these for a given matrix.

Best Answer

If $V$ is the adjacency matrix, then the graph has verices $\mathcal V=\{v_1,v_2,v_3\}$ and edges $\mathcal E = \{(v_1,v_3), (v_2,v_3), (v_3,v_1)\}$

Related Solutions

[Math] How to find the adjacency matrix for the nodes of an n-dimensional finite grid

Ok, so I worked it out, after a lot of trial and error. Here is the code that I'm using in python. If there is a better way of doing this, I would happily accept another answer.

import numpy as np

def _unserialise_coordinate(serial, spacing):
    coord = []
    for i in range(len(spacing)):
        coord.append(int(np.floor(serial/spacing[i])))
        serial = int(serial % spacing[i])

    return(coord)

def _serialise_coordinate(coord, spacing):
    return(np.dot(coord, spacing))

def _generate_adjacency_matrix(grid_dimensions):
    """Generate an adjacency matrix for nodes of an orthotopic grid with
    dimensions given by grid_dimensions
    """
    n_centres = np.prod(grid_dimensions)

    adjacency = np.zeros((n_centres, n_centres))

    spacing = [int(np.prod(grid_dimensions[(k+1):])) for k in range(len(grid_dimensions))]

    for i in range(n_centres):
        coord = _unserialise_coordinate(i, spacing)
        neighbours = []
        for d in range(len(grid_dimensions)):
            if coord[d] > 0:
                down = coord.copy()
                down[d] -= 1
                neighbours.append(down)
            if coord[d] < (grid_dimensions[d] - 1):
                up = coord.copy()
                up[d] += 1
                neighbours.append(up)

        for neighbour in neighbours:
            serial = _serialise_coordinate(neighbour, spacing)
            adjacency[i,serial] = 1

    return(adjacency)

[Math] Relation between Adjacency Matrix and Incidence Matrix

What does each column $b_j$ of B encode, geometrically?
Can you show that $b_i\cdot b_j$ computes the number of edges that vertex $i$ and $j$ share?
The theorem should now be straightforward: consider the three cases where two vertices $i,j$ are adjacent, not adjacent, and equal.

Related Question