Monografia Teoria de Grafos

UNIVERSIDAD NACIONAL DE TRUJILLO
Facultad de Ciencias agropecuarias
ESCUELA DE AGRONOMIA




TEORIA DE GRAFOS



MONOGRAFÍA



Por:
Rojas Max Juan Francisco












Trujillo – 2014
Curso de Matemática Básica
























ÍNDICE

Resumen………………………………………………………………………. 1

Introducción........................................................................................... 2I. Grafos - Conceptos fundamentales…………………………….……… 3

1. Aristas
2. Vértices
3. Caminos
II. Representación de grafos………………………………………………… 5

1. Estructura de lista
2. Estructuras matriciales
III. Tipos y caracterización de grafos…………………………………….. 7

1. Grafos dirigidos
2. Multigrafos
3. Grafos conexos
4. Grafos completos
5. Grafos bipartitos
6. Arboles
7. Grafos ponderados

IV.Aplicaciones……………………………………………………………….. 12

Conclusiones………………………………………………………………….. 13
Bibliografía…………………………………………………………………….. 14








RESUMEN
El objetivo está centrado en mostrar los tópicos de la Teoría de grafos para comprender, manejar los conceptos y lograr una eficiente resolución de problemas. Y para poder relacionar la teoría de grafos con problemas de otras ramas de lasmatemáticas y otras disciplinas. Se demuestra que se puede aplicar a diferentes áreas incluida la ingeniería; se utiliza rutinariamente aunque de manera inconsciente en la química, física, electrónica, etc. A diario observamos muchas cosas que nos parecen cotidianas pero se puede decir que forman parte de algo que en matemáticas se denomina como grafos: mapas de carreteras, líneas telefónicas,circuitos eléctricos, automóviles, entre otros.











INTRODUCCION
Al diseñar una red de ordenadores y los enlaces entre ellos podemos representarlo en un dibujo, donde los puntos hacen alusión a los ordenadores y unas líneas que los unen representando los nexos entre ellos.
Este dibujo nos da una idea de lo que es un grafo. Es un conjunto donde los vértices del grafo serían cada uno de losordenadores, mientras que las líneas que los unen serían las conexiones que estableciéramos entre cada par de ordenadores.
La gran cantidad de aplicaciones de los grafos en Matemáticas y otras disciplinas, es la causa por la que la Teoría de Grafos es una de las partes de las Matemáticas que más se ha desarrollado en las últimas décadas. Los problemas clásicos como el de los siete puentes deKönigsberg (El origen de la teoría de grafos se remonta al siglo XVIII con el problema de los puentes, el cual consistía en encontrar un camino que recorriera los siete puentes del río, de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos) o el de la coloración de un mapa, y otros problemas de redes de comunicación, de emparejamiento, vigilancia o diseño de circuitosintegrados son sólo otros ejemplos de aplicación de los grafos.




Imagen 1 Imagen 2
Un grafo como un dibujo Los 7 puentes de Königsberg


I. Grafos - Conceptos fundamentales
II.
La teoría de grafos (también llamada teoría de lasgráficas) es un campo de estudio de las matemáticas, que estudia las propiedades de los grafos (también llamadas gráficas) estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados que pueden ser orientados o no.
La teoría de grafos es una rama de la Matemática discreta y de las aplicadas, y es un tratado que usa diferentes conceptos dediversas áreas como Análisis combinatorio, Álgebra abstracta, probabilidad, geometría de polígonos, aritmética y topología. Actualmente ha tenido mayor preponderancia en el campo de la informática, las ciencias de la computación y telecomunicaciones.
Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de...