6.2.2 Representación Computacional de los grafos

6.2.2 Representación Computacional de los grafos

Representación mediante matrices: La forma más fácil  de guardar datos en nodos es mediante la utilización de un vector que indique los nodos, de manera  que aristas entre los nodos se puedan ver como relaciones entre los índices.

Sintaxis:

Tipo_de_variable[ ][ ]… [ ]   Nombre_del_array = new  Tipo_de_variable[dimensión1][dimensión2]…[dimensiónN];

Arreglos Unidimensionales: Es un arreglo que solo posee una dimensión, está formado por un conjunto de elementos del mismo tipo de datos que almacenan bajo un nombre y se diferencia por la posición de cada uno en el arreglo que inicia desde el 0.Estos pueden ser de 1 hasta n veces, donde n es un número de elementos del arreglo.

Sintaxis:

TipoDato nombre[]=new TipoDato[Total de elementos];

6.2.1 Matemática

6.2.1 Representación Matemática de los grafos

Por medio de la teoría de los grafos podemos resolver diversos problemas, como la síntesis para circuitos secuenciales, contadores, o sistemas de apertura. Se utiliza en diferentes áreas por ejemplo, en las áreas de Sistemas y Computación, en áreas de ingeniería. También por medio de ellas podemos responder preguntas tales como, ¿Qué tarea debo hacer primero?, ¿Qué tiempo es más corto?, ¿Cuál es el más barato?, y así podemos obtener caminos óptimos para las soluciones aplicando diversos algoritmos como puede ser el algoritmo de Floyd.

 Un grafo G es un par (V,E) donde:

o   V ={v₁,…,v_n} es un conjunto de vértices

o   E = {e₁,…,e_m} es un conjunto de aristas,

o   Con cada e_k Î {v_i, v_j}, con  v_i, v_j Î V, v_i ≠ v_j

·         Los vértices se representan como puntos y las aristas como líneas entre vértices

·         Ejemplo:

o   G = (V,E)

o   V = {a,b,c,d }

o   E = {{a,b}, {b,c}, {a,c}, {a,d}, {d,b} }

·         Proponer otro recorrido:

6.2 Representación de los grafos

6.2 Representación de los grafos

Representación de grafos

Existen diferentes formas de representar un  grafo, y hay muchos métodos para almacenarlos en una computadora. La estructura de datos usada dependerá de las características del grafo, y el algoritmo usado para manipularlo. Entre las más comunes esta las listas y matrices, con frecuencia se usa una combinación de ambas.

Estructura de lista

Lista de incidencia: El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado).

Lista de adyacencia: El grafo está representado por un arreglo de listas de adyacencia. Para un vértice i, la lista de adyacencia está formada por todos los vértices adyacentes a i. Puede construirse en tiempo lineal, y las inserciones pueden hacerse al principio de cada lista, con lo que se asegura tiempo constante.

Lista de grados: También llamada secuencia de grados o sucesión gráfica de un una secuencia de números, que corresponde a los grados de los vértices del grafo.

Estructuras matriciales

Matriz de adyacencia: El grafo está representado por una matriz cuadrada M de tamaño n^2, donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento m_ {x, y} es 1, de lo contrario, es 0.

Matriz de incidencia: El grafo está representado por una matriz de A (aristas) por V (vértices), donde [vértice, arista] contiene la información de la arista (1 - conectado, 0 - no conectado)

6.1.2 Tipos de grafos (Simples, completos, bipartidos, planos, conexos, ponderados)

6.1.2 Tipos de grafos (Simples, completos, bipartidos, planos, conexos, ponderados)

Grafo

Un grafo es un conjunto de vértice o nodos unidos por aristas o arcos.

Grafo acíclico

Es aquel  grafo no contiene ningún ciclo simple.

Grafo cíclico

Un grafo se dice cíclico si contiene algún ciclo simple.

Grafo bipartito

Un grafo bipartito es cualquier grafo, cuyos vértices pueden ser divididos en dos conjuntos, tal que no haya aristas entre los vértices del mismo conjunto. Se ve que un grafo es bipartito si no hay ciclos de longitud impar.

Grafo completo

Un grafo es completo si cada vértice tiene un grado igual a n-1, donde n es el número de vértice que compone el grafo. Además  es un grafo simple en el que cada vértice es adyacente a cualquier todo otro vértice.

Grafo conexo

Decimos que es un grafo conexo, si es posible formar un camino desde cualquier vértice a cualquier otro en el grafo.

Grafo denso

Un grafo denso es aquel grafo en el que el número de aristas está cercano al número de máximo de aristas.

Grafo dirigido

Es un conjunto de vértices V y un conjunto de aristas E tal que para cada arista perteneciente al conjunto de aristas E se asocia con dos vértices en forma ordenada.

Grafo no dirigido

