Principio de Inducción Matemática

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

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

Supóngase que cada ecuación verdadera está
marcada con una “X”. Dado que la primera
ecuación es verdadera, S1=1(2)/2 X S2=2(3)/2 X S3=3(4)/2 X
Sn-1=(n-1)n/2 X Sn=n(n+1)/2 X Sn+1=(n+1)(n+2)/2 ?

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

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.

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,…

Grafo Normal

Grafo Ciencias de la Computación

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.

Relaciones y Grafos

Propiedades de Relación

Representación de Matriz Booleana

Operaciones sobre la Matriz Booleana

Composición Usando Matrices

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.

Un grafo Imposible

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?

Solución: Coloreo de Grafo Se colorea cada vértice
de manera que no queden dos vértices adyacentes con el
mismo color.

Asignación de Galpones (o colores)

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?.

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?

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.