Grafos

Grafos

Aplicación de los grafos al responder las 2 siguientes preguntas:
¿Cuántos sudokus hay? ¿Cuántas maneras hay de colorear los países de mapa mundi?

Antes de espantar a los posibles lectores de este artículo al mencionar la palabra "Matemáticas" recordemos que hay ramas de las Matemáticas, como la Matemática Discreta, que tienen aplicaciones directas en la vida cotidiana,constituyendo pero no limitándose también en parte de las bases de las ciencias de la computación.

A continuación veremos algunas de las situaciones de la vida diaria en las cuales se pueden usar las matemáticas discretas para conseguir la respuesta y que más adelante veremos las respuesta.
¿Cuántos sudokus hay? ¿Cuántas maneras hay de colorear los países de mapa mundi? Vamos a ver que la Teoría degrafos trata de contestar a estas preguntas

Las matemáticas discretas son un área de las matemáticas encargadas del estudio de los conjuntos discretos: finitos o infinitos numerables. En oposición a las matemáticas continuas, que se encarga del estudio de conceptos como la continuidad y el cambio continuo, la matemáticas discretas estudian estructuras cuyos elementos pueden contarse uno por unoseparadamente. Es decir, los procesos en matemáticas discretas son contables, como por ejemplo, los números enteros, grafos y sentencias de lógica.
La clave en matemáticas discretas es que no es posible manejar las ideas de proximidad o límite y suavidad en las curvas, como se puede en el cálculo. Por ejemplo, en matemáticas discretas una incógnita puede ser 2 ó 3, pero nunca se aproximará a 3 porla izquierda con 2.9, 2.99, 2.999, etc. Las gráficas en matemáticas discretas vienen dadas por un conjunto finito de puntos que se pueden contar por separado; es decir, sus variables son discretas o digitales, mientras que las gráficas en cálculo son trazos continuos de rectas o curvas; es decir, sus variables son continuas o analógicas.
La matemática discreta es la base de todo lo relacionado conlos procesos digitales, y por tanto, se constituye en parte fundamental de la ciencia de la computación, una de las ramas de estudio impartidas en los estudios de Ingeniería Informática.

Durante este escrito nos enfocaremos en un área específica de las matemáticas discretas y esta es el área de grafos palabra de origen griego y su significado etimológico es “trazar”. Un grafo es un conjunto deobjetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto .
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras.
A continuación vemos algunas imágenes de los diferentes tipos de grafos:

La historia de las matemáticasdiscretas ha visto un gran número de problemas difíciles de resolver. En teoría de grafos, mucha de la investigación realizada en sus inicios fue motivada por intentos para probar el teorema de los cuatro colores, el cual fue probado más de cien años después de su inicial descripción.
En teoría de grafos, el teorema de cuatro colores es un teorema sobre la coloración de grafos que establece losiguiente:
Dado cualquier mapa geográfico con regiones continuas, éste puede ser coloreado con cuatro colores diferentes, de forma que no queden regiones adyacentes (es decir, regiones que compartan no sólo un punto, sino todo un segmento de borde en común) con el mismo color.

No es posible colorear cualquier mapa en estas condiciones utilizando sólo tres colores. En cambio, sí es posible hacerloconsiderando cinco colores.
En cada caso o problema los "colores" representan o simbolizan algo distinto y no necesariamente son literalmente colores.
En el ejemplo del mapa podemos asociar cada país a un vértice de un grafo y unirlos con una arista si tienen frontera en común. La demostración, que se fue asistida por computación, se realizó hace relativamente escasos años. Necesitaron más de...