grafos

Matemática Discreta
Talleres divulgativos
“matemáticas en acción”
24 Noviembre 2004
Francisco Santos

¿Qué es la Matemática Discreta?
En matemáticas, “discreto” es lo contrario de “continuo”.

continuo

discreto

“Matemática discreta” es casi sinónimo de “combinatoria”,
aunque lo primero es más amplio que lo segundo.
La matemática discreta trata de números enteros,
conjuntosfinitos, objetos geométricos discretos
(poliedros, complejos simpliciales,…)

La matemática discreta engloba:
- combinatoria (“el arte de contar”)
- “geometría discreta” (poliedros, etc)
- teoría de grafos
- álgebra discreta (grupos y cuerpos finitos, códigos
algebraicos,…)
- etc…
En esta charla nos fijamos en cuatro ejemplos:
(1) particiones de un número.
(2) grafos Eulerianos yHamiltonianos.
(3) empaquetando esferas que se besan.
(4) poliedros regulares.

¿Es una disciplina nueva?
Desde luego que no. Veremos varios ejemplos de
Teoremas de Matemática Discreta descubiertos por
Leonard Euler (1707-1783). Antes de Euler cabe citar
a Jakob Bernoulli, Abraham de Moivre, Blaise Pascal.
… pero la Matemática Discreta ha vivido un renacer
(¿revolución?) en el siglo XX, por dosrazones:
-ha pasado de ser una mera “colección de problemas
sueltos y trucos de resolución” a tener una estructura
definida y bien fundamentada (por ejemplo, con los
trabajos de G.C. Rota en los 1960’s.
- la Matemática Discreta es la parte de las matemáticas
más cercana a los ordenadores, y tiene una relación
bidireccional con ellos: los ordenadores son discretos.

“… the recentdevelopment of combinatorics is
somewhat of a cinderella story: It used to be looked
down on by “mainstream” mathematicians as being
somehow less respectable than other areas, in
spite of many services rendered to both pure and
applied mathematics. Then along came the prince
of computer science with its many mathematical
problems and needs --- and it was combinatorics
that best fitted the glassslipper held out”.
A. Björner, R. P. Stanley, 1999
“El desarrollo reciente de la combinatoria es en cierto modo la historia de la
cenicienta: los matemáticos ortodoxos la miraban por encima del hombro,
considerándola menos respetable que otras áreas a pesar de sus muchos
servicios tanto a la matemática pura como aplicada. Pero entonces llegó el
príncipe de la informática con todos susproblemas y necesidades matemáticas, y la combinatoria fue a quien mejor le entraba el zapatito de cristal”.

(1) Particiones de un número

Un poco de combinatoria

La combinatoria es el arte de contar o, para ser más
precisos, el arte de decir cuántos objetos hay en un
cierto conjunto, o de cuántas maneras se puede
hacer algo, sin necesidad de contarlo explícitamente.

Por ejemplo, en uncurso básico de combinatoria
se aprende que hay 13 983 816 de
combinaciones posibles en la lotería primitiva (el
“número combinatorio 49 sobre 6”).

… y también que ese mismo número cuenta
las posibles maneras de ir desde el punto
(0,0) al punto (43,6) mediante caminos monótonos
en la retícula de cuadrados de lado 1.

Particiones de un número
Dado un número natural n llamamos“particiones
de n” a todas las maneras de escribir n como
suma de números naturales. Por ejemplo:
hay 11 particiones del número 6:
1+1+1+1+1+1
2+1+1+1+1
2+2+1+1
2+2+2
3+1+1+1
3+2+1
3+3

4+1+1
4+2
5+1
6

Euler, en 1740, demostró el siguiente
Teorema: para todo número n, hay tantas
particiones de n en partes distintas como
particiones de n en partes impares.
Ejemplo: para n=9:
Distintas:9
8+1
7+2
6+3
6+2+1
5+4
5+3+1

Impares:
9
7+1+1
5+3+1
5+1+1+1+1
3+3+3
3+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1

Demostración: Para cada n, sea pn el número
de particiones de n. Llamamos función
generatriz de la sucesión (pn) a la función:
P(x) = po + p1 x + p2 x2 + p3 x3 + + p4 x4 + ….
Se tiene que:
P(x) = (1 +
(1 +
(1 +
(1 +
(1 +

x + x2 + x3 + + x4 +….)
x2 + x4 + x6 + +...