Grafos

Grafos es una representación grafica de diversos puntos que se conocen como nodos o vértices, los cuales se encuentran unidos atreves de líneas que reciben el nombre de aristas.
DEFINICION DE TEORIA DE GRAFO.
En la teoría de grafo se usa la siguiente definición un árbol binario es un grafo conexo, a cíclico y no dirigido tal que el grado de cada vértice no es mayor a 3. De esta forma soloexiste un camino entre un par de nodos.
Buena parte de la terminología para grafos dirigidos es aplicable también a los no dirigidos. Por ejemplo, los vértices V, W son adyacente si (V, W) es una arista [ o, en forma equivalente, si (W,V lo es ]. Se dice que la arista (V, W) es índice sobre los vértices V y W.
Un camino es una secuencia de vértices V1, V2……….un tal que (Vi, Vi + 1) es una arista para1=i<n, un camino es simple si todos sus vértices son distintos con excepción de V1 y Vn que puede ser el mismo. La longitud del camino es n-1, el número de aristas a lo largo del camino. Se dice que el camino V1, V2…..,Vn conecta V1 y Vn.
Un grafo es conexo si todas sus partes están conectadas.
Sea G= (V, A) un grafo en conjunto de vértices V y conjunto de aristas A. Un subgrafo de G es ungrafo G = (V, A) donde:
1.-V’ es un subconjunto de V
2.-A’ consta de aristas (V, W) en A tales que V, W están en V’.
3.- A’ consta de todas las aristas (V, W) en A, tal que V, W están en V’,
Entonces G’ se conoce como un subgrafo inducido por G.
MÉTODOS DE REPRESENTACIÓN
Los métodos de representación de grafos dirigidos se pueden emplear también para representar los no dirigidos. Un aristano dirigido entre V, W se representa únicamente con dos aristas dirigidas, una de V a W y otra de W a V.
ARBOLES ABARCADORES DE COSTO MINIMO
Los vértices del grafo representan ciudades y el arista, las posibles líneas de comunicación entre ellas. El costo asociado a una arista representa el costo de seleccionar esa linea para la red. Un árbol abarcador de costo mínimo representa una red quecomunica todas las ciudades a un costo mínimo.
RECORRIDOS DE GRAFOS
Es un gran número de problemas con grafos, es necesario visitar sistemáticamente los vértices del grafo. Las búsquedas en profundidad y en amplitud, temas de esta sección, son dos técnicas importantes para hacerlo. Ambas técnicas pueden utilizarse para determinar de manera eficiente todas las vértices que están conectadas a unvértice dado.
GRAFOS NO DIRIGIDOS
Un grafo no dirigido G = (V, A) consta de un conjunto finito de vértices V y de un conjunto de aristas A. Se diferencia de un grafo dirigido en que cada arista en A es un par no ordenado de vértices. Si (V, W) es una arista no dirigida, entonces (V, W) = (W, V). De ahora en adelante se hará referencia a los grafos no dirigidos tan solo como grafos.
Los grafos seemplean en distintas disciplinas para modelar relaciones simétricas entre objetos. Los objetos se representan por el vértice del grafo, y dos objetos esta conectados por una arista si están relacionados entre si. En este capítulo se presentan varias estructuras de datos que pueden utilizarse para representar grafos y los algoritmos para tres problemas comunes que se relacionan con grafos nodirigidos.
Construcción de arboles abarcadores minimales componentes biconexos y comparaciones maxi males.
PAREAMIENTO DE GRAFO.
En este capítulo se bosquejara un algoritmo para resolver << problemas de paramiento >> en grafos. Un ejemplo simple de parámetros ocurre cuando se tiene un conjunto de profesores para distribuir en el conjunto de cursos.
Esto se representa con un grafo dondelos vértices están divididos en dos conjuntos V1 y V2, de modo que los vértices de conjunto V1 representa a los profesores y los vértices en V2 los cursos que el profesor V sea adecuado para impartir el curso de W se representa con un arista (V, W) un grafo como este cuyo vértice se puede dividir en dos grupos disjuntos y las aristas presentan un extremo en cada grupo se conoce como BIPARTIDO....