MATEMTICAS DISCRETAS

OBJETIVO:
Investigar, las definiciones, teoremas y ejercicios de Grafos, Digrafos, Multigrafos, Grafos Hamiltonianos y Grafos Eulerianos, mediante la indagacin de informacin necesaria en el internet, especialmente en archivos PDF los cuales tienen un contenido abundante acerca de los temas a tratar. Dicha informacin nos permitir comprender y tener una clara idea de lo que son los grafos en general. Adems podremos desarrollar pequeas aplicaciones mediante un lenguaje de programacin.

MARCO TERICO:

GRAFOS
Definiremos un grafo como un sistema matemtico abstracto. Un grafo es un conjunto de puntos y un conjunto de lneas donde une un punto con otro. Los grafos representan conjuntos de objetos que no tienen restriccin de relacin entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vas frreas, circuitos elctricos y enfocado a la informtica nos permiten modelar redes de computadora, estructura de datos. Los grafos se constituyen principalmente de dos partes: las aristas, vrtices y los caminos que pueda contener el mismo grafo.

Definicin formal de un grafo: Llamaremos grafo, G al par ordenado formado por un conjunto finito no vaco, V, y un conjunto, A, de pares no ordenados de elementos del mismo. V, es el conjunto de los vrtices o nodos del grafo. A, ser el conjunto de las aristas o arcos del grafo. Utilizaremos la notacin G= (V, A) para designar al grafo cuyos conjuntos de vrtices y aristas son, respectivamente, V y A.

MATEMTICAS DISCRETAS

A cualquier arista de un grafo se le puede asociar una pareja de vrtices del mismo. Si u y v son dos vrtices de un grafo y la arista a est asociada con este par, escribiremos a =uv. Por ejemplo, si V= {v1, v2, v3, v4, v5} y A = {v1 v2, v1 v3, v1 v2 v4, v2 v5}

Entonces el grafo G=(V,A) tiene a v1, v2, v3, v4 y v5 como vrtices y sus aristas son v1 v2, v1 v3, v1 v2 v4 y v2 v5. Aristas: Son las lneas con las que se unen las aristas de un grafo y con la que se construyen tambin caminos. Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vrtice. Aristas Paralelas: Se dice que dos aristas son paralelas si vrtice inicial y el final son el mismo. Aristas Cclicas: Arista que parte de un vrtice para entrar en el mismo. Cruce: Son dos aristas que cruzan en un punto.

Vrtices: Son los puntos o nodos con los que estn conformados un grafo. Vrtices Adyacentes: Diremos que los vrtices u y v son adyacentes, si existe una arista a tal que a=uv. A los vrtices u y v los llamamos extremos de la arista. Vrtice Aislado: Es un vrtice de grado cero. Vrtice Terminales: Es un vrtice de grado 1.

Caminos: Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesin finita no vaca de aristas {x, v1}, {v1, v2},..., {vn, y}. En este caso

MATEMTICAS DISCRETAS

x e y se llaman los extremos del camino El nmero de aristas del camino se llama la longitud del camino.

Si los vrtices no se repiten el camino se dice propio o simple. Si hay un camino no simple entre 2 vrtices, tambin habr un camino simple entre ellos. Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado. Llamaremos ciclo a un circuito simple Un vrtice a se dice accesible desde el vrtice b si existe un camino entre ellos. Todo vrtice es accesible respecto a si mismo. Clasificacin de Grafos: Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vrtices que representa un arco no est ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco est representado por un par ordenado de vrtices, de forma que y representan dos arcos diferentes. Ejemplos: G1 = (V1, A1) V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} G2 = (V2, A2) V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)} G3 = (V3, A3) V3 = {1, 2, 3} A3 = {<1, 2>, <2, 1>, <2, 3>} Grficamente estas tres estructuras de vrtices y arcos se pueden representar de la siguiente manera:

MATEMTICAS DISCRETAS

