Definiciones: Vértices, arcos o ejes y matrices

               Un grafo es una colección de un conjunto de vértices, V, y de arcos, U. Los arcos, U, representan la relación binaria entre los vértices, V. La Figura 1‑52 es un grafo con cuatro vértices, v₁, v₂, v₃ y v₄, y 6 arcos, u₁, u₂, u₃, u₄, u₅ y u₆.

Figura 1.- Ejemplo de grafo

                El conjunto U de los arcos, o ejes, es un subconjunto del producto cartesiano, VxV, de los vértices. En nuestro ejemplo, el número de vértices es 4, y el conjunto de VxV está formado por 16 elementos (4x4=16):

Ecuación 1

               Los arcos del grafo de la Figura 1 no están orientados, es decir, no tienen definido un origen y un fin. En este caso, el arco (v_i, v_j) = (v_j, v_i) y cumple la propiedad simétrica. Por tanto, el conjunto U de los arcos, subconjunto de VxV, está formado por los siguientes elementos:

Ecuación 2

               Un arco, u, unido con un vértice, v, se denomina incidente al vértice v y el vértice, v, se denomina coincidente al arco u. Por ejemplo, el arco u₂ de la Figura 1 es incidente a los vértices v₁ y v₂. El vértice v₂ es coincidente a los arcos u₂, u₃ y u₆.

                Dos arcos, u_i y u_j se denominan adyacentes si son incidentes al mismo vértice. Dos vértices v_k y v_l se llaman adyacentes si se unen mediante un arco. En el ejemplo, los arcos u₁, u₂ y u₅ son adyacentes porque se unen en el mismo vértice, v₁. Los vértices v₂ y v₄ son adyacentes porque se unen a través del mismo arco, u₆.

                Podemos ponderar un grafo asignándole a cada arco, u_i, un peso, p_i. La ponderación nos va a indicar la fuerza que posee la relación binaria entre los vértices adyacentes a este arco.

                Para poder definir un grafo se utilizan varias clases de matrices, entre las cuales las principales son las matrices de incidencia y las matrices de adyacencia. Corrientemente se usan las de adyacencia, cuyos elementos representan los arcos adyacentes a los vértices v_i y v_j.

               La matriz de adyacencia A_ij = [a_ij]_nxn de un grafo con n vértices es cuadrada y si no está ponderado, se define como:

Ecuación 3

               Si el grafo está ponderado:

Ecuación 4

Índice