Hear See Think

(Source: enkiseshat, via smoot)

matthen:

This shows how the dodecahedron, a shape with 12 pentagon faces, can be distorted so that it can be drawn with no lines crossing.  In fact any convex polyhedron has this property (loosely ‘convex’ means no dents or spikes). Related is the fact that for convex polyhedra the number of vertices, minus the number of edges, plus the number of faces is always 2. Here that is 20 red vertices - 30 edges + 12 faces = 2. Can you draw a cube with no lines crossing, and does the formula work add up to 2? [more] [code]

I love how the perspective makes this look like it’s happening in 3-space.  Matthen, your work is consistently inspiring!

matthen:

When designing an art gallery, you might want to make it so that people can walk through it visiting each exhibit exactly once returning back to the front door.  In the plan on the left, this is possible.  In the other plan, it is impossible to visit every dot (exhibit) without revisiting an exhibit.  There is no quick method to check a general art gallery to see if it has this property (that it is Hamiltonian) - you just have to check all possible paths.  [more] [code]

Actually, sometimes you can notice a simple feature of a graph that ensures it has a Hamiltonian cycle.  Two related examples:

Theorem (Ore): Let G be a simple graph on n > 2 vertices. If for every pair of nonadjacent vertices u and v in G we have $$deg(u) + deg(v) \geq n,$$ then G is Hamiltonian.

Theorem (Dirac): Let G be a simple graph on n > 2 vertices. If for every u in V(G) we have $$deg(u) \geq n/2,$$ then G is Hamiltonian.

These are sufficient conditions for a graph to be Hamiltonian, but they are not necessary; there are Hamiltonian graphs that don’t satisfy either of these.  Going in the other direction, here’s one necessary condition:

Theorem: If G is a simple Hamiltonian graph, then for each S subset of V(G), the number of components of G - S is at most |S|.

In other words, if throwing away n vertices of G ever breaks G up into more than n pieces, G cannot be Hamiltonian.  But there are non-Hamiltonian graphs that have this feature, like the graph on the right in the animation above. 

So we don’t have the whole story yet.  If you’re looking at a graph which none of the above theorems say anything about, it may be Hamiltonian and you’d be hard pressed to see it without just checking all paths manually.  It may be that the Hamiltonian property doesn’t put enough restrictions on the structure of a graph to provide us with complete necessary & sufficient conditions to characterize it.  However, if we happen to notice a graph satisfies either of the first two theorems mentioned above, we can actually run an algorithm on it to find a Hamiltonian cycle in a reasonable amount of time.

Apparently a complete solution to this problem would earn its solver $1,000,000, as it is equivalent to the P-vs-NP Millennium Problem.

Source:

• Graph Theory: Modeling, Applications, and Algorithms by Agnarsson & Greenlaw, Prentice Hall 2007

(via intothecontinuum)

matthen:

A geometric construction of the parabola. The blue point is called the focus, and the horizontal line is the directrix. The blue lines show all the points which are at an equal distance from the red point and the blue focus point. The point of the blue line directly above the red dot contributes to the parabolic curve, because the parabola is defined as the set of all points equidistant to the focus and the directrix. [more] [code]

(via intothecontinuum)