Algunos de los principales tipos de grafos son los que se muestran a continuacin: Grafo regular: Aquel con el mismo grado en todos los vrtices. Si ese grado es k lo llamaremos kregular. Por ejemplo, el primero de los siguientes grafos es 3regular, el segundo es 2regular y el tercero no es regular. Grafo bipartito: Es aquel con cuyos vrtices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vrtices pertenecientes al mismo conjunto. Ejemplo. de los dos grafos siguientes el primero es bipartito y el segundo no lo es Grafo completo: Aquel con una arista entre cada par de vrtices. Un grafo completo con n vrtices se denota Kn. A continuacin pueden verse los dibujos de K3, K4, K5 y K6 Un grafo bipartito regular: se denota Km, n donde m, n es el grado de cada conjunto disjunto de vrtices.

A continuacin ponemos los dibujos de K1, 2, K3, 3, y K2, 5 Grafo nulo: Se dice que un grafo es nulo cuando los vrtices que lo componen no estn conectados, esto es, que son vrtices aislados.

MATEMTICAS DISCRETAS

Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunvoca (uno a uno), entre sus vrtices de tal forma que dos de estos quedan unidos por una arista en comn.

Grafos Platnicos: Son los Grafos formados por los vrtices y aristas de los cinco slidos regulares (Slidos Platnicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.

Representacin Grfica: Un grafo se representa mediante un diagrama en el cual a cada vrtice le corresponde un punto y si dos vrtices son adyacentes se unen sus puntos correspondientes mediante una lnea. Ejemplo:

MATEMTICAS DISCRETAS

El grafo de la figura tiene como conjunto de vrtices V = {v1, v2, v3, v4, v5} siendo su conjunto de aristas, A = v1v2, v2v3, v2v5, v3v4, v3v5} Vrtices adyacentes: v1 y v2; v2 y v3; v2 y v5; v3 y v4; v3 y v5.

Vrtices no adyacentes: v1 y v3; v1 y v4; v2 y v4; v4 y v5. _

Representacin de Grafos: Mediante una matriz de adyacencias:

Una de las formas de representar un grafo simple es mediante una de sus matrices de adyacencia. Dado un grafo G = (V, E), para construir una de sus matrices de adyacencias, necesitamos ordenar sus vrtices. Si el grafo tiene n vrtices, |V| = n, y los ordenamos como V = {v1, v2,.vn}, la matriz de adyacencia de G con respecto a esa ordenacin de los vrtices es la matriz A = (aij) de n filas y n columnas determinada por la siguiente condicin.

Ejemplo: Sea G un grafo de orden n. Llamaremos matriz de incidencia de G a la matriz nxn que llamaremos A = (aij) donde aij donde aij = 1 si {i, j} A y aij = 0 en otro caso. La matriz de adyacencia siempre es simtrica porque aij = aij

MATEMTICAS DISCRETAS

Mediante una matriz de incidencias:

Otro modo usual de representar grafos es utilizando matrices de incidencias. Sea G= (V, E) un grafo no dirigido con |V| = n y |E| = m. Sea una ordenacin de los vrtices de G, digamos v1, v2,..., vn, y una ordenacin de las aristas de G, digamos e1, e2,en. La matriz de incidencias de G con respecto a esa ordenacin de los elementos de V y E es la matriz B = (bij) de n filas y m columnas definidas por la siguiente condicin:

Ejemplo: siendo G = ({a, b, c, d}, {{a, b}, {b, c}, {c, d}, {d, a}, {d, b}}), la matriz de incidencia de G con respecto a la ordenacin a, b, c, d de sus vrtices y {a, b}, {b, c}, {c, d}, {d, a}, {d, b} de sus aristas, es la matriz:

EJEMPLOS 1) Sean V = {v1, v2, v3, v4, v5} y A = {v1v2, v1v4, v2v3, v2v5, v3v5, v4v5}. Constryase la representacin grfica del grafo G = (V, A).

MATEMTICAS DISCRETAS

Solucin: Representamos cada uno de los vrtices por un punto y luego cada arista por una lnea que una a dos vrtices que representan los extremos de la misma como muestra la figura. La solucin no es, obviamente, la nica.

