español

Grafos
En Informática es una estructura de datos abstracta, que consiste en un conjunto de nodos o vértices y un conjunto de arcos o aristas que establecen relación entre los nodos. Informalmentese define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas. Un grafo G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es unconjunto que consta de dos elementos de V.


Grafos ponderados.- Llamamos grafos ponderados a los grafos en los que se asigna un numero a cada una de las aristas. Este numero representa un pesopara el recorrido a través de la arista. Este peso podrá indicar, por ejemplo, la distancia, el costo monetario o el tiempo invertido, entre otros.
Definimos la longitud de un camino en un grafoponderado como la suma delos pesos de las aristas de ese camino.

La teoría de grafos es el estudio de grafos y la teoría de redes. Generalmente es considerada parte de la Combinatoria, pero haevolucionado por su parte lo suficiente como para ser considerada una materia por si misma.2 La teoría de grafos tiene extensas aplicaciones en todas las áreas de la matemática y la ciencia. Existen, incluso,grafos continuos. Propiedades
Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
Incidencia: una arista es incidente a unvértice si ésta lo une a otro.
Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa muchopara problemas de optimización, como el del vendedor viajero o del camino más corto.
Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamentedistinguibles del resto.

En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima...