Un plano de metro es un grafo
Un grafo es un conjunto de puntos, llamados vértices, unidos por líneas, llamadas aristas. Sirve para describir una red de metro, de amistades o de ordenadores y para preguntar si puedes llegar de un punto a otro.
Una ciudad cierra una estación y la gente se pregunta si todavía se puede ir del hospital a la universidad. Un grafo responde con precisión.
Al final de esta lección
Nota
Puedo describir una red como un grafo y decidir si hay un camino entre dos vértices.
Palabras clave
| Palabra | Qué significa |
|---|---|
| Vértice | un punto del grafo, como una estación |
| Arista | una línea que une dos vértices |
| Grado | el número de aristas de un vértice |
| Camino | una sucesión de vértices unidos por aristas |
| Conexo | un grafo donde hay camino entre cualquier pareja de vértices |
| Árbol | un grafo conexo y sin ciclos |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un grafo son vértices y aristas
En el plano de una red hay cuatro estaciones, los vértices: Plaza, Norte, Campus y Hospital. Cada tramo de línea entre dos estaciones es una arista.
El grado de un vértice cuenta sus aristas. Plaza tiene dos tramos, a Norte y a Campus, así que su grado es 2.
Ejemplo resuelto: el grado de cada estación
| Vértice | Vecinos | Grado |
|---|---|---|
| Plaza | Norte, Campus | 2 |
| Norte | Plaza, Campus | 2 |
| Campus | Plaza, Norte, Hospital | 3 |
| Hospital | Campus | 1 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Python calcula los grados
python3 -c "red = {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B', 'D'], 'D': ['C']}; print([len(red[n]) for n in red], sum([len(red[n]) for n in red]) // 2)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un camino va de arista en arista
Un camino es una sucesión de vértices en la que cada pareja seguida está unida por una arista. De Norte a Hospital hay uno: Norte, Campus, Hospital.
Un grafo es conexo si hay camino entre cualquier pareja de vértices. Si una estación queda aislada, la red no es conexa.
Qué estaciones alcanzas desde Plaza
red = {"Plaza": ["Norte", "Campus"], "Norte": ["Plaza"], "Campus": ["Plaza", "Hospital"],
"Hospital": ["Campus"], "Puerto": []}
por_visitar = ["Plaza"]
visitadas = []
while len(por_visitar) > 0:
estacion = por_visitar.pop()
if estacion not in visitadas:
visitadas.append(estacion)
for vecina in red[estacion]:
por_visitar.append(vecina)
# Puerto no aparece: nadie lo une con el resto.
print("Se llega a:", visitadas)
print("Hay camino a Puerto:", "Puerto" in visitadas)
Un error frecuente
Advertencia
Mucha gente cree que un grafo conexo es uno donde cada vértice se une con todos los demás. No es así. Conexo solo pide que exista algún camino entre cada pareja, aunque pase por varias aristas.
Un árbol es un grafo conexo sin ciclos
Un ciclo es un camino que vuelve al vértice de salida sin repetir aristas. Un árbol es un grafo conexo que no tiene ciclos.
Un árbol con n vértices tiene siempre n − 1 aristas. Con 5 vértices, 4 aristas. Una arista más crea un ciclo, y una menos deja un vértice aislado.
Ejemplo resuelto: ¿es un árbol?
| Grafo | Vértices | Aristas | Conexo | Árbol |
|---|---|---|---|---|
| Cadena de 4 estaciones | 4 | 3 | Sí | Sí |
| Triángulo de 3 estaciones | 3 | 3 | Sí | No, tiene un ciclo |
| Dos parejas separadas | 4 | 2 | No | No |
| Una estación y tres ramales | 4 | 3 | Sí | Sí |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un árbol de 5 vértices
python3 -c "arbol = {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A'], 'D': ['B'], 'E': ['B']}; print(len(arbol), sum([len(v) for v in arbol.values()]) // 2)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.