Problema de la película "Una mente indomable"

Encontrar de la gráfica:

1)La matriz de Adyacencia.

2)La matriz dando el numero de los 3 pasos.

3)La función generadoraque pasa por los puntos i -> j.

4)La función generadora que pasa por los puntos 1 -> 3.

ISOMORFISMO

El concepto matemático de Isomorfismo ( del griego Iso-morfos: igual forma) pretende captar la idea de tener la misma estructura.

Dos estructuras matemáticas entre las que existe una relación de Isomorfismo se llaman Isomorfas.

Se puede definir concisamente como: un Isomorfismo es un homomorfismo biyectivo tal que su inversa es también homomorfismo (1).

Características del Isomorfismo:

El descubrimiento de un Isomorfismo entre dos estructuras significa esencialmente que el estudio de cada una puede reducirse al de la otra, lo que nos da dos puntos de vista diferentes sobre cada gestión y suele ser esencial en su adecuada comprensión. También significa una analogía como una forma de inferencia lógica basada en la asunción de que dos cosas son la misma en algunos aspectos, aquellos sobre los que está hecha la comparación.

Ejemplos de isomorfismos

Por ejemplo, si X es un número real positivo con el producto e Y es un número real con la suma, el logaritmo ln:X→Y es un isomorfismo, porque ln(ab) = ln(a) + ln(b) y cada número real es el logaritmo de un único número real positivo. Esto significa que cada enunciado sobre el producto de números reales positivos tiene (sin más que sustituir cada número por su logaritmo) un enunciado equivalente en términos de la suma de números reales, que suele ser más simple.

(1): Homomorfismo: Dados dos conjuntos no vacíos A y A', y las leyes de composición interna

La función es un homomorfismo respecto de + y * si y solo si la imagen de la composición en A es igual a la composición de las imagenes en A'. Es decir: es homomorfismo respecto de + y *.

Problema del viajante.

LA BASE DEL PROBLEMA:

El problema del viajante es un ejemplo que muestra y analiza la problemática que subyace tras algunos tipos de problemas matemáticos que a priori parecen tener una solución relativamente fácil, y en la práctica presentan un gran problema.

La respuesta al problema es conocida, es decir se conoce la forma de resolverlo, pero sólo en teoría, en la práctica la solución no es aplicable debido al tiempo que computacionalmente se precisa para obtener su resultado.

El problema del viajante o también conocido como problema del viajante de comercio o por sus siglas TSP: Travelling Salesman Problem. es uno de los problemas mas famosos en el campo de la optimización combinatoria computacional.

A pesar de su aparente sencillez del planteamiento , este es uno de los mas complejos desde hace siglos.

ENUNCIADO:

Sean N ciudades de un territorio. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y minimice la distancia recorridad por el viajante. Es decir, encontar una permutación P={ C₀, C₂,...,Cn-₁} tal que...

sea mínimo. La distancia entre cada ciudad viene dada por la matríz D: NxN, donde d [x, y] representa la distancia que hay entre la ciudad X y la ciudad Y.

Enrico Bombieri Teoría de Números, Geometría Algebráica, Ecuaciones en Derivadas Parciales, Variable Compleja, Teoría de los Grupos Finitos.

De Milan, Italia Se interesó por la Teoría de números desde la temprana edad de 13 años. Bombierí está considerado como uno de los matemáticos más versátiles y extraordinarios de la actualidad. Practicamente ha influido en todos los campos en donde ha trabajado. Ha demostrado siempre una gran habilidad para dominar rápidamente los aspectos esenciales de campos complicados por su novedad, aplicando una gran energía e intuición en la obtención de resultados de envergadura. Es un buen escritor de matemática, distinguiéndose por una gran claridad expositiva. Medalla Fields 1974 Trabaja actualmente en Princeton, en elInstituto de Estudios Avanzados.

DONALD KNUTH

DONALD KNUTH

