Uno mas uno

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 degrado 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 ndimensional. Se denota por Qn al cubo asociado al cubo n-dimensional.f) un grafo bipartido si V=V1∪V2 y cada arista de E une un vértice de V1 y otro de V2

g) un grafo bipartido completo si V=V1∪V2 y dos vértices de V están unidos por una arista de E si y solo siun 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 unaunidad 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 n2procesadores, 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. Undigrafo 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 elementosllamaremos aristas o arcos. Al par (u, v)∈E 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...