Grafos
Contents
1. 4 Editar arcos seleccionando el nodo origen y final como antes y editar arco en el men contextual Se puede aprovechar la ventana de di logo para cambiar las opciones gr ficas de los arcos 5 Editar nodos tras seleccionar el nodo deseado con el bot n derecho se puede editar sus caracter sticas a trav s de la ventana de di logo Si lo desea puede cambiar las opciones gr ficas de cada nodo P g 14 de 15 Grafos Manual de usuario 6 Resultado final el grafo est terminado puede grabar el resultado final imprimirlo copiar la imagen o analizar el grafo con los algoritmos disponibles 1 A 7 Guardar el archivo Para guardar el archivo siga la opci n del men Archivo gt Guardar Seleccione la unidad de disco y el directorio donde desee guardar la informaci n y elija un nombre para el fichero antes de pulsar el bot n Guardar Guardar Archivo de Grafo A Primi 3 proba grf ps A Tipo Fichero de Gratos gr y Cancelar pa 8 An lisis Como paso final se puede resolver y analizar el grafo para ello se entra en el men An lisis y seleccionamos el an lisis por medio del algoritmo de Ford Fulkerson en este caso para el c lculo del flujo m ximo R pidamente el programa presentar la soluci n de los c lculos en un cuadro Y modificar el aspecto gr fico del grafo para mostrar gr ficamente tambi n el resultado SIME RIGHTS RESERVED Alejandro Rodr guez Villalo2. Opciones de Formato General Modos 5cos minimo m ximo m coste Trazo i a Color l Eidireccional Restaurar Aplicar a nuevos Aplicar a todo En la parte inferior del cuadro de dialogo hay tres botones el primero Restaurar permite dejar los par metros como estaban antes de modificarlos el siguiente Aplicar a nuevos aplica los cambios establecidos nicamente a los grafos que se creen a partir del momento de los cambios y el ultimo Aplicar a todo aplica los cambios al grafo que se tenga en el espacio de trabajo Las opciones de car cter general ser n aplicadas igualmente a todo el grafo como por ejemplo el color del fondo la rejilla u opciones como Bidireccional Nota Para que los cambios efectuados anteriormente sean reflejados en la pantalla una vez que se ha pulsado uno de los botones de aplicar cambios tengan efecto en pantalla se debe hacer un click de rat n el alg n lugar del tapiz de dibujo del grafo Esto forzar al programa a redibujar la pantalla con los nuevas opciones gr ficas P g 9 de 15 Grafos Manual de usuario Rejilla Esta opci n activa o desactiva la cuadricula de referencia de dibujo Im n Si est activada limita los movimientos posibles de los nodos en la fase de dibujo a puntos de la rejilla Centrar Grafo Esta opci n centra el grafo en el tapiz de dibujo Ajustar tapiz Ajusta el tama o del tapiz de acuerdo con el tama o del grafo dibujado Las
3. Si al instalar el programa apareciera el siguiente mensaje de error Error al registrar el m dulo CAWINNTISYSTEMS32IMSFLXGRD OCX Simplemente pulse el bot n de Continuar El programa debe terminar de instalarse correctamente y funcionar con normalidad P g 2 de 15 Grafos Manual de usuario Inicio del Programa men s Ka Grafos Para iniciar el programa tan solo hay que hacer click en su icono a trav s de la ruta Inicio gt Todos los programas gt Grafos tras lo cual el programa se iniciar y tras presentar un mensaje inicial de presentaci n presentar la pantalla inicial del programa Acerca de Grafos E rafos versi n 1 1 2 Programa para la construcci n edici n y an lisis de grafos en modo tabular o gr fico Permite exportar el grafo a diferentes formatos de ficheros gr ficos Contermpla valores de minimo m ximo y coste en los arcos y coste en los nodos Arcos bidireccionales etc 2003 Alejandro Rodr guez Yillalobos arodrigueziMomp upy es Advertencia este programa est protegido por las leyes de derechos de autor y otros tratados internacionales La reproducci n o distribuci n il cita de este programa o cualquier parte del mismo est penada por la ley con severas sanciones civiles y penales y ser objeto de todas las acciones judiciales que correspondan La utilizaci n del programa es muy sencilla leyendo atentamente este manual y experimentando con l aprender r
4. pidamente todas las opciones del mismo En la parte superior de la pantalla se presentan una serie de men s que contienen todas las opciones y funciones necesarias para trabajar con grafos Los distintos men s son Archivo Edici n Formato An lisis y Ayuda P g 3 de 15 Grafos Manual de usuario Archivo Mue o Ctri UU Abrir Cer Formato Opciones Cr Guardar Cer Rejilla Ctrl F Guardar como A we Im n Ctrl I Exportar imagen Chrl E Copiar imagen Cero Centrar grafo Ajustar tapiz Configurar impresora Estrella Aleatorio a Gr fica Tablero sa Fu Configurar p gina sz Imprimir Ctrl F rbol minimo Alg Dijkstra Ndi Arbol m ximo Alg Dijkstra Ndi Camino minimo 4lq Dijkstra Mdi PJd2 Camino critico Alg Dijkstra Pdi Md2 Camino minimo Alg BellmanFord Mdi Mdz Camino m ximo Alg BellmanFord MNdi Mdz Todos los Caminos m nimos Alg Floywdwearshall rbol de valor total minimo Alg Kruskal Arbol de valor total m ximo Alg Kruskal rbol de valor total minimo Alg Prim rbol de valor total m ximo Alg Prim Ayuda Flujo m sirno Alg FordFulkerson Ndi Ndz Nota es posible que en futuras versiones de Grafos la apariencia de estos men s cambie ligeramente incorporando nuevas funciones t Creando un nuevo grafo modo gr fico Para
5. llamada Nodos permite modificar los par metros referidos a los nodos del grafo Permite seleccionar los elementos del nodo a mostrar que pueden ser la etiqueta el coste ambos o ninguno Permite asimismo especificar el grosor del trazo de dibujo del nodo as como el color de fondo del mismo y el radio de la circunferencia que lo representa P g 8 de 15 Grafos Manual de usuario Grafos Opciones de Formato General Modos Arcos e etiqueta Tr coste Restaurar Aplicar a nuevos Aplicar a todo La tercera pesta a llamada Arcos permite modificar los par metros referentes a los arcos del grafo Al igual que la opci n anterior permite seleccionar los elementos del arco a mostrar que pueden ser el flujo m nimo el flujo m ximo el coste o todos Esta opci n es importante ya que identifica tambi n la interpretaci n de los datos introducidos en modo tabular que deben ser introducidos separados por el signo punto y coma Tambi n permite modificar el grosor del trazo que representa gr ficamente al arco as como su color La casilla Bidireccional representa la posibilidad de que el programa al detectar que hay arcos que unen dos nodos en sentido contrario pero con valores de flujo o coste iguales sean dibujados como uno solo pero con puntas de flecha en ambos extremos En caso de que los arcos tuviesen diferentes valores serian dibujados como dos arcos diferentes aunque esta casilla est activada Grafos
6. siguientes opciones del men Formato representan la forma de dibujar en pantalla un grafo abierto mediante la opci n Abrir o un grafo creado de forma tabular Por defecto est activada la opci n Estrella Esta opci n dibuja el grafo con forma de pol gono de tantos lados como nodos un ejemplo se puede ver en la siguiente pantalla j E F r 7 La opci n Flujo dibuja el grafo de forma que los nodos que tengan m s arcos que salen de ellos est n a la izquierda y los nodos que m s arcos reciben est n a la derecha De este modo el flujo representado ir a de izquierda a derecha Un ejemplo lo tenemos en la siguiente pantalla La opci n Aleatorio dibuja el grafo en pantalla sin seguir ning n orden predeterminado sino simplemente colocando los nodos de forma aleatoria Un ejemplo se puede ver en la siguiente pantalla E ri d E La opci n Tablero dibuja los nodos verticalmente en forma de columna ordenados de forma descendente seg n la numeraci n de los mismos En la siguiente pantalla se aprecia un ejemplo PSI 170 di C b l P g 10 de 15 Grafos Manual de usuario El men An lisis En el men An lisis se encuentran todas las posibilidades de aplicaci n de algoritmos para resolver y analizar los grafos creados Las opciones disponibles dependen del numero de nodos del grafo seleccionados algunos algoritmos necesitan como dato de entrada un nodo inicial Nd1 en ver
7. Grafos Manual de usuario Grafos Manual de usuario Grafos forma parte de un proyecto de investigaci n y desarrollo de aplicaciones inform ticas de dise o modular orientadas hacia la docencia investigaci n y labores profesionales de Ingenier a de Organizaci n Industrial 0000000 Instalaci n Inicio del programa men s Creando un nuevo grafo Modo gr fico Creando un nuevo grafo Modo tabular Guardar un grafo creado El men Archivo Abrir Ctrl A Exportar imagen Ctrl E Copiar imagen Ctrl C Configurar impresora Configurar p gina Imprimir p gina Ctrl P O El men Formato Opciones Ctrl 0 Rejilla Ctrl R Im n Ctrl l Centrar grafo Ajustar tapiz Opciones de dibujo O El men An lisis 1 Un ejemplo paso a paso P g 1 de 15 Grafos Manual de usuario Instalaci n El proceso de instalaci n es sencillo siguiendo la filosof a de la mayor a de programas del entorno Windows solo requiere la ejecuci n del fichero SETUP EXE el cual arrancar un asistente que le guiar en tres sencillos pasos en el proceso de instalaci n El paso mas importante es el de selecci n de carpeta de destino de los ficheros del programa E Grafos Seleccionar carpeta de instalaci n El instalados instalar Grafos en la siguiente capeta Para instalado en esta carpeta haga cie en Siguiente Para ristalailo en Luna capela distinta haga cic en Examinar Campela C rehrros de program
8. Manual de usuario Imprimir p gina Ctrl P Una vez configurada o seleccionada la impresora y el formato de p gina podr lanzar el proceso de impresi n El programa mostrar una ventana de previsualizaci n para que vea como quedar a el trabajo de impresi n antes de ejecutarse Si quiere puede volver atr s y ajustar de nuevo los par metros de impresi n y la escala de la imagen con el Zoom o bien pulsar el bot n Imprimir para lanzar el trabajo de impresi n 0 El men Formato Dentro del men Formato est n disponibles las siguientes opciones de men Opciones Chrl w Rejilla Ctrl F we Im n Ctrl I Opciones Dentro de esta opci n de men se engloban los par metros de funcionamiento del programa Dispone de tres pesta as la primera General engloba las opciones para cambiar el tipo de las fuentes empleadas en el dibujo de los grafos El nivel de zoom o ampliaci n gr fica con el cual se quiere trabajar en el dibujo de los grafos El tama o de la rejilla cuadricula de referencia para el dibujo de los grafos as como el color de la misma El tama o del tapiz u hoja donde se dibuja el grafo y el color de fondo del mismo Centrar grafo Ajustar tapiz Estrella Aleatorio Tablero Flujo Grafos Opciones de Formato General Modos ACOS ABC abcO l23 Rejla 40 Ea Restaurar Aplicar a nuevos Aplicar a todo La segunda pesta a
9. a Giealost Instalar Grafos s lo para este usua o o pata todos los usuanos de este equipo O Para bodog los upuaros 2 S lo para este usuario El equipo necesario para instalar y utilizar Grafos es el siguiente Sistema Operativo Microsoft Windows NT 2000 XP Memoria RAM viene determinada por los requisitos del sistema operativo pero para obtener mejores prestaciones gr ficas se recomienda 128Mb RAM m nimo Espacio en disco duro menos de 50 Mb de espacio libre en el disco duro Perif ricos est ndar compatibles con el sistema operativo Se recomienda el uso de una Impresora en color y de una tarjeta gr fica de altas prestaciones Internet conexi n est ndar a Internet para uso de servicios de actualizaci n autom tica y consulta de ayuda on line Importante compruebe que dispone del Service Pack m s reciente y de las actualizaciones indispensables para la versi n de Windows que utilice Grafos es un software desarrollado en Microsoft Visual Studio NET y por tanto requiere de NET Framework 1 1 redistributable instalado en su ordenador para poder funcionar no confundir con NET Framework Para buscar las actualizaciones m s recientes visite Windows Update Para comprobar si tiene instalada la versi n adecuada de NET Framework o para m s informaci n visite How to get the NET Framework Para instalar el programa adem s necesita disponer de Microsoft Windows Installer Posible error al instalar
10. a interpretar que el flujo m nimo son 5 y el coste son 10 En cambio si se hubiese seleccionado mostrar flujo m ximo flujo m nimo y coste el programa interpretar a como flujo m nimo 5 flujo m ximo 10 y coste 12 Los valores omitidos siempre tendr n un valor de cero D Guardar un grafo creado m ENEE Ey Una vez que se tiene un grafo creado se puede guardar en un disco para trabajar posteriormente con l modificarlo etc El programa almacena los grafos en un formato propio en fichero de extensi n grf El proceso es el siguiente Abrir el men Archivo y seleccionar la opci n Guardar se presentar una pantalla como la de la figura en la que seleccionar la carpeta donde se desea almacenar el grafo y el nombre del archivo Se hace click en el bot n aceptar quedando el grafo archivado para su posterior utilizaci n P g 6 de 15 Grafos Manual de usuario EN El men Archivo Dentro del men Archivo adem s de las opciones de crear un grafo nuevo y guardar existen las siguientes opciones que se comentan a continuaci n Mue o Crri UU Abrir Cer Abrir Ctrl A Abre un archivo previamente guardado para Guardar Cerr poder realizar su an lisis modificarlo imprimirlo etc Para ello Guardar como presenta un cuadro de dialogo donde seleccionar el archivo que se desea abrir para una vez aceptado presentarlo en Exportar imagen Sega pantalla Copiar imagen ctrl E Config
11. bos P g 15 de 15
12. crear un grafo nuevo se ha de seleccionar la opci n Nuevo en el men s archivo Por defecto el programa entra en la introducci n de datos del grafo en 2 Gr fica modo gr fico es decir dibujando el mismo en primer lugar para una vez dibujado introducir los datos correspondientes al mismo Tambi n es posible introducir un grafo de modo tabular es decir por medio de una tabla Para ello hay que seleccionar en el men Edici n la opci n Tabular El proceso de creaci n en modo gr fico es el siguiente Situando el rat n en la pantalla gr fica y haciendo un click en el bot n A adir Nado derecho del rat n aparecer el siguiente men contextual en el que se ha Editar modo de seleccionar la opci n A adir Nodo Esta operaci n se ha de repetir E hasta tener en pantalla los nodos necesarios n Alinear Modos Una vez creados los nodos hay que crear los arcos que unen cada nodo A adir rco para ello hay que pinchar con un click del bot n izquierdo del rat n en el Editar Arco Borrar rco com 00m oom ajustado Grafos Manual de usuario nodo inicial y un click del bot n derecho en el nodo final del arco con lo que los nodos cambiaran de color quedando el inicial de color verde y el final de color rojo Volver a aparecer el anterior men contextual en el que hay que seleccionar la opci n a adir arco tras lo cual quedaran los dos nodos conectados por el arco esta operaci n se d
13. de mientras que otros algoritmos requieren de un par de nodos seleccionados uno inicial Nd1 en verde y el final Nd2 en rojo Cuando se aplica un an lisis a un grafo r pidamente el programa presentar en pantalla el resultado en una ventana con los datos num ricos y tambi n gr ficamente en el grafo Esto se puede apreciar m s adelante en las pantallas correspondientes a los ejemplos de aplicaci n de los diferentes algoritmos de c lculo Una de las caracter sticas que diferencian a Grafos de otros programas es que el usuario tiene libertad para dibujar O modelar cualquier grafo A Mo se encuentra soluci n independientemente del algoritmo quel Los nodos no est n conectados o existe un lazo despu s quiera usar Posteriormente podr decidir a qu algoritmo env a el grafo para ser analizado Error en el proceso BellmanFord Si se intenta aplicar el an lisis a un grafo mediante un algoritmo para el cual no se cumplen las condiciones necesarias para su correcto an lisis por ejemplo falta de informaci n en los nodos o en los arcos o condiciones internas del grafo como lazos el programa presentar un mensaje de advertencia indicando esta circunstancia no pudiendo realizar el an lisis por medio del algoritmo causante del mismo Esto no es un error del programa sino simplemente que el grafo dibujado no cumple con las condiciones y supuestos necesarios para el algoritmo necesario Para m s informaci n sobre
14. e dialogo en el que hay que introducir el numero total de nodos que se desean para el grafo a crear una vez que se acepta el programa preguntar si se desea que Tabular A programa numere autom ticamente los nodos aceptamos puesto que posteriormente se pueden cambiar los nombres de los mismos Esta opci n renombra los nodos autom ticamente desde 1 hasta el total de nodos introducidos Edici n AAA Total Nodos Total Hodos Grafos Desea renumerar autom ticamente los nodos Una vez hecho esto aparecer la tabla donde introducir los datos de flujos coste etc del grafo Los valores se introducen separados por punto y coma por ejemplo para un arco con valores de 5 para el flujo m nimo 10 para el flujo m ximo y 15 de coste la introducci n en la tabla seria 5 10 15 Con lo que tendremos el grafo totalmente introducido Nota El signo de coma se debe utilizar como separador decimal Aunque en algunos algoritmos de resoluci n los valores nos enteros no ser n soportados Hay que destacar la importancia que tiene a la hora de introducir los datos del grafo en formato tabular la correcta y previa selecci n de los elementos a mostrar en el apartado Opciones del men Formato Dichas opciones determinan como interpreta el programa los valores introducidos para el arco Por ejemplo Si se ha seleccionado como elementos a mostrar el flujo m nimo y el coste y se introduce como dato 5 10 12 el program
15. eber repetir con todos los arcos del grafo quedando el ejemplo como se aprecia en las siguientes im genes Ejemplo de grafo con cuatro nodos 4 r Ei ka d A A a E S EA IE E DE A e E A adir arcos Grafo completo Una vez en este punto es el momento de introducir los datos de coste A adir Modo flujo etc en los nodos y en los arcos para ello hay que volver a hacer USO Editar Nodo del men contextual seleccionando primero con el bot n izquierdo del rat n el nodo inicial y con el derecho el nodo final tras lo que aparecer el men contextual en el que habr que seleccionar la opci n Editar Arco Aparecer un cuadro de dialogo en el que introducir los valores del arco fadir arco as como personalizar la apariencia gr fica del arco grosor y color del trazo Una vez completado el grafo se puede pasar a guardarlo en un archivo Borrar Nodo Alinear Modos F Editar Arco Borrar Arco oom Grafos Editar Arco 200M zoom ajustado Mi inima k simo Cancelar Aceptar Nota Si una vez creado el grafo en modo gr fico se pasa a modo tabular el programa advertir que se perder el formato la posici n y opciones gr ficas de los nodos y arcos del grafo aunque no la informaci n ni la estructura del grafo P g 5 de 15 Grafos Manual de usuario o Creando un nuevo grafo modo tabular Seleccionando en el men Edici n la opci n Tabular aparecer un cuadro de a
16. estos supuestos y condiciones se debe estudiar la Teor a de Grafos de dicho algoritmo La explicaci n del an lisis que realiza cada algoritmo esta disponible mediante enlaces a cada uno de ellos en la p gina principal del programa A continuaci n se presentan las diferentes pantallas que aparecer n al seleccionar el men An lisis en funci n del numero de nodos seleccionados Algoritmos de an lisis disponibles en grafo con un nodo inicial seleccionado j f Algoritmos de an lisis disponibles en grafo con un nodo inicial y un nodo final seleccionados C k E P g 11 de 15 Grafos Manual de usuario Algoritmos de an lisis disponibles en grafo sin seleccionar nodos A B E T EO A continuaci n se muestran pantallas de ejemplos de an lisis para algunos de los algoritmos disponibles En la versi n m s reciente del programa aparecer n nuevas funciones y algoritmos Algoritmo de Dijkstra C lculo del rbol m nimo o ea rr 4 md 4 e Algoritmo de Dijkstra C lculo del camino m nimo Hi d H I a t M H Algoritmo de Dijkstra C lculo del camino critico Algoritmo d de Floyd Wharshall C lculo de todos los caminos P g 12 de 15 Grafos Manual de usuario Algoritmo de Kruskal C lculo del rbol m nimo de A i E e 5 Algoritmo de Kruskal C lculo del rbol m ximo Ee EA Ls Algoritmo de P
17. rim C lculo del valor total m nimo A A e A F Un ejemplo paso a paso En las siguientes pantallas se va a realizar el proceso de creaci n del siguiente grafo paso a paso para su posterior an lisis de flujo mediante el algoritmo de Ford Fulkerson P g 13 de 15 Grafos Manual de usuario 1 Primero se selecciona en el men Archivo la opci n nuevo para posteriormente seleccionar en el men Formato gt Opciones dentro de la pesta a arcos que el programa muestre nicamente el flujo m ximo que es el dato con el que se va a trabajar En las siguientes pantallas se aprecia el proceso de creaci n de nodos y arcos as como la edici n de valores de flujo de los arcos Es recomendable que durante este proceso grabe repetidas veces el grafo en un fichero sobretodo cuando trabaje con grafos grandes de este modo conservar una copia de seguridad del mismo Grafos Opciones de Formato General Nodos Acos 2 A adir nodos tal y como se ha explicado anteriormente y utilizando el men contextual que aparece con el bot n derecho del rat n sobre el fondo de la pantalla Repetir esto para todos los nodos 3 A adir arcos igual que se explicado seleccionando el primer nodo o nodo origen con el bot n izquierdo del rat n y a continuaci n el nodo destino con el bot n derecho En el men contextual opci n a adir arco Repetir esta operaci n para todos los arcos
18. urar impresora Configurar p gina Imprimir Ctrl F Salir Exportar imagen Ctrl E Exporta el dibujo del grafo a un archivo con formato gif tif png omp El programa presenta una pantalla en la que solicita el nombre y la ruta del archivo a exportar Tras aceptar el programa generar un fichero en el formato indicado Copiar imagen Ctrl C Esta opci n copia la imagen del grafo en el portapapeles en formato bitmap mapa de bits para poder utilizarla en cualquier otro programa mediante la opci n pegar Ctrl V com nmente utilizada en Windows De esta manera podr f cilmente pasar los grafos dise ados a otras aplicaciones de Windows como editores de texto programas de retoque de imagen presentaciones archivos html para la web etc onfigurar impresora Esta funci n es com n para otros programas de Windows con ella puede seleccionar la impresora donde desea imprimir y configurar sus par metros de impresi n como la calidad de impresi n la posici n del papel etc Configurar p gina Al igual que la funci n anterior podr configurar el tama o de papel en el que desea imprimir el grafo la posici n del mismo y los m rgenes de impresi n Tenga en cuenta que el tama o de la imagen a imprimir ser el de su visualizaci n en pantalla por lo que tendr que combinar esta configuraci n con el uso del Zoom de la pantalla para cambiar la escala de la imagen P g 7 de 15 Grafos
Download Pdf Manuals
Related Search
Grafos grafoscopia grafoskop grafos online grafos de amor grafostilem grafos dibujos grafos dirigidos grafosello grafos isomorfos grafos simples grafos conexos grafos bipartitos grafos eulerianos grafos en python grafos completos grafos software grafos significado grafos hamiltonianos grafos estrutura de dados grafos dirigidos y no dirigidos grafoscopia y documentoscopia grafos de euler Graficas Tab cerca de mi Graficas Tab cerca de mi horario