6.2.- Representación de los grafos

Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas.

Representación mediante matrices: La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.

Representación mediante listas: En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.

Representación mediante matrices dispersas: Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.

Dígrafo (grafo dirigido).

A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas, como en el siguiente caso.

Aplicaciones de los dígrafos

Una de las aplicaciones más importantes es de hallar el camino más corto hacia un destino, ya sea de una ciudad a otra, de unos departamentos a otros, para el recorrido de árboles, sirve para la representación de algoritmos, etc. Un ejemplo de esto es la tarea de freír un huevo.

Grado de un grafo.

Grado de incidencia positivo: El grado de incidencia positivo de un nodo nj es el número de arcos que tienen como nodo inicial a nj. Ejemplo: El grado de incidencia de 1 es igual a 3.

Grado de incidencia negativo: El grado de incidencia negativo de un nodo nj es el número de arcos que terminan en nj. Ejemplo: El grado de incidencia negativo de 1 es igual a 1.

Grado de un nodo: Paradigrafos es el grado de incidencia positivo menos el grado de incidencia negativo del nodo. Ejemplo: El grado de 1 es igual a 3 –1 = 2, el grado del nodo 4 es 2 –2 = 0. Para grafos no dirigidos es el número de líneas asociadas al nodo.

Ciclo de un grafo.

Ciclo: Es una cadena finita donde el nodo inicial de la cadena coincide con el nodo terminal de la misma.

Ciclo simple: Es el ciclo que a su vez es una cadena simple.

Estructuras no lineales: Grafos

Las estructuras de datos no lineales se caracterizan por no existir una relación de adyacencia, entre sus elementos, es decir, un elemento puede estar relacionado con cero, uno o más elementos.

La estructura no lineal de datos más general es el grafo donde sus nodos pueden relacionarse de cualquier manera sin una relación de orden predefinida.

Estructuras no lineales: Grafos Entre las múltiples aplicaciones que tienen estas estructuras podemos mencionar:

•Para modelar diversas situaciones tales como: sistemas de aeropuertos, flujo de tráfico, y responder a preguntas como:

¿Qué tiempo es más corto?, ¿Cómo es más barato?, o ¿Qué camino es más corto?

•Los grafos también son utilizados para realizar planificación de actividades, tareas del computador, planificar operaciones

en lenguaje de máquinas para minimizar tiempo de ejecución. ¿Qué tarea debo hacer primero?

•Para representar circuitos eléctricos, de aguas etc... , y preguntar, están todas las componentes conectadas.

Grafos Los grafos pueden ser utilizados como la estructura básica para múltiples aplicaciones en el área de la Computación.

Un grafo G (N, A, f) es un conjunto no vacío, donde:

•N={n1, n2, ... ,nM) es el conjunto de nodos o vértices

•A= {a1, a2,..., a K} es el conjunto de aristas y

• La función f: R →ΜΧΜindica los pares de nodos que esta αn relacionados.

•Grafos Dirigidos (Dígrafos) En estos grafos, las aristas que comunican dos nodos tienen un único sentido, una arista puede ir de x a y, pero no dé y a x. Se expresa gráficamente con flechas que indican el sentido de la relación entre cada par de nodos.

Grafos

•Grafos no dirigidos En estos grafos, las aristas que comunican dos nodos tienen dos sentidos. Si una arista va de x a y, la misma arista va de y a x. Se expresa gráficamente por líneas. La representación gráfica de un grafo se define con un círculo o rectángulo para los nodos y las relaciones con líneas o flechas según sea un grafo no dirigido o un dígrafo, respectivamente.

TIPOS DE GRAFOS.

Grafos Simples

Aquí lidiaremos con grafos simples, es decir en los que hay una arista o lado entre vértices como máximo, y en los que no hay loops o lazos que conectan algún vértice consigo mismo.
El grado de un nodo de un grafo simple es la cantidad de aristas o lados que concurren a él.

Trayectorias y Circuitos

Si en un grafo simple se van recorriendo sucesivamente sus aristas de modo tal que dos sucesivas sean adyacentes, es decir que concurran al mismo vértice por el que se pasa de una a la otra, se está recorriendo o determinando una trayectoria o
camino.
Cuando cierta trayectoria comienza y termina en el mismo nodo decimos que es un circuito.
Cuando una trayectoria pasa sólo una vez por todas y cada una de las aristas o lados se dice que la trayectoria es semi- euleriana, y si esta trayectoria fuera un circuito se la denomina circuito euleriano.

No existe un grafo simple con un sólo nodo de grado impar.
Esto refiere entre otros temas las paridades de los nodos de un grafo simple, es decir cuántos nodos pares e impares tiene.
Dado cierto grafo, al agregarle una arista, a cada nodo de los extremos de esta arista se le suma una unidad a su grado.
Es decir, que si alguno de esos nodos de los extremos tenían grado impar, pasan a tener grado par y viceversa.
Analizando las posibles combinaciones de paridades de estos nodos de los extremos del nuevo vértice:

                                      i) par-par,
                                     ii) par-impar,
                                    iii)impar-impar,

Se nota que la cantidad de nodos con grados impares resulta:

i)o aumentada en dos unidades,

ii)o inalterada,

iii)o reducida en dos unidades.

Para mostrar esto se toma un cierto conjunto de puntos del plano sin vértices que los conecten, y se lo considera un grafo sin vértices. Claramente todo nodo en este caso tiene grado cero.

Cualquier grafo simple puede entonces obtenerse partiendo de unir los nodos de un grafo sin vértices, agregando sucesivamente sus aristas, hasta completarlo.

A partir de esto puede afirmarse que todo grafo simple tiene o ningún nodo de grado impar o por lo menos dos nodos de grado impar.
Es decir, no existe un grafo simple con un sólo nodo de grado impar.

Grafos completos

En teoría de grafos, un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista.

Un grafo completo de n vértices tiene n(n − 1) / 2 aristas, y se nota Kn. Es un grafo regular con todos sus vértices de grado n − 1. Ningún grafo completo tiene lazos y está conectado totalmente, por ende, la única forma de hacer disconexo el grafo con una eliminación de vértices es aplicarla a todos.

El teorema de Kuratowski dice que un grafo planar no puede contener K5 (ó el grafo bipartito completo K3,3) y todo Kn incluye a Kn − 1, entonces ningún grafo completo Kn con es planar

Los grafos completos de 1 a 12 vértices son los siguientes:

K1:0

K2:1

K3:3

K4:6

K5:10

K6:15

K7:21

K8:28

K9:36

K10:45

K11:55

K12:66

Grafo bipartito

Un Grafo bipartito se denomina en Teoría de grafos a un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V1 y V2 y las aristas siempre unen vértices de un conjunto con vértices de otro:

no existe ninguna arista e = x1,x2 ni e = y1,y2

Siendo V el conjunto que contiene todos los vértices del grafo.

Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.

Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los vértices en U de azul y los vértices deV de verde obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un gráfico no tiene la propiedad de que se puede colorear con dos colores no es bipartito.

Un grafo bipartito suele con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto es, si los dos subconjuntos tiene la misma cantidad de elementos, decimos que el grafo bipartito G es balanceado.

Ejemplo Grafo bipartito

Representación de grafos. Matriz de incidencia. Matriz de adyacencia.

Definición 1.4.1. Dado un grafo G = (V, E) con n vértices {v1, ..., vn} su matriz de

adyacencia es la matriz de orden n×n, A(G)=(aij) donde aij es el número de aristas que

unen los vértices vi y vj.

Ejemplo 1.4.2.