Grafos. Nociones básicas
Introducción I Definiciones y ejemplos I Tipos de grafos I Representación de grafos I Representación de grafos en el ordenador I Conectividad

1.2. Definiciones y ejemplos

Definición 1.2.1. Un grafo G = (V, E) consiste en un conjunto finito V cuyos miembros se llaman vértices y una familia finita EcVxV de pares no ordenados de vértices a cuyos elementos llamaremos aristas o arcos y denotaremos por (u, v) donde u,v eV.

El número de vértices, es decir la cardinalidad del conjunto V se denomina orden del grafo y se denota por |V |. Por lo general se utiliza n para denotar el orden de G. El número de aristas, es  decir la cardinalidad de E, se denomina tamaño del grafo y se denota por |E |. Por lo general se utiliza m para denotar el tamaño de G.

Definición 1.2.2. Dado un grafo G = (V, E)

a)      se llama bucle o lazo a toda arista de la forma (v, v)

b)      se llaman aristas múltiples a las aristas que aparecen repetidas en E

c)      se dice que dos vértices son adyacentes si están unidos por una arista

d)      se dice que dos aristas son adyacentes si tienen un vértice en común,

e)      se dice que una arista y un vértice son incidentes si el vértice es extremo de la arista,

f)        se dice que un vértice es aislado si no es adyacente a ningún otro vértice.

g)      se dice que un grafo es simple si no tiene bucles ni aristas múltiples

Ejemplo 1.2.3.

En el grafo anterior u, v son vértices adyacentes, (u, v) y (v, w) son aristas adyacentes, z es un vértice aislado.

Ejemplo 1.2.4. Grafo simple:

Definición 1.2.5.

Dado un grafo G = (V, E), se llama grado de un vértice al número de aristas incidentes en el, contando los bucles como dos aristas. Se denota por deg(v) al grado del vértice v.

En el grafo del ejemplo 1.2.3 tenemos deg(u)=4, deg(v)=2, deg(w)=1, deg(x)=3, deg(y)=2 y deg(z)=0.

Proposición 1.2.6. Dado un grafo G = (V, E), se cumple que:

Corolario 1.2.7. El número de vértices de grado impar es par.

Definición 1.2.8. Llamaremos subgrafo de un grafo G=(V, E) a cualquier otro grafo G′=(V′, E′) con E′cE y V′cV.

Subgrafos particularmente importantes son aquellos que se obtienen de un grafo suprimiendo uno o varios vértices y las aristas incidentes en estos vértices.

Los siguientes cuatro grafos son subgrafos del grafo del ejemplo 1

Definición 1.2.9. Dos grafos G y G’ son isomorfos si existe una correspondencia uno a uno entre los vértices de G y los vértices de G’, tal que el número de aristas que unen cualquier par de vértices en G es igual al número de aristas que unen el par correspondiente de vértices en G’.

Si G=(V, E) y G′=(V′,E′) son isomorfos, entonces |V|=|V′|, |E|=|E′| y las sucesiones de grados de G y G′coinciden.

Ejemplo 1.2.10. Los siguientes grafos son isomorfos:

Esto puede comprobarse al etiquetar los vértices de ambos grafos asignando la misma etiqueta a los vértices correspondientes.

DESCARGAR ESTE ARCHIVO EN PDF