Conceptos fundamentales de la teoría de gráficas

Mer av detta

LOS PARADIGMAS DE LA INVESTIGACIÓN CIENTÍFICA

av Jonatan Gavanzo

SERES HUMANOS UNITARIOS Martha E. Rogers

av 05-EF-HU-JOSHELIN THALIA PORRAS RONDON

Legislacion de la historia clinica

av johana orozco toro

constitucion politica de los estados unidos mexicanos

av hector garcia

Conceptos fundamentales de la teoría de gráficas

Árbol de peso minimo

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.

Caminos

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.

Aplicaciones en la actualidad

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.

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

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

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.

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.

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.

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.

Árboles

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.

Grafos

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.

Un poco de historia

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.

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.

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

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

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.

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