Reachability in graphs using adjacent matrix Assuming a graph $G$ with $N$ nodes distributed in a $\mathcal{L}\times\mathcal{L}$ area randomly. There is an edge between two nodes if and only if the Euler distance between them is equal or less than $\mathcal{R}$. The adjacent matrix is $A$. We define an operation on adjacent matrix "$\circ$". For adjacent matrix $A$ and $B$
$$C=A\circ B$$
$$ c_{ij}=\left\{
\begin{array}{rcl}
0       &      & {\sum_{k=1}^{N}a_{ik}b_{kj}=0}\\
\\
1       &      & {\sum_{k=1}^{N}a_{ik}b_{kj}>0}
\end{array} \right. $$
$A^{[1]}=A$, $A^{[i+1]}=A^{[i]}\circ A$.
Define the intial adjacent matrix $A_0=A$. We select a pair of elements randomly from $A_i$ :$A_i(m,n)$ and $A_i(n,m)$. $A_{i+1}(m,n)=A_{i+1}(n,m)=1-A_{i}(m,n)=1-A_{i}(n,m)$.
Other element of $A_{i+1}$ is equal to the corresponding element of $A_i$.
Then we can get a series of matrix $A_0, A_1, \cdots, A_s$.
There comes the question: $A_0^{[\infty]} \circ A_1^{[\infty]} \circ A_2^{[\infty]} \circ \cdots \circ  A_s^{[\infty]}$=$?$
I have waited for more than a week? Could anyone help?
 A: First, observe a few facts:


*

*$M_G^{[i]} = M_G^i$

*$M_G^{[\infty]} = M_G^\infty$ is the transitive closure of graph $G$.

*$(A\circ B)_{ij}=1$ if and only if $N_{G_A}(v_i) \cap N_{G_B}(v_j) \neq \emptyset$.

*$G_{A_{i+1}}$ is obtained from $G_{A_i}$ by addition or removal of exactly one edge.

*If the added/removed edge is not a bridge, then $A_i^{[\infty]}=A_{i+1}^{[\infty]}=A_i^{[\infty]} \circ A_{i+1}^{[\infty]}$.


All of the above are easily proven. Here we claim that if the added/removed edge is a bridge, then $A_i^{[\infty]} \circ A_{i+1}^{[\infty]}$ equals to the operand that corresponds to the graph with the extra edge. Now we prove the stronger proposition that if $G_B$ is obtained from $G_A$ by addition of some number of edges, then $A^{[\infty]} \circ B^{[\infty]} = B^{[\infty]}$. Let $v_i$ and $v_j$ be two arbitrary vertices. There are three cases for $v_i$ and $v_j$:


*

*$v_i$ and $v_j$ are in the same component of $G_A$ and in the same component of $G_B$. Then $(A^{[\infty]} \circ B^{[\infty]})_{ij} = 1$ because $v_i \in N_{G_A}(v_i) \cap N_{G_B}(v_j)$. Thus $(A^{[\infty]} \circ B^{[\infty]})_{ij}=B_{ij}^{[\infty]}=1$

*$v_i$ and $v_j$ are in different components of $G_A$ but in the same component of $G_B$. Then with the same argument $(A^{[\infty]} \circ B^{[\infty]})_{ij}=B_{ij}^{[\infty]}=1$.

*$v_i$ and $v_j$ are in different component in both $G_A$ and $G_B$. Then obviously $N_{G_A}(v_i) \cap N_{G_B}(v_j) = \emptyset$ and thus $(A^{[\infty]} \circ B^{[\infty]})_{ij}=B_{ij}^{[\infty]}=0$.


That completes the proof that $A^{[\infty]} \circ B^{[\infty]}=B^{[\infty]}$.
By this proposition, it can be proven by induction that $A_0^{[\infty]} \circ A_1^{[\infty]} \circ A_2^{[\infty]} \circ \cdots \circ  A_s^{[\infty]}$ equal to the transitive closure of the graph that has every edge that any of the $G_{A_i}$ had. The exact value, of course, can not be evaluated without knowledge of $s$ and the way we choose the edges to be added/removed.
