Gephi

I just discovered a new ( free, open source ) tool for graphs and networks. What Photoshop is for pictures, Gephi ( supposedly ) is for graphs. Software is definitely a requirement for Graph Theory. I haven't looked at Gephi in-depth yet, I might. It is exciting though. There is so much going on. When you turn away from a certain area for just a brief period things might have changed quite a lot when you get back. I 'worked with' ( read: used to study graph theory ) Mathematica with the Combinatorica package which is really a gem by itself.

Link: Gephi

Solving the Königsberg Bridge Problem with Mathematica

One of the most famous problems in the history of mathematics is the Königsberg Bridge Problem because it clearly marks the beginning of Graph Theory.

"... In addition to that branch of geometry which is concerned with magnitudes, and which has always received the greatest attention, there is another branch, previously almost unknown, which Leibniz first mentioned, calling it the geometry of position. ..."
Soluti problematis ad geometriam situs pertinentis, Euler 1736

The Königsberg bridge problem asks if the seven bridges of the city of Konigsberg (*) over the river Preger can all be traversed in a single trip without doubling back, with the additional requirement that the trip ends in the same place it began. Euler proved in 1736 that there is no such traversal. (*) Königsberg = Kaliningrad in the Russian exclave between Poland and Lithuania.

Using Graph Theory the problem is equivalent to asking if the multigraph on four nodes and seven edges (see figure) has an Eulerian cycle. Using Mathematica we would model each bridge as an edge and the parts of the city as a vertex. There are different ways to create a graph in Mathematica, but this problem suits the method of creating a graph from an adjacency matrix. Since EulerianQ returns false we know that Mathematica confirms Euler's original answer.

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.

MT365 - More video programmes

MT365 - Video 2.
Video 2 is about tilings at the Alhambra. One of the options I considered for 2010 was studying m336 next to m208. I decided not to because of the geometry part of M336: it's about tiling patterns which I find a rather difficult subject. Designs 1 of MT365 is about the same subject. But where in M336 one must be able to prove that the only rotational patterns possible are of orders 2,3,4 and 6 that fact is accepted as is without proof in MT365. Designs 1 could very well be the step I need to start confident on M336 I have in my plan for 2012.

MT365 - Video 5.
This video is about the proof of the four colour theorem. No more than four colors are needed to color any map. Thomas Kempe, a 19th century mathematician ( played by an actor of course ) explains his proof in detail based on unavoidable sets and reducibility. I knew it couldn't be the real proof because I knew the real proof wasn't found until 1976 but I didn't see why Kempe's proof was flawed. Neither did the mathematicians he explained it to at the time. After ten years or so it became apparent that his proof wasn't entirely correct. In 1976 the theorem was proved but by a computer. The proof consisted of hundreds of computer-generated pages. - I wonder if there are still people around who hope for a compacter proof. The 1976 proof was largely based on Kempe's proof by the way. What if there is an entirely different approach possible to tackle this problem?

Four Cubes problem

After only one section on MT365 Graph Theory you will be able to fully understand and apply the techniques used in solving the Four Cubes problem, or Instant Insanity as it seem to be called. I found a YouTube video where some professor explains the problem.


I did not know the problem was so popular, yet another YouTube video on the subject ( warning: loud KrautRock music in background ).

Graph Browser

At the Wolfram site you can download a Graph Browser which requires either Mathematica 7 or a ( free ) Mathematica player. The graph browser connects to a graph database on the internet which contains quite a lot of graphs. In MT365 the only graph by name studied sofar is the Petersen Graph. A query on Petersen actually returned tha exact graph as we have studied.

Mathematica and Graph Theory

Mathematica can ( and probably will ) be a great help while studying Graph Theory MT365. The possibilities Mathematica offers are overwhelming. Being able to produce neat graphs from a list of edges is just the beginning.

The figure above is the well known Konigsberg graph.

The Handshaking Lemma ( First steps in Graph Theory )

Beginning Graph Theory is basically learning new words. I once heard that the Eskimo's have over one hundred  words for snow. It looks as though mathematicians have as many words for graphs. Graph, regular graph, null graph, complete graph, labelled graph, unlabelled graph, subgraph, cycle graph and this is only the beginning. The first theorem in Graph Theory is called 'The Handshaking Lemma'.

In any graph the sum of all the vertex degrees is equal to twice the number of edges.

Cayley graph of D8

G = { a,b | a3=b2=1, ab=ba3 }
Set of elements / vertices {1, a, a2, a3, b, ba, ba2, ba3}
Generating set / colors {a, b} ( a yellow, b blue )
Two elements (x, y) are connected by an arc if y=ax (yellow arc), y=bx (blue arc).
Now you know the Cayley Graphs of all Dihedral Groups...

Algebraic Graph Theory

I am interested in graphical representations of finite groups. Today I discovered that...

"For every finitely generated group G there exists a graph X such that the automorphism group of X, Aut(X) is isomorphic to G."

An interesting theorem. Well, I thought so anyway. Just had to be. All based on my intuition.

The branch of mathematics which studies this area is called Algebraic Graph Theory.