Grafos

GRAFOS
Definición
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énllamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos.

Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos. Cada arco en un grafose especifica por un par de nodos.
El conjunto de nodos es {A, B, C, D, F, G, H} y el conjunto de arcos {(A, B), (A, D), (A, C), (C, D), (C, F), (E, G), (A, A)} para el siguiente grafo. Si lospares de nodos en los arcos dirigidos, el grafo se denomina grafo directo, dirigido o dígrafo.


Características
Al número de nodos del grafo se le llama orden del grafo.
Un grafo nulo es un grafo deorden 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 más arcosque 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 estáconectado con todos y cada uno de los nodos restantes.
El camino de un nodo así mismo se llama ciclo.


Funcionamiento
La cabeza de cada flecha representa el segundo nodo en el par de nodosordenados que hacen un arco, mientras que la cola de la flecha representa el primer nodo en el par.
un nodo n se dice que es incidente a un arco x, si n es uno de los dos nodos en el par ordenado de nodosque componen x. (también se dice que x es incidente a n). El grado de un nodo es el numero de arcos incidentes a él.
Un nodo n es adyacente al nodo n si existe un arco de m a n.
Una relación R en unconjunto A es un grupo de pares ordenados de elementos de A. Si (x,y) es un miembro de la relación R, entonces x se dice que está relacionado con y en R.
Una relación se puede representar por un...