grafos
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...
Regístrate para leer el documento completo.