Son aquellos grafos  en los cuales los lados no están orientados (no son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas

Grafo nulo

El grafo nulo es el grafo cuyos conjuntos de aristas y de vértices son vacíos.

 Grafo plano

Un grafo plano es uno que es posible dibujar en el plano sin que ningún par de aristas se crucen entre sí.

Grafo ponderado

Un grafo ponderado es aquel que  asocia un valor o peso a cada arista en el grafo. El peso de un camino en un grafo con pesos es la suma de los pesos de todas las aristas atravesadas.

Grafo regular

Un grafo regular es un grafo cuyos vértices tienen el mismo grado.

Grafo simple

Un grafo simple es un grafo o dígrafo que no tiene bucles, y que no es un multígrafo.

Grafo no Simple:

Grafo no  dirigido que tiene lados paralelos y lazos.

Grafo trivial

Un grafo trivial es  aquel  grafo vacío con un único vértice.

Grafo vacío

Un grafo vacío es el grafo cuyo conjunto de aristas es vacío.

6.1.1 Componentes de un grafo (vértices, aristas, lazos y valencia)

6.1.1 Componentes de un grafo (vértices, aristas, lazos y valencia)

 Aristas: Una arista es  una relación entre dos vértices de un grafo.

Aristas Adyacentes: estas son dos   aristas  que se dirigen en al mismo vértice y se juntan en él.

Aristas Paralelas: estas son dos aristas si el vértice inicial y el final son uno mismo.

Cruce: Son dos aristas que cruzan en un punto.

Grado o Valencia de un Vértice:   Es el número de aristas que inciden sobre un vértice.

Lazo: es una arista cuales extremos inciden sobre el mismo vértice.

Vértice: son puntos o nodos con los que están conformado los  grafos. Llamaremos grado de un vértice, al número de aristas de las que es extremo. Se le dice vértice “par” o “impar” según sea su grado.

6.1 Elementos y características de los grafos.

6.1 Elementos y características de los grafos.

Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices. Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc. La notación G = A (V, A) se utiliza comúnmente para identificar un grafo. Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.

5.5 Aplicaciones de las relaciones y las funciones en la computación

5.5 Aplicaciones de las relaciones y las funciones en la computación

Las relaciones tienen una importancia fundamental tanto en la teoría como en las aplicaciones a la informática.

Una estructura de datos tales como una lista, una matriz o un árbol, se usan para representar conjuntos de elementos junto con una relación entre los mismos.

Las relaciones que son parte de un modelo matemático están a menudo implícitamente representadas por relaciones en una estructura de datos.

Aplicaciones numéricas, recuperación de información y problemas de redes son algunos ejemplos donde las relaciones ocurren como parte de la descripción del problema, y la manipulación de relaciones es importante en la resolución de procedimientos.

Las relaciones también juegan un importante papel en la teoría de computación, incluyendo estructuras de programas y análisis de algoritmos.

5.4 Funciones (Inyectiva, Suprayectiva, Biyectiva).

Esta clasificación obedece a la forma en que están relacionados los elementos del dominio con los del recorrido. Conviene utilizar la notación: f | Df → Cf “función que mapea al dominio Df en el recorrido Cf”.

Función inyectiva (uno a uno): es inyectiva o uno a uno y se denota como 1-1, si a diferentes elementos del dominio le corresponden diferentes elementos del codominio. En esta función, para dos valores cualesquiera x1 y x2 de su dominio se cumple que: x1 es diferente de x2, entonces f(x1) es diferente que f(x2).

Ejemplo: La función f(x) = 3x + 1 es 1-1 ya que si se define como f | R → R entonces se tendrá que a diferentes elementos del dominio les corresponden diferentes elementos del codominio.

Ejemplo: Sea M el conjunto de mujeres con hijos, H el conjunto de los hijos y f la función que asocia a cada mujer con su hijo primogénito. Es una función 1-1 o inyectiva.

Para comprobar gráficamente que una función es 1-1 basta con comprobar que toda recta paralela al eje "x" corta a la gráfica de la función en un solo punto a la vez.

Función suprayectiva (sobre): Una función es suprayectiva o sobre si todo elemento de su Codominio es imagen de por lo menos un elemento de su Dominio.

Si para toda b ∈ Cf, existe a ∈ Df tal que f(a) = b, entonces f es sobreyectiva.

Otra forma de expresar que una función es sobre es decir que debe cumplir con que su Codominio y su Recorrido sean iguales.

Ejemplo: Sea la función f(x) = 3x + 1 definida como f | R → R. En este caso se ve que todo número real es imagen de algún otro número real bajo la función f. Esto significa que el recorrido es igual al codominio y por lo tanto la función dada es suprayectiva o sobre.

Función biyectiva (1-1 y sobre): Una función es biyectiva si al mismo tiempo es inyectiva y suprayectiva, y la relación entre los elementos del dominio y los del codominio es biunívoca.

 Una función puede ser:

I) 1-1 y sobre (biyectiva). 

II) 1-1, pero no sobre. 

III) No 1-1, pero sí sobre. 

