Definición de grafos
Muy importante es determinar, antes del análisis del término grafos, el origen etimológico del mismo pues nos permitirá conocer de primera mano el porqué de su significado actual. De esta manera podemos dejar patente que aquel emana de la palabra griega grafo, graphein, que puede traducirse como “grabar o escribir”.
Este hecho es el que determina, por ejemplo, que hoy día utilicemos dicho concepto como parte indisoluble de otros términos a los que les da ese citado significado que está relacionado con la escritura. Este sería el ejemplo de bolígrafo que es un instrumento que utilizamos para escribir, grafólogo que es aquella persona que se dedica a determinar las cualidades psicológicas de alguien a través de la escritura que realiza, o el polígrafo que es quien se encarga de estudiar diversas formas de escribir que se llevan a cabo de forma secreta.
En la lingüística, un grafo es un objeto unitario de naturaleza abstracta que abarca a las grafias que componen una letra. La palabra tiene origen griego y significa “imagen” o “dibujo”.
Para las ciencias de la computación y la matemática, un grafo es una representación gráfica de diversos puntos que se conocen como nodos o vértices, los cuales se encuentran unidos a través de líneas que reciben el nombre de aristas. Al analizar los grafos, los expertos logran conocer cómo se desarrollan las relaciones recíprocas entre aquellas unidades que mantienen algún tipo de interacción.
En este sentido no podemos pasar por alto el hecho de que el primer documento escrito que tenemos acerca de lo que son los grafos fue realizado en el siglo XVIII, y más concretamente en el año 1736, por Leonhard Euler. Este fue un matemático y físico, de origen suizo, que destacó por ser una de las figuras más importantes de su tiempo en la citada materia.
En concreto dicho autor realizó un artículo basándose en los puentes que existen en la ciudad de Kaliningrado. A partir de ellos, y mediante lo que es la teoría de los grafos, desarrolló una exposición acerca de los grafos y los vértices que se sustenta en el hecho de que es imposible regresar al vértice que ejerce como punto de partida sin antes no pasar por alguna de las aristas en dos ocasiones.
Los grafos pueden ser clasificarse de diversas maneras según sus características. Los grafos simples, en este sentido, son aquellos que surgen cuando una única arista logra unir dos vértices. Los grafos complejos, en cambio, presentan más de una arista en unión con los vértices.
Por otra parte, un grafo es conexo si dispone de dos vértices conectados a través de un camino. ¿Qué quiere decir esto? Que, para el par de vértices (p, r), tiene que existir algún camino que permita llegar desde p hasta r.
En cambio, un grafo es fuertemente conexo si el par de vértices tiene conexión a través de, como mínimo, dos caminos diferentes.
Un grafo simple, además, puede ser completo si las aristas están en condiciones de unir todos los pares de vértices, mientras que un grafo es bipartito si sus vértices surgen por la unión de un par de conjuntos de vértices y si se cumple una serie de condiciones.