Grafos Estructura De Datos

TRABAJO FINAL DE ESTRUCTURA DE DATOS |
LUIS ALBERTO HIPOLITO GAONA ESTRUCTURA DE DATOS INGENIERIA EN COMPUTACION JAQUELINE SANCHEZCENTRO UNIVERSITARIIO UEAM VALLE DE TEOTIHUACAN |
|
|

INTRODUCCION
GRAFOS
¿QUE ES UN GRAFO?
Un grafo en el ambito de las ciencias de la computacion es una estructura de datos,en concreto un tipo abstracto de datos (TAD),que consiste en un conjunto de nodos (tambien llamados vertices) y un conjunto de arcos(aristas) que establecen relacion entre losnodos. El concepto de grafo TAD desciende directamente del concepto matematico de grafo.Informalmente de define como G=(V,E), siendo los elementos V los vertices, y los elementos de E, las aristas.Formalmente, un grafo, G, se define como un par ordenado, G=(V,E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.
El origen de la palabra grafo es griego y susignificado etimologico es trazar,aparececon gran frecuencia como respuesta a los problemas de la vida cotidiana, algunos ejemplos podrian ser los siguientes: un grafo de una serie de tareas a realizar indicando su secuenciacion(un orgamigrama), grafos matematicos que representan las relaciones binarias, una red de carreteras, la red de enlacen ferroviarios o aereos o la red electrica de una cuidad.Encada caso,es conveniente representar graficamente el problema dibujando un graof como un conjunto de puntos(vertices) con lineas conectandolos(arcos).

Los grafos son estructuras de datos no lineales que tienes una naturaleza generalmente dinamica.Su estudio podria dividirse en dos grandes bloques:
* Grafos dirigidos
* Grafos no dirigidos
Un ejemplo de grafo dirigido lo constituye lared de aguas de una ciudad ya que cada tubería solo admite que el agua la recorran n un único sentido. Por el contrario la red de carreteras puede ser recorridas en ambos sentidos.
Un grafo nulo es un grafo de orden cero
Un grafo se denomina simple si no tiene bucles y no existe mas que un camino para unir dos nodos
Un grafo no dirigido es bipartido si el conjunto de sus vértices puede serdividido en dos subconjuntos de tal forma que cualquiera de las aristas que componen el grafo tiene cada uno de sus extremos en un subconjunto distinto. Un grafo no dirigido será bipartido si y solo si no contienen ciclos con un numero de aristas par.
Diremos que dos vértices están conectados si entre ambos existe un camino que los une.

REDES SOCIALES
¿QUE ES UNA RED SOCIAL?
Las redes socialesso n estructuras sociales compuestas de grupos de personas, las cuales estan conectadas por uno o varios tipos de relacion, tales como amistad, parentesco, intereses comunes o que comparten conocimientos, e ideas de libre expresion, puede haber muchos tipos de lazos entre los nodos. La investigacion multidisciplinariar ha mostrado que las redes sociales operan en muchos niveles desde lasrelaciones de parentesco hasta las relaciones de organizaciones a nivel estatal, desempeñando un papel critico en la determinacion de la agneda politoca y el grado en el cual los individuos o las organizaciones alcanzan sus objetivos o reciben influencias.
El analisis de redes sociales estudia esta estructura social aplicando la teoria de grafos e identificando las entidades como nodos o vertic es y lasrelaciones como enlaces o aristas.La estructura del grafo resultante es a menudo muy compleja.Como se ha dicho,en su forma mas simple, una red social es un mapa de todos los lazos relevantes entre todos los nodos.Se habla en este caso de redes “socio centricas” o “completas”.Otra opcion es identificar la red que envuelve a una persona(en los diferentes contextos sociales en los que interactua);...