IV) Ni 1-1 ni sobre.

5.3 RELACIONES DE EQUIVALENCIA (CERRADURAS, CLASES DE EQUIVALENCIA, PARTICIONES)

Cerradura de una relación                  

Definición. Sea R una relación en un conjunto A. Una cerradura reflexiva ref( R ) de R en A es la “menor” relación que la incluye y que es reflexiva, con símbolos: (∀ R’ reflexiva) (A ⊆ R’ ⊆ ref( R )) ⇒ R’ = ref( R )) Una cerradura simétrica sim( R ) de R en A es la “menor” relación que la incluye y que es simétrica, con símbolos: (∀ R’ reflexiva) (A ⊆ R’ ⊆ ref( R )) ⇒ R’ = ref( R ))
Una cerradura transitiva trans( R ) de R en A es la “menor” relación que la incluye y que es transitiva, con símbolos: (∀ R’ reflexiva) (A ⊆ R’ ⊆ ref( R )) ⇒ R’ = ref( R )

La cerradura reflexiva y la cerradura simétrica de una relación es muy simple de encontrar, solamente se le agregan los pares necesarios de una forma directa. Cuando conocemos la matriz asociada a la relación, la forma de encontrar las cerraduras anteriores es muy simple.

Teorema: Sea R una relación en A y M_R su matriz asociada. La cerradura reflexiva y la cerradura simétrica de R son únicas y se pueden obtener mediante las matrices siguientes

M_ref(R) = M_R ∪ I_n, donde I_n es la matriz identidad de orden |A|.

M_sim(R) = [a _ij], donde a _ji = 1 si a _ij = 1 en M_R.

La Matriz identidad I_n de orden n es:

{$ {(1,…,0), (vdots, ddots, vdots), (0,…,1)] $}

O sea que para lograr la cerradura reflexiva debemos agregar 1′s en la diagonal, para la cerradura simétrica debemos agregar 1′s en luagres simétricos a la diagonal principal donde existan 1′s.

Cierre de equivalencia

Para calcular el cierre de equivalencia de una relación binaria R sobre un conjunto A: 

Calcularemos primero su cierre reflexivo, ρ(R)

Sobre el resultado calcularemos el cierre simétrico, σ(ρ(R))

finalmente el cierre transitivo del resultado anterior, τ (σ(ρ(R)))

Clases de Equivalencia

Al conjunto de los elementos del conjunto A que están relacionados con él se llama clase de equivalencia.

Ejemplo:

La relación a - b = 2.k (múltiplo de 2), siendo a y b números enteros es una relación de equivalencia porque cumple las propiedades: Reflexiva: a - a = 0 = 2.k (k = 0). Simétrica: a - b = b - a porque b - a  = -(a - b). Si a - b es múltiplo de 2, -(a - b) también lo será. Transitiva: a - b = 2.k1   b - c = 2.k2  Sumando queda a - c = 2.k3 Entonces a - c es múltiplo de 2. 

En el ejemplo anterior, la clase de equivalencia del número cero (uno de los elementos del conjunto de los números enteros)  C(0) = {... -4, -2, 0, 2, 4, ...}, pues 0 - (-4) es múltiplo de 2, 0 - (-2) es múltiplo de 2 ya sí sucesivamente. La clase de equivalencia del número 1 será C(1) = {... -5, -3, -1, 1, 3, 5, ...} pues la diferencia entre 1 y los números indicados es múltiplo de 2. 

Del mismo modo podríamos calcular las clases de equivalencia de más números. 

El conjunto formado por las clases de equivalencia se llama conjunto cociente.

En el ejemplo anterior el conjunto cociente Z / 2 es el conjunto formado por las clases de todos los elementos Z / 2 = {C(0), C(1), C(2), ... }.

Particiones

Sea X un conjunto. P es una partición de X si y sólo si:

 

Los conjuntos de P son disyuntos 2 a 2, es decir, si  y entonces                                                                                                              

Observe que si P es una partición de X, entonces todo elemento de X está en uno y sólo un elementouno y sólo un elemento de modo que   parte a   en conjuntos disyuntos. 

Por ejemplo, el conjunto de barriles propuesto al comienzo de la sección es una partición del conjunto de mangos. Otro ejemplo de una partición es de la división política de un país: El país (visto como un conjunto de personas) se parte en estados o departamentos no vacíos disyuntos entre sí.

Ejemplo

   Sea ={1, 2, 3, 4, 5, 6, 7, 8, 9}

Entonces = {{1, 9}, {2, 8}, {3, 4, 5, 6, 7}}  

Es una partición de X en tres conjuntos: elementos externos (1,9), elementos semi-externos (2, 8) y elementos internos (3, 4, 5, 6, 7). 

Note que Q = {{1, 2, 9}, {2, 8}, {3, 4, 5, 6, 7}} no es partición de X 

(¿por qué?).

Como lo habíamos insinuado, resulta que toda relación de equivalencia determina de manera natural una partición.