- Grafos
- Aristas – Vértices –
Caminos - Clasificación de
grafos - Grafos
Eulerianos. - Grafos
Conexos - Árboles.
- Bosques de
árboles. - Recorrido de un
grafo. - Representación de grafos
en programas. - Dígrafo (grafo
dirigido). - Aplicaciones de los
dígrafos - Grado de un
grafo. - Ciclo de un
grafo. - Estructuras no lineales:
Grafos - Anexo
Hoy en día podemos ver muchas cosas que nos
pueden parecer de lo mas cotidianas, carreteras, líneas
telefónicas, líneas de televisión
por cable, el transporte
colectivo metro, circuitos
eléctricos de nuestras casas, automóviles, y
tantas cosas mas; lo que no pensamos frecuentemente es que estos
forman parte de algo que en matemáticas se denomina como grafos.
En este trabajo se
tratará de explicar lo que son los grafos, sus tipos, y
algunas derivaciones de ellos, así como su
representación gráfica y en algunos casos, su
representación en algún programa
informático, así como en la
memoria.
En este trabajo, se explicando de manera muy
sencilla los conceptos y algunas metodologías con un
lenguaje no
tan rebuscado para su mayor entendimiento.
Desafortunadamente no existe una terminología
estandarizada en la teoría
de los grafos, por lo tanto es oportuno aclarar que las presentes
definiciones pueden variar ligeramente entre diferentes
publicaciones de estructura de
datos y de teoría de grafos, pero en general se puede
decir que un grafo como indica su nombre lo indica es la
representación (para nuestro caso) gráfica de los
datos de una
situación particular, ejemplo:
Los datos contienen, en algunos casos,
relaciones entre ellos que no es necesariamente
jerárquica. Por ejemplo, supongamos que unas líneas
aéreas realizan vuelos entre las ciudades conectadas por
líneas como se ve en la figura anterior (más
adelante se presentaran grafos con estructuras de
datos); la estructura de
datos que refleja esta relación recibe el nombre de
grafo.
Se suelen usar muchos nombres al referirnos a los
elementos de una estructura de datos. Algunos de ellos son
"elemento", "ítem", "asociación de ítems",
"registro",
"nodo" y "objeto". El nombre que se utiliza depende del tipo de
estructura, el contexto en que usamos esa estructura y quien la
utiliza.
En la mayoría de los textos de estructura de
datos se utiliza el termino "registro" al hacer referencia a
archivos y
"nodo" cuando se usan listas enlazadas, árboles
y grafos.
También un grafo es una terna G = (V,A,j
), en donde V y A son conjuntos
finitos, y j es una aplicación que hace
corresponder a cada elemento de A un par de elementos de
V. Los elementos de V y de A se llaman,
respectivamente, "vértices" y "aristas" de
G, y j asocia entonces a cada arista con sus dos
vértices.
Esta definición da lugar a una representación
gráfica, en donde cada vértice es un punto del
plano, y cada arista es una línea que une a sus dos
vértices.
Son las líneas con las que se unen las aristas de un
grafo y con la que se construyen también caminos.
Si la arista carece de dirección se denota indistintamente {a,
b} o {b, a}, siendo a y b los vértices que
une.
Si {a ,b} es una arista, a los vértices a y b
se les llama sus extremos.
- Aristas Adyacentes: Se dice que dos aristas son
adyacentes si convergen en el mismo vértice. - Aristas Paralelas: Se dice que dos aristas son
paralelas si vértice inicial y el final son el
mismo. - Aristas Cíclicas: Arista que parte de un
vértice para entrar en el mismo. - Cruce: Son dos aristas que cruzan en un
punto.
Son los puntos o nodos con los que esta conformado un
grafo. Llamaremos grado de un vértice al número de
aristas de las que es extremo. Se dice que un vértice es
`par' o `impar' según lo sea su grado.
- Vértices Adyacentes: si tenemos un par de
vértices de un grafo (U, V) y si tenemos un arista que
los une, entonces U y V son vértices adyacentes y se
dice que U es el vértice inicial y V el vértice
adyacente. - Vértice Aislado: Es un vértice de grado
cero. - Vértice Terminal: Es un vértice de grado
1.
Sean x, y " V, se dice que hay un camino en G de x a
y si existe una sucesión finita no vacía de
aristas {x,v1}, {v1,v2},…,
{vn,y}. En este caso
- x e y se llaman los extremos del camino
- El número de aristas del camino se llama la
longitud del camino. - Si los vértices no se repiten el camino se dice
propio o simple. - Si hay un camino no simple entre 2 vértices,
también habrá un camino simple entre
ellos. - Cuando los dos extremos de un camino son iguales, el
camino se llama circuito o camino cerrado. - Llamaremos ciclo a un circuito simple
- Un vértice a se dice accesible desde el
vértice b si existe un camino entre ellos. Todo
vértice es accesible respecto a si mismo
Los grafos se pueden clasificar en dos grupos: dirigidos
y no dirigidos. En un grafo no dirigido el par de vértices
que representa un arco no está ordenado. Por lo tanto, los
pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo
dirigido cada arco está representado por un par ordenado
de vértices, de forma que y representan dos arcos
diferentes.
Ejemplos
G1 = (V1, A1)
V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2,
4), (3, 4)}
G2 = (V2, A2)
V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5),
(3, 6)}
G3 = (V3, A3)
V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3>
}
Gráficamente estas tres estructuras de vértices
y arcos se pueden representar de la siguiente manera:
Para ver el gráfico seleccione la
opción "Descargar" del menú superior
Algunos de los principales tipos de grafos son los que
se muestran a continuación:
- Grafo regular: Aquel con el mismo grado en
todos los vértices. Si ese grado es k lo llamaremos
k-regular.
Por ejemplo, el primero de los siguientes grafos es
3-regular, el segundo es 2-regular y el tercero no es
regular
- Grafo bipartito: Es aquel con cuyos
vértices pueden formarse dos conjuntos disjuntos de modo
que no haya adyacencias entre vértices pertenecientes al
mismo conjunto
Ejemplo.- de los dos grafos siguientes el primero es
bipartito y el segundo no lo es
- Grafo completo: Aquel con una arista entre
cada par de vértices. Un grafo completo con n
vértices se denota Kn.
A continuación pueden verse los dibujos de
K3, K4, K5 y
K6
- 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.
Para ver el gráfico seleccione la
opción "Descargar" del menú superior
- 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.
Para ver el gráfico seleccione la
opción "Descargar" del menú superior
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.
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".
Un árbol se define como un
tipo de grafo que no contiene ciclos, es decir es un grafo
también acíclico, pero a su vez es conexo. Tal es
el caso de los siguientes dos grafos en donde se puede notar que
ninguno de los dos contiene repeticiones (ciclos).
Los bosques de árboles son un
caso similar a los árboles, son acíclicos, pero no
son conexos. Como ejemplo tenemos la siguiente
figura.
Para ver el gráfico seleccione
la opción "Descargar" del menú
superior
Recorrer un grafo significa tratar de alcanzar todos
los nodos que estén relacionados con uno que llamaremos
nodo de salida. Existen básicamente dos
técnicas para recorrer un grafo: el
recorrido en anchura; y el recorrido en
profundidad.
- Recorrido en anchura:
El recorrido en anchura supone
recorrer el grafo, a partir de un nodo dado, en niveles, es
decir, primero los que están a una distancia de un
arco del nodo de salida, después los que están
a dos arcos de distancia, y así sucesivamente hasta
alcanzar todos los nodos a los que se pudiese llegar desde el
nodo salida. - Recorrido en profundidad: el recorrido en
profundidad trata de buscar los caminos que parten desde el
nodo de salida hasta que ya no es posible avanzar más.
Cuando ya no puede avanzarse más sobre el camino
elegido, se vuelve atrás en busca de caminos
alternativos, que no se estudiaron previamente.
Representación de grafos en programas.
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.
A un grafo dirigido se le puede definir como un
grafo que contiene aristas dirigidas, como en el siguiente
caso.
Una de las aplicaciones mas importantes
es de hallar el camino mas 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 incidencia positivo: El grado
de incidencia positivo de un nodonjes el número de arcos
que tienen como nodo inicial anj. Ejemplo: El grado de
incidencia de 1 es igual a 3. - Grado de incidencia negativo: El grado
de incidencia negativo de un nodonjes el número de arcos
que terminan ennj. Ejemplo: El grado de incidencia negativo de
1 es igual a 1. - Grado de un nodo: Paradigrafoses 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: 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
estα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 de 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.
Las representaciones de grafos más
habituales están basadas en matrices de adyacencia
y listas de adyacencia. En este ejercicio se pretende
representar distintos grafos utilizando tanto matrices como
listas de adyacencia.
El plan de estudios
de determinada titulación se compone de 6 asignaturas, que
por simplicidad, denominaremos y 
. A la hora de matricularse de las distintas
asignaturas se ha de tener en cuenta una serie de dependencias
entre ellas (prerrequisitos). De esta forma, un alumno no se
puede matricular en una asignatura hasta haber aprobado aquellas
otras que sean prerrequisito de dicha asignatura. Representaremos
a continuación los prerrequisitos del plan de estudios
como un grafo dirigido de dependencias.
Por ejemplo, un arco del nodo 
al nodo 
indica que no es posible matricularse de sin haber aprobado previamente . A continuación se muestran las operaciones
del TAD grafos necesarios para construir el grafo de
dependencias.
Para ver el gráfico
seleccione la opción "Descargar" del menú
superior
Teniendo en cuenta que una operación de la
forma
Para ver el gráfico
seleccione la opción "Descargar" del menú
superior
añade al grafo
Para ver el gráfico
seleccione la opción "Descargar" del menú
superior
un arco con origen en
Para ver el gráfico
seleccione la opción "Descargar" del menú
superior
y destino en
Para ver el gráfico
seleccione la opción "Descargar" del menú
superior
, se pide: Representar gráficamente
y mediante matrices de adyacencia cada uno de los
grafos
Para ver el gráfico
seleccione la opción "Descargar" del menú
superior
Solución
propuesta:
A continuación se muestra la
representación gráfica de los
grafos.
Para ver el gráfico
seleccione la opción "Descargar" del menú
superior
La representación basada en matrices de
adyacencia utiliza dos componentes. El primero es un conjunto que
contiene los nodos del grafo. El segundo es una matriz booleana
que representa los arcos. Existe un arco entre un nodo 
y otro 
si la posición de fila y columna tiene el valor
(representado por una 
). Las casillas vacías tienen
valor
Para ver el gráfico
seleccione la opción "Descargar" del menú
superior
Una compañía telefónica
desea realizar un estudio sobre las llamadas que realizan sus
abonados. Para ello, se desea construir un grafo cuyos nodos son
los abonados (identificados por su número de teléfono). La existencia de un arco con
origen en el nodo y destino en el nodo indica que el abonado ha llamado alguna vez al abonado . En este grafo se realizan también borrados
cuando alguno de los abonados se da de baja de la
compañía telefónica. A continuación
se muestra una serie de operaciones para la obtención del
grafo de llamadas entre usuarios:
Se pide: Representar gráficamente y
mediante listas de adyacencia cada uno de los grafos
, 
y 
.
Solución
propuesta:
Para ver el gráfico
seleccione la opción "Descargar" del menú
superior
- Teniendo en cuenta que el conjunto de
asignaturas del plan de estudios no varía (aunque si lo
pueden hacer los prerrequisitos), es posible representar el
grafo del apartado a) ¿utilizando listas de
adyacencia? ¿Por qué?
Solución
propuesta:
Sí. De hecho, la representación
basada en listas de adyacencia es más general que la
basada en matrices de adyacencia. Por tanto, como es posible
representarlo utilizando matrices de adyacencia, también
es posible representarlo utilizando listas de
adyacencia.
- Teniendo en cuenta que el conjunto de abonados
varía continuamente y es infactible dar una cota
máxima del número de abonados, sería
posible representar el grafo del apartado b) utilizando
matrices de adyacencia? Por qué?
Solución
propuesta:
No, ya que no podemos fijar de antemano las
dimensiones de la matriz de adyacencia ni tampoco el nombre de
los nodos a que corresponde cada fila y columna de dicha
matriz.
Margareth Iglesias
República Bolivariana de Venezuela.
Ministerio de Educación, Cultura y
Deporte.
I U. Politécnico "Santiago
Mariño"
Barcelona – Edo.
Anzoátegui.