Fun Science: Network Theory and Graphs

If you have a set of items and you can connect or sequence them in many ways, you probably have a graph or network. Clearly if you have these objects, some connection arrangements might be preferable to others. Heart cells are connected in patterns that contract the heart in the proper pattern. If you must deliver items to ten different locations, different paths may be more efficient (the traveling salesman problem).

Euler’s 1735 Koenigsberg bridge problem is considered the first graph theory problem. At the time, the city of Koenigsberg had seven bridges (shown above). Euler wished to find a path which crossed each bridge exactly once. He showed mathematically that no path satisfied those constraints.

The famous game “six degrees of Kevin Bacon” is a network theory problem. This game says that with six steps, any actor can be linked to Kevin Bacon through films pairs of actors appeared in. This idea was originally introduced at the Erdös number. Paul Erdös was a brilliant and highly published mathematician (over 1500 papers!) who worked in graph theory and combinatorics. The Erdös number was how many papers it took by coauthoring to connect you to Erdös. He was also wonderfully eccentric. Once, visiting a friend, he woke in the night to get some juice. In the morning, his friend found red liquid all over the floor. Erdös, puzzled by the juice carton, had simply stabbed a hole in the side to drink from. His biography is a fascinating glimpse into a nearly alien mind.

In my own research, I look at how oscillators synchronize in small networks, such as rings. Even in a simple ring, many new types of synchrony occur, compared to all-to-all connections. It is easy to believe that the structure of the brain, and how various regions and subregions connect, might greatly influence human thinking. On a more science fiction note, I suspect that artificial intelligence will not exist in machines without complex networks of elements.

This was just a very quick overview of a huge field. In the future, I plan to write on topics like small-world networks, scale-free networks, and synchrony on networks. Check out my other science posts on synchrony, fractals, the Mandelbrot set, and chaos.

Advertisements

3 thoughts on “Fun Science: Network Theory and Graphs

  1. balladofthebee

    I was unable to prevent myself from trying to figure out the Koenigsberg bridge problem despite knowing beforehand it was mathematically impossible to solve. Thanks to your wonderful post I have also just been reading about the very interesting Paul Erdős. Eccentric indeed!

    Like

    Reply
    1. Vironevaeh Post author

      I think no more than two of the islands may have an odd number of bridges for the path to be possible. I’m sure there are other constraints too. I think the Koenigsberg bridge problem is something of a combinatorics thing, which is a crazy type of math.

      Like

      Reply
  2. Pingback: Fun Science: Small World Networks | Vironevaeh

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