Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 304 vistas

    Isomorfismo de Grafos

    Cargado por

    Franyelis Diaz
    Un grafo es una representación matemática de relaciones entre elementos. Consiste en nodos y aristas que los conectan. Existen diferentes tipos de grafos como bipartitos, nulos, isomorfos y eulerianos. Determinar si una sucesión de grados representa un grafo es un problema de complejidad que depende del tamaño del grafo. El isomorfismo de grafos busca emparejamientos biyectivos que preserven las conexiones y aún se desconoce si pertenece a clases algorítmicas como P o NP.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd

    Isomorfismo de Grafos

    Cargado por

    Franyelis Diaz
    304 vistas8 páginas
    Un grafo es una representación matemática de relaciones entre elementos. Consiste en nodos y aristas que los conectan. Existen diferentes tipos de grafos como bipartitos, nulos, isomorfos y eulerianos. Determinar si una sucesión de grados representa un grafo es un problema de complejidad que depende del tamaño del grafo. El isomorfismo de grafos busca emparejamientos biyectivos que preserven las conexiones y aún se desconoce si pertenece a clases algorítmicas como P o NP.

    Derechos de autor

    © Attribution Non-Commercial (BY-NC)

    Formatos disponibles

    DOC, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Un grafo es una representación matemática de relaciones entre elementos. Consiste en nodos y aristas que los conectan. Existen diferentes tipos de grafos como bipartitos, nulos, isomorfos y eulerianos. Determinar si una sucesión de grados representa un grafo es un problema de complejidad que depende del tamaño del grafo. El isomorfismo de grafos busca emparejamientos biyectivos que preserven las conexiones y aún se desconoce si pertenece a clases algorítmicas como P o NP.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd
    Descargar como doc, pdf o txt
    304 vistas8 páginas

    Isomorfismo de Grafos

    Cargado por

    Franyelis Diaz
    Un grafo es una representación matemática de relaciones entre elementos. Consiste en nodos y aristas que los conectan. Existen diferentes tipos de grafos como bipartitos, nulos, isomorfos y eulerianos. Determinar si una sucesión de grados representa un grafo es un problema de complejidad que depende del tamaño del grafo. El isomorfismo de grafos busca emparejamientos biyectivos que preserven las conexiones y aún se desconoce si pertenece a clases algorítmicas como P o NP.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd
    Descargar como doc, pdf o txt
    de 8

    Definicin de grafo: Los grafos son artefactos matemticos que permiten expresar de una forma visualmente muy sencilla

    y efectiva las relaciones que se dan entre elementos de muy diversa ndole. Un grafo simple est formado por dos conjuntos: Un conjunto V de puntos llamados vrtices o nodos. Un conjunto de pares de vrtices que se llaman aristas o arcos y que indican qu nodos estn relacionados. De una manera ms informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.

    Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto disjunto de vrtices. A continuacin ponemos los dibujos de K1,2, K3,3, y K2,5

    Grafo nulo: Se dice que un grafo es nulo cuando los vrtices que lo componen no estn conectados, esto es, que son vrtices aislados. Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunvoca (uno a uno), entre sus vrtices de tal forma que dos de estos quedan unidos por una arista en comn. Grafos Platnicos: Son los Grafos formados por los vrtices y aristas de los cinco slidos regulares (Slidos Platnicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.

    Grafos Eulerianos. Para definir un camino euleriano es importante definir un camino euleriano primero. Un camino euleriano se define de la manera ms sencilla como un camino que contiene todos los arcos del grafo. Teniendo esto definido podemos hablar de los grafos eulerianos describindolos simplemente como aquel grafo que contiene un camino euleriano. Como ejemplos tenemos las siguientes imgenes: El primer grafo de ellos no contiene caminos eulerianos mientras el segundo contiene al menos uno. Grafos Conexos. Un grafo se puede definir como conexo si cualquier vrtice V pertenece al conjunto de vrtices y es alcanzable por algn otro. Otra definicin que dejara esto ms claro sera: "un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une".

    Sucesiones grficas (Havel & Hakimi)

    Este mtodo desarrollado por Havel y Hakimi ser el que implementemos en el proyecto. Es grfico y est basado en la reconstruccin del grafo, el cual obtenemos tras ir insertando vrtices y aristas en sucesivas iteraciones.

    Condiciones Las condiciones para que una sucesin de grados de un grafo sea grfica son: La suma debe ser par El valor mximo debe ser menor que la longitud. Por ejemplo la sucesin 6,4,4,2,1,1 no es grfica pues el valor mayor de la sucesin (6) es igual que la longitud de esta (6). Si la sucesin t1-1, t2-1, t3-1,....., ts-1, d1, d2,......, dk es grfica entonces tambin lo es la sucesin s, t1, t2, t3,....., ts, d1, d2,......, dk.

    Si dos grafos son isomorfos entonces tienen la misma sucesin de grados, pero que dos grafos tengan la misma sucesin de grados no quiere decir que sean isomorfos.Por ejemplo los dos siguiente grafos tienen la misma sucesin 4,4,3,2,2,2,1. Pero no son isomorfos porque por ejemplo en el grafo G los nodos de grado 4 no estn unidos, mientras que en el grafo G' los nodos de grado 4 si lo estn.

    G Caracterizacin

    La sucesin s, t1, t2, t3,....., ts, d1, d2,......, dk es grfica lo es la sucesin t1-1, t2-1, t3-1,....., ts-1, d1, d2,......, dk Demostracin Sea G el grafo cuya sucesin es s, t1, t2, , ts, d1, ,dk y sean S, T1, T2, Ts , D1, , Dk los vrtices correspondientes Si S es adyacente a T1, T2, Ts, borramos S y el grafo H=G-{S} es el grafo buscado.

    Si no es as, S no es adyacente a un Ti pero S es adyacente a un vrtice Dj con ti dj

    Si ti= dj , basta intercambiar los papeles de Ti y de Dj

    Si ti >dj,

    Ti tiene ms vecinos que Dj. Sea Z vecino de Ti pero no vecino de Dj. Eliminamos las aristas dibujadas con lneas continuas ( SD j, ZTi ) y creamos las discontinuas ( STi, ZDj ). Este grafo G1 tiene la misma sucesin grados en el vrtice S pero tiene un vecino entre los Ti ms que en el grafo G. Si en G' ya es S adyacente a T1, T2,Ts, se procede como antes. Y si no lo es se repite el cambio discontinuas-continuas. Como s es finito se alcanza en algn momento un grafo Gm cuya sucesin es la dada.

    Algoritmo Partiendo de una sucesin no creciente de enteros positivos o nulos para decidir si sta es grfica o no, lo que hay que hacer es aplicar la caracterizacin vista en el apartado anterior 2.2.2.2 hasta que suceda alguna de las dos situaciones siguientes: Se alcanza una sucesin de 0's la sucesin si es grfica.

    Se obtiene un nmero negativo la sucesin no es grfica.

    Isomorfismo de grafos
    Dados G=(V,E) y G=(V,E), se denomina isomorfismo de G a G a la aplicacin biyectiva f tal que para a,bV, {a,b}E se cumple {f(a),f(b)}E. Es decir, la aplicacin que relaciona biyectivamente pares de vrtices de E con pares de vrtices de E, de modo que los vrtices conectados por aristas siguen estndolo. G y G se denominan isomorfos, y son matemticamente 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 biyeccin f: V V definida por f(a) = 2, f(b) = 1, f(c) = 3, f(d) = 4 que conserva la adyacencia.

    Complejidad
    Los problemas matemticos 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 cmputo. Sin embargo, que un problema sea decidible no implica que se pueda encontrar su solucin, pues muchos problemas que disponen de algoritmos para su resolucin son inabordables para un computador por el elevado nmero 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 solucin. tratables: aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo razonable. Los problemas pueden clasificarse tambin atendiendo a su complejidad. Aquellos problemas para los que se conoce un algoritmo polinmico 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 slo 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 sera 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 aplicacin de algoritmos no muy complejos. Este caso ser el que desarrollaremos en la segunda parte del proyecto, apartado 2.3.

    También podría gustarte