Miembros \ Profesores \ Gregorio Hernández Peñalver \ Grafos

Grafos

Interfaz grafo simple - matriz de adyacencia

Descarga de la aplicación

Descripción:

El objetivo de esta aplicación es, por un lado, representar gráficamente un grafo simple y su correspondiente matriz de adyacencia, permitiendo una serie de operaciones como por ejemplo mover los vértices a las posiciones que queramos, añadir o borrar tanto vértices como arcos, permutar vértices, agrupar todos los vértices en el mismo punto o agrupar todos los vértices circularmente. La particularidad de este programa es que estos cambios se pueden realizar tanto en la ventana correspondiente al grafo como en la ventana correspondiente a la matriz puesto que los cambios que se hagan en una ventana se ven reflejados en la otra (ya que estamos manejando el mismo grafo aunque representado de dos formas distintas).

Por otro lado hay una serie de algoritmos que se pueden aplicar sobre los grafos introducidos tales como comprobar si dos grafos son isomorfos, crear un grafo usando la lista de grados, crear un grafo aleatoriamente, buscar el mayor grafo completo posible (donde el mínimo sería un K3) o reordenar la matriz según la lista de grados.

Esta aplicación también permite almacenar en un fichero o recuperar de un fichero grafos seleccionados por el usuario. También permite imprimir un grafo o una matriz o mostrar algunos grafos típicos como por ejemplo algunos platónicos planos, la rueda, Petersen, etc.

Instalación. Navegadores y Plug-in:

La aplicación se podrá ejecutar sobre los navegadores Microsoft Internet Explorer (posterior a 5.0) así como sobre sobre Netscape Navigator (versión  4.7). Para poder trabajar localmente con ficheros o mandar trabajos a la impresora, hay que conseguir el entorno de ejecución de Java de la página de Sun (que incluye un plug-in) y usar la herramienta "Policy Tool" para dotar al applet de plenos permisos en el caso de que el applet no esté firmado digitalmente.

Manual de usuario:

A continuación se va a explicar la combinación de teclas que hay que usar para manejar la aplicación. Téngase en cuenta que dependiendo de en qué ventana se ejecute una de estas combinaciones (ya sea la ventana del grafo o de la matriz) el efecto será el mismo, es decir, se hará lo que indique esa combinación de teclas.

  • Shift + Botón izquierdo: Añadir un vértice.
  • Shift + Botón derecho: Borrar un vértice.
  • Control + Botón izquierdo: Añadir un arco.
  • Control + Botón derecho: Borrar un arco.

Las operaciones sobre arcos tienen la particularidad de que al intervenir dos vértices, hay que hacer un par de cosas. En primer lugar hay que pulsar Control + Botón (izquierdo o derecho según lo que se quiera hacer) sobre el primer vértice y mantener pulsada esta combinación de teclas hasta tener el puntero del ratón sobre el otro vértice y finalmente liberar las teclas pulsadas.

Si desea mover un vértice del grafo, pinche con el botón izquierdo del ratón sobre ese vértice y manténgalo pulsado desplazando el puntero hasta la nueva posición y por último libere el botón izquierdo del ratón.

Si desea permutar dos vértices de la matriz, pinche con el botón izquierdo del ratón sobre la etiqueta de uno de los vértices que desee permutar y manténgalo pulsado desplazando el puntero hasta la etiqueta del otro vértice que quiera permutar, liberando finalmente el botón izquierdo del ratón.

Una vez conocidas las operaciones básicas de la intefaz, se va a explicar las opciones que presenta la barra de menús.

