*Grafos Introduccion

modificado por: De La Cruz Monroy Jhonatan Josue

Un grafo ( griego grafos: dibujo, imagen) Conjunto de puntos unidos entre sí por segmentos o arcos de curva usados para representar un proceso o una relación funcional de cualquier tipo, es el principal objeto de estudio de la teoría de grafos.

Un grafo es una pareja G = (V, A), donde V es un conjunto de puntos, llamados vértices, y A es un conjunto de pares de vértices, llamadas aristas. Para simplificar, notaremos la arista {a, b} como ab.

 En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un grafo más claro. Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy legibles.

Prácticamente cualquier red puede ser modelada con un grafo: una red de carreteras que conectadas, una red eléctrica o un alcantarillado.

 Un poco de Historia sobre…

LA TEORIA DE GRAFOS

primeros resultados de teoría de grafos fue Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg.

En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos.

En 1852 Francis Guthrie planteó el problema de los cuatro colores que plantea si es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken, Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.

La teoria de los grafos estudia las propiedades de los grafos, que son colecciones de nodos ( o vertices ) conectados por aristas ( o lados ) las cuales pueden tener direccion.

USOS DE..

Un grafo se puede utilizar para representar ciudades y carreteras que las unen, rutas aereas y sus destino, un diagrama de compuertas logicas en electronica y hasta un arbol sintetico,Estructuras de datos en la representación de grafos para almacenarlos en una computadora.

Induccion matematica informatica

// Varela López David//

// Solano Zendejas Luis Roberto//

El principio de Inducción Matemática es un método que se utiliza para demostrar propiedades, formulas, validarlas y probar que son verdaderas.

Es un método simple que consta de tres pasos fundamentales en los cuales se debe demostrar la propiedad reemplazando su incógnita por 1, luego por k y finalmente por k+1. Los pasos para desarrollar la Inducción Matemática se detallan en el contenido del presente trabajo de investigación.

Sea P(n) una proposición que depende de la variable n, con n perteneciente a los Naturales. Si:

• 1 satisface a P y, • k pertenece a los Naturales, k satisface P! (k+1) satisface P,

entonces todos los números naturales satisfacen P.

Usaremos el Axioma de Inducción Matemática para demostrar la validez, en los Números Naturales, de ciertas proposiciones P que depende de una variable n, con n perteneciente a los Naturales.

Procederemos de la siguiente manera:

• Verificaremos la proposición para el numero 1.

• Supondremos que la proposición es verdadera para un numero natural cualquiera k. (Hipótesis de inducción).

• Demostraremos la proposición para el numero natural (k+1).

Así, gracias al axioma de inducción Matemática, podemos concluir que la proposición la satisfacen todos los números naturales.

 !Ejemplo 1:

Demostraremos que:

1+2+3+…………+n = n(n+1), “ n perteneciente a los naturales (*)

1= 1(1+1). Por lo tanto 1 satisface la proposición (*)

Supongamos valida la proposición (*) para k perteneciente a los Naturales, es decir supongamos que:

1+2+3+………+k = k(k+1). (Hipótesis de inducción).

Demostremos que k - 1 también satisface la proposición (*), es decir, demostremos que:

1+2+3+………+k+(k+1) = (k+1)(k+2).

Demostración:

(1+2+3+…….+k)+(k+1) = k(k+1) + (k+1)

= k(k+1)+2(k+1)

= (k+1)(k+2)

Luego la proposición (*) es verdadera “n perteneciente a los naturales.

En resumen, primero demuestras reemplazando el n por un 1, luego demuestras reemplazando el n por un k y finalmente lo demuestras reemplazando el n por (k+1).

En conclusión la inducción es válida por la construcción misma del conjunto de los naturales mediante los axiomas de Peano. De hecho, la inducción imita la construcción del conjunto: 0 es un natural, y, si n lo es, entonces n+1 (sucesor de n) lo es también.

Existen otras inducciones, para otros conjuntos elaborados de forma distinta, como por ejemplo la inducción transfinita, y la inducción sobre las fórmulas de la lógica proposicional.

Además de la Demostración por Inducción, existe la definición o construcción por inducción.

‘’‘ ‘’‘