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.3. Tipos de grafos

Definición 1.3.1.

Se dice que el grafo G = (V, E) es

a)      un grafo regular de grado n si todos sus vértices tienen grado n.

Grafos regulares de grado 2.

Grafos regulares de grado 3.

b)      un grafo completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices

c)      un ciclo si V = {v1, v2, . . . vn},  n³> 3, y  E = {(v1, v2), (v2, v3), . . . , (vn, v1)}. Se denota por Cn al ciclo de n vértices

d)      una rueda si V = {v0, v1, v2, . . . vn}, n n> 3, y E = {(v1, v2), (v2, v3), . . . , (vn, v1), {(v1, v0), (v2, v0), . . . , (vn, v0) }. Se denota por Wn a la rueda de n+1 vértices

e)      un cubo si sus vértices y aristas están relacionados como los de un cubo n-dimensional. Se denota por Qn al cubo asociado al cubo n-dimensional.

f)        un grafo bipartido si V=V1UV2 y cada arista de E une un vértice de V1 y otro de V2

g)      un grafo bipartido completo si V=V1UV2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,s al grafo bipartido completo donde V1 tiene r vértices y V2 tiene s vértices

 

Ejemplo 1.3.2. Una red de n ordenadores conectados a una unidad central estarían dispuestos formando un grafo del tipo Wn. Por otra parte, en un ordenador que tenga múltiples procesadores para efectuar procesamiento en paralelo, en el caso de que tenga n2 procesadores, estos se pueden conectar formando una red en forma de cuadrilátero, aunque una de las formas de conexión más importantes es la de 2n ordenadores según el grafo Qn.

 

Definición 1.3.3. Un digrafo o grafo dirigido es un par D = (V, E) consistente en un conjunto finito no vacío V cuyos miembros se llaman vértices y una familia finita E de pares ordenados de vértices a cuyos elementos llamaremos aristas o arcos.

Al par (u, v)eE lo denotaremos por uv y diremos que u es el extremo inicial y que v es el extremo final.

 

V={u, v, w, x, y, z}

E={ uu, vu, vw, vy, xv, xw, yz, zy }

Un digrafo simple es un par D = (V, E) consistente en un conjunto finito no vacío V cuyos miembros se llaman vértices y una familia finita E de pares ordenados distintos de vértices distintos a cuyos elementos llamaremos aristas o arcos.

Definición 1.3.4. Dado un digrafo D = (V, E), se llama grado de entrada de un vértice al número de arcos que lo tienen por extremo final y se llama grado de salida de un vértice al numero de arcos que lo tienen por extremo inicial.

 

DESCARGAR ESTE ARCHIVO EN PDF