TRABAJO DOMICILIARIO
1.- De la Diapositiva de GRAFOS. Los conceptos de las siguientes palabras:
GRADO DE UN NODO:
El grado de un nodo es la cantidad de aristas que inciden en él. Una arista
"incide" en un nodo si lo conecta con otro nodo (o consigo mismo, en el
caso de un bucle). En un grafo simple, el grado de un nodo es igual a la
cantidad de vecinos que éste tiene.
LAZO O BUCLE:
Un bucle o lazo (loop en inglés) en un grafo o dígrafo es una arista que
conecta al mismo vértice consigo mismo. Un grafo simple no puede tener
bucles.
Camino:
En Teoría de Grafos, se llama camino a una secuencia de vértices dentro de
un grafo tal que exista una arista entre cada vértice y el siguiente.
Grafo conexo:
Un grafo dirigido tal que para cualesquiera dos vértices u y v existe un
camino dirigido de ida y de regreso se dice que es un grafo fuertemente
conexo.
Grafo árbol:
En álgebra, matemática discreta, programación, informática, dícese del
grafo que es simple conexo y que no contiene ciclos.
Grafo completo:
Un grafo es completo si existen aristas uniendo todos los pares posibles de
vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los
une. El conjunto de los grafos completos es denominado usualmente,
siendo el grafo completo de n vértices.
Grafo etiquetado:
Formalmente, dado un grafo G, un vértice etiquetado es una función que
hace corresponder vértices de G a un conjunto de etiquetas. Un grafo con
tal función definida es llamado grafo de vértices etiquetados. En este caso,
G es llamado como grafo de aristas etiquetadas.
Multígrafo:
Un multígrafo o pseudografo es un grafo que está facultado para tener
aristas múltiples; es decir, aristas que relacionan los mismos nodos. De esta
forma, dos nodos pueden estar conectados por más de una arista.
Subgrafo:
Un subgrafo de un grafo G es un grafo cuyo conjunto de vértices es un
subconjunto del de G, cuyo conjunto de aristas es un subconjunto del
conjunto de las aristas de G, y tal que la aplicación w es la restricción de la
aplicación de G.
DIJSKSTRA:
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es
un algoritmo para la determinación del camino más corto dado un vértice
origen al resto de vértices en un grafo con pesos en cada arista. Su nombre
se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
FLOYD - WARSHALL:
En informática, el algoritmo de Floyd-Warshall, descrito en 1959 por
Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el
camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el
camino entre todos los pares de vértices en una única ejecución.
Subgrafo inducido:
Subgrafo inducido por un conjunto de vértices: Sean G' = (V',A') y G = (V,A),
y G' es un subgrafo de G, se dice que G' es un subgrafo de G inducido por V',
si G' contiene todas las aristas de G, restringido a los vértices de V'.
Árbol libre:
El problema consiste en decidir si un grafo no dirigido es árbol libre o no. La
entrada está compuesta por diversos casos de prueba. Para cada caso, la
primera línea contiene el número de vértices del grafo, V (entre 1 y 10.000),
y la segunda el número de aristas, A (entre 0 y 100.000).
Árbol abarcador:
Un árbol abarcador de G es un subgrafo de G que es un árbol y contiene
todos los vértices de G. Teorema 1: si a y b son vértices de un árbol R= (V, A)
entonces hay un camino único que conecta estos vértices. ... Teorema 2: si
G= (V, A) es un grafo no dirigido, entonces G es conexo si y solo si tiene un
árbol abarcador.
PRIM:
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos
para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido
y cuyas aristas están etiquetadas.
KRUSKAL:
El algoritmo de Kruskal es un algoritmo de la teoría de grafos para
encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es
decir, busca un subconjunto de aristas que, formando un árbol, incluyen
todos los vértices y donde el valor de la suma de todas las aristas del árbol
es el mínimo.
2.- Desarrollar los siguientes ejercicios:
Actividad Precedente Tiempo
inmediato Optimista
A - 7
B - 3
C A 7
D A 9
E B,C 10
F D 4
G D 8
H E,F 5
I G,H 7
J I 6
K I 10
L J 5
M K 3
N L,M 9
Construir:
a) Realizar la Red de actividades
b) Calcular la Ruta critica
c) Identificar las holguras
d) Construir el diagrama Gantt
e) Elaborar el PERT. Donde:
➢ Deberás considerar tus propios datos del tiempo probable y el
tiempo pesimista
➢ Determinar la estimación del proyecto al 95%.
➢ Considerar para ello; Las estimaciones de cada actividad, desviación
estándar y varianza
A) Realizar la Red de actividades
B) Calcular la Ruta critica
RUTA CRITICA
A+C+E+H+I+K+M+N= 58
C) Identificar las holguras
D) Construir el diagrama Gantt
E) Elaborar el PERT. Donde:
➢ Deberás considerar tus propios datos del tiempo probable y el tiempo pesimista
➢ Determinar la estimación del proyecto al 95%.
➢ Considerar para ello; Las estimaciones de cada actividad, desviación estándar y
varianza
Precedente DESVIACION
Actividad Tiempo Optimista Tiempo Probable Tiempo Pesimista Tiempo Esperado VARIANZA
inmediato ESTANDAR
A - 7 9 11 9 0.67 0.44
B - 3 4 5 4 0.33 0.11
C A 7 9 12 9 0.83 0.69
D A 9 11 13 11 0.67 0.44
E B,C 10 12 14 12 0.67 0.44
F D 4 5 6 5 0.33 0.11
G D 8 10 12 10 0.67 0.44
H E,F 5 6 7 6 0.33 0.11
I G,H 7 8 9 8 0.33 0.11
J I 6 8 10 8 0.67 0.44
K I 10 12 14 12 0.67 0.44
L J 5 6 7 6 0.33 0.11
M K 3 5 7 5 0.67 0.44
N L,M 9 10 11 10 0.33 0.11
RUTA CRITICA
A+C+E+H+I+K+M+N= 71
Precedente Tiempo Tiempo Tiempo Tiempo DESVIACION
Actividad VARIANZA
inmediato Optimista Probable Pesimista Esperado ESTANDAR
A - 7 9 11 9 0.67 0.44
B - 3 4 5 4 0.33 0.11
C A 7 9 12 9 0.83 0.69
D A 9 11 13 11 0.67 0.44
E B,C 10 12 14 12 0.67 0.44
F D 4 5 6 5 0.33 0.11
G D 8 10 12 10 0.67 0.44
H E,F 5 6 7 6 0.33 0.11
I G,H 7 8 9 8 0.33 0.11
J I 6 8 10 8 0.67 0.44
K I 10 12 14 12 0.67 0.44
L J 5 6 7 6 0.33 0.11
M K 3 5 7 5 0.67 0.44
N L,M 9 10 11 10 0.33 0.11
4.47
1 sigma = 68%
2 sigmas = 95% (para este ejemplo nos interesa utilizar el valor de 2 sigmas)
3 sigmas = 99,7%
DESVIACION ESTANDAR=√ 4.47=2.114
MENOR TIEMPO PROBABLE = 71 – 2 (2.114) =66.772 DIAS
MAYOR TIEMPO PROBABLE = 71 + 2 (2.114) =75.228 DIAS
3.- De acuerdo al cuadro que se muestra a continuación, Desarrollar lo siguiente:
a) La red de actividades.
b) El Diagrama Gantt.
c) Estimación de la duración de actividades
Precedente Tiempo Tiempo Tiempo Tiempo DESVIACION
Actividad VARIANZA
inmediato Optimista Probable Pesimista Esperado ESTANDAR
1 - 10 15 17 15 1.17 1.36
2 1 6 7 8 7 0.33 0.11
3 2 2 2 3 2 0.17 0.03
4 3 2 4 5 4 0.50 0.25
5 4 1 1 2 1 0.17 0.03
6 3 3 6 7 6 0.67 0.44
7 5,10 1 1 2 1 0.17 0.03
8 6,7 2 3 4 3 0.33 0.11
9 8 1 1 2 1 0.17 0.03
10 5 1 2 3 2 0.33 0.11
11 9 1 2 3 2 0.33 0.11
2.61
d) Elaborar el PERT. Donde:
➢ Determinar la estimación del proyecto al 95%.
➢ Considerar para ello; Las estimaciones de cada actividad, desviación
estándar y varianza
1 sigma = 68%
2 sigmas = 95% (para este ejemplo nos interesa utilizar el valor de 2 sigmas)
3 sigmas = 99,7%
DESVIACION ESTANDAR=√ 2.61=1.616
MENOR TIEMPO PROBABLE = 36 – 2 (1.616) =32.768 DIAS
MAYOR TIEMPO PROBABLE = 36 + 2 (1.616) =39.232 DIAS
4.- Del primer trabajo que presentaste con diez actividades lógicas. Armar lo
siguiente
Precedente Tiempo Tiempo Tiempo Tiempo DESVIACION
Actividad VARIANZA
inmediato Optimista Probable Pesimista Esperado ESTANDAR
A TRAZO Y REPLANTEO - 1 1 1 1 0.00 0.00
B EXCAVACIONE A 1 2 3 2 0.33 0.11
C CIMIENTO CORRIDO B 1 2 3 2 0.33 0.11
D SOBRECIMIENTO C 2 3 4 3 0.33 0.11
E ZAPATAS B 3 4 7 4 0.67 0.44
F VIGAS DE CIMENTACION B 3 6 7 6 0.67 0.44
G MURO DE LADRILLO DE ARCILLA E 7 8 10 8 0.50 0.25
H COLUMNAS G 5 6 7 6 0.33 0.11
I VIGAS H 3 4 5 4 0.33 0.11
J LOSA ALIGERADA I 4 5 6 5 0.33 0.11
1.81
a) La red de actividades.
b) El Diagrama Gantt.
c) Estimación de la duración de actividades
Precedente Tiempo Tiempo Tiempo Tiempo DESVIACION
Actividad VARIANZA
inmediato Optimista Probable Pesimista Esperado ESTANDAR
A TRAZO Y REPLANTEO - 1 1 1 1 0.00 0.00
B EXCAVACIONE A 1 2 3 2 0.33 0.11
C CIMIENTO CORRIDO B 1 2 3 2 0.33 0.11
D SOBRECIMIENTO C 2 3 4 3 0.33 0.11
E ZAPATAS B 3 4 7 4 0.67 0.44
F VIGAS DE CIMENTACION B 3 6 7 6 0.67 0.44
G MURO DE LADRILLO DE ARCILLA E 7 8 10 8 0.50 0.25
H COLUMNAS G 5 6 7 6 0.33 0.11
I VIGAS H 3 4 5 4 0.33 0.11
J LOSA ALIGERADA I 4 5 6 5 0.33 0.11
1.81
d) Elaborar el PERT. Donde:
➢ Determinar la estimación del proyecto al 95%.
➢ Considerar para ello ; Las estimaciones de cada actividad, desviación estándar
y varianza.
➢ NOTA: Considerar tu propia base de datos para resolver Los tiempos
Optimista, Normal y Pesimista.
1 sigma = 68%
2 sigmas = 95% (para este ejemplo nos interesa utilizar el valor de 2 sigmas)
3 sigmas = 99,7%
DESVIACION ESTANDAR=√ 1.81=1.345
MENOR TIEMPO PROBABLE = 30 – 2 (1.345) =27.31 DIAS
MAYOR TIEMPO PROBABLE = 30 + 2 (1.345) =32.69 DIAS
