Matpic
mathematics, in pictures
Concept

Hierholzer's algorithm

The procedure that builds a closed walk using every edge of a graph exactly once, by walking until stuck and splicing in detours from vertices with edges to spare. It is a proof as well as a method: the splicing fails only when the degree condition does.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

Königsberg as a graph. The four landmasses as circles and the seven bridges as edges; every circle has an odd number of edges.

Seven bridges, and the invention of throwing things away

Euler solved a puzzle about a Prussian city by deleting the city. What survived the deletion was a new branch of mathematics.

discrete · eulerian paths The de Bruijn graph on 2 letters and words of 3, and the cycle through it. A graph whose vertices are short words and whose arrows are words one letter longer, with a closed walk using every arrow exactly once marked, and the cyclic sequence it spells.

Every word once, around a cycle

A cyclic string of eight bits holds all eight three-bit words, each exactly once — and the reason such a thing exists is that the constraint linking overlapping windows is itself the construction.

computation · de bruijn

Named alongside it

The objects these essays reach for when they reach for this one.

GraphAbstractionCountingCyclic wordDe bruijn sequenceDegreeEncodingEulerian circuitExhaustive searchMatrixParity

All concepts