Chapter Problems

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