Grafo: Es un
conjunto de objetos llamados vértices unidos mediante enlaces llamados aristas
que permite realizar enlaces entre varios elementos de un conjunto. Es una
manera muy descriptiva de solucionar un problema mediante posibles soluciones o
decisiones a tomar.
Aristas: Elemento que enlaza dos vértices generalmente una linea que hace posible la relación dentro de un conjunto.
Vértice: Son los puntos fundamentales de un grafo, elementos de un conjunto que puede tener relaciones entre si.
Los grafos surgieron como una necesidad en la solución de problemas donde existían
El primer articulo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se base en su articulo problemas de los puentes Königsberg. el problema se planteaba de la siguiente manera: Partiendo desde un punto de la ciudad es posible pasar atravez de todos los puentes solamente una vez llegando a todas las zonas de la ciudad y volver al punto de inicio.
Euler pudo concluir que era imposible la solución a dicho problema, aplicando modificaciones al problema podía tener solución.
Un Grafo cuenta con las siguientes propiedades:
Adyacencia: Dos aristas son adyacentes si tienen un vertice en comun.
Incidencia: Una arista es indicente a un vertice si esta lo uno a otro.
Ponderación: Corresponde a una funcion donde a cada arista se le asigna un varlo el cual esta implicado con el problema. el dato asignado puede ser moneda, distancia, peso, etc.
Etiquetado: Dato que se le asigna a las vertices o aristas, presentando de manera descriptiva las opciones y decisiones en le problema.
Ejemplo de Grafo:
0 comentarios:
Publicar un comentario