Representaciones de los Grafos

Representaciones de los Grafos.

La primera forma, la más inmediata de representar un grafo, es mediante su respectivo dibujo o diagrama. También, ya estudiamos una forma de representar esos dibujos mediante simbología matemática.

Por ejemplo, si tenemos el grafo de la figura 1.13 (a), lo podemos representar mediante:

G = (V, E)

V = {1, 2, 3, 4, 5, 6}

E = {(2,1), (2,4), (1,6), (6,4), (4,4), (4,5), (3,2)}

Ahora bien, por conveniencia, podemos etiquetar el grafo, como en la figura 1.13 (b), con lo cual, el grafo nos quedaría representado por:

G = (V, E)

V = {1, 2, 3, 4, 5, 6}

 E = {a, b, c, d, e, f, g}

Pero, aparte de estas formas, resulta que también podemos representar el grafo mediante una matriz, lo cual se desarrolla a continuación:

Matriz de Incidencia. Sea G = (V, E) un grafo con ν vértices y ε aristas, entonces le corresponde una matriz de dimensión ν × ε denominada la matriz de incidencia de G.

Si denotamos los vértices de G por v1, v2,..., vν y las aristas por e1, e2,..., eε. Entonces la matriz de incidencia de G es la matriz M(G) = [mij] donde mij es el número de veces que la arista ej incide en el vértice vi; los valores posibles son 0,1 ´o 2 (2 en el caso que la arista sea un lazo).

Para digerir un poco mejor esta definición, construyamos la matriz de incidencia para el grafo de la figura 1.13 (b).

Ejemplo: En primer lugar, la matriz debe ser de dimensión ν × ε, en ´este caso observemos que ν (G) = 6 y que ε (G) = 7, por lo tanto la matriz tendrá 6 filas y 7 columnas, es decir, será de dimensión 6×7.

Luego, construimos la matriz, colocando como referencia para las filas los vértices y como referencia para las columnas las aristas:

Luego, vamos rellenando cada uno de los cuadros internos de la tabla, por ejemplo, el valor que corresponde en la esquina superior izquierda es 1, ya que en el vértice 1 incide una vez con la arista a. Luego la tabla se completa como sigue:

Por lo tanto, la matriz de incidencia del grafo es:

Matriz de Adyacencia. Sea G = (V, E) un grafo, la matriz de adyacencia relacionada con G es una matriz de dimensión ν × ν, denotada por A (G) = [aij] en donde aij es el número de aristas que van de vi hasta vj.

Igual que para la matriz de incidencia, vamos a construir la matriz de adyacencia relacionada con el grafo de la figura 1.13 (b), con el objeto de esclarecer la definición.

Ejemplo: En primer lugar, la matriz debe ser de dimensión ν × ν, en ´este caso observemos que ν (G) = 6, por lo tanto la matriz tendrá 6 filas y 6 columnas, es decir, será de dimensión 6×6.

Construimos la matriz, colocando como referencia para las filas los vértices y de igual forma para las columnas:

Luego comenzamos a llenar la tabla, observando que como estamos trabajando con un grafo dirigido, las aristas van en un sólo sentido. ¿Cuántas aristas van del vértice 1 al vértice 1? Ninguna, por lo que en el primer cuadro de la esquina superior izquierda el valor que corresponde es 0. Luego la tabla se completa de la siguiente manera:

Por lo tanto, la matriz de adyacencia del grafo es:

Ya que el grafo con el que estamos trabajando es un grafo etiquetado, se pueden reemplazar los valores numéricos por los nombres concretos de las aristas, así se tiene una información más clara del grafo. De igual manera que para un dígrafo, se pueden construir matrices de incidencia y adyacencia relacionados a un grafo no dirigido, con la única diferencia de se toman en cuenta ambas direcciones de las aristas. Podemos desarrollar ´estas ideas con la figura 1.14.

Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, dibujo computacional, en todas las áreas de Ingeniería. Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos

Óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd. Para la administración de proyectos, utilizamos técnicas como técnica de revisión y evaluación de programas (PERT) en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.

Se emplean en problemas de control de producción, para proyectar redes de ordenadores, para diseñar módulos electrónicos modernos y proyectar sistemas físicos con parámetros localizados (mecánicos, acústicos y eléctricos). Se usa para la solución de problemas de genética y problemas de automatización de la proyección (SAPR). Apoyo matemático de los sistemas modernos para el procesamiento de la información. Acude en las investigaciones nucleares (técnica de diagramas de Feynman).

Por el momento, ya tenemos teoría suficiente relacionada a grafos para desarrollar de manera más integral a los autómatas, que en realidad es nuestro objetivo principal. Por lo tanto, aunque la teoría de grafos es mucho más extensa, nos quedaremos con los conceptos introductorios que hemos estudiado en esta sección.