Grafos

GRAFOS
Un grafo G es un par ordenado G = (V,E), donde:
* V es un conjunto de vértices o nodos, y
* E es un conjunto de aristas o arcos, que relacionan estos nodos.
Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.
Se llama orden del grafo G a su número de vértices, | V |.
El grado de un vértice o nodo V es igual alnúmero de arcos E que se encuentran en él.
Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual losvértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Grafo no dirigido
Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V,E) donde:
*
* es un conjunto de pares no ordenados de elementos de .
Un par no ordenado es un conjunto de la forma {a,b}, de manera que {a,b} = {b,a}. Para los grafos,estos conjuntos pertenecen al conjunto potencia de V de cardinalidad 2, el cual se denota por.
Grafo dirigido
Un grafo dirigido o digrafo es un grafo G = (V,E) donde:
*
* es un conjunto de pares ordenados de elementos de .
Dada una arista (a,b), a es su nodo inicial y b su nodo final.
Por definición, los grafos dirigidos no contienen bucles.
Un grafo mixto es aquel que se define conla capacidad de poder contener aristas dirigidas y no dirigidas. Tanto los grafos dirigidos como los no dirigidos son casos particulares de este.
Pseudografo
Un pseudografo es un grafo G = (V,E) donde:
*
* es un conjunto de pares no ordenados de elementos de .
Es decir, un pseudografo es un grafo no dirigido que acepta bucles en .
Pseudografo dirigido
Un pseudografo dirigido es ungrafo G = (V,E) donde:
*
* es un conjunto de pares ordenados y etiquetados de elementos de
Es decir, un pseudografo dirigido es un grafo dirigido que acepta bucles en .

Propiedades
* Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
* Incidencia: una arista es incidente a un vértice si ésta lo une a otro.* Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del vendedor viajero o del camino más corto.
* Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.CERCO CONVEXO

El problema del cerco convexo consiste en encontrar el área más pequeña de un polígono convexo que encierre un conjunto de puntos en el plano.

Sea un conjunto S en el plano; y P un punto en S. Se dice que P es un punto del cerco, si existe una línea L a través de P, tal que todos los puntos en S excepto P, se encuentran a un lado de L (excepto P, ninguno pertenece a la línea).El cerco convexo de un conjunto finito de puntos S, consiste de puntos del cerco ordenados que se encuentran en el borde de S. Para la Figura 16 el cerco convexo es la secuencia de los puntos p1, p2, p3, p4, p5.

El cerco convexo de un conjunto finito de puntos S en el plano, es la secuencia p1, p2, ..., pn de puntos de cercos de S en el siguiente orden:
1. El punto p1 es el punto con lacoordenada mínima y (p1 es un punto de cerco).
2. Para i ≥2, sea i el ángulo desde la horizontal al segmento de línea p1, pi. Los puntos p2, p3, ..., pn están ordenados tal que i, i, ..., n están en una secuencia ordenada.

METODO DE GRAHAM

Es un método de cálculo computacional de la envolvente convexa de un grupo finito de puntos en el plano de complejidad O(nlogn). El nombre hace...