One-mode Seven Bridges of Koenigsberg network (Euler 1741)

Source: R/data_ison.R

The Seven Bridges of Koenigsberg is a notable historical problem in mathematics and laid the foundations of graph theory. The city of Koenigsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges. A weekend diversion for inhabitants was to find a walk through the city that would cross each bridge once and only once. The islands could not be reached by any route other than the bridges, and every bridge must have been crossed completely every time (one could not walk half way onto the bridge and then turn around and later cross the other half from the other side). In 1735, Leonard Euler proved that the problem has no solution.

Two pairs of the seven bridges run parallel, joining the same two landmasses: the Kraemer and Schmiede bridges join the Altstadt to the Kneiphof, and the Gruene and Koettel bridges join the Kneiphof to the Vorstadt. These parallel bridges are the problem and not an artefact of the data, so tie_is_parallel() marks four of the seven ties, and as_matrix() reports two rather than one in those cells. Each tie is named for the bridge it stands for in a 'name' column.

data(ison_koenigsberg)

Format

#> -- # Seven Bridges of Koenigsberg ----------------------------------------------
#> # A labelled, undirected network of 4 landmasses and 7 bridge ties (4 parallel)
#>
#> -- Nodes
#> # A tibble: 4 x 3
#>   label      lat   lon
#>   <chr>    <dbl> <dbl>
#> 1 Altstadt  54.7  20.5
#> 2 Kneiphof  54.7  20.5
#> 3 Lomse     54.7  20.5
#> 4 Vorstadt  54.7  20.5
#>
#> -- Ties
#> # A tibble: 7 x 3
#>    from    to name
#>   <int> <int> <chr>
#> 1     1     2 Kraemer Bruecke
#> 2     1     2 Schmiedebruecke
#> 3     1     3 Holzbruecke
#> 4     2     3 Honigbruecke
#> 5     2     4 Gruene Bruecke
#> 6     2     4 Koettelbruecke
#> # i 1 more row
#>

Source

{igraphdata}. Euler presented the solution to the St Petersburg Academy on 26 August 1735; it was published in 1741 and is catalogued as Eneström 53.

References

Euler, Leonard. 1741. “Solutio problematis ad geometriam situs pertinentis.” Commentarii academiae scientiarum Petropolitanae.