Teoría De Grafos
Páginas: 24 (5958 palabras)
Publicado: 1 de febrero de 2013
Tabla de Contenidos
Introducción…………….………...………………………………………………………….. 2
Teoría de grafos………………………………………………………………………………. 3
• Idea Intuitiva….………………………………………………………………………. 3
• Historia………..…………………………………………………………………..…... 3
• Estructuras de datos en la representación de grafos………………………………….. 4
Estructura de lista…………………………………………………………. 5
Estructurasmatriciales……………………………………………………. 6
• 3 Definiciones………………………………………………………………………… 6
Vértice…………………………………………………………………….. 6
Grafo……………………………………………………………………… 6
Subgrafo………………………………………………………………….. 7
Aristas dirigidas y no dirigidas…………………………………………… 8
Ciclos y caminos hamiltonianos………………………………………….. 9
Caracterización degrafos………………………………………………... 10
▪ Grafos simples…………………………………………………. 10
▪ Grafos conexos………………………………………………… 11
▪ Grafos completos……………………………………………… 12
▪ Grafos bipartitos……………………………………………….. 12
Operaciones en Grafos…………………………………………………... 13
▪ Subdivisión elemental de una arista…………………………… 13
▪ Eliminación débil de un vértice……………………………….. 13
Homeomorfismo de grafos………………………………………………. 13Árboles….…………………………………….…………………………... 13
Grafos ponderados o etiquetados………………...………………………. 14
Teorema de los cuatro colores……………………………………………. 14
Grafos planos………………………..………………………………….. 16
Diámetro……….………………..……………………………………….. 17
• Aplicaciones……………………………………………………………………….. 18
Teoría de Nudos………………………………………………………………………………19• Idea Intuitiva………………………………………………………………………… 19
• Historia……………………………………………………………...……………….. 20
• Generalidades sobre la teoría de nudos……………………………………………… 22
• Definición……………………………………………………………………………. 24
• Tabla de nudos………………………………………………………………………. 24
• Diagramas de nudos y movimientos de Reidemeister………………………………. 26
• Aplicaciones…………………………………………………………………………. 28Bibliografía…..………………………………………………………………………………30
Anexos………..………………………………………………………………………………31
Introducción
El siguiente trabajo pretende introducir los temas de teoría de grafos y nudos en el curso de Topología Elemental, desde su fundamento histórico, continuando con las definiciones y ejemplos, para concluir con algunas aplicaciones.
Como aún no cuentocon las bases como para hacer una investigación descriptiva donde pueda emitir juicios propios, me he limitado a la recopilación de información, tratándole de dar un esquema lógico para los que nos estamos iniciando en este tipo de teorías. Mi intención es tratar de tomar los aspectos básicos de la teoría de grafos y nudos, entenderlos y exponerlos de una forma clara y sencilla, de tal forma quemis compañeros y compañeras de curso obtengan los conocimientos previos para la posterior profundización que se llevará a cabo mediante alguna estrategia seleccionada por la profesora del curso.
Para la recopilación de la información se utilizaron esencialmente documentos de algunas páginas de internet, entre ellas es.wikipedia.org y www.mitecnologico.com entre otras.Teoría de grafos
Idea Intuitiva
[pic]
Diagrama de un grafo con 4 vértices y 6 aristas.
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección depares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Historia
El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primer resultado de la teoría de grafos....
Introducción…………….………...………………………………………………………….. 2
Teoría de grafos………………………………………………………………………………. 3
• Idea Intuitiva….………………………………………………………………………. 3
• Historia………..…………………………………………………………………..…... 3
• Estructuras de datos en la representación de grafos………………………………….. 4
Estructura de lista…………………………………………………………. 5
Estructurasmatriciales……………………………………………………. 6
• 3 Definiciones………………………………………………………………………… 6
Vértice…………………………………………………………………….. 6
Grafo……………………………………………………………………… 6
Subgrafo………………………………………………………………….. 7
Aristas dirigidas y no dirigidas…………………………………………… 8
Ciclos y caminos hamiltonianos………………………………………….. 9
Caracterización degrafos………………………………………………... 10
▪ Grafos simples…………………………………………………. 10
▪ Grafos conexos………………………………………………… 11
▪ Grafos completos……………………………………………… 12
▪ Grafos bipartitos……………………………………………….. 12
Operaciones en Grafos…………………………………………………... 13
▪ Subdivisión elemental de una arista…………………………… 13
▪ Eliminación débil de un vértice……………………………….. 13
Homeomorfismo de grafos………………………………………………. 13Árboles….…………………………………….…………………………... 13
Grafos ponderados o etiquetados………………...………………………. 14
Teorema de los cuatro colores……………………………………………. 14
Grafos planos………………………..………………………………….. 16
Diámetro……….………………..……………………………………….. 17
• Aplicaciones……………………………………………………………………….. 18
Teoría de Nudos………………………………………………………………………………19• Idea Intuitiva………………………………………………………………………… 19
• Historia……………………………………………………………...……………….. 20
• Generalidades sobre la teoría de nudos……………………………………………… 22
• Definición……………………………………………………………………………. 24
• Tabla de nudos………………………………………………………………………. 24
• Diagramas de nudos y movimientos de Reidemeister………………………………. 26
• Aplicaciones…………………………………………………………………………. 28Bibliografía…..………………………………………………………………………………30
Anexos………..………………………………………………………………………………31
Introducción
El siguiente trabajo pretende introducir los temas de teoría de grafos y nudos en el curso de Topología Elemental, desde su fundamento histórico, continuando con las definiciones y ejemplos, para concluir con algunas aplicaciones.
Como aún no cuentocon las bases como para hacer una investigación descriptiva donde pueda emitir juicios propios, me he limitado a la recopilación de información, tratándole de dar un esquema lógico para los que nos estamos iniciando en este tipo de teorías. Mi intención es tratar de tomar los aspectos básicos de la teoría de grafos y nudos, entenderlos y exponerlos de una forma clara y sencilla, de tal forma quemis compañeros y compañeras de curso obtengan los conocimientos previos para la posterior profundización que se llevará a cabo mediante alguna estrategia seleccionada por la profesora del curso.
Para la recopilación de la información se utilizaron esencialmente documentos de algunas páginas de internet, entre ellas es.wikipedia.org y www.mitecnologico.com entre otras.Teoría de grafos
Idea Intuitiva
[pic]
Diagrama de un grafo con 4 vértices y 6 aristas.
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección depares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Historia
El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primer resultado de la teoría de grafos....
Leer documento completo
Regístrate para leer el documento completo.