TAD de los grafos - Lema del apretón de manos

José A. Alonso

07-06-2023

En la teoría de grafos, se conoce como "Lema del apretón de manos" la siguiente propiedad: la suma de los grados de los vértices de g es el doble del número de aristas de g.

Comprobar con QuickCheck que para cualquier grafo g, se verifica dicha propiedad.

Soluciones

Se usarán las funciones

grado definida en el ejercicio Grado de un vértice y
nAristas definida en el ejercicio Número de aristas de un grafo.

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import TAD.Grafo (Grafo, nodos)
import TAD.GrafoGenerador
import Grafo_Grado_de_un_vertice (grado)
import Grafo_Numero_de_aristas_de_un_grafo (nAristas)
import Test.QuickCheck

prop_apretonManos :: Grafo Int Int -> Bool
prop_apretonManos g =
  sum [grado g v | v <- nodos g] == 2 * nAristas g

-- La comprobación es
--    λ> quickCheck prop_apretonManos
--    +++ OK, passed 100 tests.

Soluciones en Python

from hypothesis import given

from src.Grafo_Grado_de_un_vertice import grado
from src.Grafo_Numero_de_aristas_de_un_grafo import nAristas
from src.TAD.Grafo import nodos
from src.TAD.GrafoGenerador import gen_grafo


# La propiedad es
@given(gen_grafo())
def test_apreton(g):
    assert sum((grado(g, v) for v in nodos(g))) == 2 * nAristas(g)

# La comprobación es
#    src> poetry run pytest -q Grafo_Lema_del_apreton_de_manos.py
#    1 passed in 0.32s