TAD de los grafos: Lema del apretón de manos
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
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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. |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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 |