Teoría Combinatoria de Matrices y el Teorema Master de MacMahon

Abstract

El primer artículo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736, se titula Solutio problematis ad geometriam situs pertinentis (La solución de un problema relativo a la geometría de la posición). El problema planteaba lo siguiente: ¿es posible, partiendo de un lugar arbitrario, regresar al lugar de partida cruzando cada puente (los puentes de Königsberg) una sola vez? Euler consigue demostrar que el grafo asociado al esquema de puentes de Königsberg no tiene solución, es decir, no es posible regresar al vértice de partida sin pasar por alguna arista dos veces. Gracias a la teoría de grafos se pueden resolver diversos problemas, como por ejemplo, la síntesis de circuitos secuenciales, contadores o sistemas de apertura.