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:

Interesting graph

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]}

About these ads


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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 39 other followers

%d bloggers like this: