Problem 24 - Discrete Mathematics with Applications

Question

A column of the adjacency matrix of a digraph is zero. Prove that the digraph is not strongly connected.

Step-by-Step Solution

Answer

If a column of the adjacency matrix of a digraph is zero, it means that there exists a vertex, say V, with no incoming edges. This implies that for any other vertex U, there is no directed path from U to V. Since there exists a pair of vertices U and V without directed paths between them, the digraph is not strongly connected.

Step 1: Understanding adjacency matrix and strongly connected digraph

For a digraph with n vertices, its adjacency matrix is an n × n matrix, where the element at the (i, j) entry is 1 if there is an edge from vertex i to vertex j, and 0 otherwise. In other words, if there is an edge from vertex i to vertex j, the adjacency matrix has a non-zero entry in the j-th column. On the other hand, a digraph is strongly connected if for every pair of vertices (u, v), there is a directed path from u to v and a directed path from v to u.

Step 2: First step: Analyzing the zero column in the adjacency matrix

Let's assume that there is a column in the adjacency matrix of a digraph with all its elements being zero. This means that there exists a vertex, say V, with no incoming edges. In other words, no other vertex in the digraph has a direct edge toward vertex V.

Step 3: Second step: Proving the absence of a directed path

Now, let's consider any other vertex in the digraph, say U. Since there is no direct edge from any vertex to V, it implies that there is no directed path from U to V, as the path would require at least one directed edge to reach V.

Step 4: Third step: Concluding that the digraph is not strongly connected

As we have shown that there is no directed path from U to V for any vertex U, this directly contradicts the definition of a strongly connected digraph. Therefore, we can conclude that the digraph is not strongly connected.

Key Concepts

Adjacency Matrix

The adjacency matrix is a fundamental concept in graph theory, often used to represent graphs succinctly in matrix form. For a directed graph, or digraph, the adjacency matrix is a square matrix with dimensions corresponding to the number of vertices in the graph. The entry in the matrix located at the position \((i, j)\) is 1 if there is a directed edge from vertex \(i\) to vertex \(j\). Otherwise, this entry is 0.

• This setup allows for a clear and concise representation of connections within the graph.
• A zero in any position indicates the absence of a direct path from one vertex to another.

An interesting property to observe in adjacency matrices is when a whole column consists of zeros. It indicates that the corresponding vertex has no incoming edges from any other vertex in the graph. This can have important implications for the structure and connectivity of the graph, especially concerning paths and reachability.

Strongly Connected Digraph

A digraph is referred to as strongly connected when there's a path from every vertex to every other vertex, and vice versa. This means for any two vertices \(u\) and \(v\), there should be a directed path from \(u\) to \(v\) as well as from \(v\) to \(u\).
To determine strong connectivity using the adjacency matrix, examine its structure for any zero columns or rows:

• A column full of zeros indicates a vertex with no incoming edges, disrupting the possibility of a path from any vertex to this one.
• A row of zeros would indicate no outgoing paths from a vertex, which similarly affects strong connectivity.

For a digraph to qualify as strongly connected, each vertex must reach and be reachable from every other vertex with directed paths. A zero column in the adjacency matrix logically disproves such connectivity, hence showing the graph is not strongly connected.

Directed Path

A directed path in a digraph refers to a sequence of directed edges from a starting vertex \(u\) to an ending vertex \(v\), such that the path obeys the direction of edges. Paths are crucial for determining the connectivity of the graph.
Each directed edge in the sequence must be aligned directionally:

• If a path exists from vertex \(u\) to \(v\), there will be a set of directed edges that takes you from \(u\) through intermediate vertices, if any, to \(v\).
• The absence of such paths between any two vertices means the graph lacks strong connectivity.

In the context of the adjacency matrix, achieving a directed path from one vertex to another implies non-zero entries across a row and column where vertices connect one after another. When a vertex lacks incoming paths (as shown by a zero column), it indicates that no other vertex can reach this one, precluding it from forming part of any completely accessible network of paths. This is a fundamental blockage to claiming strong connectivity in the graph.