Donald Ervin Knuth, (nacido el 10 de enero de 1938 en Milwaukee, Wisconsin) es uno de los más reconocidos expertos en ciencias de la computación por su seminal investigación dentro del análisis de algoritmos y compiladores. Es Profesor Emérito de la Universidad de Stanford.
Se le conoce principalmente por ser el autor de la obra "The art of computer programming" (El arte de programar computadoras), una de las más respetadas referencias en el campo de las ciencias de la computación. Sentó las bases y dio nombre al análisis de algoritmos, y ha realizado numerosos aportes a varias ramas teóricas de la informática. Es el creador de TEX, del sistema de diseño de tipos METAFONT y del estilo de programación conocido como programación literaria (Literate programming).

El número de Erdos

El número de Erdős es un modo de describir la distancia colaborativa, en lo relativo a trabajos matemáticos entre un autor y Erdős. El término fue acuñado en honor al matemático húngaro Paul Erdős, uno de los escritores más prolíficos de trabajos matemáticos.

Definición

Para que a una persona se le pueda asignar un número Erdős, ésta debe de haber co-escrito un trabajo matemático con un autor con un número Erdős finito. Paul Erdős tiene un número Erdős de cero. Si el número Erdős más bajo de un coautor es X, entonces el número Erdős del autor es X+1.

Erdős escribió cerca de 1500 artículos matemáticos, la mayoría de ellos en co-autoría. Tuvo 509 colaboradores directos; éstas son las personas con un número Erdős de 1. La gente que hubo colaborado con ellos (pero no con Erdős mismo) tiene un número Erdős de 2 (6,984 personas), aquellas personas que han colaborado con gente que tiene un número Erdős de 2 (pero no con Erdős mismo, ni con alguien con un número Erdős de 1) tienen un número Erdős de 3, y así sucesivamente.

Una persona con ninguna conexión a la cadena de coautoría de Erdős tiene un número Erdős indefinido o infinito. Hay por supuesto, espacio para la ambigüedad acerca de lo que constituye un vínculo entre dos autores; según el sitio web del Proyecto de Número de Erdős dice: "Nuestro criterio para la inclusión de un rango entre vértices u y v es alguna investigación colaborativa entre ellos, teniendo como resultado un trabajo publicado. Cualquier número de co-autores adicionales es permitido", pero el Proyecto no incluye publicaciones cuya índole no sea de investigación, como libros de texto, obituarios y cosas por el estilo.

El número de Erdős fue definido por Casper Goffman, un analista matemático cuyo número de Erdős es 1. Goffman publicó sus observaciones en 1969 acerca de la prolífica colaboración de Erdős en un artículo titulado "¿Y cuál es tu número Erdős?".

Biografía de Paul Erdos

Paul Erdos vivió las Matemáticas con el espíritu propio de un místico. Así loo atestiguan sus palabras cuando afirmó que "toda actividad humana, buena o mala, debe llegar a un fin ... excepto la Matemática. La Matemática es eterna, porque sus problemas son finitos".

Existen varios centros de investigación en el mundo que llevan el nombre de Paul Erdös (que se pronuncia erdish) e instituciones que llevan su nombre entre el de sus fundadores. Se pueden contar por centenas los matemáticos que se consideran discípulos suyos. Sin embargo, Paul Erdös no fue nunca miembro de ninguna institución académica, jamás dirigió oficialmente una tesis, ni ocupó ningún cargo en ningún tipo de asociación matemática. Esto nos lleva a considerar a Erdös como a un auténtico fenómeno dentro del mundo de las Matemáticas y a concluir, sin ningún tipo de dudas, que la enorme influencia que ejerció en las Matemáticas del siglo XX fue debida al extraordinario contenido de su obra matemática.

Naturalmente, provocó que sus padres se volvieran extremadamente protectores hacia él. Él se presentó a las matemáticas por sus padres, tanto los propios profesores de matemáticas.

