Grafos Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo. Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). 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. Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos. Cada arco en un grafo se especifica por un par de nodos. TERMINOLOGÍA *.-Al número de nodos del grafo se le llama orden del grafo. *.-Un grafo nulo es un grafo de orden 0 (cero). *.-Dos nodos son adyacentes si hay un arco que los une. *.-En un grafo dirigido, si A es adyacente de B, no necesariamente B es adyacente de A *.-Camino es una secuencia de uno o mas arcos que conectan dos nodos. *.-Un grafo se denomina conectado cuando existe siempre un camino que une dos nodos cualesquiera y desconectado en caso contrario. *.-Un grafo es completo cuando cada nodo esta conectado con todos y cada uno de los nodos restantes. *.-El camino de un nodo así mismo se llama ciclo. Grafos dirigidos Un grafo dirigido G, también llamado digrafo o grafo, es lo mismo que un multigrafo, solo que cada arista e de G tiene una dirección asignada o , en otras palabras ,cada arista e está identificada por un par ordenado (u,v) de nodos G en vez del par desordenado [u.v]. Suponga que G es un grafo dirigido con una arista dirigida e=(u,v).Entonces e también se llama arco . Más aún se usa la siguiente terminología: (1) e empieza en u y termina en v (2) u es el origen o punto inicial de e ,y v es el destino o punto terminal de e . (3) u es un predecesor de v y v es un sucesor o vecino de u (4) u es adyacente hacia v y v es adyacente a u El grado de salida de un nodo u de G, escrito gradsal(u), es el número de aristas que empiezan en u similarmente , el grado de entrada u, escrito gradent(u), es el número de aristas que terminan en u. Un nodo u se llama fuente si tiene un grado de salida positivo y un grado de entrada nulo . Similarmente u se le llama sumidero si tiene un grado de salida nulo y un grado de entrada positivo. GRAFOS Y MULTIGRAFOS Un grafo G consiste en dos cosas: (1) Un conjunto V de elementos llamados nodos (o puntos o vértices) (2) Un conjunto E de aristas tales que cada arista e de E esta identificada por un único (desordenado) par [u,v] de nodos de V, denotado por e-[v,u]. A veces denotamos un grafo escribiendo G=(V,E) Suponga que e =[u,v]. entonces los nodos u y v se llaman extremos de e, y u y v se dice que son nodos adyacentes o vecinos. El grado de un nodo u, escrito grad(u), es el número de artistas que contienen a u.si grad(u)= 0, o sea, si u no pertenece a ninguna arista--- entonces se dice que u es un nodo aislado. Un camino P de longitud n desde un nodo u se define como la secuencia de n +1 nodos.