matematicas

-4175848-127878600
INSTITUTO TECNOLOGICO DE CHIHUAHUA II
INGENIERÍA EN INFORMÁTICA
MATEMATICAS DISCRET Maestro: Jesús Mario Espadas Roque
Chihuahua,chih. De Nobiembre del 2013
PUENTES DE KOENIGSBERG
La ciudad de Kaliningrado, antiguamente llamadaKönigsberg, es un lugar situado en la desembocadura del río Pregolya, en la antigua Prusia Oriental. Este río atravesaba la ciudad, dividiendo la zona en varias partes. Para no perder la comunicación, ésta estaba llena de un sistema de puentes conectores. En total, había siete grandes puentes en Kaliningrado: El puente del herrero, el puente conector, el puente verde, el puente del mercado, el puente demadera, el puente alto y, por último, el puente de la miel. El problema consistía en comenzar en un punto, pasar por los siete puentes sin repetir ninguno y volver al punto de partida. Fue Euler quien fue represento la ciudad de Königsberg como un grafo en el que las cuatro partes de la misma eran los vértices y los siete puentes eran las aristas: Por tanto el problema de los puentes de Königsbergpasa a ser un problema de teoría de grafos cuya solución publicó Euler en su artículo “Solución de un problema relativo a la geometría de posición”.
Los puentes de Königsgsberg-629285198374000Una de las ramas importantes de la matemática actual, la topología, nació con el siguiente acertijo que el gran Euler describió y resolvió en uno de sus artículos: "El problema que, según entiendo, es muy bienconocido, se enuncia así: En la ciudad de Königsberg, en Prusia, hay una isla, llamada Kneiphof, rodeada por los dos brazos del río Pregel. Hay siete puentes, A, B, C, D, E, F y G, que cruzan los dos brazos del río (ver la figura de abajo). La cuestión consiste en determinar si una persona puede realizar un paseo de tal modo que cruce cada uno de los puentes una sola vez. Se me ha informado de quemientras unos negaban la posibilidad de hacerlo y otros lo dudaban, nadie sostenía que fuese posible realmente".   
438404025146000206502023749000
 
255431648916700-92964054737000Grafos Hamiltonianos:
¿Cuándo es posible hacer un recorrido en un grafo que pase por cada vértice exactamente una vez y termine en el vértice original?O en otras palabras, ¿cuándo un grafo tiene un ciclo cerrado quecontenga a todos sus vértices?Cuando existe tal ciclo, lo llamaremos ciclo hamiltoniano y un grafo que posea un ciclo hamiltoniano se llama grafo hamiltoniano. Un ciclo puro Cp es evidentemente hamiltoniano; el grafo de la fig. 3.14 también. En efecto, el ciclo v1v2... v7v1 representa un ciclo hamiltoniano del grafo G.
¿Qué tan fuertemente conexo es un grafo?Una posible interpretación de estapregunta es analizar cuántas líneas o vértices deberíamos eliminar del grafo para convertirlo en no conexo. Introducimos a continuación algunas definiciones que aclaran este punto.
¿QUE ES UN GRAFO PLANO?
es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano). Los grafosK5 y el K3,3 sonlos grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos.
Todo grafo plano puede ser dibujado sobre la esfera, y viceversa. Una generalización de los grafos planos son grafos dibujados e incrustados sobre superficies de genero arbitrario. En esta terminología, los grafos planos tienen genero 0, por ser el plano y la esfera de género 0
111125118745001346206350000
‘Teorema de Kuratowski’

Un grafo es plano si no contiene como subgrafo a  ni a .
Es decir, ni  ni  son grafos planos (ya que cada uno de ellos se contiene a sí mismo como subgrafo). O lo que es lo mismo, no pueden dibujarse en un papel con la condición de que ninguna arista corte a otra en un punto que no sea desde el principio un vértice.
La demostración de este teorema...