### Theory NO. 5 : Fibbonacci strikes again!

18Feb09

Today, I noticed an amazing and worth memorizing thing. I turns out that fibbonacci series shows up also in graph theory in one of the simplest graphs:

Where’s Fibbonacci hiden here? Well, the graph can be represented as a folowing matrix:

$M={\left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \\ \end{array}\right]}$

By multiplying the matrix by itself and using induction we get:

$M^{n} ={\left[\begin{array}{ccc} FIB(n) & FIB(n-1) \\ FIB(n-1) & FIB(n-2) \\ \end{array}\right]}$

#### 6 Responses to “Theory NO. 5 : Fibbonacci strikes again!”

1. I haven’t got how does the matrix represent the Graph??

2. The matrix is the representation of the graph in the simplest posible way:
The index of any column or row represents a verticle, and if $a_ij = 1$ then it means that between verticles $v_i$ and $v_j$ exists a path (edge).
It’s also easy to conclude that if a vericle $i$ has a loop, then it has 1 in $a_ii$ on axis.

When you’ll multiply matrix $M$ by itself 2 times, then numbers in the matrix represent the number of paths which length is 2 between choosen 2 verticles.

When you’ll multiply matrix $M$ by itself 3 times, then numbers in the matrix represent the number of paths which length is 3 between choosen 2 verticles.

3. ooh Graph .. I got it now :D
I was thinking in it as a Circle and line :)
Thanks ;)

4. Maybe you’ll analyse some topology and share your insights?

5. 5 Mike

Just passing by.Btw, your website have great content!

_________________________________
Making Money \$150 An Hour

6. 6 the7new7ramanujan

it’s really amazing.