Definición y tipos de gráficos

8.1 INTRODUCCION

DEFINICIÓN:

Una gráfica (o grafica no dirigida) G consiste en un conjunto de V de vértices (o nodos) y un conjunto E de aristas (o arcos) tal que cada arista e ∈ E se asocia con un par no ordenado de vértices. Si existe una arista única e asociada con los vértices u y w, se escribe e=(v,w)o e=(w,v). En este contexto, (v,w) denota una arista entre v y w en una grafica no dirigida y no es un par ordenado.

Una gráfica dirigida(o digrafica) G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tales que cada arista e ∈ esta asociada con un par ordenado de vértices. Si hay una arista única e asociada con el par ordenado (v,w) de vértices, se escribe e=(v,w) que denota una arista de v a w.

EJEMPLO:

La arista e_1 se asocia con un par no ordenado de vértices {Gre,She}, y la arista e_10 se asocia con el par no ordenado de vértices {Cas,Dou}. La arista e_1 se denota por (Gre,She) o (She,Gre) y la arista e_10 se denota por (Cas,Dou) o (Dou,Cas). La arista e_4 es incidente sobre wor y buf y los vértices wor y buf son adyacentes.

DEFINICION DE EJEMPLO:

La figura 8,1,4 muestra una grafica dirigida. Las aristas dirigidas se indican por flechas, la arista e_1 se asocia con el par ordenado de vertices (v_2 , v_1) y la arista e_7 se asocia con:

DEFINICIÓN

Los vértices de la gráfica corresponden a los agujeros (figura 8, 1,7). Cada par de vértices se conecta por una arista. En cada arista se escribe el tiempo para mover el taladro entre los hoyos correspondientes. Una gráfica con números en las aristas (como en la figura 8, 1,7) se llama grafica ponderada. Si la arista e se etiqueta k, se dice que es el peso de la arista e es k.

EJEMPLO

DEFINICIÓN

Suponga que en este problema se requiere que la trayectoria comience en el vértice a y termine en el vértice e. se puede encontrar la ruta de longitud mínima numerando todas las rutas posibles de a a e que pasan por todos los vértices justo una vez y eligiendo la menor (vea la tabla 8, 1,1). Se ve que la ruta que visita los vértices a,b,c,d,e, en ese orden, tiene longitud minima. Por supuesto, un par diferente de vértices de inicio y terminación produciría una ruta aun mas corta. Ejemplo:

GRAFICAS DE SIMILITUD

Este ejemplo trata el problema de agrupar objetos “similares” en clases basadas en las propiedades de los objetos. Por ejemplo, suponga que cierto número de personas implementan en c++ un algoritmo dado y que se quiere agrupar los programas “parecidos” en clases determinadas por ciertas propiedades de los programas (vea la tabla 8, 1,2). Suponga que se seleccionan como propiedades.

El número de líneas en el programa.

El número de instrucciones para regresas (return) en el programa.

El número de llamadas de funciones en el programa.

EJEMPLO:

Una gráfica de similitud G se construye como sigue. Los vértices corresponden a los programas. Un vértice se denota por (p_1, p_2,p_(3 )), donde p_1 es el valor de la propiedad i, se defines una función de disimilitud s como sigue, para cada par de vértices v=(p_1,p_2,p_3) y w=(q_1,q_2,q_3) se establece

S(v,w)=|p1-q1|+|p2-q2|+|p3-q3|.

Si v_1 es el vértice correspondiente al programa i, se obtiene:

S(v_1, v_2)=36 s(v_1,v_3)=24 s(v_(1 ,) v_4)=42 s(v_(1,) v_5)=30

S(v_3, v_4)=38 s(v_(2,) v_4 )=76 s(v_(2,) v_5 )=48 s(v_3, v_4 )=54

S(v_3,v_5)=20 s(v_4, v_5 )=46

Si v y w son vértices correspondientes a dos programas, s(v,w) es una medida de que tan disimiles son los programas. Un valor grande de s(v,w) indica disimilitud, mientras que un valor pequeño indica similitud.

Para un número fijo S, se inserta una arista entre dos vértices v y w si s(v,w)<S. (en general, habrá graficas de similitud diferentes para valores distintos de S.) se dice que v y w están en la misma clase si v=w o si hay una trayectoria de v a w. en la figura 8, 1,9

Ejemplo:

EL CUBO-N (HIPERCUBO)

Con frecuencia son modelos convenientes para describir estas máquinas. Los algoritmos asociados se conocen como algoritmos paralelos. Muchos problemas se resuelven con mayor rapidez usando computadoras paralelas en lugar de seriales. Se analizara un modelo de computación paralela conocido como el cubo-n o hipercubo.

El cubo-n tiene 2^n procesadores, n>1, que se representan por vértices (figura 8, 1,10)

