sábado, 25 de abril de 2009

Ejemplos


Ejemplo1: El grafo representado a continuación, se obtiene a partir del conjunto de vértices

V={v1, v2,v3, v4, v5} y de la relación R es subconjunto de V x V, tal que, {(v1, v2)(v2, v3)(v4, v5)(v1, v4)(v2, v4) (v4, v4)(v2, v5)(v2, v3)} .


Una línea de la forma (u,u) la denominaremos lazo o bucle y una línea del tipo (u,v) con u distinto de v (uRv) la llamaremos línea simple. En cambio, cuando tengamos varias líneas que tengan como vértices terminales u y v, diremos que son líneas múltiples.

Observación: Las líneas (v2, v3) y (v3, v2) de la figura anterior son líneas múltiples y la línea (v4, v4) de la misma figura es un lazo.

En algunos casos es conveniente considerar grafos dirigidos en los cuales es necesario distinguir el sentido en que van las líneas, por medio de flechas.

Ejemplo2:



Este grafo se representa por:

G1 = (V(G1), E(G1))
V(G1) = {1, 2, 3, 4}
E(G1) = {(1,2) (1,3) (1,4) (2,3) (2,4) (3,4)}

G1 es un grafo NO DIRIGIDO. Esto es que los pares de puntos (1,2) y (2,1) representan la misma línea. Es decir, si el vértice 1 está conectado con el vértice 2, entonces el vértice 2 está conectado con el vértice 1.

Ahora bien, si tenemos el siguiente grafo:


Este grafo, sin embargo, se representa por:
G2 = (V(G2), E(G2))
V(G2) = (1,2,3)
E(G2) = ( (1,2) (2,1) (2,3) )
Aquí se repiten las conexiones de 1 con 2 porque este, como se ve, es un grafo DIRIGIDO. En este tipo de grafos si 1 está conectado con 2, no necesariamente 2 está conectado con 1.
Esto es lo que la mayoría de los autores denominan multigrafo. Sin embargo, nos dedicaremos a estudiar un tipo particular de grafos denominados grafos simples o matemáticos, que son aquellos grafos que no poseen orientación, ni líneas múltiples, ni lazos.
Usaremos la notación utilizada por F. Harary, denotaremos la cardinalidad del conjunto de vértices de un grafo simple como V(G)= p y la cardinalidad del conjunto de líneas del grafo como E(G) = q.

1 comentario: