Informe reunión del 23/03

Se introduce la clase con el problema de los parquímetros de la página 5 de la separata del libro “ForAllPracticalPurposes”, uno de los materiales entregado para trabajar durante todo el seminario, que comprende los capítulos del 1 al 4. Relacionando la aparición de este tipo de grafos con la realidad, los participantes propusieron  los siguientes ejemplos  diarios, que se analizaron si podían corresponderse:

• Horarios de los profesores (se trabajará más adelante, representa un “camino crítico”)
• Recolección de basura  (un sentido, el sentido de la calle)
• Barrido de las calles (dos sentidos, por tener que barrer ambos lados de la acera)
• PacMan (se plantearon varios posibilidades sobre su estudio)
• Circuitos eléctricos
• Aplicaciones tipo Waze (depende del tránsito, camino más corto, más rápido o costos)
• Cartero (no recorre todas las aceras, relacionado con el problema del viajante (ciclo de Hamilton)
• Cadete que hace trámites bancarios (ahorro de tiempo)
• Ejercicio para escolares: cómo recorrer  toda la escuela sin pasar dos veces por el mismo lugar
• Impresora o lápiz 3D (hay que ver bien cuál es su funcionamiento)
• Buscar departamento en un barrio determinado (“barriendo” todas las cuadras)
• Recorrido del micro escolar (problema del viajante)
• Circuito para hacer la visita a un museo
• Problema sobre ingresos y egresos de dinero (asignando signos y valores a los vértices, teniendo en cuenta que debe pasar por todas las aristas sin quedar en valores negativos. Consideraciones sobre la suma total de los positivos y los negativos para que pueda darse)
• Comisión de comunicaciones (recorrido de camiones que hacen barrido en paralelo)
• Partido de beisbol (no correspondería porque hay un único camino posible)

Sobre estas situaciones se charló la diferencia entre hacer un camino más corto o tener que pasar por todos los vértices y aristas, o si había condiciones para hacerlo, como ganar tiempo o dinero.

A continuación se conversó sobre definir la nomenclatura a usar y algunos conceptos, siguiendo la lectura de la página 6 del libro.

Para grafos: vértices y aristas, nodo y arcos para redes o grafos definidos; y en programación lineal: vértice de poliedro o punto extremo.

Concepto de valencia o grado: número de aristas que concurren en un vértice.

Se trabajará con grafos con número finito de vértices. Se definió:  grafos simples (no dirigidos) que no tienen aristas paralelas ni lazos. Se entiende  por aristas paralelas a dos o más que conectan los mismos vértices, y no así a aquellas que van dirigidas de un vértice a otro y luego al primero nuevamente.

Un camino es una secuencia de aristas conexas, un conjunto ordenado. Si no se repiten ni aristas ni vértices es un camino simple; si los vértices inicial y final son los mismo, y no hay otros repetidos, se dice que es un circuito (o ciclo) simple. Cualquier vértice en un ciclo puede ser punto de partida.

Luego, siguiendo la página 7, la figura 1.3, se plantearon caminos y ciclos para resolver la situación, determinando que la notación con los vértices no era buena ya que no permite saber si se repiten aristas, y se conversó sobre usar éstas directamente para establecerlo. A partir de este ejercicio se definió el circuito de Euler.

Circuito de Euler: ciclo que pasa por todas las aristas sin repetir ninguna; todos los vértices deben ser de grado par, y además debe ser conexo. 

Un grafo conexo es aquel en el cual dado un vértice \(u\) distinto de \(v\) existe un camino , y se cumple la relación de equivalencia:

• Propiedad  simétrica: \(u-v\Rightarrow{v-u}\)
• Propiedad transitiva: \(u-v\wedge v-w\Rightarrow{u-w}\)
•  Propiedad reflexiva: \(u-u\) (esta es por convención)

Además si  \(u-v\wedge v-w\Rightarrow{u-w}\)

¿Cómo se relacionan el número de aristas con el grado de los nodos?

Se realizó el siguiente análisis:

• Si hay una arista, hay dos vértices de grado uno, suman dos grados (el doble de la cantidad de aristas)
• Si hay dos aristas, hay dos vértices de grado uno y un vértice de grado dos, suman 4 grados (el doble de la cantidad de aristas)

Entonces el  doble del número de aristas es igual a la suma de los grados de los vértices.

Por otro lado, basado en ejemplos:

• Si hay una arista, hay cero vértices de grado par y dos vértices de grado impar.
• Si hay dos aristas con un único vértice común, hay un vértice de grado par y dos de grado impar.
• Si hay 3 aristas, puede haber ningún vértice de grado par y cuatro de grado impar.
• Si hay 4 aristas, puede haber dos vértices de grado par y dos de grado impar.

Entonces se ve que el número de vértices de grado impar siempre es par. (Esta no es una demostración).

Se trabajó luego con el problema de “Los puentes de Königsberg”. Se armó el grafo equivalente al mapa y al haber vértices de grado impar no se puede hacer un ciclo de Euler. Entonces se estableció qué arista habría que reutilizar,  “pegando” aquellos caminos que unían vértices de grado impar a ciclos que quedaban formados sin considerar esos caminos. (“Cómo encontrar circuitos de Euler”pág 8 de la separata).

A continuación se realizó la actividad 19 de la página 26 del ya mencionado material, del cual luego de algunos minutos de trabajo  se hizo puesta en común, en la que se habían considerado distintos casos de conexión de vértices de grado impar para buscar lo que proponía considerando el menor camino posible.

Tareas:

• Para el próximo encuentro a darse el día 27 de abril en la ciudad de Santa Fe, hay que llevar, de ser posible, netbook o notebook.
• Leer del apunte “Matemática y programación” pdf, los apartados: I. Elementos. 2 Primer contacto. (hincapié en el 2.4). 3. Python como calculadora
• Terminar el capítulo 1 completo de la separata del libro “ForAllPracticalPurposes” (haciendo la mayor cantidad de ejercicios posibles. Las versiones más recientes en inglés tienen muchos más ejercicios).