Matriz de adyacencia:

Un grafo se puede representar fácilmente mediante una matriz. Inclusive, es la forma mas sencilla de representarlo. A esta matriz se le denomina matriz de adyacencia. Esta matriz consiste basicamente en un arreglo bidimensional de tamaño n x n, donde n es la maxima cantidad de nodos en el grafo. Cada casilla de la matriz se carga con valores verdadero (v) o falso (f) en caso de que posean un camino de un nodo (fila) con otro (columna9. En caso de los grafos no dirigidos la matriz sera simetrica. Sin embargo, esto no ocurre en los digrafos, donde se considera la direccion de cada uno d elos arcos. Para el caso de los grafos ponderados, la matriz podra ser cargada con el peso asociado a cada uno de los arcos. La ventaja principal de la representación de grafos mediante una matriz de adyacencia es su simplicidad, dado que facilita las operaciones que puedan realizarse sobre el grafo.

En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P. La razón es que de tenerse una solución polinómica para un problema NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico. Si se demostrase que un problema NP-completo, llamémoslo A, no se pudiese resolver en tiempo polinómico, el resto de los problemas NP-completos tampoco se podrían resolver en tiempo polinómico. Esto se debe a que si uno de los problemas NP-completos distintos de A, digamos X, se pudiese resolver en tiempo polinómico, entonces A se podría resolver en tiempo polinómico, por definición de NP-completo. Ahora, pueden existir problemas en NP y que no sean NP-completos para los cuales exista solución polinómica aún no existiendo solución para A.

Como ejemplo de un problema NP-completo encontramos el problema de la suma de subconjuntos que se puede enunciar como sigue: dado un conjunto S de enteros, ¿existe un subconjunto no vacío de S cuyos elementos sumen cero? Es fácil verificar si una respuesta es correcta, pero no se conoce mejor solución que explorar todos los 2ⁿ-1 subconjuntos posibles hasta encontrar uno que cumpla con la condición.

Un problema de decisión C es NP-completo si:

1. C es un problema NP, y
2. Todo problema de NP se puede transformar polinómicamente en C.

Se puede demostrar que C es NP demostrando que un candidato a solución de C puede ser verificado en tiempo polinómico.

Una transformación polinómica de L en C es un algoritmo determinista que transforma instancias de l ∈ L en instancias de c ∈ C, tales que la respuesta a c es positiva si y sólo si la respuesta a l lo es.

Como consecuencia de esta definición, de tenerse un algoritmo en P para C, se tendría una solución en P para todos los problemas de NP.

Esta definición fue propuesta por Stephen Cook en 1971. Al principio parecía sorprendente que existieran problemas NP-completos, pero Cook demostró (teorema de Cook) que el problema de satisfacibilidad booleana es NP-completo. Desde entonces se ha demostrado que miles de otros problemas pertenecen a esta clase, casi siempre por reducción a partir de otros problemas para los que ya se había demostrado su pertenencia a NP-completo; muchos de esos problemas aparecen en el libro de Garey and Johnson's de 1979 Computers and Intractability: A Guide to NP-completeness.

Un problema que satisface la segunda condición pertenece a la clase NP-hard independientemente de que satisfaga la primera.

LA COMPLEJIDAD, UN CONCEPTO OPERATIVO Y APLICABLE

Habíamos empezado hablando de la complejidad y hora es de volver a ella.
Se habrá advertido que cada una de las teorías o conjuntos teóricos examinados se ocupa de algun aspecto, inédito y de carácter cualitativo, de la realidad. Desde la perspectiva aquí adoptada, esto es importante por varias razones:
a) Estas teorías tienen un enorme valor epistemológico, pues abren vías de acceso a la realidad, que permiten aprehender ésta sin prescindir de su complejidad.
b) A la par, estas teorías ponen de manifiesto propiedades desconocidas de la realidad y con ello ofrecen un nuevo concepto de la complejidad. En este sentido, afirmar que la realidad es compleja significa, al menos, cuatro cosas: 1) Que la realidad es borrosa. 2) Que la realidad es catastrófica. 3) Que la realidad es fractal. Y 4) que la realidad es caótica.
c) Pero hay más: a la luz de estas teorías se nos aparece una realidad paradójica; una realidad que no es nítida pero tampoco es dual, que no es continua ni discontínua, ni es estable ni inestable, ni reiterativa ni innovadora, ni ordenada ni desordenada (sobre este último aspecto: Munné, en prensa b). Las propiedades de la complejidad subsumen estas alternativas, las cuales únicamente parecen tener pleno sentido en la realidad artificialmente producida por el ser humano (edificios, máquinas, utensilios, objetos producidos, etc.).
Así las cosas, hay que avanzar en el camino abierto por las teorías examinadas. Por ejemplo, un paso más en esa dirección se puede dar profundizando en las relaciones entre los aspectos de la complejidad puestos de manifiesto por dichas teorías u otras teorías de la complejidad que se vayan formulando. Algunas de estas relaciones ya son conocidas: La dimensión geométrica de carácter fraccionado o intermedio de los fractales parece ser indicadora de borrosidad. La teoría de las catástrofes describe la morfogénesis de la estabilidad y, en este aspecto, procesos no caóticos; con todo, es relacionable con la teoría del caos, porque este "se cuela" a través de la catástrofe. Además, la teoría de las catástrofes probablemente pueda ser reentendida a través de una teoría más general de las bifurcaciones e incluso de las oscilaciones. También los atractores extraños son fractaliformes: nunca se cortan o yuxtaponen debido a su determinismo y las trayectorias se "aprietan" más y más al reducir la escala de observación. Las turbulencias consisten, como los fractales, en irregularidades. Etc.
Otra cuestión es la de las relaciones entre las teorías de la complejidad, las cuales lógicamente no están exentas de discrepancias. Han originado ya polémicas importantes, por ejemplo, entre Mandelbrot y Thom, o entre Mandelbrot y Feigenbaum. Pero más allá de disputas puntuales, una cuestión que late en toda esta temática es la que opone la borrosidad, la estabilidad, la iteración, el equilibrio, etc. a los límites, los puntos críticos, los ciclos límite, las transiciones del espacio de fases, etc. A nivel epistemológico, esta cuestión no es nueva: cuando Louis de Broglie explicó en un libro, ya clásico en la filosofía de la ciencia, el enfrentamiento entre las interpretaciones corpuscular y ondulatoria del mundo físico puso un título a su obra que revela que los conceptos en lid siguen siendo los mismos: Continu et discontinu en physique moderne (1941).
¿ Cómo las aportaciones de las anteriores teorías, nacidas en las ciencias naturales, pueden ser aplicadas, en el pleno sentido empírico de la palabra, a las ciencias del comportamiento ?
La mejor manera de comprender cómo o en que sentido hay que entender esta aplicación es darse cuenta de que los constructos aportados desde el enfoque de la complejidad (como son los conceptos de fractal, conjunto difuso, torbellino, caos, atractor extraño, etc.) son altamente formalizables. Esto significa que pueden ser aplicados de un modo transdisciplinar, sin necesidad de acudir a metáforas ni analogías.
Es lo mismo que sucede con el concepto de feedback: usted puede aplicarlo, con pleno sentido, tanto a un motor como al cuerpo humano, desde a una galaxia a un movimiento social. Sin embargo a usted no se le ocurrirá que el cuerpo humano es un motor o que un motor es igual que el cuerpo humano, ni que una galaxia y un movimiento social son confundibles. Y sin aquel concepto muchos fenómenos o procesos, si es que pueden ser planteados, no pueden llegar a ser bien comprendidos. Piénsese tan sólo en la revelancia social de los procesos de autorregulación o autocontrol.
Como epistemologías, las teorías examinadas proporcionan un nuevo modo de aprehender la realidad y ayudan a una comprensión menos reductora de los procesos básicos del comportamiento y la realidad sociales.
Y esto no se queda en el análisis. Conlleva, también, al menos potencialmente, nuevas formas de tratamiento de la realidad. Ya se ha dicho que las teorías del caos han entrado en el campo del diagnóstico. Puede añadirse que están asomando al ámbito de la intervención. Una muestra de lo que esto puede significar la tenemos en las recientes investigaciones de Brenda Zimmerman (por ej., 1992) sobre la dirección estratégica, basada en el caos y en la fractalidad de las organizaciones.

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".