Teoría de grafos · Definición

Grafo

matemáticas discretasgrafos

Es el modelo más sencillo de una red: cosas y conexiones entre ellas, sin importar la geometría del dibujo.

Definición

Un grafo \(G\) es un conjunto \(V\) de vértices junto con un conjunto \(E\) de aristas, cada una formada por dos vértices distintos.

\[G=(V,E),\qquad E\subseteq\{\{u,v\}:\ u,v\in V,\ u\neq v\}\]

Un grafo sirve para representar mapas de carreteras, redes sociales, circuitos o dependencias entre tareas. Los vértices son los objetos y una arista \(\{u,v\}\) indica que \(u\) y \(v\) están relacionados. Como la arista es un par no ordenado, la conexión es simétrica: \(\{u,v\}=\{v,u\}\). Cuando importa la dirección se habla de grafos dirigidos, que se estudian aparte.

La definición de arriba corresponde al grafo simple: no hay lazos (aristas de un vértice a sí mismo) ni aristas repetidas entre los mismos vértices. Con \(n\) vértices caben a lo sumo \(n(n-1)/2\) aristas; el grafo que las tiene todas se llama completo y se escribe \(K_n\). Otros textos permiten lazos y aristas múltiples y los llaman multigrafos.

Lo único que cuenta es qué vértices están unidos, no cómo se dibuja. Dos dibujos distintos pueden representar el mismo grafo, y un vértice sin ninguna arista, llamado aislado, sigue siendo parte del grafo. Esto contrasta con el diagrama de Hasse, donde la altura sí comunica el orden.

Con este concepto se construye el resto de la teoría: el grado de un vértice, los caminos, la conexidad, los árboles y los ciclos, que aparecerán en los siguientes conceptos del tema.

Para pensar

¿Cuántos grafos simples distintos hay sobre \(n\) vértices etiquetados?

Cada uno de los \(n(n-1)/2\) pares posibles está o no está, así que hay \(2^{n(n-1)/2}\).

Ejercicios 10

  1. ¿Cuál es el mayor número de aristas de un grafo simple con \(5\) vértices?
  2. Un grafo tiene \(V=\{1,2,3,4\}\) y aristas \(12,\ 23,\ 34,\ 41,\ 13\). ¿Cuántos pares de vértices distintos no están unidos?
  3. ¿Cuál de estos conjuntos de aristas no puede pertenecer a un grafo simple sobre \(\{a,b,c\}\)?
  4. ¿Cuál afirmación es verdadera en un grafo simple?
  5. ¿Cuántos grafos distintos se pueden formar sobre los vértices etiquetados \(\{1,2,3\}\)?
  6. ¿Cuántas aristas faltan en un grafo simple con \(6\) vértices y \(9\) aristas para tener todas las posibles?
  7. Un grafo simple con \(n\) vértices tiene \(45\) aristas y todas las posibles. ¿Cuánto vale \(n\)?
  8. ¿Para cuál pareja (vértices, aristas) existe un grafo simple?
  9. ¿Cuántos grafos simples sobre los vértices etiquetados \(\{1,2,3,4\}\) tienen exactamente \(5\) aristas?
  10. ¿Cuántos grafos simples con vértices etiquetados \(\{1,2,3,4\}\) hay en total?

Referencias

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §10.1
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §10.1
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §11.1