2) Si V = {a, b, c, d, e} y E = {{a, b}, {b, d}, {b, e}, {d, e}} entonces (V, E) es un grafo con cinco vrtices a, b, c, d y e y cuatro aristas, y la siguiente figura es su representacin grfica:

3) G = (V, A), con V = {a; b; c; d} y A = {{a, b}; {a, c}; {b, c}; {c, d}}.

MATEMTICAS DISCRETAS

4) G = (V, A), con V = {1, 2, 3, 4, 5} y A = {{1, 2}; {1, 4}; {1,5}; {2, 3}; {2, 4}; {2, 5}; {3, 4}; {4, 5}}.

5) Si seis ciudades las unimos por carretera en todas las formas posibles, el mapa de carreteras resultante es un grafo completo con seis vrtices (las ciudades) y todas las aristas posibles (las carreteras). Se trata del grafo completo K6.

Grafo completo con 6 vrtices El grafo completo Kn tiene (n/2) aristas, que corresponden a las diferentes formas de elegir dos vrtices de entre los n que tiene, es decir el n de combinaciones de n elementos tomados de 2 en 2. 6) Si en una asignatura hay dos grupos de alumnos, V1 = {1, 2, 3} y V2 = {4, 5, 6, 7, 8}, se pretende que hagan un trabajo por parejas formadas por un alumno de cada uno de los grupos, las posibles parejas que pueden formarse son las aristas del grafo bipartito completo K3, 5. Observacin: Es evidente que son intercambiables los papeles de V1 y V2, por tanto Kn, m = Km, n.

MATEMTICAS DISCRETAS

7) G = (V, E) donde V= {1, 2, 3,4} y E = {{1,2}, {1,4}, {1,3}}

8)

V = {1, 2, 3, 4, 5, 6} E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}}

9) Dado el grafo G = (V, E) donde V = {a, b, c, d, e} y E = {ab, bc, be, cd, de, ad}, constryase una representacin grfica de G.

10

MATEMTICAS DISCRETAS

Solucin: Hemos de representar cada vrtice por un punto:

A continuacin se representa cada arista por una lnea uniendo puntos que representen los extremos de dicha arista.

10) G1 = (V1, A1) V1= {1, 2, 3, 4} A1= {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

11

MATEMTICAS DISCRETAS

DIGRAFOS
Definicin formal de un digrafo: Es un grafo en el cual el conjunto de las aristas A est formado por pares ordenados del conjunto de vrtices V. lo llamaremos tambin grafo dirigido, ya que contiene aristas dirigidas, como en el siguiente caso.

Una de las aplicaciones ms importantes es de hallar el camino ms corto hacia un destino, ya sea de una ciudad a otra, de unos departamentos a otros, para el recorrido de rboles, sirve para la representacin de algoritmos, etc. A cada arista se le asigna un orden en sus extremos, en el dibujo se indica con una flecha. Los pares que forman los elementos de E estn ordenandos.

Si G= (V, E) es un digrafo, entonces:

12

MATEMTICAS DISCRETAS

EJEMPLOS
1) En la figura mostramos una representacin grfica del digrafo D = (A, R), siendo A el conjunto {a, b, c, d} y R = {(a, a), (a, c), (b, c)}.

Las aristas son (a, a), (a, c) y (b, c). d es un vrtice aislado. Los grados de entrada son: gre (a) = 1, gre (b) = 0, gre (c) = 2, gre (d) = 0 y los de salida: grs (a) = 2, grs (b) = 1, grs (c) = 0, grs (d) = 0 2) Representar grficamente el digrafo D = (Z+, R), donde R es la relacin definida sobre el conjunto de los nmeros naturales consistente en todos los pares de nmeros de la forma (x, x + 2). Solucin:

13

MATEMTICAS DISCRETAS
R= {(x, x+2): x Z+}

Como Z+ es un conjunto infinito, en la figura hemos hecho un diagrama que, necesariamente, es

3) ({a, b, c}, {(a, b), (a, c), (b, c), (c, b)}), es un digrafo que podemos representar utilizando puntos para representar los vrtices y flechas para representar las aristas.

