portada grafos 99


PORTADA

COLEGIO DE EDUCACION PROFECIONAL TECNICA EN EL ESTADO DE
MICHOACAN
APLICACIÓN DE MATEMATICAS DISCRETAS



ING. BERNARDO CERVANTES MUNGIA

INFO 205

08.- BRANDON GUSTAVO CALDERON MARTINEZ
EPIFANIO RODRIGUEZ MARTINEZ
CORIA SOLORIO JOSE VENTURA

Apatzingan Mich. 06/abril/2014
EJEMPLOS DE GRAFO
¿ Que es un grafo?
En matemáticas y ciencias de la computación,un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binariasentre elementos de un conjunto. Son objeto de estudio de la teoría de grafos.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).Grafo etiquetado con 6 vértices y 7 aristas.

¿ Que son los grafos ?
La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos (también llamadas gráficas, que no se debe confundir con las gráficas que tienen una acepción muy amplia)estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados (edges en inglés) que pueden ser orientados o no.
La teoría de grafos es una rama de la Matemática discreta y de las aplicadas, y es un tratado que usa diferentes conceptos de diversas áreas como Análisis combinatorio,Álgebra abstracta, probabilidad, geometría depolígonos, aritmética y topología.
Actualmente ha tenido mayor preponderancia en el campo de la informática, lasciencias de la computación y telecomunicaciones.Los grafos son el objeto de estudio de esta rama de las matemáticas. Arriba el grafo pez, en medio el grafo y abajo el grafo dodecaedro.


¿ Cuando aparecieron los grafos ?
El origen de la teoría de grafos se remonta al siglo XVIII con el problema de los puentes de Königsberg, el cual consistía en encontrar un camino que recorriera los siete puentes del ríoPregel (54°42′12″N 20°30′56″E) en la ciudad de Königsberg, actualmente Kaliningrado, de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos. El trabajo de Leonhard Euler sobre el problema titulado Solutio problematis ad geometriam situs pertinentis1 (La solución de un problema relativo a la geometría de la posición) en 1736, es considerado el primer resultado de la teoríade grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología.
Luego, en 1847, Gustav Kirchhoff utilizó la teoría de grafos para el análisis de redes eléctricas publicando sus leyes de los circuitos para calcular el voltaje y la corriente en loscircuitos eléctricos, conocidas como leyes de Kirchhoff, considerado la primera aplicación de la teoría de grafos a un problema de ingeniería.
En 1852 Francis Guthrie planteó el problema de los cuatro colores el cual afirma que es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que no fueresuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken en 1976, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.
En 1857, Arthur Cayley estudió y resolvió el problema de enumeración de los isómeros, compuestos químicos con idéntica composición (fórmula) pero...