Skip to main content
adjacency -> incidence.
Source Link

Label the vertices from 1 to $n$. Let $A = (a_{ij})$ be the adjacencyincidence matrix. (The entry $a_{ij}$ is 1 if there is an arrow from vertiex $i$ to vertex $j$ and $a_{ij} = 0$ otherwise.)

Then, the number of paths from vertex $i$ to vertex $j$ of length $k$ is the $a_{ij}$ entry of $A^k$. (This is a well known result that follows from the definitions of matrix multiplication and adjacencyincidence matrix.)

So, you can determine the (multi-)set of path lengths from $i$ to $j$ by forming each of the $n$ powers and looking at the $a_{ij}$ entry.

Label the vertices from 1 to $n$. Let $A = (a_{ij})$ be the adjacency matrix. (The entry $a_{ij}$ is 1 if there is an arrow from vertiex $i$ to vertex $j$ and $a_{ij} = 0$ otherwise.)

Then, the number of paths from vertex $i$ to vertex $j$ of length $k$ is the $a_{ij}$ entry of $A^k$. (This is a well known result that follows from the definitions of matrix multiplication and adjacency matrix.)

So, you can determine the (multi-)set of path lengths from $i$ to $j$ by forming each of the $n$ powers and looking at the $a_{ij}$ entry.

Label the vertices from 1 to $n$. Let $A = (a_{ij})$ be the incidence matrix. (The entry $a_{ij}$ is 1 if there is an arrow from vertiex $i$ to vertex $j$ and $a_{ij} = 0$ otherwise.)

Then, the number of paths from vertex $i$ to vertex $j$ of length $k$ is the $a_{ij}$ entry of $A^k$. (This is a well known result that follows from the definitions of matrix multiplication and incidence matrix.)

So, you can determine the (multi-)set of path lengths from $i$ to $j$ by forming each of the $n$ powers and looking at the $a_{ij}$ entry.

Source Link

Label the vertices from 1 to $n$. Let $A = (a_{ij})$ be the adjacency matrix. (The entry $a_{ij}$ is 1 if there is an arrow from vertiex $i$ to vertex $j$ and $a_{ij} = 0$ otherwise.)

Then, the number of paths from vertex $i$ to vertex $j$ of length $k$ is the $a_{ij}$ entry of $A^k$. (This is a well known result that follows from the definitions of matrix multiplication and adjacency matrix.)

So, you can determine the (multi-)set of path lengths from $i$ to $j$ by forming each of the $n$ powers and looking at the $a_{ij}$ entry.