4) En el grafo G, se verifica que gr+ (a) = 3, gr- (a) = 0, gr+ (c) = 2, gr- (d) = gr+ (d) = 2, gr- (b) =

gr+ (b) = 1, gr+ (e) = 0, gr- (e) = 2.

5) En el grafo H, se verifica que gr- (f) = 1, gr+ (f) = 2, gr+ (g) = 2, gr- (g) = 0, gr- (h) = 2, gr+ (h) = 3.

14

MATEMTICAS DISCRETAS

6) V = {u, v, w, x, y, z} E = { uu, vu, vw, vy, xv, xw, yz, zy}

7) Construya tres digrafos.

8) V = {a, b, c, d} y consideremos la relacin binaria R en V: R= {(a, a), (a, b), (a, c), (b, a), (b, b), (c, c), (c, d), (d, b), (d, c), (d, d)} Entonces el digrafo G asociado tiene a V como conjunto de vrtices y las aristas

15

MATEMTICAS DISCRETAS

dirigidas son los pares de R: G = (V, R)

16

MATEMTICAS DISCRETAS

MULTIGRAFOS
Es un grafo con varias aristas entre dos vrtices.

Definicin formal de un multigrafo: Un multigrafo es un conjunto finito V= {u, v,...} cuyos elementos llamamos los vrtices y otro conjunto finito E= {a, b,...} cuyos elementos llamamos ramas y una funcin que a cada rama le asigna un par no ordenado de vrtices. A los vrtices los representamos por puntos y a las ramas por segmentos o curvas que unen los puntos. Por ejemplo: V= {u, v, w} E= {a, b, c, d, e} y a {u, v} b {v, w} c {u, v} d {v, v}, e{u, w}

Ejemplo:
({1; 2; 3}; ({1; 1}; {1; 2}; {1; 2}; {2; 3}))

Graficamente:

17

MATEMTICAS DISCRETAS

EJEMPLOS
1) E= {a1, a2, a3, a4, a5, a6, a7} (los puentes) V= {A, B, C, D} (los distritos)
a1(A, B) a2(A, B) a3(B, C) a4(B, C) a5 (A, D) a6 (B, D) a7 (C, D)

2) Multigrafo cuyo conjunto de vrtices es: V = {v1, v2, v3} y el de aristas: A = {v1v2, v1v2, v1v3, v1v3, v2v3}

18

MATEMTICAS DISCRETAS

3) Construya dos multigrafos dirigidos.

4) Sea G = (V, A, ) donde V = {1, 2, 3, 4}, A = {a, b, c, d} y est dada por:

5) Multigrafo G = (V, A, ) donde V = {1, 2, 3, 4, 5}, A = {a1, a2, a3, a4, a5, a6} y est dada por:

19

MATEMTICAS DISCRETAS

6) Sea G un Multigrafo con n vrtices v1, v2,. . ., vn. La matriz de adyacencia de G es la matriz M (G) = (aij) nn, donde aij es el nmero de aristas de extremos vi y vj, 1 i, j n.

20

MATEMTICAS DISCRETAS

GRAFOS HAMILTONIANOS
Reciben su nombre del famoso matemtico Sir William Hamilton. No se conocen buenas caracterizaciones para grafos Hamiltoniano. No se conocen algoritmos polinomiales para decidir si un grafo es Hamiltoniano o no. En 1856, Hamilton invent un juego matemtico llamado el dodecaedro del viajero. Tal juego consiste en un dodecaedro cada uno de cuyos veinte vrtices estaba etiquetado con el nombre de una ciudad de la poca. El objetivo del juego era viajar a lo largo de las aristas del dodecaedro, visitando cada ciudad exactamente una vez y volviendo al punto de partida. Tal recorrido se denominaba un viaje alrededor del mundo.

Caminos y Ciclos de Hamilton

21

MATEMTICAS DISCRETAS

