Teoria de grafos

Solo disponible en BuenasTareas
  • Páginas : 2 (425 palabras )
  • Descarga(s) : 0
  • Publicado : 31 de enero de 2012
Leer documento completo
Vista previa del texto
Que es la teoría de grafos
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadasgráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, ungrafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usadadepende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa unacombinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidadesde memoria.
Para qué sirve
Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utilizapara diferentes áreas por ejemplo, Dibujo computacional, en toda las áreas de Ingeniería.
Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las callesde una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.
Para la administración de proyectos, utilizamos técnicascomo PERT en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.
La teoría de grafos también ha servido de inspiración para las ciencias sociales, enespecial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red....
tracking img