1º Bach Matemáticas Generales · CyL Decreto 40/2022 · A.2 Matrices como herramienta en tablas y grafos
Objetivos
Construir la matriz de adyacencia de un grafo sin lazos.
Leer grados y el número de aristas desde la matriz.
Contar caminos de longitud 2 con el producto de la matriz por sí misma.
Del dibujo a la tabla, sin perder aristas
Un grafo pequeño se puede mirar. En cuanto crece, conviene una matriz: filas y columnas con los mismos vértices, y un 1 en la casilla (i, j) si hay arista entre ellos. En un grafo no dirigido esa tabla es simétrica: la arista AB se anota arriba y abajo de la diagonal.
vértice = punto del grafo · arista = trazo que une dos vértices · lazo = arista de un vértice a sí mismo, que aquí no hay · grado de un vértice = número de aristas que inciden en él · E = número de aristas
En el ejemplo hay vértices A, B, C y D. Las aristas dibujadas son AB, BC, CA y AD. No hay BD, ni CD, ni lazos. Por eso la diagonal de la matriz es 0, 0, 0, 0 y las casillas BD, DB, CD y DC también son 0. El grado de A es 3 (llega a B, a C y a D) y la primera fila suma 3.
Sumar todos los grados cuenta cada arista dos veces, una por cada extremo. Aquí 3 + 2 = 5
5 + 2 = 7
7 + 1 = 8 = 2E, luego E = 4, que son las cuatro líneas del dibujo. Multiplicar la matriz por sí misma no dibuja aristas nuevas: la casilla (A, C) de M² cuenta caminos de dos pasos desde A hasta C.
Vértice
Vecinos en el dibujo
Grado
Suma de su fila
A
B, C, D
3
0 + 1 = 1
1 + 1 = 2
2 + 1 = 3
B
A, C
2
1 + 0 = 1
1 + 1 = 2
2 + 0 = 2
C
A, B
2
1 + 1 = 2
2 + 0 = 2
2 + 0 = 2
D
A
1
1 + 0 = 1
1 + 0 = 1
1 + 0 = 1
Gráfico del ejemplo
La figura no es decoración: los trazos corresponden a los números del ejemplo 1.
Ejemplo resuelto 1 — De las líneas a los unos
Escribe la matriz de adyacencia del grafo dibujado, en el orden A, B, C, D, y justifica la simetría.
Lista las aristas del dibujo: AB, BC, CA y AD. Son cuatro. No inventes BD ni CD: no hay trazo.Glosa: cada segmento del SVG es una arista; la diagonal del triángulo es CA, no un adorno.
Coloca un 1 en (A,B), (B,A), (B,C), (C,B), (C,A), (A,C), (A,D) y (D,A). El resto, ceros.Glosa: al ser no dirigido, cada arista escribe dos unos, salvo que fuera un lazo.
La diagonal queda a cero porque ningún vértice está unido consigo mismo.Glosa: un lazo se vería como un bucle en el dibujo y un 1 en la diagonal; aquí no aparece.
Comprueba la simetría: la casilla (fila i, columna j) coincide con (fila j, columna i). Si no, te falta uno de los dos sentidos de la misma arista.Glosa: en un grafo dirigido la matriz puede dejar de ser simétrica; este dibujo no tiene flechas.
Ejemplo resuelto 2 — Grados y doble conteo
Calcula el grado de cada vértice sumando filas y deduce E.
Suma la fila A: 3. Fila B: 2. Fila C: 2. Fila D: 1. Esos son los grados.Glosa: el grado no es el número de vértices vecinos «a ojo» si hay lazos; aquí, al no haberlos, coincide con la suma de la fila.
Suma de grado3 + 2 = 5
5 + 2 = 7
7 + 1 = 8
s = 8.Glosa: 8 no es el número de aristas. Cada arista aporta a dos grados.
Por el lema del apretón de manos, suma de grados = 2E. Entonces 2E = 8 y E = 4.Glosa: divide entre 2 al final, no al principio. Si divides cada grado, pierdes el sentido del doble conteo.
Comprueba contando segmentos en el SVG: AB, BC, CA, AD. Cuatro. Cuadra con E = 4.Glosa: si la matriz y el dibujo no dan el mismo E, hay un 1 de más o un trazo sin casilla.
Ejemplo resuelto 3 — Caminos de dos pasos
Calcula la casilla (A, C) de M² y nombra el único camino de longitud 2 de A a C.
La casilla (A, C) de M² es el producto de la fila A por la columna C: (0, 1, 1, 1) · (1, 1, 0, 0).Glosa: fila A es 0,1,1,1 y columna C es 1,1,0,0 porque la matriz es simétrica y la columna C copia la fila C.
0 · 1 = 0
1 · 1 = 1
0 + 1 = 1
1 · 0 = 0
1 + 0 = 1
1 · 0 = 0
1 + 0 = 1.Glosa: el único sumando no nulo es el de la columna B: se sale de A hacia B y desde B se puede seguir a C.
Ese 1 es el camino A-B-C. A-C-C no existe (no hay lazo) y A-D-C tampoco (D no toca a C).Glosa: A-C es un camino de longitud 1, no de longitud 2; M² no lo cuenta.
Comprueba que hay arista A-B y arista B-C en el dibujo. Las dos hacen falta. Una sola no crea camino de dos pasos.Glosa: por eso el producto mira parejas de aristas encadenadas, no aristas sueltas.
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. Un cero que importa
Alguien pone un 1 en la casilla (B, D) «porque B y D están en el grafo». ¿Qué afirma de más y cómo se ve en el dibujo?
Por qué (abre cuando hayas escrito)
Un 1 en (B, D) afirmaría que existe la arista BD. En el dibujo B está unido a A y a C, y D solo a A: no hay segmento BD. El paso erróneo confunde «pertenecer al mismo grafo» con «estar unidos». La matriz solo registra adyacencia, no convivencia. Si aceptaras ese 1, el grado de B pasaría de 2 a 3, la suma de grados subiría en 2 (también el 1 simétrico en D,B) y E pasaría de 4 a 5, en contradicción con los cuatro segmentos visibles.
2. ¿Por qué la diagonal es cero?
Explica, con este grafo concreto, qué significaría un 1 en la casilla (C, C) y por qué no debe ponerse.
Por qué (abre cuando hayas escrito)
La casilla (C, C) es la intersección de la fila C con la columna C. Un 1 diría que C tiene un lazo, una arista con los dos extremos en C. El grado de C contaría ese lazo según el convenio del curso (aquí no usamos lazos, así que la diagonal se queda en 0). En el SVG no hay ningún bucle sobre el círculo C: sus únicos trazos van a A y a B. Poner el 1 copiaría un dato que el dibujo no contiene y rompería la lectura «unos = segmentos que se ven».
3. Otro camino
¿Cuántos caminos de longitud 2 hay de A a A? Relaciónalos con el grado de A sin multiplicar la matriz entera.
Por qué (abre cuando hayas escrito)
Un camino de longitud 2 que empieza y acaba en A es salir por una arista y volver por la misma, porque los vecinos de A no están unidos entre sí de forma que cierren otro ciclo de dos (un ciclo de dos no existe en un grafo simple). Desde A se puede ir a B y volver, a C y volver, o a D y volver: tres paseos. Coincide con el grado de A. El paso es emparejar cada arista incidente con su vuelta inmediata. Si el grafo tuviera un triángulo que vuelva a A en dos pasos por vecinos distintos, habría que contarlos aparte; aquí los vecinos B, C y D no se conectan todos entre sí en un triángulo que incluya solo dos pasos distintos de la ida y vuelta. El triángulo es A-B-C-A, que es longitud 3. Por eso los retornos de longitud 2 son exactamente las tres idas y vueltas, y la casilla (A, A) de M² vale 3.
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.
Comprueba
Tres preguntas. Responde mentalmente antes de abrir el porqué.
¿Qué significa el 1 de la fila B, columna C?
Que la arista BC está en el grafo, la misma que el segmento vertical del dibujo. Por qué: la fila elige el extremo B y la columna el extremo C. El 1 no es una distancia ni un peso: en esta lección solo dice si la arista existe. El peso llegará en grafos ponderados.
¿Por qué dividimos entre 2 la suma de los grados?
Porque cada arista se ha contado en los dos extremos. Por qué: AB suma 1 al grado de A y 1 al de B. Si no divides, obtienes 8, que es el doble de las cuatro aristas. La fórmula suma de grados = 2E obliga a ese paso final.
¿Un camino de longitud 1 aparece en M²?
No. Por qué: M² combina dos aristas seguidas. La arista CA es un camino de longitud 1 y vive en la propia matriz M, casilla (C, A), no en el cuadrado. Confundirlas mezcla «estar unidos» con «llegar en dos saltos».
Reto Profesor
Matriz de un plano
Dibuja en el lienzo cuatro lugares de tu instituto y las conexiones que usas. Escribe la matriz 4×4 y la suma de grados.