Download Inducción y Grafos

Matemáticas para Ciencias de la
Computación
MCC3182
Principio de Inducción Matemática
Matemáticas para Ciencias de la
Computación
MCC3182
Supóngase que tenemos la sucesión de números naturales con la
propiedad de que dichos números son de color rojo.
1,2,3,4,5,6,7...
Supongamos que:
•
El primer natural es de color rojo (1).
•
Si todos los naturales que preceden al (n+1)-ésimo son de color
rojo, entonces el (n+1)-ésimo número es de color rojo (2).
Para demostrar que el número 8 es de color rojo, se observa que todos
los que preceden al 7 y, por (2) el número 7 también es de color rojo.
Este ejemplo ilustra el Principio de Inducción Matemática
Matemáticas para Ciencias de la
Computación
MCC3182
Inducción Matemática
Ejemplo:
Denótese por Sn=1+2+3+4+...+n (1)
Consideremos que se afirma que:
Sn=n(n+1)/2 para n=1,2,...
(2)
Se ha elaborado una sucesión de proposiciones, a saber
S1=1(2)/2=1
S2=2(3)/2=3
S3=3(4)/2=6
Matemáticas para Ciencias de la
Computación
MCC3182
Supóngase que cada ecuación verdadera está marcada con
una “X”. Dado que la primera ecuación es verdadera,
S1=1(2)/2
S2=2(3)/2
S3=3(4)/2
X
X
X
Sn-1=(n-1)n/2
Sn=n(n+1)/2
Sn+1=(n+1)(n+2)/2
X
X
?
Matemáticas para Ciencias de la
Computación
MCC3182
Supóngase ahora que puede demostrarse que si todas las
ecuaciones que preceden a la (n+1)-ésima ecuación están
señaladas, entonces la (n+1)-ésima ecuación también lo
está.
Debe probarse que si todas las ecuaciones que preceden a
la (n+1)-ésima son verdaderas, entonces la (n+1)-ésima
ecuación también es verdadera.
Sn+1=1+2+3+...+n+(n+1)
=Sn+(n+1)
=n(n+1)/2+(n+1)
=(n+1)(n+2)/2
Matemáticas para Ciencias de la
Computación
MCC3182
Principio de Inducción Matemática: Supóngase que se
tiene una proposición S(n) para cada entero positivo n, la
cual es verdadera o falsa. Consideremos que
Paso Básico:
S(1) es verdadera
Paso Inductivo:
si S(i) es verdadera para todo i<n+1, entonces S(n+1)
es verdadera.
Matemáticas para Ciencias de la
Computación
MCC3182
Ejemplo: Use inducción para demostrar que si a es distinto de 1, (Suma
Geométrica).
1+a1+a2+...+an=(an+1-1)/(a-1)
(1)
Paso Básico: Se obtiene cuando n=0,
1=(a1-1)/(a-1), lo cual es verdadero.
Paso Inductivo:Supongamos que la proposición es verdadera para n.
Ahora
1+a1+a2+...+an+an+1
=(an+1-1)/(a-1)+an+1
=(an+1-1)/(a-1)+(an+1(a-1))/(a-1)
=(an+2-1)/(a-1)
Como el paso básico y el paso inductivo ya han sido verificados, el
principio de inducción matemática establece que (1) es verdadera para
n=0,1,2,...
Matemáticas para Ciencias de la
Computación
MCC3182
Grafo Normal
Matemáticas para Ciencias de la
Computación
MCC3182
Grafo Ciencias de la Computación
Matemáticas para Ciencias de la
Computación
MCC3182
Definición
Un grafo es una conjunto de vértices V y un conjunto
de arcos E,tal que
Así E, es simplemente una relación binaria en el
conjunto V.
Matemáticas para Ciencias de la
Computación
MCC3182
Relaciones y Grafos
Matemáticas para Ciencias de la
Computación
MCC3182
Propiedades de Relación
Matemáticas para Ciencias de la
Computación
MCC3182
Matemáticas para Ciencias de la
Computación
MCC3182
Representación de Matriz Booleana
Matemáticas para Ciencias de la
Computación
MCC3182
Operaciones sobre la Matriz Booleana
Matemáticas para Ciencias de la
Computación
MCC3182
Composición Usando Matrices
Matemáticas para Ciencias de la
Computación
MCC3182
Matemáticas para Ciencias de la
Computación
MCC3182
Matemáticas para Ciencias de la
Computación
MCC3182
Definición
Un grafo simple es una conjunto de vértices V y un
conjunto de arcos E, donde cada arco es una par no
ordenado de distintos vértices a y b.
El grado de un vértice es el número de arcos que se
conectan a el.
Ejercicio: Dibuje un grafo con 3 vértices de grado 2,2
y 1.
Matemáticas para Ciencias de la
Computación
MCC3182
Un grafo Imposible
Matemáticas para Ciencias de la
Computación
MCC3182
Problema:Localización de galpones para aeronaves.
Horario de Aerolíneas
Dado un conjunto de vuelos que llegan a distintos
horarios, ¿Cuántos galpones necesitamos para
poder acomodar dichos aviones?
Matemáticas para Ciencias de la
Computación
MCC3182
Matemáticas para Ciencias de la
Computación
MCC3182
Matemáticas para Ciencias de la
Computación
MCC3182
Solución: Coloreo de Grafo
Se colorea cada vértice de manera que no queden
dos vértices adyacentes con el mismo color.
Matemáticas para Ciencias de la
Computación
MCC3182
Asignación de Galpones (o colores)
Matemáticas para Ciencias de la
Computación
MCC3182
Fuente de Problemas
• ¿Cómo podemos programar los exámenes finales
con el objetivo de que no se tomen dos al mismo
tiempo?.
• ¿cuántos habitad diferente necesito para que
algunas especies animales puedan coexitir con otras
especies?.
Matemáticas para Ciencias de la
Computación
MCC3182
Número Cromático
• Pregunta: ¿Cuál es la cantidad mínima de colores
que necesito para resolver el problema?
• ¿Cómo se yo que esa cantidad es la mínima?
Matemáticas para Ciencias de la
Computación
MCC3182
Matemáticas para Ciencias de la
Computación
MCC3182
Principio de Inducción Matemática: Supóngase que se
tiene una proposición S(n) para cada entero positivo n, la
cual es verdadera o falsa. Consideremos que
Paso Básico:
S(1) es verdadera
Paso Inductivo:
si S(i) es verdadera para todo i<n+1, entonces S(n+1)
es verdadera.