Introducción
- Autor:
- Rafael Losada Liste
- Tema:
- Construcciones, Diagramas
Grafos bipartitos completos
En un grafo completo, todo vértice se conecta a todos los demás. Si previamente dividimos los vértices en dos grupos (como si estuviesen enfrentados), podemos pensar en el grafo que conecta cada vértice de un grupo con todos los vértices del otro grupo. Un grafo así se denomina bipartito completo.
Un ejemplo muy conocido de este tipo de grafos es el que plantea el famoso problema de las tres casas y los tres servicios (K3,3). Se trata de conectar tres casas con tres fuentes de suministros (agua, luz y gas), sin que las conexiones se entrecrucen. En la ampliación de la actividad 4 del cuadernillo de actividades "La tela de araña" verás un razonamiento que demuestra que tal grafo no es posible en el plano, pero sí en otras superficies (puedes intentarlo en las hojas de ejercicios).
![[center][/center]](https://beta.geogebra.org/resource/yzj8f6fd/5iDpANcT4ZK0ZbxQ/material-yzj8f6fd.png)
En el apartado anterior, tal vez hayas llegado a la conclusión correcta de que un grafo completo de n vértices (Kn) tiene siempre n(n-1)/2 aristas. ¿Sabrías ahora averiguar cuántas aristas tiene un grafo bipartito completo Kn,m de "n" vértices de un grupo conectados con todos los "m" vértices de otro grupo? Por ejemplo, K3,3 tiene 9 aristas.
Matriz de adyacencia
La información recogida en un grafo también se puede expresar mediante números, lo que facilita los cálculos computacionales en grandes redes. Por ejemplo, la información del grafo de los puentes de Königsberg puede recogerse en una matriz, llamada matriz de adyacencia.
![[center][/center]](https://beta.geogebra.org/resource/trsh46vj/CffaSsITZyz6MpAL/material-trsh46vj.png)
Cada fila de la matriz representa el número de aristas que comparte un vértice con cada uno de los vértices. La suma de todos los números de una fila es el grado del vértice correspondiente.
Nota: Observa que la matriz es simétrica, ya que si una arista conecta A con B, también conecta B con A. Sin embargo, hay grafos (llamados grafos dirigidos) en donde cada arista tiene una orientación, de modo que A puede conectar con B pero no al revés. En ese caso, la matriz de adyacencia no será simétrica.