Teoría de grafos

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos.

Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas.

Se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Isomorfismo

Un isomorfismo entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices.

La función es biyectiva si es al mismo tiempo inyectiva y sobreyectiva; es decir, si todos los elementos del conjunto de salida tienen una imagen distinta en el conjunto de llegada.

y a cada elemento del conjunto de llegada le corresponde un elemento del conjunto de salida.

 Una función es inyectiva si a cada valor del conjunto X le corresponde un valor distinto en el conjunto Y de f.

Es decir, a cada elemento del conjunto X le corresponde un solo valor de Y tal que, en el conjunto X no puede haber dos o más elementos que tengan la misma imagen.

 

  f: V(G) =  V(H)

que preserva la relación de adyacencia. Es decir, cualquier par de vértices u y v de G son adyacentes si y solo si lo son sus imágenes, f(u) y f(v), en H.

Una función es sobreyectiva cuando la imagen, elemento de "Y" es la imagen de como mínimo un elemento de "X".

Aristas dirigidas y no dirigidas

 Los grafos que contienen aristas dirigidas se denominan grafos orientados, como el siguiente:

Una arista corresponde a una relación entre dos vertices de un grafo. Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido).

Gráficamente las aristas se representan, para el caso de los grafos no dirigidos, como una línea que une a los dos vértices. Si el grafo es dirigido, entonces la arista se representa como una flecha, que parte del nodo origen y apunta al nodo destino

Vértice

Los vértices constituyen uno de los dos elementos que forman un grafo. Un vértice o nodo es la unidad fundamental de la que están formados los grafos.

El grado de un vértice en un grafo es el número de aristas incidentes a él. es decir  el grado o valencia de un vertice es el número de aristas incidentes al vértice

Problema de los 4 colores

El problema de los cuatro colores fue planteado por primera vez por Francis Guthrie en 1852 y resuelto positivamente en 1976 por Kenneth Appel y Wolfgang Haken.
En  teoria de grafos, el teorema de cuatro colores es un teorema sobre la coloración de grafos que establece lo siguiente.
Dado cualquier mapa geográfico con regiones continuas, éste puede ser coloreado con cuatro colores diferentes con el mismo color.
 

No es posible colorear cualquier mapa en estas condiciones utilizando sólo tres colores. En cambio, sí es posible hacerlo considerando cinco colores

 

Finalmente en 1976 (¡124 años después de que se había propuesto el problema!) dos matemáticos de la Universidad de Illinois en Estados Unidos, Kenneth Appel y Wolfgang Haken, usando una computadora Cray de segunda generación, analizaron 1900 posibles arreglos de regiones en el plano, o sea, analizaron 1900 tipos distintos de mapas. La computadora tardó 1,200 horas en correr un programa que tenía miles de líneas de largo, y para todos los mapas encontró una coloración en la que a lo más se usaban cuatro colores. ¡El problema había sido resuelto!

Problema de los puentes de Königsberg

También llamado más específicamente problema de los 7 puentes de konigsberg, es un célebre problema matematico, resuelto por Leonhard Euler en 1736 y cuya resolución dio origen a la teoria de grafos.

Leonhard Euler 

Nació en Basilea, Suiza, 15 de abril de 1707, Murió en  San Petersburgo, Rusia, 18 de Septiembre de 1783).


 Fue un matemático y físico suizo. En la cual se considera como el principal matemático del siglo XVIII y uno de los más grandes de todos los tiempos.

Teoría de grafos

Esta ciudad es atravesada por el río Pregolya, el cual se bifurca para rodear con sus brazos a la isla Kneiphof, dividiendo el terreno en cuatro regiones distintas, las que entonces estaban unidas mediante siete puentes.

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos.

Königsberg

Es una ciudad de se encuentra a orillas del Mar Báltico, en territorio Ruso y a unos 50 kilómetros de la frontera con Polonia.

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primer resultado de la teoría de grafos.

El problema fue formulado en el siglo XVIII y consistía en encontrar un recorrido para cruzar a pie toda la ciudad, pasando sólo una vez por cada uno de los puentes, y regresando al mismo punto de inicio.



¿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?

La respuesta es negativa, es decir, no existe una ruta con estas características. El problema puede resolverse aplicando un método de fuerza bruta, lo que implica probar todos los posibles recorridos existentes.

Euler en 1736 demuestra una solución generalizada del problema, para dicha demostración, Euler recurre a una abstracción del mapa, enfocándose exclusivamente en las regiones terrestres y las conexiones entre ellas
Cada puente lo representó mediante una línea que unía a dos puntos, cada uno de los cuales representaba una región diferente. Así el problema se reduce a decidir si existe o no un camino que comience por uno de los puntos azules, transite por todas las líneas una única vez, y regrese al mismo punto de partida.

→

Euler determinó, en el contexto del problema, que los puntos intermedios de un recorrido posible necesariamente han de estar conectados a un número par de líneas. En efecto, si llegamos a un punto desde alguna línea, entonces el único modo de salir de ese punto es por una línea diferente. Esto significa que tanto el punto inicial como el final serían los únicos que podrían estar conectados con un número impar de líneas.

entonces se concluye que es imposible definir un camino con las características buscadas.

 

Diagrama de Hasse

El diagrama de Hasse se define como el conjunto de todos los pares ordenados (x, y) tales que y sigue a x, es decir, el diagrama de Hasse se puede identificar con la relacion a seguir.

ejemplo, sea el conjunto A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} (todos los divisores de 60). Este conjunto está ordenado parcialmente por la relación de divisibilidad.
Su diagrama de Hasse puede ser representado como sigue:

Origen

Las matematicas discretas se encarga de estudiar los conjuntos discretos, en donde sus procesos son contables, es decir se pueden contar elementos separadamente, ejemplo: numeros enteros, grafos, sentencias de logica (algoritmos).

Se dice que la historia de las matematicas discretas dio origen a la teoria de grafos, la cual consta de una serie de puntos llamados vertices, que a su vez estan conectados por una serie lineas llamadas aristas. Por ejemplo:

En este diagrama de grafo se representa con 6 vértices y 7 aristas.