.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/graph_theory/hamiltonian/plot_01_icosian_game.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_graph_theory_hamiltonian_plot_01_icosian_game.py>`
        to download the full example code.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_graph_theory_hamiltonian_plot_01_icosian_game.py:


Hamilton's icosian game
=============================

Solves Hamilton's 1857 puzzle: travel along the edges of a dodecahedron
through all 20 vertices exactly once and return to the start. The same
search shows that the Petersen graph has no such cycle.

.. GENERATED FROM PYTHON SOURCE LINES 11-16

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.graph_theory import Graph, dodecahedron_graph, hamiltonian_cycle








.. GENERATED FROM PYTHON SOURCE LINES 17-19

A tour of the dodecahedron
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 19-49

.. code-block:: Python


    g = dodecahedron_graph()
    tour = hamiltonian_cycle(g)
    print(f"Hamiltonian cycle: {tour}")

    radius = {0: 3.0, 1: 2.0, 2: 1.4, 3: 0.7}


    def position(v):
        if v < 5:
            return radius[0], 2 * np.pi * v / 5
        if v < 15:
            k = v - 5
            return (radius[1] if k % 2 == 0 else radius[2]), 2 * np.pi * k / 10
        return radius[3], 2 * np.pi * (v - 15) / 5 + 2 * np.pi / 10


    pos = np.array([[r * np.sin(t), r * np.cos(t)] for r, t in map(position, range(20))])
    fig, ax = plt.subplots(figsize=(6, 6))
    for u, v, _ in g.edges():
        ax.plot(*pos[[u, v]].T, color="0.8", lw=1)
    cycle = tour + tour[:1]
    ax.plot(*pos[cycle].T, color="tab:red", lw=2.5)
    ax.plot(*pos.T, "ko")
    for v, (x, y) in enumerate(pos):
        ax.annotate(str(v), (x, y), xytext=(4, 4), textcoords="offset points", fontsize=8)
    ax.set_aspect("equal")
    ax.axis("off")
    ax.set_title("The icosian game (Schlegel diagram of the dodecahedron)")




.. image-sg:: /api/gallery/graph_theory/hamiltonian/images/sphx_glr_plot_01_icosian_game_001.png
   :alt: The icosian game (Schlegel diagram of the dodecahedron)
   :srcset: /api/gallery/graph_theory/hamiltonian/images/sphx_glr_plot_01_icosian_game_001.png
   :class: sphx-glr-single-img


.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    Hamiltonian cycle: [0, 1, 2, 3, 4, 13, 12, 11, 10, 9, 8, 7, 6, 15, 16, 17, 18, 19, 14, 5]

    Text(0.5, 1.0, 'The icosian game (Schlegel diagram of the dodecahedron)')



.. GENERATED FROM PYTHON SOURCE LINES 50-52

The Petersen graph has no Hamiltonian cycle
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 52-59

.. code-block:: Python


    petersen = Graph(10)
    for i in range(5):
        petersen.add_edge(i, (i + 1) % 5)
        petersen.add_edge(i, i + 5)
        petersen.add_edge(5 + i, 5 + (i + 2) % 5)
    print(f"Petersen graph: {hamiltonian_cycle(petersen)}")




.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    Petersen graph: None





.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.024 seconds)


.. _sphx_glr_download_api_gallery_graph_theory_hamiltonian_plot_01_icosian_game.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_icosian_game.ipynb <plot_01_icosian_game.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_01_icosian_game.py <plot_01_icosian_game.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_01_icosian_game.zip <plot_01_icosian_game.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_