.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/graph_theory/eulerian/plot_01_konigsberg_bridges.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code. .. rst-class:: sphx-glr-example-title .. _sphx_glr_api_gallery_graph_theory_eulerian_plot_01_konigsberg_bridges.py: Euler and the Seven Bridges of Königsberg =============================================== Reduces Königsberg to four land masses joined by seven bridges and counts the bridges at each land mass. All four counts are odd, so by Euler's argument no walk can cross every bridge exactly once, and an exhaustive search agrees. Removing a single bridge leaves exactly two odd land masses, and a walk over every remaining bridge appears. .. GENERATED FROM PYTHON SOURCE LINES 13-18 .. code-block:: Python import matplotlib.pyplot as plt import numpy as np from mathematicskit.graph_theory import Graph, connected_components .. GENERATED FROM PYTHON SOURCE LINES 19-27 Land masses as vertices, bridges as edges ----------------------------------------------------- The seven bridges form a multigraph: two pairs of bridges join the same land masses. :class:`~mathematicskit.graph_theory.core.base.Graph` stores simple graphs, so each bridge becomes its own vertex placed between the two banks it joins. A land mass's degree in this graph is then exactly the number of bridges that touch it. .. GENERATED FROM PYTHON SOURCE LINES 27-44 .. code-block:: Python land = ["A: north bank", "B: south bank", "C: Kneiphof island", "D: Lomse"] bridges = [(0, 2), (0, 2), (1, 2), (1, 2), (0, 3), (1, 3), (2, 3)] g = Graph(len(land) + len(bridges)) for k, (u, v) in enumerate(bridges): g.add_edge(u, len(land) + k) g.add_edge(len(land) + k, v) degrees = [len(g.neighbors(v)) for v in range(len(land))] odd = [v for v, d in enumerate(degrees) if d % 2 == 1] print(f"connected: {connected_components(g).n_components == 1}") for name, d in zip(land, degrees): print(f" {name:20s} {d} bridges ({'odd' if d % 2 else 'even'})") print(f"odd land masses: {len(odd)} (an Euler walk allows at most 2)") .. rst-class:: sphx-glr-script-out .. code-block:: none connected: True A: north bank 3 bridges (odd) B: south bank 3 bridges (odd) C: Kneiphof island 5 bridges (odd) D: Lomse 3 bridges (odd) odd land masses: 4 (an Euler walk allows at most 2) .. GENERATED FROM PYTHON SOURCE LINES 45-47 Exhaustive search confirms Euler's argument ----------------------------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 47-76 .. code-block:: Python def euler_walks(bridge_list, n_land): """Every walk crossing each bridge exactly once, by depth-first search.""" walks = [] def extend(at, used, walk): if len(used) == len(bridge_list): walks.append(list(walk)) return for k, (u, v) in enumerate(bridge_list): if k not in used and at in (u, v): walk.append(k) extend(v if at == u else u, used | {k}, walk) walk.pop() for start in range(n_land): extend(start, frozenset(), []) return walks print(f"walks over all 7 bridges: {len(euler_walks(bridges, len(land)))}") reduced = bridges[:-1] # demolish the bridge between the island C and Lomse D reduced_degrees = np.bincount(np.ravel(reduced), minlength=len(land)) walks = euler_walks(reduced, len(land)) print(f"after removing bridge C-D: degrees {reduced_degrees.tolist()}, {len(walks)} walks over all 6 bridges") walk = walks[0] .. rst-class:: sphx-glr-script-out .. code-block:: none walks over all 7 bridges: 0 after removing bridge C-D: degrees [3, 3, 4, 2], 32 walks over all 6 bridges .. GENERATED FROM PYTHON SOURCE LINES 77-84 The map as a graph ----------------------------------------------------- Red land masses touch an odd number of bridges. On the right, one bridge is removed and the numbers give the order of a walk that crosses every remaining bridge once, starting and ending at the two odd land masses. .. GENERATED FROM PYTHON SOURCE LINES 84-120 .. code-block:: Python pos = np.array([[0.0, 1.0], [0.0, -1.0], [-0.6, 0.0], [1.2, 0.0]]) def draw(ax, bridge_list, degs, order=None): seen = {} for k, (u, v) in enumerate(bridge_list): key = (min(u, v), max(u, v)) count = sum(key == (min(a, b), max(a, b)) for a, b in bridge_list) i = seen.get(key, 0) seen[key] = i + 1 bend = 0.0 if count == 1 else (0.25 if i == 0 else -0.25) p, q = pos[u], pos[v] normal = np.array([-(q - p)[1], (q - p)[0]]) ctrl = (p + q) / 2 + bend * normal t = np.linspace(0, 1, 40)[:, None] curve = (1 - t) ** 2 * p + 2 * (1 - t) * t * ctrl + t**2 * q ax.plot(*curve.T, color="tab:brown", lw=3, zorder=1) if order is not None: mid = curve[20] ax.annotate(str(order.index(k) + 1), mid, ha="center", va="center", fontsize=9, bbox={"boxstyle": "circle", "fc": "white"}, zorder=3) colors = ["tab:red" if d % 2 else "tab:green" for d in degs] ax.scatter(*pos.T, s=900, c=colors, edgecolors="black", zorder=2) for v, (x, y) in enumerate(pos): ax.annotate(f"{'ABCD'[v]}\n{degs[v]}", (x, y), ha="center", va="center", color="white", fontweight="bold", zorder=3) ax.margins(0.15) ax.set_aspect("equal") ax.axis("off") fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 5)) draw(ax1, bridges, degrees) ax1.set_title("Seven bridges: four odd land masses,\nno walk crosses each bridge once") draw(ax2, reduced, reduced_degrees, order=walk) ax2.set_title("Bridge C-D removed: two odd land masses,\nan Euler walk exists") fig.tight_layout() .. image-sg:: /api/gallery/graph_theory/eulerian/images/sphx_glr_plot_01_konigsberg_bridges_001.png :alt: Seven bridges: four odd land masses, no walk crosses each bridge once, Bridge C-D removed: two odd land masses, an Euler walk exists :srcset: /api/gallery/graph_theory/eulerian/images/sphx_glr_plot_01_konigsberg_bridges_001.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.049 seconds) .. _sphx_glr_download_api_gallery_graph_theory_eulerian_plot_01_konigsberg_bridges.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_01_konigsberg_bridges.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_01_konigsberg_bridges.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_01_konigsberg_bridges.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_