Programacion En Tiempo Real

1.1 Introducción a los Grafos

Definición de Grafo:
Un grafo es un conjunto de puntos, vértices o nodos, unidos por líneas, aristas.
No hay restricciones para formar un grafo;Puede haber varias aristas entre dos vértices, el vértice de partida y el de llegada puede ser el mismo, Las aristas pueden o no llevar flechas.

Un grafo G es un par G = (V,E), donde V es un conjunto finito(vértices, nodos) y E es un multiconjunto de pares no ordenados de vértices, denotados por {x, y}, que se denominan lados, aristas, etc.

Decimos que x y Y son extremos de {x, y}. Denotamos V (G) por el conjunto de vértices del grafo G y por E(G) el conjunto de lados del grafo G. Además º(G) y "(G) denotan el número de vértices y el número de aristas de G respectivamente.
Puesto que E es un multiconjuntoes posible que existen pares repetidos, en este caso G tiene lados múltiples

Un digrafoes un pseudografodirigidodonde se permite a lo sumo un bucle por vértice y dos aristas entre dos vértices distintos con la condición de que tengan orientaciones opuestas.
Con esta definición cada digrafoG = (V, A)se corresponde con una única relación binaria Aen V y recíprocamente.


Hay varios tiposde grafos.consideramos tres tipos de ellos, libre, completo, regular.

Grafos Libres:
Un grafo G = (V,E) se dice libre si E = ∅, es decir, si no tiene aristas.

Grados Completos:
Un grafo simple G = (V,E) se dice completo si cada vertice esta conectado a cualquier otro vertice en G. El grafo completo con n vertices se denota Kn.

Grafos Regulares
Un grafo G = (V, E) es regular de grado ko k-regular si cada vértice tiene grado k; es decir, un grafo es regular si todos los vértices tienen el mismo grado.

1.2 Caminos y Ciclos:
Los caminos deben realizarse de acuerdo a la dirección de los lados. Si no existen lados múltiples podemos denotar sin ambigüedad la cadena como una sucesión de vértices (vértices consecutivos adyacentes). Una cadena es cerrada si el vértice inicialy final es el mismo. La cadena cerrada es un ciclo si todos los vértices (excepto los extremos) son distintos. El camino cerrado es un circuito si todos los vértices (excepto los extremos) son distintos

Un camino es una sucesión de aristas de manera que, a excepción de la primera, el segundo vértice de una es el primer vértice de la siguiente; Un camino es una sucesión de vérticesv0,v1,v2,…,vn de manera que vi−1 es adyacente de vi, para i=1,2,…,n

Teoremas:
Si en un grafo G todos los vértices tiene grado mayor a 1, pruebe que existe un ciclo.
Existe una cadena de u a v si y sólo si existe un camino simple de u a v.
Muestre que si G es simple y ± ≥ k, entonces G tiene un camino simple de longitud k.

1.3 Ciclos Hamiltoneanos

Se llama ciclo hamiltoniano a un ciclo enel que aparecen todos los vértices una única vez, es decir, a lo largo del ciclo pasamos una, y sólo una, vez por cada uno de los vértices.
La aplicación de este algoritmo exige que el grafo inicial sea completo y de número de vértices impar, llamaremos 2n+1 al número de vértices (asegurando así que es impar).
Para probar que la factorización puede realizarse, consideremos el caso en que n es 1,en ese caso estamos descomponiendo el grafo completo de grado 3.
K3 se descompone en un ciclo hamiltoniano, que es él mismo probemos acontinuacion el caso en el que n toma un valor mayor o igual a 2.
Llamaremos a los vértices de K2n+1, V(K2n+1) = {0, 1,..., 2n} Para formar los ciclo escogemos el último vértice, es decir, el vértice 2n, y formamos caminos con los restantes vértices queposteriormente se unen al vértice 2n Elegimos el primer camino de la siguiente manera: 0, 2n-1, 1, 2n-2, 2, 2n-3, 3, ..., n-1, n.
Los siguientes caminos se forman avanzando una unidad en el número de vértice de cada posición, teniendo en cuenta que el vértice 2n ya está aislado, por tanto, el vértice siguiente a 2n-1 será el vértice 0 (y no el 2n) Finalmente sabremos unir
estos vértices al...