caminos de Euler
Páginas: 5 (1027 palabras)
Publicado: 2 de marzo de 2014
CAMINOS Y CICLOS DE EULER
INTEGRANTE:
HERMES DAVID ACOSTA PAZ
INSTITUCIÓN UNIVERSITARIA CESMAG
FACULTAD DE INGENIERÍA
INGENIERÍA DE SISTEMAS
SAN JUAN DE PASTO
2013
CAMINOS Y CICLOS DE EULER
INTEGRANTE:
HERMES DAVID ACOSTA PAZ
INFORME DE MATEMATICAS DISCRETASDIRIGIDO A:
HECTOR ALIRIO GERRERO
INSTITUCIÓN UNIVERSITARIA CESMAG
FACULTAD DE INGENIERÍA
INGENIERÍA DE SISTEMAS
SAN JUAN DE PASTO
2013
CONTENIDO
Pág.
INTRODUCCIÓN
1. TEOREMA DE EULER……………………………………………………………5
1.1 HISTORA……………………………………………………………………………6
1.2 Definición……………………………………………………………………………7
1.3 Propiedades…………………………………………………………………………8
1.4Ejemplos……………………………………………………………………………...9
2. EJERCICIO GRAFO #2……………………………………………………………10
3. CONCLUSIÓN………………………………………………………………………11
BIBLIOGRAFÍA…………………………………………………………………………..12
INTRODUCCION
En este informe se hará una consigna sobre TEOREMA DE EULER, donde estará la historia porque es importante saber de dónde y cómo se plantío este teorema, a su vez también se encontrara ladefinición clara y bien explicada sobre lo ante teorema, al igual en este informe se encuentra unos ejemplos claros para sustentar lo antes dicho sobre el teorema de Euler.
También se consigna en este informe un ejercicio dejado en la clase de matemáticas discreta el día 26 de Septiembre del año en curso, donde estará el desarrollo del Grafo Numero 2 (Gll)
Para finalizar este informe se plantearaunas conclusiones y una bibliografía
1. TEOREMA DE EULER
El teorema de Euler es un camino que recorre todas las aristas de un grafo tan solo una única vez, siendo condición necesaria que regrese al vértice inicial de salida. Una definición más formal lo define como "aquel ciclo que contiene todas las aristas de un grafo solamente una vez". Se debe tener en cuenta que no importa la repetición devértices mientras no se repitan aristas.
En la teoría de grafos, un camino Euleriano o Eurel es un camino que pasa por cada arista una y solo una vez. Es cerrado.
Grafos Euleriano son exactamente aquellos grafos que están conectados con todos y donde cada uno de los vértices tiene grado par.
1.1 HISTORIA
El origen de la teoría de los ciclos eulerianos fue planteado y resuelto por elpropio Leonhard Euler en 1736 en un problema que tiene el nombre de Siete puentes de la ciudad de Königsberg (Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia rusa) dando origen a la Teoría de los grafos.
El problema se enuncia de la siguiente forma: Dos islas en el río Pregel, en Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es posible dar unpaseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?
Euler enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta: ¿se puede recorrer el dibujo sin repetirlas líneas?
Euler demostró que no era posible puesto que el número de líneas que inciden en cada punto no es par (condición necesaria para entrar y salir de cada punto, y para regresar al punto de partida, por caminos distintos en todo momento).
1.2 Definición
Un camino de Euler en un grafo no dirigido es un camino que usa cada arista exactamente una vez. Si tal camino existe, el gráficose llama transitable o semi-euleriano.
Un ciclo euleriano o circuito euleriano en un grafo no dirigido, es un ciclo que utiliza cada arista exactamente una vez. Si este ciclo existe, el gráfico se llama unicursal. Si bien los gráficos son gráficos eulerianos, no todo grafo euleriano tiene un ciclo Euleriano.
La relación de equivalencia entre los vértices de un grafo. Sean x, y vértices...
INTEGRANTE:
HERMES DAVID ACOSTA PAZ
INSTITUCIÓN UNIVERSITARIA CESMAG
FACULTAD DE INGENIERÍA
INGENIERÍA DE SISTEMAS
SAN JUAN DE PASTO
2013
CAMINOS Y CICLOS DE EULER
INTEGRANTE:
HERMES DAVID ACOSTA PAZ
INFORME DE MATEMATICAS DISCRETASDIRIGIDO A:
HECTOR ALIRIO GERRERO
INSTITUCIÓN UNIVERSITARIA CESMAG
FACULTAD DE INGENIERÍA
INGENIERÍA DE SISTEMAS
SAN JUAN DE PASTO
2013
CONTENIDO
Pág.
INTRODUCCIÓN
1. TEOREMA DE EULER……………………………………………………………5
1.1 HISTORA……………………………………………………………………………6
1.2 Definición……………………………………………………………………………7
1.3 Propiedades…………………………………………………………………………8
1.4Ejemplos……………………………………………………………………………...9
2. EJERCICIO GRAFO #2……………………………………………………………10
3. CONCLUSIÓN………………………………………………………………………11
BIBLIOGRAFÍA…………………………………………………………………………..12
INTRODUCCION
En este informe se hará una consigna sobre TEOREMA DE EULER, donde estará la historia porque es importante saber de dónde y cómo se plantío este teorema, a su vez también se encontrara ladefinición clara y bien explicada sobre lo ante teorema, al igual en este informe se encuentra unos ejemplos claros para sustentar lo antes dicho sobre el teorema de Euler.
También se consigna en este informe un ejercicio dejado en la clase de matemáticas discreta el día 26 de Septiembre del año en curso, donde estará el desarrollo del Grafo Numero 2 (Gll)
Para finalizar este informe se plantearaunas conclusiones y una bibliografía
1. TEOREMA DE EULER
El teorema de Euler es un camino que recorre todas las aristas de un grafo tan solo una única vez, siendo condición necesaria que regrese al vértice inicial de salida. Una definición más formal lo define como "aquel ciclo que contiene todas las aristas de un grafo solamente una vez". Se debe tener en cuenta que no importa la repetición devértices mientras no se repitan aristas.
En la teoría de grafos, un camino Euleriano o Eurel es un camino que pasa por cada arista una y solo una vez. Es cerrado.
Grafos Euleriano son exactamente aquellos grafos que están conectados con todos y donde cada uno de los vértices tiene grado par.
1.1 HISTORIA
El origen de la teoría de los ciclos eulerianos fue planteado y resuelto por elpropio Leonhard Euler en 1736 en un problema que tiene el nombre de Siete puentes de la ciudad de Königsberg (Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia rusa) dando origen a la Teoría de los grafos.
El problema se enuncia de la siguiente forma: Dos islas en el río Pregel, en Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es posible dar unpaseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?
Euler enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta: ¿se puede recorrer el dibujo sin repetirlas líneas?
Euler demostró que no era posible puesto que el número de líneas que inciden en cada punto no es par (condición necesaria para entrar y salir de cada punto, y para regresar al punto de partida, por caminos distintos en todo momento).
1.2 Definición
Un camino de Euler en un grafo no dirigido es un camino que usa cada arista exactamente una vez. Si tal camino existe, el gráficose llama transitable o semi-euleriano.
Un ciclo euleriano o circuito euleriano en un grafo no dirigido, es un ciclo que utiliza cada arista exactamente una vez. Si este ciclo existe, el gráfico se llama unicursal. Si bien los gráficos son gráficos eulerianos, no todo grafo euleriano tiene un ciclo Euleriano.
La relación de equivalencia entre los vértices de un grafo. Sean x, y vértices...
Leer documento completo
Regístrate para leer el documento completo.