Cuando estallo la Primera Guerra Mundial Paul no tenias mas de un año cuando su padre fue capturado por el ejército ruso, ya que atacaron a las tropas Austro-Húngaro.

En el año de 1920 no fue todo malo para Paul, ya que su padre regreso de Siberia después de haber sido capturado; había aprendido inglés para pasar las largas horas de cautiverio quién después le enseña a Paul (el acento de su inglés es una de las características de Paul a lo largo de su vida).

A pesar de que los judíos tenían ciertas restricciones para entrar a la universidad Paul logra ingresar en 1930. Él estudió para su doctorado en la universidad Péter Pázmany, en Budapest. Obtuvo su doctorado en 1934, tomo una beca post-doctoral en el Manchester, esencialmente, ser obligados a abandonar Hungría, ya que el era judío. Durante su gestión de la beca Erdos viajaba mucho al Reino Unido. Ahí se reunió con Hardy en Cambridge en 1934 y Ulam, también de Cambridge, en 1935.

Los números

A pesar de su mente abierta y ciertamente renacentista, la mayoría del trabajo matemático de Erdös se centró en la Teoría de Números. “Aunque el Universo no existiera, existirían los números”, decía. De sus primeras 64 publicaciones, 61 versaban sobre Teoría de úmeros. En este terreno abordó cuestiones fundamentales y difíciles a las que él aplicaba demostraciones elegantes.

A los 26 años su producción matemática ya superaba a la media de toda una vida. Es importante recalcar la gran importancia que daba a los trabajos hechos en colaboración con otros matemáticos y una buena prueba de ello es que de de sus 1.500 artículos, cerca de 500 fueron realizados en colaboración con otros matemáticos. Siempre defendió fervientemente las demostraciones elementales como la meta de belleza a la que todo matemático debería aspirar.

Paul Erdös falleció el 20 de septiembre de 1996, en el transcurso de una conferencia que impartía en Varsovia. Tenía ochenta y tres años y el en el momento de su muerte portaba la documentación que le acreditaba para su siguiente conferencia en Lituania. Así pues, murió como había vivido siempre, yendo de un lado para otro.

Grafo estrellado

Arriba, grafos estrellados de 0, 1, 2, 3, 4 y 5 vértices; abajo, grafos estrellados regulares

Dado un punto C en el plano y n puntos P_i, i = 0, 1, ..., n, entre los cuales no hay tres alineados, llamamos grafo estrellado de centro C y n vértices al conjunto de segmentos CP_i. Si los puntos P_i están en los vértices de un polígono regular y C en su centro, se obtienen grafos estrellados regulares.

Así, para n = 0, 1, 2, 3, 4 y 5, se pueden obtener las siguientes figuras:

Otra definición de grafo estrellado coicidiría con la de "haz de segmentos", esto es, un conjunto de segmentos cuyo centro es común en todos ellos.³ En el gráfico adyacente, sólo la figura cuyo fondo es un cuadrado se atiene a esta definición, más estricta.

Polígono estrellado

Si a partir de un polígono regular de p lados se une un determinado vértice con otro no consecutivo de orden q ("avanzando" q vértices) y se continúa el proceso del mismo modo hasta alcanzar el vértice inicial, se obtiene un polígono regular estrellado, cuyos lados y ángulos son todos iguales. La figura que se obtiene puede representarse mediante la expresión {p/q}, siendo q el número de vértices contados a partir del primero. Por ejemplo, a partir de un pentágono regular (p = 5) puede trazarse una estrella de cinco puntas uniendo el primer vértice con el tercero (q = 2), el tercero con el quinto, el quinto con el segundo, el segundo con el cuarto y el cuarto con el primero. Se obtiene así el polígono estrellado {5/2}.

Para generar un polígono estrellado, la fracción p/q debe ser irreducible, esto es, p y q han de ser primos relativos, obteniéndose en tal caso el mismo polígono que en el caso p/p-q.⁴

La notación {p/q} se debe a Ludwig Schläfli.

