Los puentes de köningsberg

Los puentes de Königsberg

Profa. Norma Ramírez Sánchez

Colegio de Matemáticas

Turno Diurno

UNAM

ENP 9 “Pedro de Alba”

Los 7 Puentes de Königsberg

En el siglo XVIII, siete puentes atravesaban el río Pregel a través de la pequeña ciudad universitaria alemana de Königsberg. Cuatro de ellos unían las orillas opuestas con la pequeña isla de Kneiphof.Un puente comunicaba Kneiphof con otra isla y los dos restantes unían a ésta con tierra firme.

Los pobladores se preguntaban “¿Cómo puede una persona planear su paseo del domingo en la tarde, de modo que cruce una sola vez cada uno de los siete puentes?”

¿Crees que es posible encontrar un trayecto que cruce cada uno de los siete puentes sólo una vez?

En caso afirmativo, dibuja el trayecto que cumpla con estos requisitos.

Si consideras que es imposible, explica por qué.

En San Petersburgo, el gran Euler resolvió el problema en 1735:

Reemplazó la tierra por puntos y los puentes por líneas que unían estos puntos.

¿Puede dibujarse la figura con un trazo continuo del lápiz, sin levantarlo del papel?

EulerBasilea, Suiza, 1707-San Petersburgo, 1783) Matemático suizo. Contribuiría con resultados destacados en el campo de la teoría de las ecuaciones diferenciales lineales, además de desarrollar la teoría de las funciones trigonométricas y logarítmicas (introduciendo de paso la notación e para definir la base de los logaritmos naturales).

Grafos

Grafo G=(V,E)

Estructura formada por un conjunto de puntos no vacío V

Conjunto E de pares no ordenados de puntos de V.

V, conjunto de vértices.

E, conjunto de aristas.

Un grafo se representa por medio de un diagrama de nodos y líneas.

Grafo dirigido

Un grafo donde los elementos de E son pares ordeandos.

Cada par e=(u,v) le llamamos arco y u y v son sus extremos inicial final

Algunas definiciones

Bucles, aristas (u,v) o arcos (u,v) con u=v.

Grafos que no posen bucles se llaman simples.

Pseudografos o multigrafo (con bucles o no) existen varias aristas entre u y v.

Un grafo G puede ser considerado como un grafo dirigido G1 en el que

(u,v) ϵ E(G) entonces (u,v) ϵ E(G1) y (v,u) ϵ E(G1)

GG 1

Grado de un vértice dG(v) o di

grado del vértice vi

Número de aristas que inciden con v.

El bucle, contribuye con dos unidades al valor del grado del vértice en el que incide.

Un grafo G no dirigido es k-regular si el grado de cada vértice es k.

Si el grado es cero, el vértice se llama aislado.

¿Cuál es el número de aristas de un grafo k-regular de n vértices?

Cadenas, caminos y conexión

Una cadena en G es una sucesión finita en la que se alternan vértices y aristas:

Voe1v1e1v2…. ekvk eiϵE vi ϵV

Cada arista ei es incidente con los dos vértices inmediatamente anterior y posterior vi-1 y vi.

A v0 y vk les llamamos vértice inicial

y final de las cadenas, siendo los restantes interiores

Una cadena es simple si las aristas son distintas dos a dos , y es un camino si son los vértices los que son distintos dos a dos. ¿Es toda cadena simple un camino?

El número de aristas de una cadena la llamalos longitud de la cadena.

Distancia entre dos vértices u,v d(u,v} es la longitud del camino más corto

El camino más corto de u a v, si existe suele recibir el nombre de geodésica

Una cadena es cerrada si los vértices inicial y final coinciden.

Ciclo, toda cadena simple cerrada donde los vértices interiores son distintos dos a dos y distintos de los extremos.

Dos vértices están conectados si existe una cadena de longitud mayor o igual que cero que los une.

Componente conexa de G.

Subgrafo de G maximal respecto del conjunto de aristas.

comp(G) es el número de componentes conexas de G

G es conexo si comp(G)=1, es decir, si dos vértices cualesquiera de G están conectados.

Regresando al problema

¿Podemos dibujar, sin levantar el lápiz, pasando una vez por cada arista?

Cuando debemos comenzar y terminar en el mismo vértice:Teorema: Un grafo conexo posee un ciclo euleriano todos sus vértices tienen grado par.

Por tanto, en el caso de los puentes de Königsberg no se puede conseguir lo que queremos (ya que ninguno de sus vértices tiene grado par).

Cuando comenzamos en un vértice y terminamos en otro:Teorema: Un grafo conexo contiene un camino euleriano tiene exactamente dos vértice de grado impar.

Por tanto en el caso de los puentes de Königsberg tampoco se podría conseguir esto, ese grafo tampoco contiene un camino euleriano.

¿Se podrá hacer algo con el sobre?

¿Con el sobre abierto?

GRACIAS