JUEGO DE ISOMORFISMO

En el siglo XX se ha precisado en matemáticas la noción intuitiva de estructura, siguiendo la concepción de Aristóteles de la materia y la forma, según la cual cada estructura es un conjunto X dotado de ciertas operaciones (como la suma o el producto), o de ciertas relaciones (como una ordenación) o ciertos subconjuntos (como en el caso de la topología), etc. En este caso el conjunto X es la materia y las operaciones, relaciones, etc., en él definidas, son la forma.

Ejemplos de Isomorfismos Por ejemplo, si X es un números 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.

Otro ejemplo: si en el espacio E elegimos una unidad de longitud y tres ejes mutuamente perpendiculares que concurren en un punto, entonces a cada punto del espacio podemos asociarles sus tres coordenadas cartesianas, obteniendo así una aplicación f:E→R³ en el conjunto de las sucesiones de tres números reales. Cuando en E consideramos la distancia que define la unidad de longitud fijada y en R³ consideramos la distancia que define la raíz cuadrada de la suma de los cuadrados de las diferencias, f es un isomorfismo. Éste descubrimiento fundamental de Descartes permite enunciar cualquier problema de la geometría del espacio en términos de sucesiones de tres números reales, y este método de abordar los problemas geométricos es el corazón de la llamada geometría analítica.

Características del Isomorfismo

El descubrimiento de Platón de que la forma es lo que importa se recoge en matemáticas con el concepto de isomorfismo. Una aplicación f:X→Y entre dos conjuntos dotados del mismo tipo de estructura es un isomorfismo cuando cada elemento de Y proviene de un único elemento de X y f transforma las operaciones, relaciones, etc. que hay en X en las que hay en Y. Cuando entre dos estructuras hay un isomorfismo, ambas son indistinguibles, tienen las mismas propiedades, y cualquier enunciado es simultáneamente cierto o falso. Por eso en matemáticas las estructuras deben clasificarse salvo isomorfismos.

El descubrimiento de Platón de que la forma es lo que importa se recoge en matemáticas con el concepto de isomorfismo. Una aplicación f:X→Y entre dos conjuntos dotados del mismo tipo de estructura es un isomorfismo cuando cada elemento de Y proviene de un único elemento de X y f transforma las operaciones, relaciones, etc. que hay en X en las que hay en Y. Cuando entre dos estructuras hay un isomorfismo, ambas son indistinguibles, tienen las mismas propiedades, y cualquier enunciado es simultáneamente cierto o falso. Por eso en matemáticas las estructuras deben clasificarse salvo isomorfismos. Ejemplos de Isomorfismos Por ejemplo, si X es un números 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.

Otro ejemplo: si en el espacio E elegimos una unidad de longitud y tres ejes mutuamente perpendiculares que concurren en un punto, entonces a cada punto del espacio podemos asociarles sus tres coordenadas cartesianas, obteniendo así una aplicación f:E→R³ en el conjunto de las sucesiones de tres números reales. Cuando en E consideramos la distancia que define la unidad de longitud fijada y en R³ consideramos la distancia que define la raíz cuadrada de la suma de los cuadrados de las diferencias, f es un isomorfismo. Éste descubrimiento fundamental de Descartes permite enunciar cualquier problema de la geometría del espacio en términos de sucesiones de tres números reales, y este método de abordar los problemas geométricos es el corazón de la llamada geometría analítica.

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 cuestió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. En ciencias sociales la aplicación de una ley análoga por no existir una específica o también la comparación de un sistema biológico con un sistema social, cuando se trata definir la palabra sistema. Lo es igualmente la imitación o copia de una estructura tribal en un hábitat con estructura urbana.

Los morfismos Los isomorfismos de una estructura consigo misma se denominan automorfismos. En general, en una categoría arbitraria, los isomorfismos se definen por ser los morfismos f:X→Y que admiten un morfismo inverso h:Y→X, inverso tanto por la derecha como por la izquierda. Pueden no ser los morfismos biyectivos, como ya ocurre en el caso de los espacios topológicos.

Publicado por Juan Ramirez Lopez

ISOMORFISMO

Matilde Aldava Herrera

Dados G=(V,E) y G´=(V´,E´), se denomina isomorfismo de G a G´ a la aplicación biyectiva f tal que para a,bÎV, {a,b}ÎE Û se cumple {f(a),f(b)}ÎE´. Es decir, la aplicación que relaciona biyectivamente pares de vértices de E con pares de vértices de E´, de modo que los vértices conectados por aristas siguen estándolo.

G y G´ se denominan isomorfos, y son matemáticamente iguales, solo varia la apariencia, o sea, que se mantienen las adyacencias, estructura, caminos y ciclos.

Los grafos G y G ‘ son isomorfos pues existe la biyección f: V ® V ‘ definida por f(a) = 2, f(b) = 1, f© = 3, f(d) = 4 que conserva la adyacencia.

Complejidad

Los problemas matemáticos se pueden dividir en primera instancia en dos grupos

Problemas indecidibles: aquellos que no se pueden resolver mediante un algoritmo.

Ø Problemas decidibles: aquellos que cuentan al menos con un algoritmo para su cómputo.

Sin embargo, que un problema sea decidible no implica que se pueda encontrar su solución, pues muchos problemas que disponen de algoritmos para su resolución son inabordables para un computador por el elevado número de operaciones que hay que realizar para resolverlos. Esto permite separar los problemas decidibles en dos:

Ø intratables: aquellos para los que no es factible obtener su solución.