Un grafo o multigrafo que contenga un ciclo de Hamilton se denomina Hamiltoniano. Nota.- En trminos de la teora de grafos, el juego consista pues, en encontrar un ciclo de Hamilton en el grafo de la figura anterior. Es claro que el grafo completo Kp es Hamiltoniano, ya que podemos empezar en cualquier vrtice e ir sucesivamente a cualquier otro vrtice todava no visitado. Sin embargo, si ponderamos las aristas de Kp, entonces el problema de encontrar un ciclo de Hamilton con el mnimo peso es difcil. Usualmente se le llama el problema del vendedor viajero, y representa el problema de encontrar como un vendedor puede visitar cada una de las p ciudades en el tiempo ms corto posible. Lo ideal sera encontrar un algoritmo bueno o eficiente que nos permitiese encontrar el ciclo de Hamilton, pero aunque existe abundante literatura sobre este problema, no se conoce ninguno. Camino de Hamilton: Un camino simple en un grafo o multigrafo G que contenga a todos los vrtices se denomina camino de Hamilton. Ejemplo: El grafo de Petersen contiene un camino de Hamilton que comienza en cada uno de sus vrtices. Este grafo es la base de la mayora de los contraejemplos en las conjeturas sobre grafos de Hamilton.

22

MATEMTICAS DISCRETAS

Teorema: Si G = (V, A) un grafo conexo con n 3 vrtices. Si gr (v) n/2, v G, entonces G es Hamiltoniano. Teorema (condicin necesaria): Sea G un grafo conexo. Si existe W C V tal que G / W tiene c componentes conexas con c > lWl entonces G no es Hamiltoniano.

EJEMPLOS
1) Los grafo completo Kn tiene n vrtices, cada uno de los cuales est unido con los n - 1 restantes, por lo que gr (v) = n 1; v Kn. Esto significa, como ya sabamos, que Kn es (n - 1)-regular. Si n 3, se verifica que n - 1 n/2. Como consecuencia entonces del teorema anterior, tenemos que los grafos completos Kn son Hamiltoniano n 3. Es estos casos es fcil hallar un ciclo Hamiltoniano, pues si se representan como en la Figura anterior, es decir, con los vrtices formando un polgono regular, el propio polgono es un ciclo Hamiltoniano.

Grafos completos por lo tanto Hamiltoniano.

2)

Camino Hamiltoniano v6v3v2v4v5v1 Ciclo Hamiltoniano v6v3v2v1v5v4v6 Es grafo Hamiltoniano

23

MATEMTICAS DISCRETAS

3) d (v2) + d (v6)= 6 6; Por lo tanto aadimos la arista (v2, v6); Llamamos G1 al nuevo grafo.

4) d (v2)+d (v6)= 6 6; Por lo tanto aadimos la arista (v2, v6); Llamamos G1 al nuevo grafo. d1 (v6)+d1 (v5)=6 6; grafo. Por lo tanto aadimos la arista (v6, v5); Llamamos G2 al nuevo

5)

Supongamos que existe ciclo Hamiltoniano C d (v5)=2 (v5, v2), (v5, v8) E(C) d (v7)=2 (v7, v2), (v7, v6) E(C) Como (v5, v2), (v7, v2) E(C) (v1, v2), (v2, v3), (v2, v8) E(C) Definimos G=G- (v1, v2), (v2, v3), (v2, v8)} d (v1)=2 (v1, v3), (v1, v6) E(C) d (v8)=2 (v8, v3) E(C)

24

MATEMTICAS DISCRETAS

C=v1v3v8v5v2v7v6v1

6) Construya un grafo Hamiltoniano con las siguientes especificaciones: 1-grafo, V=8, A<=14, Grado (v) <=4 para todo vrtice en V, debe poseer como subgrafo un K3,2 , posea un grafo de orden 5 que sea Hamiltoniano.

7) Cul de los grafos siguientes admite un circuito Hamiltoniano?

Solucin a. No admite circuitos Hamiltonianos. El razonamiento es el siguiente: Si se empieza en v1, v2, v3, v4 y si se est en los dems vrtices, en el v5 se estar dos veces. Si se empieza en v5, para luego ir a los vrtices v1 o v4 a v3 o v2 respectivamente, se tendr que pasar de nuevo por v5 (puesto que se empezar en v5). Para completar el circuito, se debe regresar a v5, por lo que se pasa tres veces por l. b. Un ciclo Hamiltoniano es:

