Grafo Y Grafica

Antecedentes: El primer artículo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se basó en su artículo en el problema de los puentes de Königsberg. La ciudad de Kaliningrado, originalmente Königsberg, es famosa por sus siete puentes que unen ambas márgenes del río Pregel con dos de sus islas. Dos de los puentes unen la isla mayor con la margen oriental y otros dos con la margen occidental. La isla menor está conectada a cada margen por un puente y el séptimo puente une ambas islas. El problema planteaba lo siguiente: ¿es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo sólo una vez cada uno, y regresando al mismo punto de partida?

Abstrayendo este problema y planteándolo con la (entonces aún básica) teoría de grafos, Euler consigue demostrar que el grafo asociado al esquema de puentes de Königsberg no tiene solución, es decir, no es posible regresar al vértice de partida sin pasar por alguna arista dos veces.De hecho, Euler resuelve el problema más general: ¿qué condiciones debe satisfacer un grafo para garantizar que se puede regresar al vértice de partida sin pasar por la misma arista más de una vez? Si definimos como "grado" al número de líneas que se encuentran en un punto de un grafo, entonces la respuesta al problema es que los puentes de un pueblo se pueden atravesar exactamente una vez si, salvo a lo sumo dos, todos los puntos tienen un grado par.

Desarrollo: Grafo

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

Grafica

Un gráfico o una representación

...