El módulo grgrafo es similar al módulo graficar (descripto más abajo), y como éste se basa en el uso de Tkinter, por lo que funciona en una instalación normal. La mayor diferencia es la posibilidad de mover interactivamente los vértices y las etiquetas de vértices y aristas.

Un ejemplo sencillo de uso puede verse en el módulo grgrsimple.

El módulo euler define una función para encontrar un ciclo de Euler (si lo hay), y el módulo euler-peli además muestra una “película” de cómo se va construyendo, ejemplificado en el archivo euler-peli.pdf.

En el módulo hamilton se definen funciones para encontrar caminos o ciclos de Hamilton (si los hubiera), la función hamilton es para grafos sin pesos y la función hamiltonc para el caso pesado.

El módulo hamilton-dibu muestra un gráfico del camino o ciclo obtenido, y el módulo hamiltonc-dibu hace lo mismo cuando las aristas tienen costos. Los gráficos resultantes pueden verse en hamilton-dibu.pdf y hamiltonc-dibu.pdf, respectivamente.

El archivo hamilton-dode.pdf encuentra un ciclo de Hamilton en el dodecaedro (el grafo original del juego de Hamilton), que necesita un tratamiento especial para dibujar los puntos. El gráfico en este caso se obtiene con el módulo hamilton-dode.

El módulo caballo sirve para encontrar un ciclo o camino de Hamilton (si lo hay) en un tablero de dimensión $m\times n$, donde las adyacencias están dadas por los movimientos de un caballo. El problema, con numerosas citas, está descripto en el archivo caballo.pdf.

El módulo petersen muestra una ilustración de este famoso grafo, determinando la existencia de un camino o un ciclo de Hamilton en él.

Este grafo tiene muchas características interesantes por lo que se usa como ejemplo y contra-ejemplo de varias propiedades.

Por ser un grafo pequeño con tantas propiedades curiosas, lo adopté como ícono de esta página.

El módulo recorrido implementa recorrido a lo ancho (fifo), y tres variantes de recorrido en profundidad (lifo), una de ellas usando recursión.

Las funciones lifo, fifo y lifovar pueden visualizarse mediante “películas” usando los módulos lifo-peli, fifo-peli y lifovar-peli.

En esos módulos pueden cambiarse los grafos a usar, y se muestran algunas posibilidades en los archivos lifo-circ.pdf, lifo-arbol.pdf, fifo-circ.pdf, fifo-arbol.pdf, lifovar-circ.pdf y lifovar-arbol.pdf.

Reproducimos los algoritmos tradicionales de Prim y Kruskal en los módulos prim y kruskal.

Como en otros casos, estos algoritmos se pueden visualizar mediante los módulos prim-peli y kruskal-peli.

En esos módulos se pueden cambiar los grafos, y algunos resultados puenden apreciarse en los archivos prim-peli.pdf y kruskal-peli.pdf

Reproducimos los algoritmos tradicionales de Dijkstra y Floyd-Warshall en los módulos dijkstra y floyd.

El algoritmo de Dijkstra, muy similar al de Prim, se puede visualizar con el módulo dijkstra-peli, como se ilustra en el archivo dijkstra-peli.pdf

El módulo cartero resuelve el problema buscando un emparejamiento de mínimo costo entre los vértices impares.

Para encontrar un emparejamiento de mínimo costo usamos un módulo de Joris van Rantwijk, reproducido acá en mwmatching (ver http://jorisvr.nl/article/maximum-matching y http://jorisvr.nl/files/graphmatching/20130407/mwmatching.py).

Este método tiene como versión sencilla encontrar un orden lineal compatible con un orden parcial dado. Resolvemos este problema basándonos en el algoritmo de “clasificación topológica” según el libro de N. Wirth, Algoritmos y estructuras de datos (Vicens Vives, 1998).

Cuando los puntos en las precedencias se piensan como tareas de un proyecto que requieren distintos tiempos, es de interés encontrar el menor tiempo posible en el que se puede terminar el proyecto, dando lugar al método del camino crítico (cpm), en el que además se encuentran las tareas críticas que no se pueden retrasar.

• En el apunte ordenlineal.pdf se describen con más detalles estos dos métodos.
• El método de clasificación topológica está implementado en el módulo toposort, y puede probarse con el módulo toposort-prueba.
• Análogamente, el método del camino crítico está en el módulo cpm, y puede probarse con el módulo cpm-prueba.

graficar está basado en tkinter y es de elaboración casera. Por lo tanto es muy elemental, y puede tener errores.

Aunque más rudimentario que el módulo Matlplotlib, descripto más abajo, ambos módulos son mucho menos amigables que, por ejemplo, GeoGebra.

Ejemplos de uso del módulo graficar:

• grseno es un gráfico sencillo del seno, mostrando cómo ajustar las escalas de los ejes.
• grexplog muestra la exponencial y su inversa, el logaritmo, incluyendo la diagonal $y = x$.
• gr1sobrex es el gráfico de la función discontinua $y = 1/x$, dando una tolerancia para alejarse de $0$.
• grnumerico es un módulo para ilustrar métodos numéricos para encontrar raíces.

  Cada uno de los métodos se ejemplifica en los siguientes módulos, en los que se pueden cambiar las funciones a analizar:

  • grbiseccion ilustra el método de la bisección para encontrar raíces.
  • grpuntofijo ilustra el método de punto fijo, esto es, iteraciones de la forma $x_{n+1} = f(x_n)$.
  • grnewton ilustra el método de Newton-Raphson para encontrar raíces de funciones suaves (es un método de punto fijo).
• graleat es una serie de gráficos mostrando cómo graficar puntos y el comportamiento de números aleatorios con distribución uniforme.
• grmandelbrot es... ¡no me acuerdo!
• Newton-fractal-1 y Newton-fractal-2 son dos vistas del fractal asociado a la convergencia del método de Newton para $z^3 - 1$, explicado en el apunte de Matemática y programación.

El módulo Matlplotlib es mucho más elaborado que el módulo graficar que mencionamos antes, pero necesita una instalación separada, que en algunos sistemas no es fácil.

Presentamos ejemplos sencillos, tratando de ver las posibilidades, imitando alguno de los ejemplos de graficar:

• pltseno: gráfico del seno.
• plt1sobrex: gráfico de $y = 1/x$.
• pltaleat: los puntos aleatorios.
• pltodo: un gráfico mostrando curvas y puntos en distintos estilos.