Tareas
Páginas: 29 (7162 palabras)
Publicado: 6 de diciembre de 2012
“ÁRBOLES Y GRAFOS”
Que Presenta:
Técnico Superior Universitario en Tecnologías de la Información y la Comunicación
LAURA BIRIDIANA MÉNDEZ HERNÁNDEZ
No. de Control: 1209100277
Dolores Hidalgo, C.I.N., Gto, A 8 de Diciembre 2012
Contenido
CAPÍTULO I. “GRAFOS Y ÁRBOLES” 1
I.I HISTORIA 1
I.II. GRAFOS 3
I.III. APLICACIONES DE LOS GRAFOS 3
I.IV.TIPOS DE GRAFOS 4
I.V.PARTES DE UN GRAFO 10
I.VI.GRAFOS Y MULTIGRAFOS 11
I.VII. GRADO DE UN NODO 13
I.VIII. VALENCIA 14
I.IX.CAMINOS 14
I.X TIPOS DE CAMINOS 15
I.XI. REPRESENTACION DE GRAFOS 20
I.XII. CICLO DE UN GRAFO 21
I.XIII.ÁRBOLES 22
I.XIV.APLICACIONES DE ARBOLES 24
I.XV.CARACTERISTICAS Y PROPIEDADES DEL LOS ÁRBOLES 25
I.XVI.ÁRBOLES BINARIOS DE BUSQUEDA 27
I.XVII.UTILIZACION DE ÁRBOLESBINARIOS DE BÚSQUEDA 28
I.XVIII.ÁRBOLES ETIQUETADOS 30
I.VIX. ÁRBOLES NO DIRIGIDOS 32
I.XX.APLICACION DE ÁRBOLES Y GRAFOS 33
I.XXI. EJEMPLOS DE APLICACIONES DE GRÁFICAS. 34
CONCLUSIÓN 41
BIBLIOGRAFÍA 42
INTRODUCCIÓN
El “gráfico” tiene varios sentidos en matemáticas. Hemos usado el término “gráfica” en el sentido de una relación o de una función. En muchas partes de la ciencia de lascomputadoras y de la informática aparecen los grafos, especialmente los grafos de árbol, y los grafos dirigidos. Los diagramas de flujo, por ejemplo, son grafos dirigidos.
Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que acada elemento del árbol pueden seguirle varios elementos.
En este ensayo se explicara de manera detalla de la teoría de arboles y grafos, sus partes, las valencias, los caminos y ejemplos de algunos de ellos.
CAPÍTULO I. “GRAFOS Y ÁRBOLES”
I.I HISTORIA
El origen de la teoría de grafos se remonta al siglo XVIII con el problema de los puentes de Königsberg, el cual consistía en encontrarun camino que recorriera los siete puentes del río pregel, en la ciudad de Königsberg, actualmente Kaliningrado, de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos. El trabajo de Leonhard Euler sobre el problema titulado Solutio problematis ad geometriam situs pertinentis1 (La solución de un problema relativo a la geometría de la posición) en 1736, esconsiderado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y latopología.
Luego, en 1847, Gustav Kirchhoff utilizó la teoría de grafos para el análisis de redes eléctricas publicando sus leyes de los circuitos para calcular elvoltaje y la corriente en los circuitos eléctricos, conocidas como leyes de Kirchhoff, considerado la primera aplicación de la teoría de grafos a un problema de ingeniería.
En 1852 Francis Guthrie planteó el problema de los cuatro colores el cual afirma que es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismocolor. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken en 1976, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.
En 1857, Arthur Cayley estudió y resolvió el problema de enumeración de los isómeros, compuestos químicos conidéntica composición (formula) pero diferente estructura molecular. Para ello represento cada compuesto, en este caso hidrocarburos saturados CnH2n+2, mediante un grafo árbol donde los vértices representan átomos y las aristas la existencia de enlaces químicos.
El termino «grafo», proviene de la expresión «graphic notation» usada por primera vez por Edward Frankland2 y posteriormente adoptada...
Que Presenta:
Técnico Superior Universitario en Tecnologías de la Información y la Comunicación
LAURA BIRIDIANA MÉNDEZ HERNÁNDEZ
No. de Control: 1209100277
Dolores Hidalgo, C.I.N., Gto, A 8 de Diciembre 2012
Contenido
CAPÍTULO I. “GRAFOS Y ÁRBOLES” 1
I.I HISTORIA 1
I.II. GRAFOS 3
I.III. APLICACIONES DE LOS GRAFOS 3
I.IV.TIPOS DE GRAFOS 4
I.V.PARTES DE UN GRAFO 10
I.VI.GRAFOS Y MULTIGRAFOS 11
I.VII. GRADO DE UN NODO 13
I.VIII. VALENCIA 14
I.IX.CAMINOS 14
I.X TIPOS DE CAMINOS 15
I.XI. REPRESENTACION DE GRAFOS 20
I.XII. CICLO DE UN GRAFO 21
I.XIII.ÁRBOLES 22
I.XIV.APLICACIONES DE ARBOLES 24
I.XV.CARACTERISTICAS Y PROPIEDADES DEL LOS ÁRBOLES 25
I.XVI.ÁRBOLES BINARIOS DE BUSQUEDA 27
I.XVII.UTILIZACION DE ÁRBOLESBINARIOS DE BÚSQUEDA 28
I.XVIII.ÁRBOLES ETIQUETADOS 30
I.VIX. ÁRBOLES NO DIRIGIDOS 32
I.XX.APLICACION DE ÁRBOLES Y GRAFOS 33
I.XXI. EJEMPLOS DE APLICACIONES DE GRÁFICAS. 34
CONCLUSIÓN 41
BIBLIOGRAFÍA 42
INTRODUCCIÓN
El “gráfico” tiene varios sentidos en matemáticas. Hemos usado el término “gráfica” en el sentido de una relación o de una función. En muchas partes de la ciencia de lascomputadoras y de la informática aparecen los grafos, especialmente los grafos de árbol, y los grafos dirigidos. Los diagramas de flujo, por ejemplo, son grafos dirigidos.
Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que acada elemento del árbol pueden seguirle varios elementos.
En este ensayo se explicara de manera detalla de la teoría de arboles y grafos, sus partes, las valencias, los caminos y ejemplos de algunos de ellos.
CAPÍTULO I. “GRAFOS Y ÁRBOLES”
I.I HISTORIA
El origen de la teoría de grafos se remonta al siglo XVIII con el problema de los puentes de Königsberg, el cual consistía en encontrarun camino que recorriera los siete puentes del río pregel, en la ciudad de Königsberg, actualmente Kaliningrado, de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos. El trabajo de Leonhard Euler sobre el problema titulado Solutio problematis ad geometriam situs pertinentis1 (La solución de un problema relativo a la geometría de la posición) en 1736, esconsiderado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y latopología.
Luego, en 1847, Gustav Kirchhoff utilizó la teoría de grafos para el análisis de redes eléctricas publicando sus leyes de los circuitos para calcular elvoltaje y la corriente en los circuitos eléctricos, conocidas como leyes de Kirchhoff, considerado la primera aplicación de la teoría de grafos a un problema de ingeniería.
En 1852 Francis Guthrie planteó el problema de los cuatro colores el cual afirma que es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismocolor. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken en 1976, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.
En 1857, Arthur Cayley estudió y resolvió el problema de enumeración de los isómeros, compuestos químicos conidéntica composición (formula) pero diferente estructura molecular. Para ello represento cada compuesto, en este caso hidrocarburos saturados CnH2n+2, mediante un grafo árbol donde los vértices representan átomos y las aristas la existencia de enlaces químicos.
El termino «grafo», proviene de la expresión «graphic notation» usada por primera vez por Edward Frankland2 y posteriormente adoptada...
Leer documento completo
Regístrate para leer el documento completo.