También es posible describir el cubo-n de manera recursiva. El cubo-1 tiene dos procesadores, etiquetados 0 y 1, y una arista. Sean h_1 y h_2 dos cubos –(n-1) cuyos vértices se etiquetan en binarios 0…..2^(n-1)-1(vea la figura 8,1,11). Se coloca una arista entre cada par de vértices, una desde h_1 y otra desde h_2 , siempre que los vértices tengan etiquetas idénticas. Se cambia la etiqueta L en cada vértice de h_1 a 0L y la etiqueta L en cada vértice de h_2 se cambia a 1L.

DEFINICIÓN

La grafica completa sobre n vértices, denotada por k_n, es la grafica simple con n vértices en la que hay una arista entre cada par de vértices distintos.

EJEMPLO:

La grafica completa sobre cuatro vértices k_4, se produce en la figura 8.1.12

DEFINICIÓN

Una gráfica G= (V,E) es bipartita si existen subconjuntos v_1 y v_2 (cualquiera de los dos posiblemente vacio) de v tales que v_1 ∩ v_2 = ø v_1 u v_2= V, y cada arista en E es incidente sobre un vértice en v_1 y un vértice en v_2

EJEMPLO:

La gráfica de la figura 8.1.13 es bipartita ya que si se deja

v_1={v_1, v_2, v_3} y v_2={v_4,v_5},

Cada arista incide en un vértice en v_1 y en un vértice en v_2

EJEMPLO GRÁFICO:

DEFINICIÓN:

La grafica bipartita completa sobre m y n vértices, denotada por k_(m,n) es la grafica simple donde el conjunto de vértices tiene una partición en v_1 con m vértices y v_2 con n vértices y donde el conjunto de aristas consiste en todas las aristas de la forma (v_1,v_2) con v_1 ∈ v_1 y v_2 ∈ v_2

Ejemplo:

La grafica bipartita completa sobre dos y cuatro vertices, k_2,4 se ilustra en la figura 8.1.15.

8.2 TRAYECTORIAS Y CICLOS

DEFINICION:

Sea v_0 y v_n vértices en una gráfica. Una trayectoria de v_0 a v_n de longitud n es una sucesión alternante de n+1 vértices y n aristas que comienza en el vértice v_0 y termina en el vértice v_n,

(v_0,e_1,v_1,e_2,v_2,…,v_(n-1),e_n,v_n ),

Donde la arista e_1 es incidente sobre los vértices v_(i-1) y v_i para i=1,…,n.

El formalismo en la definición significa: comience en el vértice v_0; recorra la arista e_1 hasta v_1; siga por la arista e_2 y así sucesivamente.

EJEMPLO:

En la gráfica de la figura 8.2, 1,

(1,e_1,2,e_2,3,e_3,4,e_4,2),

Es una trayectoria de longitud 4 del vértice 1 al vértice 2

DEFINICION:

Una gráfica G es conexa si dados cualesquiera dos vértices v y w en G, existe una trayectoria v y w.

EJEMPLO:

La gráfica G de la figura 8.2.1 es conexa ya que dados cualesquiera dos vértices v y w en G, existe una trayectoria v y w.

EJEMPLO:

La gráfica G de la figura 8.2.2 no es conexa ya que por ejemplo, no ay trayectoria del vértice v_2 al vértice v_5.

DEFINICION:

Sea G=(V ,E) en una gráfica. (V^1 ,E^1) Es una sub grafica de G si

V^1⊆V y E^1⊆E

Para toda arista e^1∈ E^1 si e^1 incide en v^1 y w^1 ∈V

EJEMPLO:

La grafica G^1=(V^1 ,E^1) de la figura 2.2.3 es una subgrafica de la gráfica G=(V ,E) de la figura 8.2.4 puesto que V^1⊆V y E^1⊆E .

DEFINICION:

Sea G una gráfica y sea v un vértice en G. La subgrafica G^1 de G que conciste en todas las aristas y vértices de G que están contenidos en alguna trayectoria que comienza en v se llama componente de G que contiene a v.

EJEMPLO:

La gráfica G de la figura 8.2.1 tiene una componente, a saber ella misma, sin duda, una gráfica conexa si y solo si tiene exactamente un componente.

DEFINICION:

Sea v y w vértices en una grafica G.

Una trayectoria simple de v y w es una ruta de v y w sin vértices repetidos.

Un ciclo(o circuito) es una trayectoria de longitud diferente de cero de v a v sin arista repetidas.

Un ciclo simple es un ciclo de v a v en el que no ay vértices repetidos, excepto por el inicio y el fin que son iguales a v.

EJEMPLO:

Para la grafica de la figura 8.2.1, se tiene la siguiente informacion.

DEFINICION:

En honor a Euler, un ciclo en una gráfica G que incluye todas las aristas y todos los vértices de G se llama ciclo de Euler.

Si una grafica G tiene un ciclo de Euler es conexa y todo vértice tiene grado par.

Si una gráfica G es una grafica conexa y cada vértice tiene grado par entonces G tiene un ciclo de

...