Estructuras Discretas

GRAFOS

0.1.

Grafos no dirigidos

Definici´n 0.1.1 Un grafo (no dirigido) es una tr´ada de objetos G = o ı (V, A, f ), donde 1. V es un conjunto, cuyos elementos se llaman v´rtices de G e 2. A es un conjunto, cuyos elementos se llaman aristas de G 3. f es una funci´n, llamada funci´n de incidencia, que asigna a cada o o arista x de A un par no ordenado de v´rtices {vi , vj } de v´rtices (noe e necesariamente distintos), llamados extremos de la arista x. En tal caso se escribe f (x) = {vi , vj }

y se dice que la arista x incide en el v´rtice vi y en el v´rtice vj e e Si vi = vj , se escribe f (x) = {vi } y decimos que x es un lazo

Ejemplo 0.1.1 Graficar el grafo G = (V, A, G), donde 1. V = {v1 , v2 , v3 , v4 , v5 } 2. A = {a, b, c, d, e, f, g} 3. f viene dada por a) f (a) = {v1, v3 } 1

b) f (b) = {v1 } c) f (c) = {v4 , v3 } d) f (d) = {v1 , v3 } e) f (e) = {v5 , v2 } f) f (f ) = {v2 , v4 } g) f (g) = {v1 , v4 }

Definici´n 0.1.2 Sea G = (V, A, f ) un grafo. Diremos que: o 1. El n´mero de incidencia de una arista aj en un v´rtice vi es: u e a) 0, si la arista aj no incide en el v´rtice vi e b) 1, si la arista aj incide en el v´rtice vi y no es un lazo e c) 2, si laarista aj incide en el v´rtice vi y es un lazo e 2. Un v´rtice vi es adyacente a un v´rtice vj , si existe una arista que e e tenga por extremos a vi y vj . Si vi es adyacente a vj , entonces vj es adyacente a vi , por lo que es com´n decir en tal caso que vi y vj son u adyacentes 3. El grado de un v´rtice vi , denotado por gr(vi ), es el n´mero de aristas e u de G que inciden en vi , en donde unlazo que incide en vi es contado dos veces. Si un v´rtice tiene grado 0, decimos que el v´rtice es aislado e e

2

4. Si V = {v1 , ..., vn }, la matriz de adyacencia de G, denotada por MG , es la matriz MG = [aij ]nxn donde aij es igual al n´mero de aristas que conectan vi y vj u 5. Si V = {v1 , ..., vn }, A = {a1 , ..., am }, la matriz de incidencia de G, denotada por IG , es la matriz IG =[bij ]nxm donde bij es igual al n´mero de incidencia de la arista aj en el v´rtice u e vi 6. Una cadena de G, denotada por (w0 , b1 , w1 , b2 , w2 , ..., bk , wk ), es una sucesi´n alternada de v´rtices (wi ) y aristas (bj ) de G de la forma o e antes escrita que comienza y t´rmina con un v´rtice, y tal que cumple e e las siguientes condiciones: a) Cada arista tiene por extremos el v´rtice que loantecede y el e v´rtice que lo sigue e b) Las aristas (de la cadena) son todas distintas Al n´mero k de arisu tas se le llama longitud de la cadena. A w0 se le llama v´rtice e inicial de la cadena y a wk se le llama v´rtice final de la cadena e Una cadena tambi´n puede denotarse m´s simplemente mediante e a la sucesi´n de sus v´rtices (w0 , w1 , w2 , ..., wk ), o la sucesi´n de sus o e o aristas(b1 , b2 , ..., bk ) 7. Una cadena simple es una cadena que tiene todos sus v´rtices dise tintos 8. Un ciclo es una cadena que tiene al menos una arista y tal que el v´rtice inicial y el v´rtice final de la cadena son iguales (w0 = wk ). Si e e todos sus v´rtices son distintos, excepto el inicial y el final, se dice que e el ciclo es simple 9. vi es accesible desde vj , si existe una cadena que tienea vi como v´rtice inicial y a vj como v´rtice final. Si vi es accesible desde vj , ene e tonces vj es accesible desde vi , m´s a´n esta es una relaci´n de equiva u o alencia 3

Ejemplo 0.1.2 Si G es el grafo del ejemplo anterior, entonces 1. El n´mero de incidencia de a en v1 y v3 es 1, mienstras que el n´mero u u de incidencia de a en v2 , v4 , v5 es 0. El n´mero de incidencia de b en u v1 es2 2. Los v´rtices v1 y v3 son adyacentes, tambi´n lo son v5 y v2 . v1 y v2 no e e son adyacentes 3. gr(v1 ) = 5, gr(v2 ) = 2, gr(v3 ) = 3, gr(v4 ) = 3, gr(v5 ) = 1 (no hay v´rtices aislados) e 4.    MG =    1 0 2 1 0 0 0 0 1 1 2 0 0 1 0 1 1 1 0 0 0 1 0 0 0      

5. Tomaremos el orden de las aristas de forma natural a, b, c, d, e, f, g   1 2 0 1 0 0 1  0 0 0 0 1 1 0    IG = ...