Leer un grafo dirigido y separar grado de salida y de entrada.
Reconocer un árbol: conexo, sin ciclos, E = V − 1.
Decir qué añade un peso o una flecha respecto de un grafo simple.
El mismo dibujo no significa siempre lo mismo
Un grafo es un conjunto de vértices y un conjunto de relaciones entre ellos. Si la relación tiene dirección, hablamos de grafo dirigido y dibujamos flechas: el arco A→B no es el arco B→A. Si la relación no tiene dirección, una sola arista vale para los dos extremos.
grado de salida = flechas que salen · grado de entrada = flechas que llegan · árbol = grafo conexo y sin ciclos · en un árbol E = V − 1 · ponderado = cada arista lleva un número (distancia, tiempo, coste) · plano = se puede dibujar sin cruces; el cruce de dos trazos no es un vértice
En el ejemplo de la izquierda hay 3 vértices y 4 arcos. De A salen dos flechas (a B y a C), así que su grado de salida es 2. A C llegan dos (desde B y desde A), grado de entrada 2. Esa cuenta no se puede hacer en el árbol de la derecha, porque allí no hay flechas: cada arista suma 1 al grado de sus dos extremos y no hay «salida» distinta de la «entrada».
El árbol tiene V = 4 y E = 3. Es conexo (se puede ir de cualquier vértice a cualquier otro) y no contiene un ciclo: si quitas una arista, dejas de poder conectar los dos lados. Un ciclo, como el triángulo A→B→C→A de la izquierda, es justo lo que un árbol prohíbe.
Grafo dirigido del ejemplo
Árbol de la derecha
Vértices
3 (A, B, C)
4
Aristas o arcos
4 arcos
3 aristas
¿Ciclo?
sí, A-B-C-A
no
Relación E y V
E = 4, V − 1 = 2
E = V − 1
Gráfico del ejemplo
La figura no es decoración: los trazos corresponden a los números del ejemplo 1.
Ejemplo resuelto 1 — Grados con flecha
En el grafo dirigido del gráfico, calcula el grado de salida y el de entrada de A, B y C.
Arcos: A→B, B→C, C→A y A→C. Léelos en las flechas, no inventes B→A.Glosa: la flecha verde A→C es un arco más, no la misma relación que C→A.
Salida: A manda a B y a C (2); B solo a C (1); C solo a A (1).Glosa: el grado de salida cuenta arcos cuyo origen es ese vértice.
Entrada: a A solo llega C (1); a B solo llega A (1); a C llegan B y A (2).Glosa: entrada y salida no tienen por qué coincidir. En A, 2 de salida y 1 de entrada.
Comprueba la suma: salidas 2+1+1 = 4 y entradas 1+1+2 = 4. Las dos sumas valen el número de arcos.Glosa: cada arco aporta 1 a una salida y 1 a una entrada. Si no cuadra, falta una flecha.
Ejemplo resuelto 2 — El árbol no es un detalle
Comprueba que la figura de la derecha es un árbol y que le sobra o le falta algo si añades una arista entre las dos hojas superiores.
V = 4, E = 3 y E = V − 1. Está conectado: desde el vértice central se llega a los otros tres.Glosa: E = V − 1 es necesario en un grafo conexo, y junto con la conexión evita ciclos.
No hay ciclo: no puedes volver al punto de partida sin repetir una arista.Glosa: un ciclo necesitaría al menos tres vértices unidos en redondo, y aquí no se cierra.
Si unes las dos hojas de arriba, añades una arista: E = 4 y V − 1 = 3. Aparece un triángulo y deja de ser árbol.Glosa: esa arista de más crea exactamente un ciclo y rompe la igualdad E = V − 1.
Sigue siendo conexo, pero ya no es árbol. Conexo y árbol no son sinónimos.Glosa: el ciclo dirigido de la izquierda también es conexo en su sentido, y tampoco es un árbol.
Ejemplo resuelto 3 — Qué falta para otros tipos
Di qué habría que añadir al árbol para que fuera ponderado y qué habría que exigir para llamarlo plano. ¿El dirigido de la izquierda es plano?
Ponderado: un número en cada arista (por ejemplo minutos). El dibujo actual no trae números, luego no está ponderado.Glosa: el peso no es el grado. El grado se calcula; el peso se declara.
Plano: que exista un dibujo sin cruces. El árbol de la derecha ya está dibujado sin cruces, así que es plano.Glosa: plano no significa «dibujado en horizontal»; significa «sin cruces forzados».
El dirigido también está dibujado sin que las flechas se crucen en un punto que no sea vértice. Es plano.Glosa: que A→C y el lado B-C se toquen en C no es un cruce: C es un vértice.
Un cruce de verdad aparecería si dos arcos se cortaran por el medio y ese corte no fuera un vértice del grafo. Aquí no ocurre.Glosa: en la lección siguiente un grafo no plano no se puede salvar cambiando el dibujo.
Ejercicios
Escribe el razonamiento completo en el editor, no solo la cifra. Si el enunciado pide figura, dibújala en el lienzo de esta misma página.
1. Suma de arcos
Un dirigido tiene suma de grados de salida 7. ¿Cuántos arcos tiene? ¿Cuánto suma la entrada?
Por qué (abre cuando hayas escrito)
Cada arco cuenta una vez en la salida de su origen, así que hay 7 arcos. La suma de los grados de entrada también es 7, porque ese mismo arco cuenta una vez en el destino. El paso es no dividir entre 2: esa división era del grafo no dirigido, donde cada arista suma a dos grados indistintos. Aquí entrada y salida ya separan los dos papeles, y cada suma, por sí sola, vale E. Si te dieran solo grados sin decir si son de salida, no podrías aplicar esta lectura.
2. ¿Árbol?
V = 6 y E = 5, conexo y sin ciclos. ¿Es un árbol? ¿Y si te dicen que tiene un ciclo?
Por qué (abre cuando hayas escrito)
E = V − 1 = 5 y, además, conexo y sin ciclos: es un árbol. Las tres condiciones van juntas en la definición que usamos; la igualdad E = V − 1 en un grafo conexo ya impide el ciclo. Si te dicen que tiene un ciclo, entonces no es árbol, y además no puede cumplir a la vez ser conexo y E = V − 1: un ciclo obliga a tener al menos una arista de más. El paso es no quedarte solo con el dibujo «parece un árbol» si el enunciado trae un ciclo.
3. Flecha inversa
En el ejemplo, ¿está el arco B→A? ¿Qué grado de salida de B cambiaría si lo añadieras?
Por qué (abre cuando hayas escrito)
No está: la flecha entre A y B apunta a B, no a A. Añadir B→A sería un arco nuevo. El grado de salida de B pasaría de 1 a 2, y el de entrada de A pasaría de 1 a 2. El paso es mirar la punta de la flecha, no el segmento. En un no dirigido esa pregunta no existiría: una sola arista AB serviría para los dos. Por eso el dirigido de la izquierda y un triángulo sin flechas no guardan la misma información aunque el «dibujo de líneas» se parezca.
Dibuja en el lienzo
Reproduce a mano el gráfico del ejemplo: ejes o nodos, los datos numéricos y una frase con la conclusión. El botón borra el lienzo sin salir de la lección.
Tres preguntas. Responde mentalmente antes de abrir el porqué.
¿Cuántos arcos salen de A en el gráfico?
Dos: A→B y A→C. Por qué: se ven dos flechas con origen en A. El arco C→A llega a A, así que cuenta como entrada, no como salida. Mezclarlas daría grado 3 y la suma de salidas dejaría de valer 4.
¿Por qué el de la derecha es un árbol?
Porque es conexo, no tiene ciclos y E = V − 1 (3 = 4 − 1). Por qué: con esas condiciones no sobra ni falta ninguna arista para unir los vértices. Si faltara una, quedaría desconectado; si sobrara una, aparecería un ciclo.
¿Un grafo ponderado es lo mismo que un grafo con grados?
No. Por qué: el peso es un dato escrito en la arista (distancia, coste). El grado es un recuento de aristas incidentes. El árbol del gráfico tiene grados pero no tiene pesos: no es ponderado hasta que alguien asigne números a las aristas.
Reto Profesor
Un mapa con flechas
Dibuja en el lienzo tres lugares de tu barrio y flechas de «puedo ir andando en ese sentido». Anota grados de salida.