• Author / Uploaded
• Nicolas Sanchez

Citation preview

Algoritmo de Brooks David Santiago Martínez 20171020150 Fredy Nicolas Sanchez 20171020158 Jairo Buitrago Villalobos 20171020002

Definición general El algoritmo de Brooks es un algoritmo que nos ayuda a determinar el número cromático o el valor máximo de este en un grafo G.

R. Leonard Brooks

Caso 1:

Rowland Leonard Brooks (6 de febrero de 1916 - 18 de junio de 1993), fue un matemático inglés, conocido por probar el teorema de Brooks sobre la relación entre el número cromático y el grado de los gráficos. Nació en Lincolnshire, Inglaterra, estudió en el Trinity College , en la Universidad de Cambridge , y también trabajó con sus compañeros de Trinity WT Tutte , Cedric Smith y Arthur Harold Stone en el problema de " cuadrar la plaza " (dividiendo rectángulos y cuadrados en cuadrados desiguales), tanto con sus propios nombres como con el seudónimo de Blanche Descartes.

Sea G un grafo conexo, no completo y con número par de vértices, entonces: X(G)⩽𝚫 X(G) →Número Cromático 𝚫 → Valencia Máxima7

Caso 2: Sea G un grafo conexo, circular o completo y con un número impar de vértices, Entonces: X(G)=𝚫+1

Es un proceso iterativo, mediante el cual habrán de programarse las actividades de algún proyecto, cuando existe limitación en la cantidad de recursos disponibles. Para decidir la secuencia que seguirán las actividades se trabaja en función al “tiempo de control” de cada una de ellas. Considerando el” tiempo de control” como la máxima duración de todas las posibles trayectorias sobre la red, a partir de cada una de las actividades. A este tiempo de control se le llamará ACTIM

Ejemplo:

determina la ruta crítica como se ve en la siguiente gráfica. Al analizar la gráfica podemos ver que las posibles trayectorias de las rutas son: 1-2→2-3→3-4→5 y 1→5 con una duración de 16 unidades de tiempo cada una.

tiempo actual en el que se asignan los recursos para dichas actividades. Por otro lado, las actividades que no pueden programarse se desplazan al próximo periodo de tiempo y esperan a que se liberen recursos para ser programadas.

PASO 2: Comparar los recursos disponibles con los requerimientos de cada una de las actividades para determinar si el proyecto puede ejecutarse; en este caso todas las actividades requieren una unidad de recurso y la cantidad disponible es de 3 unidades, por lo cual es posible ejecutar el proyecto. Donde:

Supongamos que se tiene un proyecto que consta de 7 actividades y que para su realización se dispone de tres unidades de recursos; la información de las actividades, su requerimiento de recursos y la duración como se muestra en la siguiente tabla:

PASO 1: DESARROLLO DE LA RED Y DETERMINACIÓN DE LA RUTA CRÍTICA:El primer paso es realizar el grafo (RED) y se

TTI=Tiempo de inicio de cada actividad cuando no existe limitación de recursos TT= Es el tiempo de determinación de cada actividad. TT= TI + Duración de la actividad PASO 4: CÁLCULO DE TIEMPOS Y DETERMINACIÓN DE LA SECUENCIA DE LAS ACTIVIDADES DEL PROYECTO: En este paso se tiene que determinar si en un periodo particular las actividades disponibles pueden programarse tomando en consideración tanto el nivel como el requerimiento de recursos, si puede hacerse, entonces es necesario determinar los tiempos de inicio y terminación para esas actividades, así como establecer el

TRI= Es el tiempo más rápido para iniciar una actividad. El tiempo verdadero(TA) será mayor o igual que TRI. TRI es igual al TT para todas las actividades predecesoras. TA= Es el tiempo en el cual se está considerando la asignación de recursos. Inicialmente es 0 pero subsecuentemente es igual al mínimo TT de las actividades.