Graph Theory: find the connected components of graph given the matrix

Question

I drew the graph but it's a complete mess so I assume there is some formula for this.

I confess I am not entirely sure of what I am supposed to do here. I think I am supposed to find subsets of vertices among which there is a path to each of them. So maybe I have to find the vertex or vertices which connect the two components somehow?

Answer 1

If you really want a formula, let's call $A$ your adjacency matrix of size $n$ (here, $n=6$).

$A$ represents all the paths of length 1 between two nodes, $A^2$ represents all paths of length 2 between two nodes, etc. Any path between two nodes in a graph with n nodes is at most of size $n-1$, so you need to compute $S = \sum\limits_{i=1}^{n-1}A^{i}$. $s_{ij}$ will then denote the number of paths of length at most $n-1$ between $i$ and $j$. There is a path between nodes $i$ and $j$ if and only if $s_{ij}$ is nonzero:

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

Answer 2

Writing the matrix out as a list of adjacencies \begin{array} & & & 1\to 3 & 1 \to 4 & 1 \to 5 \\ & & 2\to 3\\ & & & & & 3 \to 6\\ 4 \to 1 & 4 \to 2 & 4 \to 3 & & 4 \to 5 & 4 \to 6\\ 5\to 1 & 5 \to 2 & & 5 \to 4 & & 5 \to 6 \\ & & 6 \to 3 \end{array} some of the first things that jump out at us are:

• $4$ and $5$ are connected to lots of vertices and to each other
• $3$ and $6$ are connected to each other and nothing else.

So $\{3,6\}$ will be one connected component, since when you're at one of those vertices you're stuck and can't reach any others; $\{4,5,\dots\}$ is the beginning of another.

Looking at $1$, we see that it has edges to both of the components we've found so far; so it could become part of either one or start a new one. It can't be part of the $\{3,6\}$ component, because those vertices don't have a way to reach $1$, but vertices $4$ and $5$ do both have edges back to $1$ (just one of those would be enough). So $1$ joins $4$ and $5$ in a component $\{1,4,5,\dots\}$.

Looking at $2$, we see that it only has edges to $3$, so it is either a new component or part of the $\{3,6\}$ component. But it can't be part of that component, because neither $3$ nor $6$ has a way to reach $2$. So $\{2\}$ is its own component.

Now we've looked at all the vertices and obtained three components: $C_1 = \{1,4,5\}$, $C_2 = \{2\}$, and $C_3 = \{3,6\}$.