Teoría De Grafos

Grafos:

* Un Grafo es una Terna G = [ V,A, g] donde:
* V es un Conjunto No vacío (VERTICES).
* A es el Conjunto llamado (ARISTAS).
* g es una función que asigna a cada arista a∈A, un par no Ordenado de vertices {u,v}.
Diremos: Que u y v Son los extremos de a.
Diremos: Que u y v Son ADYACENTE si A diferente vacío.
Diremos: Que g es NULO cuandotiene n-vértices y A es vacío se Denota Nn.

Llamaremos LAZO de G a cualquier arista aЄ A (que tenga igual sus dos extremo).
Dado {u ,v} , el GRADO de v es el numero de incidencias de aristas en v y lo denotamos por gr(v).
Para cada par de{ u,v} La MULTIPLICIDAD es el numero de aristas q tiene un extremo en u, y el otro extremo en v; es Denotado m(u,v).
Un Vértice AISLADO en G, en un vérticeque tiene grado a 0.
Un Vértice COLGANTE en G, es un vértice que tiene grado a 1.

Definición:
Un Grafo G= [V,A,g] es llamado grafo finito cuando los conjuntos V y A son finitos, con n-vértices y n-aristas.

* MATRIZ DE ADYACENCIAS de G es la matriz cuadra nxm Denotada por Ma(G), cuyas componentes ij es la Multiplicidad m(m,v)
* MATRIZ DE INCIDENCIAS de G es la Matriz mxn denotadaMi(G) cuya componetes-ij es el número de veces que la arista incide en el vértice.

Grafo Simple
Un grafo simple es un grafo sin lazos ni aristas paralelas.
Teniendo en cuenta que las aristas paralelas son aristas distintas que están asociadas con el mismo par de vértices.
Grafo Regular
Un grafo es regular si todos sus vértices tienen el mismo grado.

Grafo con pesos
Es un grafo connúmeros sobre las aristas.

Grafo completo
Es un grafo con n vértices en el cual existe una arista entre cada par de vértices distintos.

Grafo Conexo
Un grafo es conexo si existe un camino entre cualquier par de vértices, es decir podemos ir de cualquier vértice a cualquier otro por un camino.

Ciclos y Caminos
Caminos
Sean V0 y Vn vértices de un grafo. Si partimos del vértice V0 recorremosuna arista hasta el vértice V1, recorremos otra arista hasta el vértice V2 y así sucesivamente, y en cierto momento llegamos al vértice Vn, llamamos a todo el recorrido un camino o ruta de V0 a Vn.

Veamos un ejemplo llamado el problema del inspector de carreteras.
La siguiente figura muestra el sistema de carreteras en Wyoming, el cual debe ser inspeccionado por una persona. En específico,este inspector de carreteras debe recorrer cada uno de estos caminos y crear un archivo con información acerca de las condiciones de cada camino, la visibilidad de las líneas en los caminos, el estado de las señales de tráfico, etc. Como el inspector de carreteras vive en Greybull, la forma más económica de inspeccionar todos los caminos será comenzar en Greybull, recorrer todos los caminosexactamente una vez, y regresar a Greybull. ¿Es posible? Vea si puede decidir antes de continuar.

Este problema se puede parafrasear para el modelo de grafica G de la siguiente manera: ¿Existe un camino del vértice Gre al vértice Gre que recorra cada arista exactamente una vez?
Podemos mostrar que el inspector de carreteras no puede partir de Greybull, recorrer cada arista exactamente una vez yregresar a Greybull. Para poner la respuesta en términos de gráficas, no existe un camino del vértice Gre al vértice Gre que recorra cada arista exactamente una vez. Para esto, supongamos que existe tal camino y consideremos al vértice Wor. Cada vez que lleguemos a Wor por alguna arista, debemos salir de Wor por alguna arista diferente. Además, hay que utilizar cada una de las aristas que tocan a Wor.Como tres aristas tocan a Wor, tenemos una contradicción. Por tanto no existe camino del vértice Gre al vértice Gre que recorra cada arista exactamente una vez. Entonces se concluye que si una gráfica G tiene un camino del vértice v a v que recorra cada arista exactamente una vez, un número par de aristas debe tocar a cada vértice.

Camino simple
Sean v y w vértices en una grafica G, un...