Back
Close

Fundamentos de teoría de grafos

Racso
98.7K views
Previous: Fundamentos

Ya sabemos qué son los grafos. Ahora, veamos cómo podemos representar grafos de otros modos además de dibujarlos. Ello será útil si queremos trabajar con grafos con un computador.

Lista de adyacencia

¿Recuerdas nuestro grafo de ciudades?

Grafo de ejemplo

Hagamos una lista de los vecinos de cada nodo:

  • CAR: MED, BUC
  • MED: CAR, BUC, BUE, ARM, BOG
  • BUC: CAR, MED, BOG, YOP
  • BUE: MED, CAL, PAS
  • ARM: MED, BOG, CAL
  • BOG: MED, BUC, YOP, ARM, CAL
  • YOP: BUC, ARM, BOG, LET
  • CAL: BUE, ARM, BOG, YOP, LET, PAS
  • PAS: BUE, CAL
  • LET: CAL, YOP

Esa es la lista de adyacencia del grafo: una lista de listas describiendo los vecinos de cada nodo.

Si el grafo es dirigido, un nodo B sólo aparece en la lista de un nodo A si hay una arista desde A hacia B. Por ejemplo, en nuestro grafo dirigido de Twitter:

Grafo dirigido de ejemplo

  • A: B, C
  • B: A
  • C: B

Matriz de adyacencia

Los grafos también pueden representarse con matrices de adyacencia. Aquí está la matriz de adyacencia de nuestro grafo de ciudades:

CARBUCYOPBOGLETCALARMMEDBUEPAS
CAR0100000100
BUC1011000100
YOP0101111000
BOG0110011100
LET0010010000
CAL0011101011
ARM0011010100
MED1101001010
BUE0000010101
PAS0000010010

Una matriz de adyacencia tiene los nodos del grafo listados en sus filas y columnas. El valor en cada celda indica si existe una arista entre el par de nodos correspondiente a la fila y la columna. Por ejemplo, la celda en la fila BOG y la columna BUC tiene un valor de 1 porque existe una arista entre BOG y BUC, mientras que la celda en la fila PAS y la columna YOP tiene un 0 porque no hay arista entre esos dos nodos.

Un grafo puede tener varias matrices de adyacencia. En el ejemplo anterior, si pones los nodos en un orden diferente, tendrás una nueva matriz de adyacencia del mismo grafo.

Como puedes ver, si un grafo es no dirigido, las matrices de adyacencia son simétricas. Por otro lado, si el grafo es dirigido, las matrices no son simétricas, pues un 1 sólo aparece en una celda si hay una arista desde el nodo de la fila hasta el nodo de la columna. Por ejemplo, la siguiente es la matriz de adyacencia de nuestro grafo de Twitter.

ABC
A011
B100
C010

Ejercicio

La función de Python mostrada se utiliza para obtener información sobre un grafo dado. El grafo se pasa a la función como una lista de adyacencia, y la función retorna el grado máximo de un nodo en el grafo, el número de ciclos en el grafo y un valor de tipo boolean indicando si el grafo tiene aristas paralelas o no.

Arregla la función para que devuelva la información deseada. Puese asumir que el grafo tendrá como máximo 5 nodos, numerados del 1 al 5.

La función debe devolver alguna información sobre un grafo dado. Corrígela para que lo haga correctamente.

Finalización

¡Felicidades! Ahora conoces algunos conceptos fundamentales de teoría de grafos. Ahora, puedes aprender más conceptos sobre los grafos, o empezar a aprender algoritmos útiles para aplicar. ¡La decisión es tuya!

Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io