Seven Bridges to Cross

Programming Snapshot – Graph Theory

Article from Issue 217/2018
Author(s):

Pretty much any computer science lecture about graph theory covers the "Seven Bridges of Königsberg" problem. Mike Schilli puts a Python script to work on a solution, but finds that a new bridge must be built.

The task of crossing the seven bridges over the Pregola River on a city tour of Königsberg (nowadays known as Kaliningrad) without missing one or walking across one twice [1] is simply captivating.

The Swiss mathematician Leonhard Euler already proved that this was impossible as early as 1736, but the task is still useful as a mathematical brain teaser today because the network of bridges can be converted into a graph (Figure 1) and bombarded with graph-theory axioms and algorithms.

[...]

Use Express-Checkout link below to read the full article (PDF).

Buy this article as PDF

Express-Checkout as PDF
Price $2.95
(incl. VAT)

Buy Linux Magazine

SINGLE ISSUES
Print Issues
Digital Issues
 
SUBSCRIPTIONS
Print Subs
Digisubs
 
TABLET & SMARTPHONE APPS
Get it on Google Play

US / Canada

Get it on Google Play

UK / Australia

Related content

  • Bridgewall

    Firewalls are typically implemented as routers,but it doesn’t have to be that way. Bridging packet filters have a number of advantages,and you can add them to your network at a later stage without changing the configuration of your network components.

    more »
  • Perl: Neo4j

    The Neo4j graph database is much better suited than relational databases for storing and quickly querying nodes and their mutual relationships. If your circle of friends is not wide enough to warrant a graph-based application, you might just want to inventory your LAN.

    more »
  • systemd-networkd

    The new networkd component of the systemd project supports basic network configuration. Despite its early stage of development, one thing is clear: This is a daemon with brains.

    more »
  • Nerf Target Game

    A cool Nerf gun game for a neighborhood party provides a lesson in Python coding with multiple processors.

    more »
  • Trembling Text

    Writing your own extension for Inkscape opens up a whole world of possibilities. Apart from creating new objects, you can modify existing objects and even animate them.

    more »
comments powered by Disqus