GRAFOS
GRAFOS Y SU REPRESENTACIÓN
En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen)
es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos,
que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de
estudio de la teoría de grafos.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o
nodos) unidos por líneas (aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre
unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede
representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las
aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).
Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio
trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.
Composición del Grafo
Un grafo está compuesto de un conjunto de vértices y un conjunto de aristas. Los vértices
y aristas también se denominan nodos y arcos respectivamente. Una arista es realmente un par de
vértices dado que conecta dos vértices cualesquiera en un grafo.
La Figura 1.1(a) muestra un grafo de rutas aéreas parciales entre cinco ciudades de
Norteamérica. En el grafo que conecta las ciudades, una arista entre Cincinnati y Florida indica que
está disponible una ruta directa. Dado que no hay una arista directa entre Cincinnati y Puerto Rico,
no existe una ruta de vuelo disponible directa entre las dos ciudades. Note que se puede ir desde
Cincinnati a Florida y luego a Puerto Rico.
Representación del Grafo
Figura 1.6 será usada para ilustrar cómo pueden usarse los conjuntos para representar
grafos.
Primero se listarán los vértices y las aristas del grafo de la Figura 1.6.
Vértices
Cincinnati
New Jersey
New York
Boston
Aristas
Cincinnati, New Jersey
Cincinnati, New York
Cincinnati, Boston
New Jersey, New York
New Jersey, Boston
New York, New Jersey
New York, Boston
Boston, Cincinnati
Representar Grafos Usando Dos Conjuntos
En este método de representación de grafos, se crean dos conjuntos a saber: vértices y
aristas, que guardan los vértices y aristas listados anteriormente. Seguidamente, se va a entender
el uso de estos conjuntos con la ayuda de dos operaciones.
· Existencia de un vértice: Primero, se buscará en el conjunto vértices para determinar si un
vértice existe o no en el grafo.
Asuma que el vértice de entrada para el grafo en la Figura 1.6 es Florida. Observe que no es
un vértice en el grafo, pues no es parte del conjunto vértices.
· Existencia de un camino: Para encontrar un camino en un grafo se necesitan dos vértices
como entrada, un vértice origen y un vértice destino. Usando los valores de entrada y el conjunto
aristas, se determinará si existe un camino en el grafo.
Para el grafo en la Figura 1.6, si el vértice origen es New York y el vértice destino es
Cincinnati, entonces se puede encontrar si un camino existe usando el conjunto aristas de la
siguiente manera:
- Encontrar si existe una arista en el conjunto aristas que tenga a New York como el primer
vértice en la entrada de aristas. Se encuentran dos entradas en el conjunto aristas.
New York, New Jersey
New York, Boston
- Se sabe, viendo los pares de estas dos entradas, que no existe un camino directo a
Cincinnati desde New York. Considere el primer par, New York y New Jersey. Este par representa un
camino entre estos vértices.
- Ahora considere New Jersey como el nuevo origen, sin cambiar el vértice destino. Se
encuentran dos entradas para New Jersey como el primer vértice en la entrada de aristas.
New Jersey, New York
New Jersey, Boston
- Aún no se tiene un camino a Cincinnati. Por lo tanto, se considera la primera de estas dos
entradas para derivar el nuevo origen. Esto da como resultado a New York como el nuevo origen.
Se hace caso omiso de esto, dado que el primer origen fue New York (en otras palabras, ¡realmente
se ha encontrado un ciclo en este grafo!). A continuación, se considera la segunda entrada con New
Jersey como el primer vértice, que da a Boston como el nuevo vértice origen.
- Usando Boston como el nuevo vértice origen, sólo se observa una entrada en el conjunto
aristas, que tiene un camino directo hacia Cincinnati, el vértice destino.
Se ha encontrado un camino entre New York y Cincinnati, a pesar que este no es el camino
más corto. El camino más corto desde New York a Cincinnati es vía Boston sin tocar New Jersey. La
discusión sobre encontrar el camino más corto entre dos vértices en un grafo, está más allá del
alcance de este curso.
También es posible que quizás no exista un camino entre dos vértices de entrada. Usando
los pasos anteriores, finalmente se agotarían todas las entradas de aristas. Esto revelará que no
existe un camino entre los dos vértices de entrada. También es posible que, a veces, se necesite
regresar al paso anterior para tomar otra ruta. Una discusión de esto, está fuera del alcance de este
curso.
Otro método de usar conjuntos para representar un grafo involucra usar sólo un conjunto,
el cual, en efecto, proporciona la misma información que dos conjuntos diferentes. A continuación,
se discute cómo se usa este método.
INSOMORFISMO DE GRAFOS
El isomorfismo de grafos, un concepto fundamental de la teoría de grafos, es importante
para comprender la equivalencia estructural entre grafos. Ocurre cuando dos grafos se pueden
mapear entre sí mediante una biyección de sus vértices, garantizando que se conservan las aristas
correspondientes, un aspecto crítico en diversos campos, como la informática y la química.
Recuerda que, si dos grafos son isomorfos, su forma es esencialmente idéntica, a pesar de las
diferencias aparentes de trazado o representación.
Para comprender mejor el isomorfismo de grafos, veamos algunos ejemplos. Los ejercicios
de isomorfismo de grafos suelen consistir en averiguar si dos grafos dados pueden considerarse
iguales cambiando el nombre de los vértices y manteniendo la estructura de conectividad.
Explicación: En este ejemplo, es evidente que los grafos G y H son isomorfos. Puedes
cambiar el nombre de los vértices A, B y C a 1, 2 y 3 respectivamente, y la conectividad o las aristas
entre los vértices permanece inalterada. Este sencillo proceso de reetiquetado demuestra que los
dos grafos tienen la misma estructura, por lo que son isomorfos.
ARBOLES
Árbol (teoría de grafos). En teoría de grafos, un árbol es un grafo en el que cualesquiera
dos vértices están conectados por exactamente un camino. Un bosque es una unión disjunta de
árboles. Un árbol a veces recibe el nombre de árbol libre.
COLORACIÓN DE LOS VÉRTICES DE UN GRAFO
En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es
una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una
coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es
llamado vértice coloración. Similarmente, una arista coloración asigna colores a cada arista talque
aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la
asignación de un color a cada cara o región tal que caras que compartan una frontera común tengan
colores diferentes. El vértice coloración es el punto de inicio de la coloración, y los otros problemas
de coloreo pueden ser transformados a una versión con vértices. Por ejemplo, una arista coloración
de un grafo es justamente un vértice coloración del grafo línea respectivo, y una coloración de caras
de un grafo plano es un vértice coloración del grafo dual.
ALGORITMO GREEDY PARA LA COLORACIÓN DE UN VÉRTICE DE UN GRAFO
REFERENCIA BIBLIOGRAFICA
Creutzburg R., Rodríguez M., García D. y Martínez M. (Junio 2015). “Algoritmo y Estructura de
Datos”. Reiner Creutzburg on 28 June 2015. Brandenburg , Germany.
International Business Machines Corporation - IBM (Enero 2008). “Estructura de Datos y
Algoritmos”. Edición Enero 2008. Copyright IBM Corp. 2008.
Moreno, E. y Ramírez H. (Febrero 2011). “Grafos: Fundamentos y Algoritmos”. Primera Edición.
Worldcolor Chile S.A.