Adyacencia, Incidencia y Grado

 Adyacencia, Incidencia y Grado

De entrada, se define el concepto de adyacencia para grafos, el cual tiene alguna relación con la idea que se tiene de adyacencia en geometría.

Adyacencia. Dos vértices x, v de un grafo G = (V, E) se dicen adyacentes si (x, y) ∈ E.

Es decir, que bajo la Definición anterior, la adyacencia relaciona dos vértices de un grafo y en lenguaje natural se puede decir que dos vértices son adyacentes, si existe una arista que los une.

Ejemplo: Al estudiar el grafo de la figura 1.11, los vértices A y 1 son adyacentes ya que existe una arista que los une, mientras que los vértices A y B no lo son.

Incidencia. Dos aristas son incidentes si tienen un mismo vértice como extremo; análogamente si tenemos una arista e = (x, y) decimos que la arista e es incidente a los vértices “x” y “y”.

Observe que la incidencia, no relaciona vértices, sino las aristas de un grafo.

Ejemplo:  Retomamos nuevamente, el grafo de la figura 1.11, podemos ver que las aristas (A, 1) y (1, B) son incidentes, ya que las dos comparten el vértice 1. En cambio las aristas (A, 1) y (C, 2) no son incidentes ya que no comparten ningún vértice.

Grado de un vértice.

El grado de un vértice x es el número de lados incidentes a él. El grado de un vértice x se denota gr(x).

Denotamos con δ (G) y ∆ (G) el mínimo y el máximo grado de los vértices de G respectivamente.

Ejemplo:  Podemos observar, en el grafo de la figura 1.11 que el grado del vértice 1 es gr (1) = 3, ya que hay tres aristas incidentes en ´ese vértice. En cambio, el grado del vértice 2 es gr (2) = 2.

En un dígrafo (grafo dirigido) distinguimos entre grado entrante (indegree) y grado saliente (outdegree) de un vértice x, el primero indica el número de lados que tienen al vértice x como terminal y el segundo indica el número de lados que tiene al vértice x como inicial, y se denotan gr−(x) y gr+(x) respectivamente.

Camino. Es una sucesión de vértices y aristas que parten de un vértice y llevan a otro vértice utilizando las aristas definidas para el grafo.

Ejemplo: Podemos ver, en el grafo de la figura 1.12, que existen dos caminos que nos llevan desde el vértice 1 al vértice 4. Es decir, (1, 2,4) o (1, 3, 2,4).

La notación (1, 2,4) significa que del vértice 1 me voy al vértice 2 y del 2 avanzo hacia el 4.

Observe que en ´este ejemplo, el grafo es no dirigido por lo que el camino (4, 2,1) también sería un camino valido. En un grafo no dirigido, los caminos se pueden recorrer en varios sentidos, en cambio si fuera un dígrafo, el sentido a recorrer de los caminos sería único.

Longitud de Camino. Es el número de aristas por las que está compuesto un camino.

Ejemplo:  En el ejemplo anterior de la figura 1.12, el camino (1, 2,4) es de longitud 2, mientras que el camino (1, 3, 2,4) es de longitud 3.

Ciclo. Es un camino que empieza y termina en el mismo vértice.

Ejemplo: Retomando nuevamente la figura 1.12, el camino (1, 3, 2,1) es un ciclo del grafo, también lo es el camino (1, 2, 3,1).

Grafo Cíclico. Se dice que un grafo es cíclico cuando contiene por lo menos un ciclo.

Bajo esta Definición, el grafo de la figura 1.12, es un grafo cíclico. Por otra parte, se dice que un grafo es acíclico cuando no contiene ciclos.

A partir de la definiciones anteriores, se puede concluir, que todo grafo que contiene un lazo o bucle, en realidad se convierte en un grafo cíclico, ya que el lazo por sí mismo es un ciclo del grafo. De esta manera, el grafo de la figura 1.13 también es cíclico.

En este punto, ya vimos varias definiciones relacionadas con grafos y la notación básica. Pero al igual que al trabajar con conjuntos, necesitamos formas de representar los grafos para que sean comprensibles y no estén sujetos a ambigüedades.