Rebecaortizm
Páginas: 21 (5105 palabras)
Publicado: 4 de diciembre de 2012
Índice
| Pág. |
Introducción……………………………………………………………………….. | 03 |
Origen y Creadores de la Teoría de los Grafos……………………………….. | 05 |
Uso o aplicaciones de los grafos…………………………………………………. | 06 |
Definición y Representación de los grafos………………………………………. | 07 |
Ciclos y Caminos Hamiltoniano…………………………………………………… | 08 |
Grafos Planos………………………………………………………………………. | 08 |
Coloración degrafos……………………………………………………………….. | 09 |
Teorema de los cuatro colores…………………………………………………… | 09 |
Grafos simples……………………………………………………………………… | 10 |
Grafos conexos…………………………………………………………………….. | 10 |
Grafos completos y bipartitos…………………………………………………….. | 11 |
Homeomorfismo de grafos………………………………………………………… | 12 |
Árboles………………………………………………………………………………. | 12 |
Grafos ponderados oetiquetados……………………………………………….. | 14 |
Diámetro de un grafo………………………………………………………………. | 14 |
El problema de los puentes de Königsberg…………………………………….. | 15 |
Conclusión…………………………………………………………………………. | 20 |
Bibliografía…………………………………………………………………………. | 22 |
Anexos……………………………………………………………………………….. | 23 |
Introducción
Hoy en día podemos ver muchas cosas que nos pueden parecer de lo más cotidianas, carreteras, líneastelefónicas, líneas de televisión por cable, el transporte colectivo metro, circuitos eléctricos de nuestras casas, automóviles, y tantas cosas más; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemáticas se denomina como grafos.
Es importante resaltar que desafortunadamente no existe una terminología estandarizada en la teoría de los grafos, por lo tanto esoportuno aclarar que las presentes definiciones pueden variar ligeramente entre diferentes publicaciones de estructura de datos y de teoría de grafos, pero en general se puede decir que un grafo como indica su nombre lo indica es la representación gráfica de los datos de una situación particular. Los datos contienen, en algunos casos, relaciones entre ellos que no son necesariamente jerárquicos. Porejemplo, supongamos que unas líneas aéreas realizan vuelos entre las ciudades conectadas por líneas; la estructura de datos que refleja esta relación recibe el nombre de grafo.
Se suelen usar muchos nombres al referirnos a los elementos de una estructura de datos. Algunos de ellos son "elemento", "ítem", "asociación de ítems", "registro", "nodo" y "objeto". El nombre que se utiliza depende deltipo de estructura, el contexto en que usamos esa estructura y quien la utiliza. En la mayoría de los textos de estructura de datos se utiliza el término "registro" al hacer referencia a archivos y "nodo" cuando se usan listas enlazadas, árboles y grafos.
El tema al que se hará referencia en la investigación es caracterizado como un tema bastante importante, muy conocido y desconocido a la vez, tiene como origen histórico el problema clásico de los siete puentes de Könisberg, propuesto por Leonhard Euler. Digo desconocido, porque en realidad vivimos beneficiándonos de todas sus aplicaciones y pasa inadvertido. Por ejemplo: el circuito eléctrico de nuestra casa, el transporte masivo o metro, líneas telefónicas, líneas de televisión por cable, y una red de computadoras, puedenrepresentarse y estudiarse mediante un grafo, entre muchas otras situaciones cotidianas. Otras aplicaciones más avanzadas son el caso de la geometría combinatoria, la investigación operativa, inteligencia artificial y la química orgánica.
La teoría de los grafos juega un papel importante en la fundamentación matemática de las ciencias de la computación. Los grafos constituyen una herramientabásica para modelizar fenómenos discretos y no fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos.
En tal sentido, en el trabajo se tratará de explicar lo que es la estructura de los grafos, sus tipos, y algunas derivaciones de ellos, así como su representación gráfica y en algunos casos, su representación en algún programa informático, así...
| Pág. |
Introducción……………………………………………………………………….. | 03 |
Origen y Creadores de la Teoría de los Grafos……………………………….. | 05 |
Uso o aplicaciones de los grafos…………………………………………………. | 06 |
Definición y Representación de los grafos………………………………………. | 07 |
Ciclos y Caminos Hamiltoniano…………………………………………………… | 08 |
Grafos Planos………………………………………………………………………. | 08 |
Coloración degrafos……………………………………………………………….. | 09 |
Teorema de los cuatro colores…………………………………………………… | 09 |
Grafos simples……………………………………………………………………… | 10 |
Grafos conexos…………………………………………………………………….. | 10 |
Grafos completos y bipartitos…………………………………………………….. | 11 |
Homeomorfismo de grafos………………………………………………………… | 12 |
Árboles………………………………………………………………………………. | 12 |
Grafos ponderados oetiquetados……………………………………………….. | 14 |
Diámetro de un grafo………………………………………………………………. | 14 |
El problema de los puentes de Königsberg…………………………………….. | 15 |
Conclusión…………………………………………………………………………. | 20 |
Bibliografía…………………………………………………………………………. | 22 |
Anexos……………………………………………………………………………….. | 23 |
Introducción
Hoy en día podemos ver muchas cosas que nos pueden parecer de lo más cotidianas, carreteras, líneastelefónicas, líneas de televisión por cable, el transporte colectivo metro, circuitos eléctricos de nuestras casas, automóviles, y tantas cosas más; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemáticas se denomina como grafos.
Es importante resaltar que desafortunadamente no existe una terminología estandarizada en la teoría de los grafos, por lo tanto esoportuno aclarar que las presentes definiciones pueden variar ligeramente entre diferentes publicaciones de estructura de datos y de teoría de grafos, pero en general se puede decir que un grafo como indica su nombre lo indica es la representación gráfica de los datos de una situación particular. Los datos contienen, en algunos casos, relaciones entre ellos que no son necesariamente jerárquicos. Porejemplo, supongamos que unas líneas aéreas realizan vuelos entre las ciudades conectadas por líneas; la estructura de datos que refleja esta relación recibe el nombre de grafo.
Se suelen usar muchos nombres al referirnos a los elementos de una estructura de datos. Algunos de ellos son "elemento", "ítem", "asociación de ítems", "registro", "nodo" y "objeto". El nombre que se utiliza depende deltipo de estructura, el contexto en que usamos esa estructura y quien la utiliza. En la mayoría de los textos de estructura de datos se utiliza el término "registro" al hacer referencia a archivos y "nodo" cuando se usan listas enlazadas, árboles y grafos.
El tema al que se hará referencia en la investigación es caracterizado como un tema bastante importante, muy conocido y desconocido a la vez, tiene como origen histórico el problema clásico de los siete puentes de Könisberg, propuesto por Leonhard Euler. Digo desconocido, porque en realidad vivimos beneficiándonos de todas sus aplicaciones y pasa inadvertido. Por ejemplo: el circuito eléctrico de nuestra casa, el transporte masivo o metro, líneas telefónicas, líneas de televisión por cable, y una red de computadoras, puedenrepresentarse y estudiarse mediante un grafo, entre muchas otras situaciones cotidianas. Otras aplicaciones más avanzadas son el caso de la geometría combinatoria, la investigación operativa, inteligencia artificial y la química orgánica.
La teoría de los grafos juega un papel importante en la fundamentación matemática de las ciencias de la computación. Los grafos constituyen una herramientabásica para modelizar fenómenos discretos y no fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos.
En tal sentido, en el trabajo se tratará de explicar lo que es la estructura de los grafos, sus tipos, y algunas derivaciones de ellos, así como su representación gráfica y en algunos casos, su representación en algún programa informático, así...
Leer documento completo
Regístrate para leer el documento completo.