Conceptos fundamentales de la teoría de gráficas

La teoría de las graficas es la rama de las matemáticas la cual estudia las propiedades de los objetos llamadas graficas

Las graficas son formadas por un conjunto finito de elementos llamados vértices o nodos las cuales son unidos mediante líneas llamadas aristas o arcos las cuales tienen una adyacencia entre ellas.

Leonhard Euler en 1736, trabajo para resolver el problema de los puentes de Königsberg el cual demostró extrayendo los detalles de la ciudad y los puentes que lo cruzaban resolvió que la ciudad no podía ser recorrida pasando una solo vez por cada uno de sus puentes

Gustav Kirchhoff 1845 publica sus leyes de los circuitos las cuales eran aplicadas al calculo de las tenciones, intensidades y resistencias.

Francis Guthrie 1852 plantea el problema de los cuatro colores, el cual consistía en utilizar solo cuatro colores y que al colorear los cualesquiera mapas de países vecinos nunca tengan el mismo color, este planteamiento fue resuelto Kenneth Apple y Wolfgang Haken, hasta los años setenta.

Arthur Cayley 1857 el mientras estudiaba la cantidad posible que podía haber de ciertas estructuras químicas, descubrió una importante familia de graficas a las que llamo árboles.

Un grafo es conjunto de puntos y conjunto de líneas donde cada línea une un punto con otro. Llamaremos grafo, G, al par ordenado formado por un conjunto finito no vacío, V, y un conjunto A, de pares no ordenados de elementos del mismo.
V es el conjunto de los vértices o nodos del grafo
A será el conjunto de las aristas o arcos del grafo.
Utilizaremos la notación G= (V, A) para designar al grafo cuyos conjuntos de vértices y aristas son respectivamente, V y A.

Son grafos los cuales no tienen ciclos y que conectan a todos los puntos, su importancia radica en que los arboles son grafos que conectan cada uno de los vértices, pero siempre utilizando el menor número posibles de aristas.

Mecánica: Para ver el comportamiento de las moléculas de un imán cuando dos ellos son adyacentes que es lo que pasa ya sea que se repulsen o se atraigan.

Química: lo utilizan para dibujar las moléculas las cuales, mediante representación de árboles en la química orgánica, se ocuparon para representación de los isómeros de los hidrocarburos saturados.

Computación: en el diseño de los circuitos integrados impresos en chips de silicón, los cuales utilizan las graficas planas esto con el fin de que las líneas conductoras no se crucen entre ellas.

Redes sociales: El cual busca el correcto almacenamiento de datos de todos los miembros que tiene esto facilitar el acceso a su información de manera eficiente.

Biología molecular: Generar modelos de proteínas y mapas genómicos

Ciencias de la computación: Utilizada para generación de nuevos algoritmos que permitan la solución de problemas establecidos.

Didáctica y lúdica: Modelar y resolver juegos orientados a la educación como lo son las torres de Hanói, como-solo, el domino, el Nim etc.

A toda cadena en la que no se repite ni vértices, ni aristas. Un camino en G es una sucesión donde se alternan vértices y aristas, comenzando y terminando con vértices y en el que cada arista es incidente con los dos vértices que la preceden y la siguiente.

Se dice que una gráfica G es ponderada si cada arista e\in\ E(G) se le asocia un numero E(e) el cual se le conoce como el peso de la arista. Si H es una subgráfica de una grafica ponderada el peso de w(H) de H es la suma de los pesos de las aristas de H. Muchos problemas de las optimizaciones utilizan una subgrafica con peso mínimo o máximo para poder resolverlo. Al árbol generador de peso mínimo también se le llama árbol óptimo.