Teoria GDD

Apuntes

Grafos CONCEPTO De fi nición: un grafo puede de fi nirse como G = (V, A), donde V representa a un conjunto de vértices/nodos y A a las aristas (que son las relaciones entre los vértices). Nodos simples y compuestos: en la computación se considera que los nodos pueden estar compuestos por muchos valores (formando así una estructura de datos) o por un único valor. ● Si un nodo contiene un único valor, se llama nodo simple. ● Si hay un conjunto de valores que caracteriza a un nodo, se llama nodo compuesto. Grado de los nodos: cantidad de aristas que afectan a un nodo. En los grafos dirigidos distinguimos: ● Grado positivo: cantidad de aristas que salen de un nodo. ● Grado negativo: cantidad de aristas que llegan a un nodo. Objetivo: el objetivo de los grafos es modelizar un problema a través de un modelo abstracto donde los elementos del problema son los vértices y las relaciones entre ellos las aristas. Hablamos de modelo abstracto dado que un grafo es una estructura que no existe realmente. Para que se convierta en un almacenamiento concreto habrá que representarlo en una estructura computacional. REPRESENTACIÓN COMPUTACIONAL DE GRAFOS De ...