General
  • Cerrar: Salir de la aplicación
  • Reordenar matriz según grados: Reordena la lista de grados de la matriz seleccionada (grafo, grafo complementario, grafo independiente o todas) de mayor a menor grado.
  • Crear grafo usando lista de grados: En primer lugar hay que introducir la lista de grados (no hace falta que esté ordenada). Cada grado puede ir separado por un blanco o por una coma y hay que pulsar ENTER al final de la lista de grados. Si la lista de grados es gráfica, permite dibujar el grafo en la ventana que se quiera (grafo o grafo independiente).
  • Buscar grafo completo: Extrae el mayor grafo completo posible (como mínimo obtiene un K3) del grafo introducido por el usuario. Dibuja en una ventana el grafo inicial y en otra el grafo completo.
  • Crear grafo aleatorio: Una vez que el usuario introduce el número de vértices, se crean los arcos aleatoriamente. Permite dibujar el grafo en la ventana que se quiera (grafo o grafo independiente).
  • Comprobar isomorfismo: Previamente hay que seleccionar la opción "grafos independientes" del menú "Mostrar" para poder introducir los dos grafos en base a los cuales se estudiará si son o no isomorfos.
  • Borrar: Elimina toda la información del grafo seleccionado por el usuario (grafo o grafo independiente).
  • Guardar: Guarda en un fichero el grafo seleccionado por el usuario (grafo, grafo complementario o grafo independiente).
  • Abrir: Recupera de un fichero un grafo guardado previamente y permite dibujarlo en la ventana seleccionada por el usuario (grafo, grafo complementario o grafo independiente).
  • Imprimir: Imprime el grafo o la matriz seleccionado por el usuario.
Vértices
  • Añadir vértice: Introduce un vértice en la esquina superior izquierda de la ventana.
  • Borrar vértice: Elimina el vértice cuya etiqueta corresponda a la introducida por el usuario.
  • Permutar vértices: Permuta los vértices introducidos por el usuario.
  • Agrupar todos en el mismo punto: Reúne todos los vértices del grafo en la esquina superior izquierda de la ventana.
  • Agrupar todos circularmente: Muestra circularmente todos los vértices del grafo ajustándolos al tamaño de la ventana.
Arcos
  • Añadir arco: Crea un arco entre los dos vértices introducidos por el usuario.
  • Borrar arco: Elimina el arco comprendido entre los dos vértices introducidos por el usuario.
Mostrar
  • grafo: Muestra una ventana con el grafo introducido por el usuario.
  • matriz: Muestra una ventana con la matriz correspondiente al grafo introducido por el usuario.
  • grafo y matriz: Muestra en dos ventanas tanto el grafo como su correspondiente matriz.
  • grafo complementario: Muestra en una ventana el grafo complementario al grafo introducido por el usuario.
  • matriz complementaria: Muestra en una ventana la matriz complementaria del grafo complementario.
  • grafo y matriz complementarios: Muestra en dos ventanas el grafo y la matriz complementarios al grafo introducido por el usuario.
  • todos: Muestra en cuatro ventanas el grafo y la matriz introducidas por el usuario así como el grafo y la matriz complementarias a dicho grafo.
  • grafos independientes: Muestra cuatro ventanas donde introducir dos grafos que no tienen relación para estudiar posteriormente su isomorfismo.
  • Mostrar zoom: Muestra a tamaño reducido el grafo que seleccione el usuario para poder ver todo el contexto gráfico del mismo.
Ver Grafos:
  • Rueda: Muestra los vértices circularmente uniendo los vértices consecutivos por un arco pero además añade un vértice en el centro y pone todos los arcos posibles entre este vértice y los que están en la periferia.
  • Cíclo:  Muestra los vértices circularmente y añade arcos entre los vértices consecutivos.
  • Completo: En función del número de vértices introducidos por el usuario se crea un grafo completo.
  • Estrella: Muestra los vértices circularmente excepto uno que se situa en el centro y se añaden todos los arcos posibles entre este vértice y todos los que se encuentran en la periferia.
  • n-Cubo: Muestra un cubo en una, dos o tres dimensiones.
  • Bipartito completo: Partiendo del número de vértices correspondientes a cada uno de los conjuntos, se muestra el correspondiente grafo bipartido.

Para iniciar la aplicación pulse el Botón de Inicio: