Ejercicios Resueltos de Matemáticas Discretas: Grafos, Recurrencias y Álgebra
Clasificado en Matemáticas
Escrito el en español con un tamaño de 26,3 KB
Examen de Enero 2012: Problemas Resueltos de Matemáticas Discretas
Problemas de Desarrollo
Problema 1: Grafos y Combinatoria
Demuestre que el número de grafos distintos que se pueden formar con 200 vértices y 50 aristas es:
La expresión
C(200, 2)
(o(200 sobre 2)
) representa las selecciones no ordenadas de un conjunto de 200 elementos, tomados en grupos de 2 elementos. Esto define todas las posibles aristas en un grafo completo con 200 vértices.Luego, se aplica la misma lógica, pero cambiando 200 por el número total de aristas posibles (
C(200, 2)
) y 2 por 50 (que es el número de aristas a seleccionar). Así es como se definen todos los grafos con 50 aristas.Proponga un ejemplo con 4 vértices y 5 aristas.
Número de grafos que se pueden