Tarea por: Yamileth de los Angeles Pereyra Cano.
Dibuja una gráfica con 4 vértices en la que cada vértice tiene grado 2.
Dibuja una gráfica con 6 vértices en la que cada vértice tiene grado 3.
Dibuja una gráfica con 4 vértices en la que cada vértice tiene grado 1.
Dibuja una gráfica con 8 vértices en la que cada vértice tiene grado 3.
8.Dibuja una gráfica con 4 vértices, cada vértice de grado 3, en la que
a) no haya lazos ni aristas múltiples.
b) si haya lazos pero no aristas múltiples.
c) si haya aristas múltiples pero no lazos.
d) haya lazos y aristas múltiples.
9.Dibuja una gráfica con 5 vértices, cada vértice de grado 4, en la que
a) no haya lazos ni aristas múltiples.
b) si haya lazos pero no aristas múltiples.
c) si haya aristas múltiples pero no lazos.
d) haya lazos y aristas múltiples.
10.Considera la siguiente gráfica:
a) Encuentra una trayectoria del vértice C al vértice F que pase por el vértice B pero no
por el vértice D.
b) Encuentra una trayectoria del vértice C al vértice F que pase por los vértices B y D.
c) ¿Cuántas trayectorias hay del vértice C al vértice A?
2.
d) ¿Cuántas trayectorias hay del vértice H al vértice F?
1.
e) ¿Cuántas trayectorias hay del vértice C al vértice F?
5.
f) Encuentra un circuito que pase por el vértice D.
g) ¿Cuántos circuitos empiezan y terminan en el vértice D?
4.
h) ¿Cuales aristas son puentes?
De la B a D, de la F a G.
11.Encuentre dos ejemplos de gráficas conexas con 4 vértices en las que cada arista sea un
puente.
12.En el problema de los puentes de Königsberg ¿cuáles de los puentes de la ciudad son
puentes en el sentido de teoría de gráficas?
13.Para cada una de las siguientes gráficas, determina si hay un circuito de Euler, una
trayectoria de Euler o ninguno de los dos. Explica tu respuesta.
La figura a) tiene un ciclo euleriano=
1->5->10->6->11->7->12->8->9->5->4->8->3->7->2->6->1->2->2->3->4->1
La figura b) no tiene ciclo euloriano.
La figura c) no tiene ciclo euloriano.
La figura d) tiene un ciclo euleriano: 0⇒3⇒6⇒5⇒8⇒4⇒7⇒3⇒2⇒5⇒1⇒4⇒0⇒2⇒1⇒0
La figura e) no tiene ciclo
La figura f) no tiene ciclo.
14.Usa las gráficas obtenidas en el ejercicio 1 para responder las preguntas a) y b) que ahí
se plantean.
15.A los habitantes de Königsberg (hoy Köningrado) les hubiera interesado saber que en el
año de 1935 se construyó un nuevo puente, uniendo las áreas de tierra B y C.
16.Supongamos que cada vez que se cruza un puente de la ciudad de Königsberg se tiene
que pagar $1.00 y que se requiere que hagas un recorrido cruzando cada puente por lo
menos una vez.
a) Describe el recorrido más barato que empieza y termina en el área de tierra B.
b) Describe el recorrido más barato si se te permite empezar y terminar en áreas de
tierra diferentes.
