Teoría General De Grafos

TEORIA DE GRAFOS

GUIA DE APRENDIZAJE No. 1

DIANA CAROLINA TARAPUES CHIRIVI
ID 320350

UNIVERSIDAD COOPERATIVA DE COLOMBIA
VILLAVICENCIO

ACTIVIDADES

* Definición de grafo
Son estructuras de datos que permiten crear relaciones que no son necesariamente de jerarquía entre los elementos de un conjunto.

* Aplicaciones de los grafos
* En la construcción de circuitoseléctricos
* En la estrategia de ventas
* Cartografía
* Mapas de rutas
* Organización de procesos

* Leonard Euler y su aporte a la teoría de grafos

Leonard Euler(1707-1783). Matemático suizo, nacido en Basilea. Fue alumno de Johannes Bernoulli. Durante doce años ganó el premio que anualmente ofrecía la Academía de París sobre diversos temas científicos. Federico elGrande lo llamó a Berlín; Catalina de Rusia lo llevó a San Petesburgo, donde trabajó incesantemente. Por su tratado sobre Mecánica puede considerarse el fundador de la ciencia moderna. Su obra fue copiosísima, a pesar de que los últimos diecisiete años de su vida estuvo totalmente ciego.

Aporte a la Teoría de Grafos.
En 1736, Euler resolvió el problema conocido como problema de los puentesde Königsberg. La ciudad de Königsberg, en Prusia Oriental (actualmente Kaliningrado, en Rusia), estaba localizada en el río Pregel, e incluía dos grandes islas que estaban conectadas entre ellas por un puente, y con las dos riberas del río mediante seis puentes (siete puentes en total). El problema que se planteaban sus habitantes consistía en decidir si era posible seguir un camino, y cómohacerlo, que cruzase todos los puentes una sola vez y que finalizase llegando al punto de partida. Euler logró demostrar matemáticamente que no lo hay. No hay lo que se denomina hoy un ciclo euleriano en el grafo que modela el terreno), debido a que el número de puentes es impar en más de dos de los bloques (representados por vértices en el grafo correspondiente).
A esta solución se la considera elprimer teorema de teoría de grafos.
* El problema de los siete puentes
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 puntoinicial como el final serían los únicos que podrían estar conectados con un número impar de líneas. Sin embargo, el requisito adicional del problema dice que el punto inicial debe ser igual al final, por lo que no podría existir más de un único punto conectado con un número impar de líneas.

En particular, como en este diagrama los cuatro puntos poseen un número impar de líneas incidentes (tres deellos inciden en tres líneas, y el restante incide en cinco), entonces se concluye que es imposible definir un camino con las características buscadas.

* Teorema de los cuatro colores
"En un plano o en una esfera no se necesitan más de cuatro colores para colorear un mapa de manera que dos regiones vecinas, es decir, que compartan una frontera y no únicamente un punto, no queden coloreadasdel mismo color"
El teorema de los cuatro colores se formuló formalmente en 1850 sin que se le diera mucha importancia. Unos 20 años después solo se había demostrado que tres colores eran insuficientes para colorear cualquier mapa sin que haya regiones contiguas con el mismo color y con cinco colores sobraban.
Pero 124 años después por medio de computadoras se verificó en 1900 mapas diferentesque cuatro colores eran suficientes para iluminarlos correctamente.
Esta demostración fue aceptada por muchos matemáticos, pero otros consideran que puede existir un tipo de mapa que no haya sido abordado en la comprobación y que sea la excepción a la regla, es decir, para estos matemáticos no vale si la demostración no se hace con papel y lápiz.

* Definir y representar gráficamente...