ensayo sobre la drogadiccion

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.

Grafosregulares de grado 3.
b) un grafo completo si cada par de vértices está unido por una arista. Se denota por Knal 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}, nn 3, y E = {(v1, v2), (v2, v3), . . . , (vn, v1), {(v1,v0), (v2, v0), . . . , (vn, v0) }. Se denota por Wna 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 Qnal cuboasociado al cubo n-dimensional.

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

g) un grafo bipartido completo si V=V1V2y dos vértices de Vestá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


Ejemplo1.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 efectuarprocesamiento 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 2nordenadoressegú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 depares ordenados de vértices a cuyos elementos llamaremos 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,...