As of May 4 2007 the scripts will autodetect your timezone settings. Nothing here has to be changed, but there are a few things

Please follow this blog

Search this blog

Sunday, February 14, 2010

Doing Graph Theory

What is Graph Theory like? ( After a few weeks of study anyway. ) Let's take the The Konigsberg Bridges problem as an example. This problem marks the start of Graph Theory and was solved by Leonhard Euler. The question was to find a route through the city crossing each bridge only once. Then the Graph Theorist enters the scene.

He translates the relevant parts of the city to a graph such that the seven bridges become seven edges and the various city areas shrink to mere vertices. He translates the original question to a question about the graph: is this graph Eulerian? If so, then the answer to the original question is yes.

But what exactly is an Eulerian graph? An Eulerian graph is a connected graph which contains an Eulerian trail. A graph theorists knows a theorem which helps him to decide if the graph contains an Eulerian trail. We however, have to explain first the words connected graph and Eulerian trail. An Eulerian trail is a closed trail that includes every edge. Again. Two new words! Closed trail and edge ( = connection between two vertices. ) A closed trail is a trail with start and finish at the same vertex ( = a dot in a graph. ) A trail is a walk in which all edges, but not necessarily all vertices, are different. A walk of length k is a succession of k edges of the form uv, vw, wx, ..., yz. This walk is denoted by uvwx...yz, and is referred to as a walk between u and z. Remains the word connected graph. A graph is connected if there is a path between each pair of vertices.

Why not show all these definitions, relations and corresponding theorems in a graph?! Exactly. ( There is an aspect of self-reference here but I lack the knowledge of terms to exactly describe it. Maybe after M381. )

I created this graph using Personal Brain. It is possible to share and publish brains on the internet in order to collaborate on some project. MT365 is the first course I am using Personal Brain for. It is too soon to evaluate though.

No comments:

Post a Comment

Popular Posts

Welcome to The Bridge

Mathematics: is it the fabric of MEST?
This is my voyage
My continuous mission
To uncover hidden structures
To create new theorems and proofs
To boldly go where no man has gone before

(Raumpatrouille – Die phantastischen Abenteuer des Raumschiffes Orion, colloquially aka Raumpatrouille Orion was the first German science fiction television series. Its seven episodes were broadcast by ARD beginning September 17, 1966. The series has since acquired cult status in Germany. Broadcast six years before Star Trek first aired in West Germany (in 1972), it became a huge success.)