Un grafo permite estudiar quién está conectado con quién. Puede representar estaciones, tareas, páginas o personas, pero primero hay que decidir qué significa cada punto y cada enlace. Empezaremos leyendo una red pequeña y después construiremos sus grados, sus tablas y sus recorridos.
1. Los vértices son elementos; las aristas son conexiones directas
En el dibujo, A, B, C y D son cuatro estaciones imaginarias. Una línea entre dos significa que existe un enlace directo. Los puntos se llaman vértices y las líneas, aristas. El grafo guarda esas incidencias, no necesariamente la forma física o longitud de una carretera.
AB y BA nombran la misma arista. Simple significa que no hay lazos ni conexiones repetidas entre el mismo par.
Una conexión directa o un recorrido de varios pasos
¿Se puede ir de D a B en el dibujo? ¿Hay arista DB?
Lista de aristas
No aparece DB: no hay enlace directo.
Dos pasos
D está unido con A y A con B.
Recorrido
D−A−B permite llegar usando dos aristas.
Hay recorrido de D a B, pero no arista DB.
Estar conectado mediante varios pasos no convierte los extremos en vecinos directos.
Redibujar no cambia las incidencias
Si movemos B al otro lado del papel manteniendo las mismas cuatro aristas, ¿cambia el grafo etiquetado?
Datos que se conservan
Los mismos vértices y los mismos pares conectados.
Datos visuales que cambian
Posiciones y longitudes dibujadas.
Modelo
Esos últimos datos no eran parte del grafo sin pesos.
No cambia el grafo etiquetado.
No deducimos costes o distancias de una colocación elegida para que el dibujo sea claro.
2. Una flecha indica sentido y un peso añade un dato de coste
Una red dirigida usa arcos A→B con origen y destino.
Un peso añade un número a la conexión: minutos, kilómetros, euros u otra magnitud declarada. El peso puede no tener relación con lo largo que se dibuja el trazo.
Un multigrafo permite varias aristas entre el mismo par, como dos servicios distintos. Un lazo une un vértice consigo mismo. Son modelos válidos, pero sus reglas de conteo deben incluir esas posibilidades. Siempre indicamos si trabajamos con grafo simple, dirigido, ponderado o alguna combinación.
Respetar flechas
En el dibujo dirigido, compara A→C→D y D→C→A.
Primer recorrido
Los dos arcos A→C y C→D existen.Sentido contrario
No existe D→C; no podemos comenzar el segundo.Conclusión
La línea no autoriza recorrerla en ambos sentidos.
El primero es válido y el segundo no.
Para viajar en ambos sentidos hacen falta los dos arcos o declarar una arista no dirigida.
Dos servicios no se funden en uno
Entre P y Q hay dos servicios de duraciones 5 y 9 minutos. ¿Qué datos guardaría un multigrafo ponderado?
Vértices
P y Q.
Conexiones
Dos aristas distintas entre esos mismos vértices.
Pesos
Cinco y nueve minutos, uno para cada servicio.
Dos conexiones paralelas con pesos distintos.
Un grafo simple con un único peso perdería información salvo que definiéramos qué resumen queremos conservar.
3. El grado cuenta extremos de aristas en un vértice
En un grafo simple no dirigido, el grado d(v) es cuántas aristas llegan a v, igual al número de vecinos. Un vértice aislado tiene grado cero. Con conexiones paralelas las contamos por separado; un lazo cuenta dos porque sus dos extremos están en el mismo vértice.
Cada arista aporta dos al total de grados, de modo que la suma es 2m, donde m es el número de aristas. Por eso el total es par y la cantidad de vértices con grado impar también es par: solo esos sumandos pueden cambiar la paridad.
Contar en el grafo del inicio
Halla los grados de A,B,C,D con E={AB,AC,AD,BC}.
A
Inciden AB,AC,AD: grado tres.
B y C
B usa AB,BC; C usa AC,BC: grado dos cada uno.
D
Solo AD: grado uno.
Revisar
3+2+2+1=8=2·4.
Grados (3,2,2,1), cuatro aristas.
Los dos vértices impares son A y D: hay una cantidad par de ellos.
Un lazo tiene dos extremos en el mismo sitio
Hay dos aristas paralelas PQ y un lazo en P. Halla grados y recuento total.
P
Dos incidencias de las paralelas más dos del lazo: cuatro.
Q
Dos incidencias: grado dos.
Comprobar
Total seis; hay tres aristas y 2·3=6.
d(P)=4 y d(Q)=2.
P tiene un único vecino distinto de sí, pero su grado no es uno en este multigrafo.
4. En una red dirigida contamos por separado entradas y salidas
El grado de entrada cuenta los arcos que llegan; el de salida, los que parten. Una flecha tiene un origen y un destino: sumando entradas obtenemos m y sumando salidas también m. No usamos solo una lista de vecinos que oculte la dirección.
Un lazo dirigido aporta una entrada y una salida al mismo vértice. Un vértice con salida cero puede recibir tráfico y no permitir continuarlo. Estas cuentas resumen sentidos locales; para saber si se puede llegar lejos hay que seguir recorridos.
Una tabla de entradas y salidas
En A→B, A→C, B→C y C→D, cuenta para cada vértice.
A y B
A tiene entrada cero y salida dos; B una entrada y una salida.
C y D
C recibe dos y sale una; D recibe una y no sale.
Totales
Entradas 0+1+2+1=4; salidas 2+1+1+0=4.
Cuatro arcos, con ambos totales iguales a cuatro.
La suma conjunta sería ocho, pero perderíamos qué sentido corresponde a cada incidencia.
Añadir un lazo dirigido
Añade C→C a la red anterior.
Antes en C
Entrada dos y salida una.
Aporte del lazo
Una nueva entrada y una nueva salida.
Después
Entrada tres y salida dos; ahora hay cinco arcos.
En C: entrada tres, salida dos.
Cada total global aumenta en uno, no en dos; el total de ambos tipos juntos sí aumenta en dos.
5. Una lista y una matriz describen las mismas conexiones con otro orden
La lista de aristas enumera conexiones; la lista de adyacencia da los vecinos de cada vértice. En no dirigidos, cada arista aparece en las listas de sus dos extremos. La lista de vértices debe conservar los aislados, aunque no aparezcan en ninguna arista.
En una matriz de adyacencia fijamos un mismo orden para filas y columnas. La casilla (i,j) vale uno si hay conexión de i a j y cero si no. En un grafo simple no dirigido es simétrica, y sin lazos tiene diagonal cero. Para pesos necesitamos diferenciar conexión de peso cero y ausencia: por ejemplo usando un símbolo ∞ para la ausencia.
Del dibujo a las listas
Escribe vecinos del grafo inicial.
A
B,C,D.
B
A,C.
C y D
C: A,B; D: A.
Verificar
Las longitudes de las listas son los grados tres,dos,dos,uno.
A:{B,C,D}; B:{A,C}; C:{A,B}; D:{A}.
Cada una de las cuatro aristas aparece exactamente en dos listas.
Leer una matriz con el orden declarado
En la matriz del dibujo, con orden A,B,C,D, interpreta la casilla (2,3) y la (2,4).
Fila dos
Representa B.
Columna tres
Representa C; el uno indica arista BC.
Columna cuatro
Representa D; el cero indica que no hay BD.
BC existe y BD no existe.
Sin el orden de vértices, los índices numéricos no identifican nombres concretos.
Un aislado y un peso cero requieren conservar datos distintos
En una red con vértices P,Q,R, solo existe PQ con coste cero.
Lista completa
R sigue siendo un vértice aunque no aparezca en aristas.
Coste
PQ=0 es una conexión real y gratuita según el modelo.
Ausencia
PR y QR necesitan otro símbolo, como ∞, para no confundirlas con PQ.
Hay una conexión de peso cero y un vértice aislado.
Una tabla de pesos que usara cero para todo perdería la distinción.
6. Un recorrido sigue conexiones; un camino simple evita repetir vértices
Usaremos recorrido para una sucesión de vértices consecutivos unidos por conexiones admitidas, con posibles repeticiones. Camino simple no repite vértices. Ciclo simple vuelve al inicial sin repetir los demás; en un grafo simple no dirigido tiene al menos tres aristas.
Un grafo no dirigido es conexo si cualquier pareja puede unirse por un camino. Si no, se divide en componentes conexas. En dirigidos, fuertemente conexo exige caminos orientados entre cada pareja en ambos sentidos; débilmente conexo solo pide conexión al ignorar las flechas.
Clasificar recorridos del dibujo inicial
Compara D−A−B−C, A−B−C−A y A−B−A−D.
Primero
No repite vértices: camino simple.
Segundo
Vuelve a A y no repite B ni C: ciclo simple.
Tercero
Es recorrido válido, pero repite A y la arista AB: no es camino simple.
Camino simple, ciclo simple y recorrido con repeticiones.
A−B−A es cerrado, pero no un ciclo simple del grafo sin aristas paralelas.
Conexión débil no asegura poder volver
Clasifica la red dirigida A→B, A→C, B→C, C→D.
Ignorar sentidos
Todos los vértices quedan unidos en una componente.
Respetar sentidos
Desde D no hay salida hacia A.
Clasificar
Débilmente conexa, pero no fuertemente conexa.
Débilmente conexa y no fuertemente conexa.
Añadir un vértice E aislado separaría otra componente incluso al ignorar sentidos.
7. Un árbol conecta todo sin ciclos y deja un único camino simple
Un árbol es un grafo no dirigido conexo y sin ciclos. Entre dos vértices hay un único camino simple: si hubiera dos distintos, juntos permitirían formar un ciclo. Para n vértices tiene n−1 aristas; con un solo vértice necesita cero.
En un árbol finito con al menos dos vértices hay hojas, de grado uno: los extremos de un camino simple de longitud máxima deben serlo, pues en otro caso el camino podría extenderse o cerraría un ciclo. Quitar una hoja y su arista conserva un árbol; repetirlo resta un vértice y una arista cada vez.
Un bosque con n vértices y c componentes tiene n−c aristas.
Comprobar la estructura antes de usar la fórmula
Con V={A,B,C,D} y E={AB,AC,CD}, localiza el camino de B a D.
Recorrer
B−A−C−D.
Estructura
Conecta los cuatro y no hay ciclo: árbol.
Cuenta
Cuatro vértices, tres aristas. Quitar AC separa {A,B} de {C,D}.
Camino único B−A−C−D; es un árbol.
Añadir BD crearía el ciclo B−A−C−D−B.
La cuenta n−1 sola no demuestra que sea árbol
Compara un triángulo ABC junto con D aislado.
Cantidades
Cuatro vértices y tres aristas: cumple m=n−1.Fallo de conexión
D no se une al triángulo.
Fallo de aciclicidad
ABC es un ciclo.
No es árbol aunque tenga n−1 aristas.
En cambio, para un bosque con siete vértices y dos componentes, m=7−2=5, contando la estructura de cada árbol.
8. El dibujo no puede añadir datos que el modelo no contiene
Un cruce de trazos no es por sí solo un vértice: dos carreteras pueden pasar a distinta altura. La lista de vértices y conexiones decide si se puede cambiar de una a otra. Si añadimos una intersección real, debemos representarla explícitamente y actualizar las aristas.
Un grafo puede omitir horarios, capacidades o frecuencias. Si la pregunta depende de esos datos, hay que incorporarlos antes de calcular. Tampoco una lista de grados o un número total de aristas reconstruye necesariamente el grafo: son resúmenes que sirven para comprobar ciertas condiciones.
Dos puentes que se cruzan en el papel
En el último dibujo solo hay AB y CD. ¿Existe un recorrido de A a C?
Componente de A
Contiene A y B.
Otra componente
Contiene C y D.
Cruce
No hay vértice común declarado en la intersección.
No hay recorrido de A a C en este modelo.
Dibujar un punto nuevo y dividir los enlaces cambiaría el grafo y podría cambiar la respuesta.
Una suma de grados par no garantiza que exista cualquier lista
¿Puede un grafo simple de cuatro vértices tener grados (3,3,1,1)?
Control inicial
Suman ocho, un número par: pasa esa comprobación necesaria.
Los dos de grado tres
Cada uno debe conectarse con los otros tres vértices.
Consecuencia
Los dos vértices restantes recibirían al menos dos aristas cada uno, contradiciendo su grado uno.
No puede; la suma par no era una condición suficiente.
Un resumen puede descartar algunos errores sin demostrar que todo el modelo sea realizable.
Ahora lo resolvemos de principio a fin.
EJEMPLO RESUELTO 1
Grados
Grafo con aristas AB,AC,BC,CD. Halla grados y número de aristas.
Listar incidencias de A
AB y AC: grado dos.
Incidencias de B
AB y BC: grado dos.
Incidencias de C
AC, BC y CD: grado tres.
Incidencias de D
Solo CD: grado uno.
Contar aristas
AB,AC,BC,CD son cuatro conexiones distintas.
Comprobar por doble recuento
2+2+3+1=8=2·4.
Grados 2,2,3,1; 4 aristas.
8=2·4.
EJEMPLO RESUELTO 2
Árbol
Una red es un árbol con 9 estaciones. ¿Cuántas conexiones tiene?
Dato estructural
La red ya se declara árbol: conexa y sin ciclos.
Aplicar la relación
Un árbol con n vértices tiene n−1 aristas.
Sustituir
9−1=8 conexiones.Comprobar el significado
Añadir otra conexión entre vértices ya presentes cerraría un ciclo; quitar una de las ocho desconectaría la red.
8 conexiones.
Añadir una conexión más entre sus vértices crearía un ciclo.
Los símbolos que hemos usado
- G=(V,E)
- Grafo formado por el conjunto de vértices V y de aristas E.
- n=|V|
- Número de vértices de un grafo finito.
- m=|E|
- Número de aristas de un grafo finito.
- d(v)
- Grado de v, número de incidencias de aristas en ese vértice.
- Vecino
- Vértice conectado mediante una arista al vértice considerado.
- Componente conexa
- Conjunto maximal de vértices que pueden alcanzarse entre sí.
Ahora te toca a ti.
Tienes cinco ejercicios. Inténtalos; las pistas te ayudan si te atascas.
Practicar este tema →