grafos

PROGRAMACIÓN EN TIEMPO REAL






ING. ARIEL BENJAMIN DE LA ROSA ZAPATA







INTEGRANTES:




Carmona Cabrera Daniel




PROYECTO DE INVESTIGACION





EQUIPO No:








Soledad de Graciano Sánchez S.L.P. 5 de septiembre del 2013
CONTENIDO
Índice de figuras…………………………………………………………………….……III
Índice de Tablas…………………………………………………………………….……IVIntroducción…………………………………………………………………..……………1
Desarrollo…………………………………………………………………..………………2
1.1 Introducción a grafos………………..………………… ……………...……………..2
1.2 Caminos y Ciclos. ………………………………………….…………………………3
1.3 Ciclos Hamiltonianos ………………………………………….……………..………4
1.4 Algoritmos de la ruta más corta. ……..………………………………………..……5
1.5 Representaciones gráficas…………………………………………………..………6
1.6 Isomorfismo.……………………………………………………………..……………7
1.7 Grafos planares. ……………………………………………………………...………8
1.8 Algoritmos para uso grafos………………………………………………..…………8
1.9 Ejercicio de la locura instantánea…………………………………………..………9
Conclusiones……………………………………………………………………………12
Bibliografía……………………………………………………….……….………………11
2.1 Arboles…………………………………………………………………….…….……14
2.2 Arboles con Raíz……………..……………………….…….…….………….……..16
2.3 Árbol binario.…..…….……………………………………….………….……………17
2.4 Arboles generadores………..…………..……………….….…………..………….17
2.5 Algoritmo de Prim……………………………..………….……..………..…………18
2.6 Algoritmo de Dijkstra……………………………..…….…………………..……….26

Unidad III.- codificación…………………………………….…….…………..…………27
3.1 Grupos……………………………………………..……………………...………….28
3.2 Propiedades de los grupos….……………………………….………….………….28
3.3vIsomorfismo de grupos……………………..............…………..…………………31
3.4 Grupo depermutaciones………………………………………………..………….31
3.5 Homomorfismo de grupos………………………………….……..………………..33
3.6 Conclusiones………………………………………………….……….……………34


UNIDAD IV

Introducción……………………………………………….…………………….…..…30
4.1. Introducción a lenguajes y autómatas……………………………………….…30
4.2. Circuitos secuenciales y máquinas de estado finito………………….…....…31
4.3. Autómatas de estado finito…………………………………………….…..……31
4.4. Lenguajes y gramáticas……………………………………………….…………32
4.5. Autómatas deestado finito no determinista……………………………...……33
4.6. Relación entre lenguajes y autómata……………………………………..……34
Conclusiones……………………….…………………………………………………..34


UNIDAD v

Introducción……………………………………………….…………..………….…..…34
5.1 Definición……………………………………………………….…..…………….…34
5.2. notación para la maquina de turing …………………….……….…..….…....…34
5.3. Descripción instantánea deMT…………….……………………….….…..……36
5.4. Lenguajes de una MT………………………………...…………….…..…………37
5.5. MT de varias cinatas …………………………………………………...…...……37
5.6. MT no determinante…………………………………………..……………..……38
5.7. MT con cinta semi-infinita ……………………………………………….…....…38
5.8. MT multitarea……...…….……………………………………………….…..……39
5.9. Maquinas contadoras..…………...………………………………………………40. Ejemplo demostrativo de MT (examen) ……………..……………….………..……40Conclusiones……………………….…………………………………………………..41

UNIDAD VI………………………………………………………………………………42
Introducción……………………………………………………………………………..42
6.1 Modelado de Redes………………………………………………………………..42
6.2 Algoritmo de flujo Maximo………………………………………………………….43
6.3 Teorema de flujo máximo y corte minimo……………………………………...…44
6.4 Acoplamiento…………………………………………………………………...……45
6.5 Redes de petri……………………………………………………………………….45
Conclusiones……………………………………………………………………………..46Bibliografía………………………………………………………………………………..47



















ÍNDICE DE FIGURAS
1. Fig.1 pág.3
Representación de un camino

2. Fig. 2 pág. 3
Representación de un circuito
Simple imagen de representacion

3. Fig. 3 pág. 4
Imagen de un circuito Hamiltoniano
Pasa por todos los vértices y termina en el origen

4. Fig. 4 pág. 5
Imagen de un Algoritmo Dijkstra
Como hacer un algoritmo deeste tipo

5. Fig. 5 pág. 7
Imágenes de dos Ismorficos
Diferentes tipos de formas pero isomorficos

6. Fig. 6 pág. 8
Comparación de un grafo planar
(Izquierda...