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,

...