Jose

Redalyc
Sistema de Información Científica
Red de Revistas Científicas de América Latina, el Caribe, España y Portugal

LÓPEZ, CARLOS ANDRÉS; ARDILA URUEÑA, WILLIAM Diseño de aplicación para manipulación de grafos con algoritmos heurísticos de análisis Scientia Et Technica, vol. XIV, núm. 40, diciembre, 2008, pp. 268-273 Universidad Tecnológica de Pereira Pereira, Colombia
Disponible en:http://www.redalyc.org/src/inicio/ArtPdfRed.jsp?iCve=84920454049

Scientia Et Technica ISSN (Versión impresa): 0122-1701 scientia@utp.edu.co Universidad Tecnológica de Pereira Colombia

¿Cómo citar?

Número completo

Más información del artículo

Página de la revista

www.redalyc.org Proyecto académico sin fines de lucro, desarrollado bajo la iniciativa de acceso abierto

268
Scientiaet Technica Año XIV, No 40, Diciembre de 2008. Universidad Tecnológica de Pereira.

DISEÑO DE APLICACIÓN PARA MANIPULACION DE GRAFOS CON ALGORITMOS HEURISTICOS DE ANALISIS
Design of application for graph`s handling with heuristic algorithms of analysis RESUMEN El siguiente artículo muestra la manera de desarrollar una sencilla aplicación de entorno grafico sobre la cual se puede experimentardiversas técnicas, desde algoritmos de resolución de grafos hasta heurísticas empleadas en inteligencia artificial. Palabras Clave: Grafos, algoritmo, heurística, aplicación, C# Abstract The next section shows how to develop a simple graphical application environment on which to experiment with various techniques, from algorithms resolution graph until heuristics used in artificial intelligence. Keywords: graphs, algorithms, heuristic, application, C#. • • WILLIAM ARDILA URUEÑA Msc. Instrumentación Física Docente: Universidad Tecnológica de Pereira Correo: williamar@utp.edu.co CARLOS ANDRÉS LÓPEZ. Ingeniero de Sistemas Docente programa de Ingeniería de sistemas. Universidad Tecnológica de Pereira

1. INTRODUCCION Los grafos fueron creados por Leonard Euler como método para encontrarrespuesta a problemas asociados con la conexión entre vías de comunicación y la posibilidad que encierran las posibles rutas cuando existen diversas alternativas. Este mismo modelo aparece en el campo de las estructuras de datos ya que los grafos pueden considerarse como una forma de árbol eneario, en este articulo se expone la manera como a través de la programación orientada a objetos es posiblediseñar modelos fácilmente implementables en un ambiente de desarrollo como C# que permite además adicionar técnicas de resolución de problemas en esta área tales como los caminos de Euler o de Hamilton.

Circuito de Euler: trayecto que recorre todas las aristas de un grafo conexo donde el punto inicial coincide con el punto final. Circuito Hamiltonianos: trayecto que recorre cada vértice de un grafoexactamente una vez.

Las siguientes son dos definiciones necesarias: Grado de un vértice: cantidad de aristas que inciden en el. Arista: segmento que une dos vértices (ver figura 1).

2. MARCO TEORICO Un grafo es una colección de puntos llamados vértices unidos por líneas llamadas aristas, donde cada arista une dos vértices. Cuando las aristas tienen dirección estamos hablando de grafosdirigidos. Existe una variedad de ejemplos, ejercicios y problemas dentro de la teoría de grafos que requieren metodologías específicas, ejemplo de ello son [1]: • Trayectoria de Euler: es aquella que recorre todas las aristas de un grafo conexo. Figura 1: a) Vértice x de grado 0 (0 aristas). b) Vértices x e y de grado 1 (ambos están unidos por una arista). c) Vértices z e y de grado 1 (tocados poruna arista), vértice x de grado 2 (tocado por dos aristas).

Fecha de Recepción: 13 de Septiembre de 2008. Fecha de Aceptación: 15 de Diciembre de 2008.

269

Scientia et Technica Año XIV, No 40, Diciembre de 2008. Universidad Tecnológica de Pereira.

Heurística: capacidad de encontrar soluciones para un problema específico empleando razonamientos similares a los empelados por los seres...