GRAFOS: RELACIÓN DE EQUIVALENCIA

Si la relación es reflexiva, significa que por ejemplo v1Rv1, lo que indica que el vértice v1 tiene un lazo.

Si en un grafo dirigido la relación R es simétrica, es decir, v1Rv2 entonces v2R v1, tenemos que existen dos líneas que unen a v1 y v2.

Si la relación es transitiva, o sea, (v1Rv2) y (v2Rv3) si y sólo si v1Rv3, se tiene la existencia de un triángulo v1 v2 v3.

Grado o valencia de un vértice (se denota grad(vi) o val(vi)) e indica el número total de líneas que tiene un vértice vi.
En el problema de los puentes de Königsberg (resuelto por Euler) encontramos un multigrafo de cuatro vértices y siete líneas que representan la relación entre los vértices.
Los vértices A, B, D tienen tres líneas y el vértice C cinco líneas. De este modo, tenemos

val(A) = val(B) = val(D) = 3 y val(C) = 5.

Si tenemos una línea xij = (vi, vj), entonces los vértices vi y vj se llaman vértices adyacentes y a vi lo denominaremos vértice inicial y vj vértice final. Además se dice que la línea es incidente al vértice vi como también es incidente al vj.
Las líneas son concurrentes entre sí, si varias líneas tienen un vértice vi en común.

Las líneas (A, C), (C, D), (B, C) son concurrentes entre sí. Entonces el número total de líneas concurrentes al vértice vi es igual al grado o valencia de vi.
A los vértices con valencia mínima los denotaremos con d(G) y aquellos vértices con valencia máxima D(G).

En el grafo anterior vemos que d(G) = 3 y D(G) = 5.


En particular, si d(G) = D(G) = r, entonces todos los vértices de G tienen la misma valencia "r" y el grafo se dice regular de grado r.

Obs.: No siempre es posible construir grafos regulares para valores cualesquiera de p, q y r, ya que de acuerdo con el Teorema de Euler se debe cumplir con 2q = pr.


Al conjunto de todos los vecinos de un vértice dado le llamaremos vecindad de vi o conjunto de adyacencia de vi, y se denota N(vi).
Así, N(vi) = { vj/ vjRvi }.

En particular, un vértice vi para el cual N(vi)= 0, se le denomina vértice aislado.

Por ejemplo, en el siguiente grafo v4 es un punto aislado.