• Author / Uploaded
• Franyelis Diaz

Citation preview

Definición de grafo: Los grafos son artefactos matemáticos 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 vértices o nodos. ‘’‘Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados. De una manera más 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 vértices. A continuación ponemos los dibujos de K1,2, K3,3, y K2,5

Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados. Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común. Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), 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 más sencilla como un camino que contiene todos los arcos del grafo. Teniendo esto definido podemos hablar de los grafos eulerianos describiéndolos simplemente como aquel grafo que contiene un camino euleriano. Como ejemplos tenemos las siguientes imágenes: 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 vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: "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 gráficas (Havel & Hakimi)

Este método desarrollado por Havel y Hakimi será el que implementemos en el proyecto. Es gráfico y está basado en la reconstrucción del grafo, el cual obtenemos tras ir insertando vértices y aristas en sucesivas iteraciones.

Condiciones Las condiciones para que una sucesión de grados de un grafo sea gráfica son: •

La suma debe ser par

•

El valor máximo debe ser menor que la longitud. Por ejemplo la sucesión 6,4,4,2,1,1 no es gráfica pues el valor mayor de la sucesión (6) es igual que la longitud de esta (6).

•

Si la sucesión t1-1, t2-1, t3-1,....., ts-1, d1, d2,......, dk es gráfica entonces también lo es la sucesión s, t1, t2, t3,....., ts, d1, d2,......, dk.

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

G

G‘

Caracterización La sucesión s, t1, t2, t3,....., ts, d1, d2,......, dk es gráfica ⇔ lo es la sucesión t1-1, t2-1, t3-1,....., ts-1, d1, d2,......, dk Demostración Sea G el grafo cuya sucesión es s, t1, t2, … , ts, d1, … ,dk y sean S, T1, T2, …Ts , D1, … , Dk los vértices 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 vértice Dj con ti ≥ dj

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

Si ti >dj,

Ti tiene más vecinos que Dj. Sea Z vecino de Ti pero no vecino de Dj. Eliminamos las aristas dibujadas con líneas continuas ( SD j, ZTi ) y creamos las discontinuas ( STi, ZDj ). Este grafo G1 tiene la misma sucesión grados en el vértice S pero tiene un vecino entre los Ti más 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 algún momento un grafo Gm cuya sucesión es la dada.

Algoritmo Partiendo de una sucesión no creciente de enteros positivos o nulos para decidir si ésta es gráfica o no, lo que hay que hacer es aplicar la caracterización vista en el apartado anterior 2.2.2.2 hasta que suceda alguna de las dos situaciones siguientes: •

Se alcanza una sucesión de 0's ⇒ la sucesión si es gráfica.

•

Se obtiene un número negativo ⇒ la sucesión no es gráfica.

Isomorfismo de grafos 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(c) = 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.