Reachability in graphs using adjacent matrix

Question

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?

Answer 1

First, observe a few facts:

1. $M_G^{[i]} = M_G^i$
2. $M_G^{[\infty]} = M_G^\infty$ is the transitive closure of graph $G$.
3. $(A\circ B)_{ij}=1$ if and only if $N_{G_A}(v_i) \cap N_{G_B}(v_j) \neq \emptyset$.
4. $G_{A_{i+1}}$ is obtained from $G_{A_i}$ by addition or removal of exactly one edge.
5. 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$:

1. $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$
2. $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$.
3. $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.