Teorias De Grafos En Informatica

MATEMATICA APLICACIONES DE LA TEORIA DE GRAFOS EN LA INFORMÁTICA
CONTENIDO
Introducción
Proposito
Formulacion del problema y justificacion
Objetivos
Grafos
Historia
Definicion
Tipos de grafos
Modelos de los grafos
Aplicaciones
Arboles
Arbol Binario
Arbol de decision y aplicaciones
Software algoritmos voraces

INTRODUCCIÓN
La teoría de grafos también llamada teoría de lasgráficas, es una disciplina que es importante tanto para las matemáticas como para la teoría de la computación. En esta última disciplina todo es manejado a través de los grafos que son estructuras discretas que constan de puntos y de líneas que se conectan entre sí. Es importante saber que existen diferentes tipos de grafos, que se distinguen entre sí por el tipo y el número de líneas que pueden conectarpara cada par de puntos.
PROPOSITO
Se encuentran muchos problemas informáticos que pueden ser resueltos a través de la teoría de grafos.
El propósito principal es mostrar algunas de las aplicaciones que contienen la teoría de grafos y cómo se pueden resolver, con la ayuda de las matemáticas.
Algunos de los temas relacionados con dichas aplicaciones son:
Las estructuras de datos como losgrafos.
El diseño de circuitos planos.
La solución de variados problemas en campos tan particulares como la teoría de juegos, redes telefónicas, eléctricas, bases de datos, sistemas operativos y de comunicaciones en general.
FORMULACION DEL PROBLEMA Y JUSTIFICACION
Formulación del problema
El problema básicamente se centra en la falta de información sobre algunas aplicaciones informáticas desdeun tema tan amplio como es la teoría de grafos.
Lo que pretendemos solucionar es contar rápidamente con un texto, en el cual se puedan encontrar algunas de las más importantes aplicaciones informáticas en el ámbito de la teoría de grafos.
Justificación de la investigación
La finalidad de nuestro trabajo es proveer de un texto en donde se encuentren algunas de las más grandes e importantesaplicaciones informáticas, teoría y terminología básica de la teoría de grafos, a los estudiantes de informática matemática e ingeniería de Sistemas, los cuales apenas empiezan a estudiar la teoría de grafos y a comprender que ésta puede ser de gran ayuda para la ciencia de la computación ya que a través de ella se logran muchas de las aplicación mostradas alrededor de toda su carrera.

OBJETIVOSObjetivo General:
Conformar un proyecto que muestre algunas de las aplicaciones de la teoría de grafos en las redes de comunicaciones, manejo de información y secuencia de programas.
Objetivos Específicos:
Mostrar ejemplos y aplicaciones de la teoría de grafos en el diseño y estructura de redes de comunicaciones.
Establecer situaciones donde se muestra la importancia de los grafos dirigidos en laejecución de programas
Diseñar estructuras de bases de datos mostrando la utilidad de los grafos a través de ejemplos ilustrados.
GRAFOS

Estructura que consta de un conjunto de puntos y lineas.
REPRESENTACIÓN DE GRAFOS EN PROGRAMAS

Representación mediante matrices

Representaciónmediante listas
TIPOS DE GRAFOS
grafo simple
grafo dirigido
multigrafo

Pseudografo

MODELOS CONGRAFOS
Grafos de llamadas
Puede usarse un multigrafo dirigido para representar llamadas: cada vértice representa un número de teléfono y cada arista representa una llamada.
La arista que representa una llamada sale del número del teléfono desde el que se hace la llamada y llega al número de que lo recibe.
Grafo de la Red
La red de Internet se puede representar mediante un grafo dirigido en elque cada pagina Web está representada por un vértice y en el que una arista comienza en la pagina a y termina en la pagina b si hay un enlace en la página a que conduce a la pagina b.
Grafos de precedencia y procesamiento concurrente
Los Sistemas Operativos, pueden ejecutarse más rápidamente si ciertas sentencias se ejecutan simultáneamente. Es importante no ejecutar sentencias que requieran...