Estructura de Datos              

Introducción básica a grafos

El problema se puede plantear usando una estructura matemática conocida como “grafo”. La base del grafo es un conjunto finito V de puntos llamados “vértices”. La estructura del grafo está dada por las conexiones entre los vértices. Si dos vértices están conectados se dibuja una línea que va desde un vértice al otro. Estas conexiones se llaman “aristas” (“edges”) del grafo. Los vértices pueden identificarse con un número de 0 a nv − 1 donde nv es el número total de vértices. También es usual representarlos gráficamente con un letra a, b, c, ... encerrada en un círculo o usar cualquier etiqueta única relativa al problema. Desde el punto de vista de la teoría de conjuntos un grafo es un subconjunto del conjunto G de pares de vértices. Un par de vértices está en el grafo si existe una arista que los conecta. También puede representarse como una matriz A simétrica de tamaño nv×nv con 0’s y 1’s. Si hay una arista entre el vértice i y el j entonces el elemento Aij es uno, y sino es cero. Además, si existe una arista entre dos vértices i y j entonces decimos que i es “adyacente” a j.