Ø tratables: aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo razonable.

Los problemas pueden clasificarse también atendiendo a su complejidad. Aquellos problemas para los que se conoce un algoritmo polinómico que los resuelve se denominan clase P. Los algoritmos que los resuelven son deterministas. Para otros problemas, sus mejores algoritmos conocidos son no deterministas. Esta clase de problemas se denomina clase NP. Por tanto, los problemas de la clase P son un subconjunto de los de la clase NP, pues sólo cuentan con una alternativa en cada paso.

El problema de isomorfismo de grafos no se sabe si es un problema de la clase P o de la clase NP, y si hubiese una clase intermedia entre ambas, el isomorfismo de grafos sería el tipo de problema ideal para ella.

Existe un caso concreto de grafos (los árboles) donde el problema del isomorfismo si se puede resolver mediante la aplicación de algoritmos no muy complejos. Este caso será el que desarrollaremos en la segunda parte del proyecto, apartado 2.3.

GRAFOS PLANARES 5.4.1

Colaboracion de Araceli Pichrado Osuna

Un grafo ( griego grafos: dibujo, imagen) Conjunto de puntos unidos entre sí por segmentos o arcos de curva usados para representar un proceso o una relación funcional de cualquier tipo, es el principal objeto de estudio de la teoría de grafos. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas). También es llamado grafo al conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que ayudan a representar relaciones binarias entre elementos de un conjunto.

Grafo planar: grafo que puede ser dibujado (mat. “embebido” en un plano) sin que ninguna arista se intersecte.

No planar: grafo que no puede ser redibujado sobre un plano sin que sus aristas se intersecten.

Teorema de Kuratowski

El Kazimierz Kuratowski, matemático polaco, encontró una caracterización de los grafos planares, conocida como el teorema de Kuratowski:

Un grafo es planar si y sólo si no contiene un subgrafo que es una subdivisión elemental de K5 (el grafo completo de 5 vértices) o K3,3 (el grafo bipartito completo de 6 vértices).

Una subdivisión elemental de un grafo resulta de insertar vértices en las aristas (por ejemplo, cambiando •——• por •—•—•). Una formulación equivalente a este teorema es: Un grafo es planar sí y sólo sí no contiene ningún subgrafo homeomorfo a K5 ó K3,3.

Otros criterios de planaridad

La práctica, es difícil usar el teorema de Kuratowski para decidir rápidamente si un grafo es planar. Sin embargo existe un algoritmo rápido para este problema: para un grafo de n vértices y e el número de aristas, es posible determinar en tiempo O(n) (lineal) si el grafo es planar o no. Teorema 1. Si n ≥ 3 entonces e ≤ 3n - 6 Teorema 2. Si n > 3 y no existen ciclos de longitud 3, entonces e ≤ 2n - 4.

El grafo K3,3, por ejemplo, tiene 6 vértices, 9 aristas y ningún ciclo de longitud 3. Por el teorema 2, no puede ser planar. Nótese que estos teoremas están construidos con una implicancia (si), y no con una equivalencia (si y sólo si) y por ende, sólo pueden ser usados para probar que el grafo no es planar, pero no que sea planar. Si ambos teoremas fallan, deben usarse otros métodos.

Fórmula de Euler

La fórmula de Euler enuncia que si un grafo conexo, plano es dibujado en un plano sin intersección de aristas, v la cantidad de vértices, e la cantidad de aristas y f la cantidad de regiones (regiones conectadas por aristas, incluyendo la región externa e infinita), entonces: v − e + f = 2, Emphasized

Por ejemplo, la Característica_de_Euler es 2. De manera más ilustrativa, en los grafos de ejemplo en el primer planar tenemos: v=6, e=7 and f=3. Si el segundo grafo se redibuja sin las intersecciones de aristas, tenemos v=4, e=6 and f=4.

La fórmula de Euler se puede probar de la siguiente manera: si el grafo no es un árbol, entonces se remueve la arista que completa el ciclo. Esto disminuye el valor de e y f en uno, dejando v − e + f constante. Repítase hasta llegar a un árbol. Los árboles tienen v = e + 1 y f = 1, que respaldan la fórmula v - e + f = 2.

En un grafo simple, conexo y planar, cualquier región (posiblemente exceptuando la exterior) está conectada por al menos tres aristas y cada arista toca como mucho dos regiones. Usando la fórmula de Euler, se puede demostrar que estos grafos son escasos en el sentido que e ≤ 3v - 6 si v ≥ 3.

Se le dice planar maximal al grafo que es planar pero al agregarle cualquier arista se destruiría la propiedad. Todas las regiones (incluso la externa) están conectadas por tres aristas, explicando la definición alternativa de triangular para este tipo de grafos. Si un grafo triangular tiene v vértices con v > 2, entonces tiene exactamente 3v - 6 aristas y 2v - 4 regiones. Un grafo es plano si se puede dibujar sin cruces de aristas. Cuando un grafo o multigrafo se puede dibujar en un plano sin que dos segmentos se corten, se dice que es plano.

Un juego muy conocido es el siguiente: Se dibujan tres casas y tres pozos. Todos los vecinos de las casas tienen el derecho de utilizar los tres pozos. Como no se llevan bien en absoluto, no quieren cruzarse jamás. ¿Es posible trazar los nueve caminos que juntan las tres casas con los tres pozos sin que haya cruces?
disposición de las casas, los pozos y los caminos implica la presencia de al menos un cruce. Sea Kn el grafo completo con n vértices, Kn, p es el grafo bipartito d