# 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?

-
Is $A_0$ reflexive? – Untitled Sep 12 '13 at 5:59
Yes, but $A_0$ is uncertain matrix due to the random distribution of nodes. I know the meaning of the result. What I'm confused is how to calculate the result. – xzhh Sep 13 '13 at 2:40
Don't ask multiple questions in one post. It makes it hard to get a good answer. Post the new one separately. – Untitled Sep 13 '13 at 4:36

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.

-
Thank you very much for your reply. I have got a better understanding of the problem. If I reduce $A_0^{[\infty]} \circ A_1^{[\infty]} \circ A_2^{[\infty]} \circ \cdots \circ A_s^{[\infty]}$ to $B_0^{[\infty]} \circ B_1^{[\infty]} \circ B_2^{[\infty]} \circ \cdots \circ B_t^{[\infty]}$, $A_i^{[\infty]} \circ\cdots A_{i+x}^{[\infty]}$-> $B_?^{\infty}$ if there is only addition of edges, then there is only removal of an extra edge from $B_i$ to $B_{i+1}$. If we choose randomly with the same probabilty from all the node pairs and change its state 0<->1, can we calculate the result? – xzhh Sep 13 '13 at 3:17
So you are saying that the edges are selected uniformly at random, and you want to calculate the probability distribution of $A_0^{[\infty]} \circ \cdots \circ A_s^{[\infty]}$, right? Well, we also need to know the nature of $A_0$ and $s$ for that. What about them? – Untitled Sep 13 '13 at 4:33
All the $N$ nodes are distributed randomly in the $L*L$ area and there is an edge between a node pair iff the distance between them is equal to or less than $R$. $A_0$ is not hard to be obtained. What's the meaning of $s$? – xzhh Sep 13 '13 at 4:46
I assume by randomly you mean uniformly with respect to $x$ and $y$ coordinates. right? – Untitled Sep 13 '13 at 8:57
$s$ is the number of edges added or removed. It is the index of last matrix in the statement of the question. – Untitled Sep 13 '13 at 8:59