25

MATEMTICAS DISCRETAS

v1 e1 v2 e2 v3 e3 v4 e4 v1

26

MATEMTICAS DISCRETAS

GRAFOS EUROLIANOS
Informalmente, un grafo (digrafo) euleriano es aqul en que pueden recorrerse todas sus las aristas (arcos) de manera consecutiva y sin repetirlas. Si un grafo est formado por dos subgrafos eulerianos unidos al menos por un vrtice y sin aristas en comn, entonces es euleriano. Un grafo conexo G= (V, A) es euleriano todo vrtice tiene grado par. Un grafo conexo tiene un camino abierto euleriano tiene exactamente dos vrtices de grado impar.

Camino euleriano: Es un camino que contiene a todas las aristas del grafo, apareciendo cada una exactamente una vez. Ciclo euleriano: Es un camino euleriano que comienza y acaba en el mismo vrtice. Grafo euleriano: Es un grafo que admite un ciclo euleriano. Ejemplo: Circuito euleriano: a, b, c, d, b, f, d, e, a, c, e, f, a

27

MATEMTICAS DISCRETAS

Cmo saber si un grafo (o multigrafo) es euleriano?

Teorema de Euler:
Un grafo conexo es euleriano no tiene vrtices de grado impar

Ejemplo:

A tiene grado 3el grafo de los puentes no es euleriano. Si el grafo/multigrafo tiene slo dos vrtices de grado impar se llama semieuleriano. Se puede convertir en euleriano aadindole una arista:

Semi-euleriano

euleriano

EJEMPLOS:
1) Este grafo es Euleriano. Un posible circuito euleriano es

28

MATEMTICAS DISCRETAS

C : v1; v2; v3; v4; v5; v3; v6; v7; v1; v3; v7; v2; v6; v1

2) Construir un circuito euleriano para un grafo que tiene todos sus nodos de grado par.

Entrada: G = (V, X) conexo con todos los nodos de grado par. comenzar por cualquier nodo v y construir un ciclo Z mientras exista e X n Z hacer elegir w tal que existe (w; u) Z y (w; z) X n Z desde w construir un ciclo D con D Z = 0; Z = unir Z y D por medio de w fin mientras retornar Z 3) El circuito C = (3, 2, 1, 3, 6, 1, 5, 2, 4, 5, 6, 4, 3). Observacin: Informalmente, un grafo ser euleriano cuando seamos capaces de trazarle de manera continua, sin levantar el lpiz del papel, sin dibujar dos veces la misma arista, y coincidiendo el origen y el extremo.

29

MATEMTICAS DISCRETAS

4) Una posible trayectoria euleriana es: T: u1; u2; u4; u3; u2; u5; u4 http://www.nemediano.com.mx/teoriaGrafos Caminos Euleriano

Grafo transverso 5) C = {1, 2, 3, 4, 6, 3, 5, 4, 1}

30

MATEMTICAS DISCRETAS

CONCLUSIN:
Los grafos en general, son un conjunto de puntos y lneas donde unen un punto con otro, grficamente representamos los vrtices por puntos y las aristas por lneas que los unen. Los grafos nos permiten modelar diversas situaciones reales tales como redes de computadora, circuitos elctricos, redes telefnicas etc. A un grafo se lo puede representar mediante un diagrama o matrices. La teora de grafos es tambin utilizada en la informtica para desarrollar aplicaciones las cuales son enfocadas a resolver problemas tales como la coloracin de un mapa, problemas de redes de comunicacin, diseo de circuitos integrados etc.

BIBLIOGRAFA:
http://docencia.udea.edu.co/regionalizacion/teoriaderedes/informaci%F3n/C3_Ar boles.pdf. (Enero 2008). http://docencia.udea.edu.co/regionalizacion/teoriaderedes/informaci%F3n/C1_Re presentacionMatrices.pdf. (Enero 2008). http://commons.wikimedia.org/wiki/File:Puentes_Konigsberg.jpg?uselang=es?usel ang=es (Mayo 2012).

31