Fundamentos de teoría de grafos [esp|eng]

Racso
2,400 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content
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.
1
2
3
4
5
def get_graph_info(adj_list):
#adj_list es la lista de adyacencia de un grafo. Es una lista de listas, donde cada elemento es un par de nodos conectados por una arista.
#Por ejemplo, si adj_list=[[0,1],[2,3],[4,3]], tenemos tres aristas: una contectando los nodos 0 y 1, otra conectando los nodos 2 y 3, y una conectando los nodos 4 y 3.
return 2, 0, False #arreglar: para el grafo dado, retornar: el máximo grafo de los nodos, el número de ciclos, un booleano representando si hay aristas paralelas o no.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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!

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content