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
 
SUBSCRIPTIONS
 
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.

  • 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.

  • 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.

  • Graphviz

    Using drawing tools to manually create graphs and diagrams can be a slow and convoluted process. The Graphviz toolbox offers a faster way. Based on a short text with the information for the graph, Graphviz quickly generates a neat drawing.

  • Networking with VirtualBox

    Tour the VirtualBox virtualization tool, a free and easy environment for virtual versions of Linux, Unix, and Windows.

comments powered by Disqus

Direct Download

Read full article as PDF:

Price $2.95

News