anonymous
  • anonymous
Given an undirected graph H, let C be the adjacency matrix of H. What is the meaning of entries in \(C^n\)?
Discrete Math
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
schrodinger
  • schrodinger
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
KingGeorge
  • KingGeorge
If I'm remembering correctly...and I may not be, the \(i,j\)-th entry in \(C^n\) is the number of paths of length \(n\) between the \(i\)-the vertex and the \(j\)-th vertex.
anonymous
  • anonymous
How do you know? :O
KingGeorge
  • KingGeorge
I think I saw this in a combinatorics class I had last year. I could probably dig out the proof if you want.

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

anonymous
  • anonymous
Ah! I would love to know the proof, at least to understand why. :)
anonymous
  • anonymous
By the way, if the proof involves MI, please, please do not post it...
KingGeorge
  • KingGeorge
What do you mean by MI?
anonymous
  • anonymous
Ehm, sorry, induction.
KingGeorge
  • KingGeorge
Ah. Well my proof does do it by induction...
anonymous
  • anonymous
King George is correct. Wahid yes ;)
anonymous
  • anonymous
Haha, because the hint of the proof is to prove by induction, and I don't want to copy your work, lol!
anonymous
  • anonymous
Would you mind explaining the intuition behind?
KingGeorge
  • KingGeorge
Well, it's actually a pretty short proof. The main part that uses induction, is where you write\[C^n=C^{n-1}C,\]and for a given entry \(C_{ij}\), you can write\[(C^{n-1}C)_{ij}=\sum_{k}(C^{n-1})_{ik}C_{kj}\]
KingGeorge
  • KingGeorge
After that, it's a counting argument.
anonymous
  • anonymous
This is really rough but you can think of it like this: the i,jth entry of C is 1 only if i and j are connected. Now if we multiply C by itself, to get the i,kth entry (of C^2), we would be multiply the ith row of C by the kth column of C now the ith row would be 1's in places where i is adjacent to some other node and 0's elsewhere and the kth column would be the same, 1's only where k was adjacent to some node, and 0's elsewhere so to get the i,kth entry of C^2, it would only be non-zero if i and k were adjacent to some other node, which would imply that there was a path of length 2 from i to k, and everytime they shared a common node, it would add 1 to the entry, so the entry counts the number of patsh of length 2 and then u go up from there, each power basically extends the path by 1 edge if it is possible, (if it not possible the product would just be 0)
KingGeorge
  • KingGeorge
So I guess the underlying idea of the proof, is to count the number of paths of length \(n-1\) from a vertex \(i\) to a vertex \(k\), and then the number of paths of length \(1\) from the vertex \(k\) to the vertex \(j\). And then let \(k\) vary over the whole graph.
anonymous
  • anonymous
Not sure if it looks good. Base case: When n=1, \(A^1 = A\), which shows the number of path to vertex j, \(v_j\), to vertex i, \(v_i\), with the path length being 1. So, it is true for n=1. Induction step: Assume it is true for n=m-1. Consider the i,j-th entry of \(A^m\), \[(A^m)_{ij}\]\[ = (AA^{m-1})_{ij} \]\[= A_{i1}(A^{m-1})_{1j} + A_{i2}(A^{m-1})_{2j} +...+A_{in}(A^{m-1})_{nj}\]\[=\sum_{k}A_{ik}(A^{m-1})_{kj}\] Consider \( A_{i1}(A^{m-1})_{1j}\), \( A_{i1}(A^{m-1})_{1j}\) is the number of paths of length 1 from \(v_i\) to \(v_1\) times the number of paths of length m-1 from \(v_1\) to \(v_j\), which is equal to the number of paths of length m from \(v_i\) to \(v_j\) with \(v_1\) being the second vertex visited. This argument follows for each term \( A_{ik}(A^{m-1})_{kj}\), where \( A_{ik}(A^{m-1})_{kj}\) is the number of paths of length m from \(v_i\) to \(v_j\) with \(v_k\) being the second vertex visited. Hence, \(\sum_{k}A_{ik}(A^{m-1})_{kj}\) is the total number of all possible paths with length m from \(v_i\) to \(v_j\).
experimentX
  • experimentX
let's take this graph for example http://en.wikipedia.org/wiki/Adjacency_matrix#Examples also let's take that we are at vertex 3 of that graph.
experimentX
  • experimentX
from 3, you can go to vertex 2 or vertex 4. now let us represent the vertex 3 by \[ V = \begin{bmatrix} 0\\ 0\\ 1\\ 0\\ 0\\ 0 \end{bmatrix} \] Let the adjacency matrix be A. \[ A V = \begin{bmatrix} 0\\ 1\\ 0\\ 1\\ 0\\ 0 \end{bmatrix} \]
experimentX
  • experimentX
it means that ... after one step, either you end up in vertex 2 or vertex 4. therefore it makes sense to construct adjacency matrix this way, and represent state by vectors.
experimentX
  • experimentX
now let's look at \[ A^2 V = A \begin{bmatrix} 0\\ 1\\ 0\\ 1\\ 0\\ 0 \end{bmatrix} = A \left( \begin{bmatrix} 0\\ 1\\ 0\\ 0\\ 0\\ 0 \end{bmatrix} +\begin{bmatrix} 0\\ 1\\ 0\\ 0\\ 0\\ 0 \end{bmatrix} \right)\]

Looking for something else?

Not the answer you are looking for? Search for more explanations.