Grafos. Elementos y Características

REPÚBLICA BOLIVARIANA DE VENEZUELA[pic 1]

MINISTERIO DEL PODER POPULAR PARA LA EDUCACIÓN UNIVERSITARIA, CIENCIA Y TECNOLOGÍA

UNIVERSIDAD POLITÉCNICA TERRITORIAL DEL ESTADO ARAGUA

“FEDERICO BRITO FIGUEROA”.

LA VICTORIA, ESTADO ARAGUA

[pic 2]

[pic 3]

Profesor:   Prof. Richard Barràez                   Autor (es):

Matemática Aplicada                                      TSU. Oliveros, Kariney  

                                                                        C.I.: V-19.268.804

                                                                        TSU. Pérez, Hairam            

                                                                        C.I.: V-24.669.510

                                                                        TSU. Piñero, Tita

                                                                        C.I.: V-08.589.231

                                                                        Sección: 1 Informática Nocturno

                                                                         Trayecto IV

La Victoria, Julio del 2017

INDICE GENERAL

Introducción…………………………………………………………………....1

Índice General………………………………………………………………....2

1. Definición………………………………………………………………5

1. Grafos……………………………………………………………….5
2. Elementos y Características………………………………………5
3. Componentes……………………………………………………….6
4. Tipos de Grafos……………………………………………………..7
5. Complementos de un Grafo……………………………………….8
6. Representación de un Grafo………………………………………10

1. Aplicación de la Teoría de Grafos…………………………………..

2.1 En la Telemática……………………………………………………

2.2 Redes o Comunicaciones………………………………………..

2.3 Tránsito Terrestre o Aérea Marítimo…………………………..

2.4 Mapas (cartografía)……………………………………………….

2.4 Organigrama……………………………………………………….

1. Aplicación en la Informática………………………………………..

3.1 Programación……………………………………………………..

3.2 Redes……………………………………………………………..

3.3 Base de Datos……………………………………………………

Conclusión…………………………………………………………………….

INTRODUCCIÒN

La investigación se realizó con base al tema central que son los “Grafos” las cuales esta divididas Definición, características y aplicación. El nacimiento del concepto “Grafos” se puede situar, por  el año 1730, cuando Euler (matemático) se convirtió en el padre de la Teoría de Grafos al modelar un famoso problema no resuelto, llamado el "problema de los puentes de Königsberg". [pic 4]

 Hace referencia a un río con dos islas que atraviesa la ciudad; las islas están unidas entre sí y con las orillas, a través de (7) siete puentes. El problema consistía en establecer un recorrido que pasara una y sólo una vez por cada uno de los (7) siete puentes, partiendo de cualquier punto y regresando al mismo lugar. [pic 5]

Por consiguiente para probar que no era posible, Euler sustituyó cada zona de partida por un punto y cada puente por un arco, creando así un grafo; el 1er primer grafo, diseñado para resolver un problema, entonces mostrar que el problema no tiene solución equivale a mostrar que el grafo no puede ser recorrido según criterios determinados. [pic 6]

Además en un problema genérico, dado un grafo (con múltiples líneas entre pares de puntos) se debe encontrar un camino que recorra el grafo pasando por cada arista exactamente una vez.

Finalmente la solución del grafo debe ser conexo, y en cada punto deben incidir un número par de líneas. Esta condición es suficiente para definir lo que se llama un ciclo euleriano. A partir del matemático Euler, el modelado mediante grafos fue ampliando esta metodología hasta convertirse en la actualidad, en una herramienta de trabajo para ciencias tan diferentes como la Física, la Química, la Psicosociología, la Economía, la Lingüística, entre otros.

Así mismo la teoría de grafos está íntimamente relacionada con varias ramas de la Matemática como por ejemplo: la Teoría de Conjuntos, el Análisis Numérico, Probabilidad, Topología, entre otros; siendo la base conceptual en el tratamiento de problemas combinatorios. Más aún, la eficacia de los grafos se basa en su gran poderío de abstracción y la representación de cualquier relación (de orden, precedencia, etc.), lo que facilita enormemente tanto la fase de modelado como de resolución del problema.

Gracias a la Teoría de Grafos se han desarrollado una gran variedad de algoritmos y métodos de resolución eficaces que nos permiten tomar una mejor decisión. No se debe confundir el grafo con el sistema real al que está asociado. El grafo es una estructura que admitimos adecuadamente en lo concerniente a las propiedades que nos interesan, donde luego aplicamos las deducciones y reglas matemáticas para obtener datos y poder decidir.

Una aplicación frecuente de la teoría de grafos es el método de camino hamiltoniano óptimo para decidir el camino a seguir por un cobrador, de tal modo de economizar sus energías, las suelas de sus zapatos y su bolsillo. El objetivo es hallar un camino que pase por todos las casas una y solo una vez y que nos del costo menor en distancia. Dicho de otro modo, se deben buscar las permutaciones de las casas de forma tal que la distancia recorrida total sea mínima. Se conoce la distancia entre cada par de casas, según si las calles son flechadas o no se orientarán o no las conexiones entre pares de casas. [pic 7]

...