GRAFOS


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”.

Grafos
Este hecho es el que determina, por ejemplo, que hoy díautilicemos 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 seencarga 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 comonodos 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 fuerealizado 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 lograunir 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 tieneconexió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.


Vértices y aristas de un grafo
Generalmente, un grafo es dibujado en formatal que cada vértice esta representado por un punto (letra mayúscula) en el plano y cada arista por una curva que une los vértices(letra minúscula).
Dos vértices son adyacentes si son extremos de una misma arista
Una arista que unes un vértice consigo mismo se denomina a un bucle, en este ejemplo:
Consideremos como ejemplo un mapa de ciudades (los vértices) y las rutas (las aristas) que unendichas ciudades

Tipos de grafos

Se dice que el grafo G = (V, E) es
a)      un grafo regular de grado n si todos sus vértices tienen grado n.

Grafos regulares de grado 2.

Grafos regulares de grado 3.
b)      un grafo completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices

c)      un ciclo si V = {v1, v2, . . . vn},  n 3, y  E = {(v1, v2),...