Una introducción gentil a la teoría de Grafos: Parte 1
En mi camino a aprender matemáticas puras
Prerrequisitos
Muchas áreas de la matemática definen sus elementos básicos a través de la teoría de conjuntos. Por el momento, lo único que deberías saber es la respuesta a las siguientes preguntas:
- Qué es un conjunto?
- Qué es un subconjunto?
Definición de un Grafo
Un grafo se define por dos conjuntos:
- Un conjunto de vértices o nodos que no puede ser vacío y que tiene una cantidad finita de elementos, es decir, que se pueden contar y llegar a un número final.
- Un conjunto de enlaces llamados aristas que contiene subconjuntos con pares de los elementos del conjunto vértices. Este puede estar vacío, en ese caso, la representación gráfica son puntos en el plano (Con el plano me refiero a una hoja de papel o cualquier superficie donde se vaya a dibujar).
Nota: Por efecto de Medium, los subíndices se pintarán como superíndices, pero la convención es que se usen subíndices en los nombres de los grafos.
Ejemplo:
Este grafo llamado K³ se define de la siguiente manera:
- v = { A, B, C }
- e = { { A, C }, { B, A }, { B, C } }
Donde v es el conjunto de vértices y e es conjunto de aristas.
Listo, ya sabes qué es un grafo y cómo se define formalmente.
Algunos Grafos Comunes
A continuación voy a mostrar una lista de grafos comunes:
- Grafo cíclico: Son los grafos que empiezan en un vértice y te puedes desplazar de vértice en vértice hasta llegar al punto inicial sin repetir ninguno vértice (a excepción del inicial claramente). En otras palabras, que parecen una rueda. El nombre de los grafos cíclicos es la letra C de (cyclic) y el subíndice es el número de vértices.
2. Grafo nulo: Son los grafos cuyo conjunto de aristas es vacío. Es decir, que ningún vértice se conecta con otro. Los grafos nulos se nombran con la letra N de (null) y el subíndice es el número de vértices.
3. Grafo Completo: Son los grafos cuyo conjunto de aristas contiene todos los pares posibles de vértices. Es decir, que cada vértice se conecta con todos los demás. Los grafos completos se nombran con la letra K y el subíndice es el número de vértices.
Así hay muchos grafos que suelen pertenecer a familias que tienen la misma propiedad. Los grafos estrella tienen un vértices al que todos los demás se conectan y nada mas, los grafos camino son aquellos que tienen una arista inicial y una final y se conectan formando un camino sin repetir arista (es como el cíclico sin la conexión entre el final y el inicial). Hay muchas de estas familias.
Complemento de un grafo
El complemento de un grafo es aquel grafo que contiene las aristas necesarias para formar el grafo completo.
En la figura anterior se ve el grafo C⁵ y a la derecha su complemento. Nótese que el nombre del complemento es C⁵ con una barra encima. Si se unen ambos grafos el resultante sería el grafo K⁵.
Subgrafo
Un grafo H es subgrafo de un grafo G si el conjunto de vértices de H es un subconjunto del conjunto de vértices de G. Y el conjunto de aristas de H es un subconjunto del conjunto de aristas de G. En otras palabras, si tengo un grafo y quito algunos vértices y quito algunas aristas, el grafo resultante es un subgrafo del inicial.
Importante: Hay una regla estricta para “eliminar” aristas y vértices. Si quitas un vértice, debes quitar todas las aristas que se conectaban a ese vértice, no pueden quedar aristas sin vértices en los extremos. Pero, si pueden quedar vértices sin conexión con otros vértices.
Dejaremos la introducción en este punto, hemos aprendido
- Que es un grafo
- Algunos grafos comunes
- Que es un grafo complementario
- Que es un subgrafo
