Graphs and Matrices

A walk of length $k$ in a digraph is a succession of $k$ arcs joining two vertices. A trail is a walk in which all the arcs (but not necessarily all the vertices) are distinct. A path is a walk in which all the arcs and all the vertices are distinct. Show that the number of walks of length $k$ from vertex $i$ to vertex $j$ in a digraph $D$ with $n$ vertices is given by the $ij$-th element of the matrix $A^{k}$, where $A$ is the adjacency matrix of the digraph.

Consider a digraph. The out-degree of a vertex $v$ is the number of arcs incident from $v$ and the in-degree of a vertex $V$ is the number of arcs incident to $v$. Loops count as one of each.

Determine the in-degree and the out-degree of each vertex in the digraph given by the adjacency matrix

and hence determine if it is an Eulerian graph. Display the digraph and determine an Eulerian trail.

A digraph is strongly connected if there is a path between every pair of vertices. Show that if $A$ is the adjacency matrix of a digraph $D$ with $n$ vertices and $B$ is the matrix

then $D$ is strongly connected iff each non-diagonal element of $B$ is greater than 0.

Write down the adjacency matrix $A$ for the digraph shown. Calculate the matrices $A^{2}$, $A^{3}$ and $A^{4}$. Consequently find the number of walks of length 1, 2, 3 and 4 from $w$ to $u$. Is there a walk of length 1, 2, 3, or 4 from $u$ to $w$? Find the matrix $B=A+A^{2}+A^{3}+A^{4}$ for the digraph and hence conclude whether it is strongly connected. This means finding out whether all off diagonal elements are nonzero.

The digraph for Problem 21.1.4.

A graph $G(V,E)$ is a set of nodes $V$ (points, vertices) connected by a set of links $E$ (edges, lines). We assume that there are $n$ nodes. The adjacency ($n \times n$) matrix $A=A(G)$ takes the form with 1 in row $i$, column $j$ if $i$ is connected to $j$, and 0 otherwise. Thus $A$ is a symmetric matrix. Associated with $A$ is the degree distribution, a diagonal matrix with row-sums of $A$ along the diagonal, and 0's elsewhere. We assume that $d_{ii}>0$ for all $i=1,2,\ldots ,n$. We define the Laplacian as $L := D-A$. Let

A graph $G(V,E)$ is a set of nodes $V$ (points, vertices) connected by a set of links $E$ (edges, lines). We assume that there are $n$ nodes. The adjacency ($n \times n$) matrix $A=A(G)$ takes the form with 1 in row $i$, column $j$ if $i$ is connected to $j$, and 0 otherwise. Thus $A$ is a symmetric matrix. Associated with $A$ is the degree distribution $D$, a diagonal matrix with row-sums of $A$ along the diagonal, and 0's elsewhere. $D$ describes how many connections each node has. We define the Laplacian as $L := D-A$. Let $A = (a_{ij})$, i.e. $a_{ij}$ are the entries of adjacency matrix. Find the minimum of the weighted sum

with the constraint $\overrightarrow {x}^{T} \overrightarrow {x}=1$, where $\overrightarrow {x}^{T} = (x_{1}, x_{2}, \ldots , x_{n})$. Use the Lagrange multiplier method. The sum is over all pairs of squared distances between nodes which are connected, and so the solution should result in nodes with large numbers of inter-connections being clustered together.

Find the eigenvalues of the three adjacent matrices

provided by three simple graphs. Find the ``energy'' $E(G)$ of each graph defined by

Consider the two directed graphs with the adjacency matrices

Consider the directed graph $G$

The directed graph G of Problem 21.1.9.

Let $G$ be a graph with vertices $V$ and edges $E$. The graph $G$ is transitive if $(v_{1},v_{2}), (v_{2},v_{3}) \in E$ implies that $(v_{1},v_{3}) \in E$. The transitive closure $\widetilde{G}$ of $G$, is the smallest transitive graph $\widetilde{G}$ which has $G$ as a subgraph. Let $H$ be the adjacency matrix for $G$ and $\widetilde{H}$ be the adjacency matrix for $\widetilde{G}$. If $(H)_{ij}=1$ and $(H)_{jk}=1$ then $(\widetilde{H})_{ij} = (\widetilde{H})_{jk} = (\widetilde{H})_{ik} = 1$. Write a C++ program which finds $\widetilde{H}$ for any given adjacency matrix $H$. Find the adjacency matrix for the transitive closure of the graph given by the adjacency matrix

Compare the two adjacency matrices

Do they admit an Euler path?

Consider the adjacency matrix

Is there a Hamilton cycle?

Let $G$ be a graph with vertices $V_{G} = \left\{ 1,\ldots ,n_{G}\right\}$ and edges $E_{G} \subseteq V_{G} \times V_{G}$. The $n_{G} \times n_{G}$ adjacency matrix $A_{G}$ is given by $(A_{G})_{ij} = \chi_{E_{G}}(i,j) \in \left\{ 0,1\right\}$ where $i,j \in V$. In the following products of graphs $G_{1}$ and $G_{2}$ with $n_{G_{1}} n_{G_{2}} \times n_{G_{2}} n_{G_{2}}$ adjacency matrices. The rows and columns are indexed by $V_{G_{1}} \times V_{G_{2}}$, where we use the ordering $(i,j) \leq (k,l)$ if $i<k$ or, $i=k$ and $j \leq l$.

The cartesian product $G_{1} \times G_{2}$ of two graphs $G_{1}$ and $G_{2}$ is the graph with vertices

and edges

It follows that

where $\boxplus$ is the usual addition with the convention that $1 \boxplus 1 = 1$. Thus

The lexicographic product $G_{1} \bullet G_{2}$ of two graphs $G_{1}$ and $G_{2}$ is the graph with vertices

and edges

Thus $E_{G_{1} \times G_{2}} \subseteq E_{G_{1} \bullet G_{2}}$. It follows that

Hence

Here $\overrightarrow {1}_{n_{G_{1}}}$ is the $n_{G_{2}} \times n_{G_{2}}$ with every entry equal to 1.

The tensor product $G_{1} \otimes G_{2}$ of two graphs $G_{1}$ and $G_{2}$ is the graph with vertices

and edges

It follows that

Thus $A_{G_{1} \otimes G_{2}} = A_{G_{1}} \otimes A_{G_{2}}$ where $\otimes$ is the Kronecker product of matrices.

The normal product $G_{1} \star G_{2}$ of two graphs $G_{1}$ and $G_{2}$ is the graph with vertices

and edges

Thus