Teoría De Grafos En Linux

Hola, hoy escribo para deciros que he encontrado un programa de software libre el cual nos permite dibujar de una forma muy intuitiva nuestros grafos, además de hacer muchas más cosas con ellos que ahora luego os detallaré.
El programa se llama GraphThing y esta basado en GTK+ y wxWidgets 2.6.1, es muy ligero pero de algoritmo muy potente. El autor del proyecto se llama David Symonds y el programa lo podemos encontrar en Castellano y Catalán gracias a Josep M. López.
Se puede instalar en Mc-OS, Windows, FreeBSD, Linux, y hay paquetes debianizados tanto para Debian como para Ubuntu Dapper, Edgy y Feisty Fawn. Además del código fuente.
Para Dapper y Edgy lo po0déis encontrar en la web de GetDeb la versión 1.3.2 y en Feisty Fawn podéis instalar la versión 1.3.1 desde Synaptic.

El programa nos permite dibujar grafos preestablecidos, que son: Completo, Bipartido Completo, Ciclo, Piñón, Hanoi, Escalera, Malla, Nulo, Estrella, Árbol, Rueda, Petersen y los Platónicos: Cubo, Tetraedro, Octoedro, Dodecaedro e Icosaedro. En la imagen de arriba podéis ver un Icosaedro al cual le hemos calculado su matriz de adyacencia de grado 1 (la matriz de adyacencia la podemos calcular de grado mayor a 1 de forma sencilla).Para dibujar nuestros propios grafos es muy sencillo, hay que hacer lo siguiente:

  • Para Poner un vértice: Señalamos “Modo Vértice” y luego en la pantalla damos doble click con el ratón y nos aparecerá el vértice, al cual le podremos cambiar el nombre dándole doble click del ratón sobre el vértice dibujado.
  • Para Poner una arista: Lo pimero es tener por lo menos dos vértices dibujados, después marcamos la opción “Modo arista”, seguidamente con el ratón señalamos uno de los vértices y después señalamos el vértice de destino.

 

Para que la arista tenga una dirección basta que le déis doble click del ratón sobre la arista, os aparecerá una ventana, os váis a la opción “Dirección De Arista” y marcáis la dirección que deseis, le dáis a Aceptar y ya lo tenéis. (Ver imagen superior derecha).Para añadir pesos y flujos a las aristas lo primero es que en la barra de herramientas os vayáis a la opción “Ver” y señaléis: “Pesos” y “Flujos”. Seguidamente dáis doble clicck a la arista que queráis y en la ventana que os aparecía anteriormente modificáis las opciones: “Peso de la arista” y “Flujo de la arista” (Ver imagen superior derecha), para ver como queda dadle a la imagen superior izquierda.

Entre las cosas que podemos hacer con GraphThing tenemos:

  • Calcular grafo línea.
  • Calcular grafo complementario.
  • Calcular subgrafo.
  • Buscar camino más corto.
  • Búsqueda en anchura.
  • Búsqueda en profundidad.
  • Árbol de expansión mínimo.
  • Flujo máximo.
  • Saber si un grafo es conexo, euleriano, hamiltoniano o planar.
  • Calcular la matriz de adyacencia.
  • Calcular la sucesión de grados, el radio o el diámetro.
  • Calcular número, índice y polinomio cromático.

Con el programa todavía no se pueden dibujar aristas sobre un mismo vértice (o bucles) ni más de una arista entre dos vértices, pero David, su creador; me ha dicho por e-mail que en cuanto tenga tiempo lo hará🙂
Para guardar nuestros trabajos con Grapththing los guardaremos con la extensión .gt. Pero si queremos por ejemplo, añadir a nuestros documentos de Openoffice los grafos que tenemos lo podemos hacer con un capturador de pantalla guardándolo en formato jpg, para ello os recomiendo Desktop Data Manager
para los de Feisty lo tenéis en Synaptic.

Bueno, todo eso es muy bonito, pero ¿qué carajo es un grafo y para qué sirve? Bueno la respuesta a esto es muy larga, así que os dejo unos enlaces:

Teoria de Grafos (Wikipedia, en Inglés, pero muy completo)
Teoria de Grafos (Wikipedia, en castellano)

Enlaces relacionados:

Web de Graphthing
Proyecto CityBuilder (Gran proyecto en el cual para su construcción se ha utilizado GraphThing)

Ya no queda más que deciros que un servidor siempre estará a favor de una enseñanza libre e igualitaria en todos los estratos sociales y gubernamentales.
Agradecer a David por su generosidad en atenderme. Very, very thanks David🙂

Saludos🙂

Powered by ScribeFire.

3 comentarios en “Teoría De Grafos En Linux

  1. Pingback: GDS

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s