.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/combinatorics/matching/plot_01_hall_marriage.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_combinatorics_matching_plot_01_hall_marriage.py>`
        to download the full example code.

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

.. _sphx_glr_api_gallery_combinatorics_matching_plot_01_hall_marriage.py:


Hall's marriage theorem
=============================

Checks Hall's condition on random bipartite graphs and confirms that it
holds exactly when a matching covers every left vertex. When it fails,
the example prints the subset whose neighbourhood is too small.

.. GENERATED FROM PYTHON SOURCE LINES 11-16

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.combinatorics import hall_condition








.. GENERATED FROM PYTHON SOURCE LINES 17-19

A graph that fails Hall's condition
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 19-25

.. code-block:: Python


    applicants = {"Ann": ["math"], "Bo": ["math"], "Cy": ["math", "art"], "Di": ["art", "music"]}
    result = hall_condition(applicants)
    print(f"satisfied: {result.satisfied}, violating subset: {sorted(result.violating_subset)}")
    print(f"best matching: {result.matching}")





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

 .. code-block:: none

    satisfied: False, violating subset: ['Ann', 'Bo']
    best matching: {'Ann': 'math', 'Cy': 'art', 'Di': 'music'}




.. GENERATED FROM PYTHON SOURCE LINES 26-28

Hall's condition vs. perfect matchings on random graphs
-----------------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 28-46

.. code-block:: Python


    rng = np.random.default_rng(0)
    probabilities = np.linspace(0.1, 0.7, 13)
    rates = []
    for p in probabilities:
        hits = 0
        for _ in range(200):
            adjacency = {u: [v for v in range(6) if rng.random() < p] for u in range(6)}
            result = hall_condition(adjacency)
            assert result.satisfied == (len(result.matching) == 6)
            hits += result.satisfied
        rates.append(hits / 200)

    fig, ax = plt.subplots()
    ax.plot(probabilities, rates, "o-")
    ax.set_xlabel("edge probability")
    ax.set_ylabel("fraction with a perfect matching")
    ax.set_title("6 x 6 random bipartite graphs")



.. image-sg:: /api/gallery/combinatorics/matching/images/sphx_glr_plot_01_hall_marriage_001.png
   :alt: 6 x 6 random bipartite graphs
   :srcset: /api/gallery/combinatorics/matching/images/sphx_glr_plot_01_hall_marriage_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none


    Text(0.5, 1.0, '6 x 6 random bipartite graphs')




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

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


.. _sphx_glr_download_api_gallery_combinatorics_matching_plot_01_hall_marriage.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_hall_marriage.ipynb <plot_01_hall_marriage.ipynb>`

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

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

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

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


.. only:: html

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

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