formato 2 (anexo no.3) - · pdf file5 historia de la teoria de grafos la teoría de...
If you can't read please download the document
TRANSCRIPT
FORMATO 2 (Anexo No.3)
FORMULARIO DE LA DESCRIPCIN DE LA TESIS DOCTORAL O DEL TRABAJO DE GRADO
TTULO COMPLETO DE LA TESIS DOCTORAL O TRABAJO DE GRADO: APLICACIONES DE LA TEORIA DE GRAFOS EN LA INFORMTICA
AUTOR O AUTORES
Apellidos Completos Nombres Completos
PIEDRA HERNANDEZ PATERNOSTRO MOVILLA
VIVIANA SOFIA CARLOS ANDRES
DIRECTOR (ES) TESIS DOCTORAL O DEL TRABAJO DE GRADO
Apellidos Completos Nombres Completos
NIETO CLAVIJO
GUSTAVO ADOLFO
TRABAJO PARA OPTAR AL TTULO DE: TESIS DE GRADO FACULTAD: CIENCIAS BASICAS PROGRAMA: Carrera _X_ Licenciatura ___ Especializacin ____ Maestra ____ Doctorado ____ NOMBRE DEL PROGRAMA: INFORMATICA MATEMATICA NOMBRES Y APELLIDOS DEL DIRECTOR DEL PROGRAMA: PATRICIA ARACELY HERNANDEZ ROMERO CIUDAD: BOGOTA AO DE PRESENTACIN DEL TRABAJO DE GRADO: 2009 NMERO DE PGINAS 86 TIPO DE ILUSTRACIONES:
- Tablas y grficos SOFTWARE requerido y/o especializado para la lectura del documento__NINGUNO________
DESCRIPTORES O PALABRAS CLAVES EN ESPAOL E INGLS: Son los trminos que definen los temas que identifican el contenido.
ESPAOL INGLS
Arista no dirigida Arista dirigida Aristas mltiples Bucle Grafo no dirigido Grafo simple Grafo dirigido Multigrafo dirigido Adyacente Incidente Grafo bipartito Hoja Grafo regular Subgrafo
Edge not addressed Directed edge Multiple edges Loop Graph not addressed Simple graph Directed graph Multigraph directed Adjacent Incident Bipartite graph Sheet Regular graph Subgraph
RESUMEN DEL CONTENIDO EN ESPAOL E INGLS: ESPAOL
El principal objetivo es conformar un proyecto que muestre algunas de las aplicaciones de la teora de grafos en las redes de comunicaciones, manejo de informacin y secuencia de programas. Tambin mostrar ejemplos y aplicaciones de la teora de grafos en el diseo y estructura de redes de comunicaciones, establecer situaciones donde se muestra la importancia de los grafos dirigos en la ejecucin de programas y disear estructuras de bases de datos mostrando la utilidad de los grafos a travs de ejemplos ilustrados. La finalidad de nuestro trabajo es proveer de un texto en donde se encuentren algunas de las mas grandes e importantes aplicaciones informticas, teora y terminologa bsica de la teora de grafos, a los estudiantes de informtica matemtica e ingeniera de Sistemas de los primeros semestres, los cuales empiezan a estudiar la teora de grafos y a comprender que sta puede ser de gran ayuda para la ciencia de la computacin, por ende as para sus carreras respectivas. INGLES The main objective is to build a project that shows some of the applications of graph theory in communication networks, information management and sequencing programs. We also show examples and applications of graph theory in the design and structure of communication networks, establish situations, showing the importance of the graph directed in program implementation and design of database structures showing the usefulness of a graph illustrated through examples. The purpose of our work is to provide a text where some of the biggest and important applications, theory and basic terminology of graph theory, students of mathematics and computer engineering of the first semester, the are beginning to study the theory of graphs and understand that it can be very helpful for computer science, and hence for their respective careers.
1
APLICACIONES DE LA TEORIA DE GRAFOS EN LA
INFORMTICA
VIVIANA SOFIA PIEDRA HERNANDEZ
CARLOS ANDRES PATERNOSTRO MOVILLA
2
TRABAJO DE GRADO
INFORMATICA MATEMATICA
PONTIFICIA UNIVERSIDAD JAVERIANA
FACULTAD DE CIENCIAS
CARRERA DE INFORMATICA MATEMATICA
Bogot, D. C.
10 de julio de 2009
3
DEDICATORIA
Este trabajo esta dedicado a quienes nos apoyaron econmica,
fsica, emocional y mentalmente a lograr dar cada paso en
nuestro camino profesional. A nuestros padres, familias y
maestros.
4
RESUMEN
El principal objetivo es conformar un proyecto que muestre algunas de las aplicaciones de la
teora de grafos en las redes de comunicaciones, manejo de informacin y secuencia de
programas. Tambin mostrar ejemplos y aplicaciones de la teora de grafos en el diseo y
estructura de redes de comunicaciones, establecer situaciones donde se muestra la
importancia de los grafos dirigos en la ejecucin de programas y disear estructuras de
bases de datos mostrando la utilidad de loa grafos a travs de ejemplos ilustrados.
La finalidad de nuestro trabajo es proveer de un texto en donde se encuentren algunas de
las mas grandes e importantes aplicaciones informticas, teora y terminologa bsica de la
teora de grafos, a los estudiantes de informtica matemtica e ingeniera de Sistemas de
los primeros semestres, los cuales empiezan a estudiar la teora de grafos y a comprender
que sta puede ser de gran ayuda para la ciencia de la computacin, por ende as para sus
carreras respectivas.
5
AGRADECIMIENTOS
Gracias a Jos Luis Piedra, Reinaldo Paternostro, Carmen
Hernndez y Vilma Movilla, nuestros padres y principales
colaboradores en nuestra educacin. A Gustavo Nieto quien con
su inteligencia y paciencia nos ayudo a crear este trabajo. A
Alejandro Forero.
10 de julio de 2009
6
INDICE
1 INTRODUCCIN .................................................................................................................... 7
2 MARCO TERICO Y REVISIN DE LITERATURA ......................................................... 8
3 FORMULACION DEL PROBLEMA Y JUSTIFICACION .................................................. 9
4 OBJETIVOS ........................................................................................................................... 10
5 HISTORIA DE LA TEORIA DE GRAFOS .......................................................................... 11
7 TRMINOS CLAVE .............................................................................................................. 19
8 DEFINICIONES ..................................................................................................................... 20
9 MODELOS CON GRAFOS ................................................................................................... 29
10 APLICACIONES INFORMTICAS USANDO LA TEORA DE GRAFOS ..................... 33
11 GRAFOS BIPARTITOS ......................................................................................................... 36
12 GRAFOS ISOMORFOS ......................................................................................................... 37
13 CONEXIN ............................................................................................................................ 39
13.1 CAMINOS ....................................................................................................................... 39 13.2 CONEXIN EN GRAFOS NO DIRIGIDOS .................................................................... 41 13.3 CONEXIN EN GRAFOS DIRIGIDOS ........................................................................... 43 13.4 APLICACIONES INFORMATICAS PARA LA CONEXIN ENTRE GRAFOS ............ 45
14 CAMINOS EULERIANOS Y HAMILTONIANOS .............................................................. 47
15 ALGORITMO DE DIJKSTRA .............................................................................................. 51
16 RBOLES ............................................................................................................................... 52
17 INTRODUCCION A LOS RBOLES ................................................................................... 54
18 ARBOL BINARIO .................................................................................................................. 56
19 ALGORITMOS DE RECORRIDOS ..................................................................................... 57
19.1 IN-ORDEN ...................................................................................................................... 57 19.2 PREORDEN ..................................................................................................................... 58 19.3 POSTORDEN .................................................................................................................. 58
20 RBOLES DE DECISIN ..................................................................................................... 61
20.2 APLICACIONES DE RBOLES BINARIOS .................................................................. 64 20.3 APLICACIONES INFORMATICAS DE RBOLES DE DECISION ............................... 70 20.4 RBOLES DE JUEGOS .................................................................................................. 72
21 ARBOL RECUBRIDOR ........................................................................................................ 78
22 ALGORITMO DE KRUSKAL .............................................................................................. 79
23 ALGORITMO DE PRIM ....................................................................................................... 83
24 BIBLIOGRAFIA..................................................................................................................... 91
7
1 INTRODUCCIN
La teora de grafos tambin llamada teora de las grficas, es una disciplina que es
importante tanto para la