Función biyectiva

(Redirigido desde Biyectiva)

Ejemplo de función biyectiva.

En matemática, una función es biyectiva si es al mismo tiempo inyectiva y sobreyectiva; es decir, si todos los elementos del conjunto de salida tienen una imagendistinta en el conjunto de llegada, y a cada elemento del conjunto de llegada le corresponde un elemento del conjunto de salida.

Formalmente,

Una implicación directa de lo anterior, es que en una función biyectiva la cardinalidad del conjunto de salida o dominio, y el de llegada o codominio, son iguales. Esto también se puede ver en el ejemplo, donde |X|=|Y|=4.

Funcion Sobreyectiva

Función sobreyectiva

(Redirigido desde Sobreyectiva)

Ejemplo de función sobreyectiva.

En matemática, una función es sobreyectiva (epiyectiva, suprayectiva, suryectiva, exhaustiva o subyectiva), si está aplicada sobre todo el codominio, es decir, cuando la imagen , o en palabras más sencillas, cuando cada elemento de "Y" es la imagen de como mínimo un elemento de "X".

Formalmente,

Los siguientes diagramas corresponden a función sobreyectiva:

Combinatoria

La Combinatoria es la parte de las Matemáticas que se dedica a buscar procedimientos y estrategias para el recuento de los elementos de un conjunto o la forma de agrupar los elementos de un conjunto.

Gráfica Bipartita

Una gráfica G es bipartita si existe una partición de los vértices de G en dos conjuntos V1 y V2 (no vacios) de forma que cada arista de G tenga un extremo en V1 y el otro en V2

Por ejemplo, la gráfica de la siguiente figura es bipartita:

Los véritces rojos forman el conjunto V1 y los vértices verdes el conjunto de vértices V2

Teorema de los 4 colores

Teorema de los cuatro colores

Artículo principal: Teorema de los cuatro colores

En 1852 Francis Guthrie planteó el problema de los cuatro colores.

Otro problema famoso relativo a los grafos: ¿Cuántos colores son necesarios para dibujar un mapa político, con la condición obvia que dos países adyacentes no puedan tener el mismo color? Se supone que los países son de un solo pedazo, y que el mundo es esférico o plano. En un mundo en forma de toroide; el teorema siguiente no es válido:

Cuatro colores son siempre suficientes para colorear un mapa.

El mapa siguiente muestra que tres colores no bastan: Si se empieza por el país central a y se esfuerza uno en utilizar el menor número de colores, entonces en la corona alrededor de a alternan dos colores. Llegando al país h se tiene que introducir un cuarto color. Lo mismo sucede en i si se emplea el mismo método.

La forma precisa de cada país no importa; lo único relevante es saber qué país toca a qué otro. Estos datos están incluidos en el grafo donde los vértices son los países y las aristas conectan los que justamente son adyacentes. Entonces la cuestión equivale a atribuir a cada vértice un color distinto del de sus vecinos.

Hemos visto que tres colores no son suficientes, y demostrar que con cinco siempre se llega, es bastante fácil. Pero el teorema de los cuatro colores no es nada obvio. Prueba de ello es que se han tenido que emplear ordenadores para acabar la demostración (se ha hecho un programa que permitió verificar una multitud de casos, lo que ahorró muchísimo tiempo a los matemáticos). Fue la primera vez que la comunidad matemática aceptó una demostración asistida por ordenador, lo que ha creado una fuerte polémica dentro de la comunidad matemática, llegando en algunos casos a plantearse la cuestión de que esta demostración y su aceptación es uno de los momentos que han generado una de las más terribles crisis en el mundo matemático.

Estos son los diagramas de arbol que pasan, cabe mencionar que es una de las cosas que me llamo la atencion debido a que en la clase nos han mencionado algo de esto y creo que sera m uy interesante aprender esto.

"Una mente indomable"

Esta es la imagen que representa uno de los problemas matemáticos de la pelicula "Una mente indomable".