grafos

TEORÍA DE GRAFOS

LINA MARCELA OCAMPO

EDWIN FABIAN MARTÍNEZ LILIANA INÉS PÉREZ VELASCO

MATEMÁTICAS DISCRETAS

LICENCIATURA EN MATEMÁTICASVI SEMESTRE

ARMENIA, JUNIO 20 DE 2012UNIVERSIDAD DEL QUINDÍO

TEORÍA DE GRAFOS

Conceptos Básicos: Un grafo es un conjunto de puntos (vértices) en el espacio, que están conectados por un conjunto de líneas (aristas). Algunos conceptos son:

V= {a ,b , c , d , e }, conjunto de vértices o nodos.

E={(a ,a ) (a ,b ) (a ,d ) (b , c ) }, conjunto de aristas o arcos que relacionan los nodos.

|V|=¿ orden del grafo ¿ su número de vértices.

grad=¿ el grado de un vértice o nodo V , es igual al número de aristas o arcos E que se encuentran en él.

La longitud de un camino es igual al número de aristas que hay en él.

Un bucle es una arista que relaciona al mismo nodo, es decir, una arista donde el nodo inicial y el nodo final coinciden.

Dos aristas son adyacentes si tienen un vértice en común; dos vértices son adyacentes si una arista los une.

Una arista ( x , y ) se dice que es incidente con los vértices ( x , y ), si esta lo une al otro.

Grafo dirigido o dígrafo, es aquel en el que a cada arista se le asigna un orden en sus extremos, en la figura se indica con una flecha.

Un multígrafo, es un grafo con varias aristas entre dos vértices.

Un camino, es una sucesión finita de vértices y aristas alternos, donde cada arista tiene por extremos los vértices adyacentes.

La longitud de un camino es el número de aristas que hay en el camino.

Un camino cerrado es aquel donde coinciden sus extremos (V 0=V n ).

Un camino simple, es aquel donde todos los vértices son diferentes.

Un ciclo, es un camino cerrado donde el primero y el último vértice son el mismo (camino simple cerrado).

Un circuito, es un camino cerrado que no repite aristas.

Dos grafos son isomorfos, cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

Un grafo es conexo, si para cada par de vértices existe un camino que los conecta (ida-regreso), en caso contrario se dice que es desconexo.

Un camino euleriano, es un camino que conecta todas las aristas, apareciendo cada una de ellas una sola vez, si sus extremos coinciden, entonces decimos que es un circuito euleriano.

Un Ciclo hamiltoniano, es un camino hamiltoniano cerrado, es decir, es un camino simple que contiene todos los vértices del grafo sin repetir ninguno.

d

a

b

c

e f

g

Figura 11.7.

EJERCICIOS 11.1

1. Enumere tres situaciones, diferentes de las vistas en esta sección, en que un grafo pueda ser útil.

Cálculo de alternativas en juegos: ayudan a determinar estrategias ganadoras (p.ej. Ajedrez).

Modelación y resolución de problemas.

Control de semáforos en cruce.

Plano de una planta de un edificio.

Los grafos se utilizan para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto.

2. Para el grafo de la figura 11.7, determine:(a) Un camino de b a d que no sea recorrido;(b) Un recorrido b-d que no sea un camino simple;(c) Un camino simple de b a d;(d) Un camino cerrado de b a b que no sea un circuito;(e) Un circuito de b a b que no sea un ciclo; y, (f) Un ciclo de b a b.

d

a

b

c

e f

g

Figura 11.7.

a b

cd

Figura 11.8.

Solución.(a). {b , e } , {e , f }, {f , g } , {g ,e } , {e ,b }, {b , c } , {c ,d }(b). {b , e } , {e , f }, {f , g } , {g ,e } , {e ,d }(c). {b , c } , {c ,d }(d). {b , e } , {e , f }, {f , g } , {g ,e } , {e ,b }(e). {b , e } , {e , f }, {f , g } , {g ,e } , {e ,d } , {d , c } , {c ,b }(e). {b , c } , {c ,d } , {d ,e } , {e ,b }

3. Para el grafo de la figura 11.7, ¿Cuántos caminos simples existes de b a f ?

Solución.J {b , e } , {e , f }J {b , e } , {e ,g } , {g , f }J {b , c } , {c ,d } , {d , e } , {e , f }J {b , c } , {c ,d } , {d ,e } , {e , g } , {g , f }J {b ,a }, {a , c } , {c ,d } , {d , e} , {e , f }J {b ,a }, {a , c } , {c ,d } , {d , e} , {e , g } , {g , f }

Por lo tanto, existen 6 caminos simples de b a f .

4. ¿Cuántos caminos simples diferentes existes entre los vértices a y f en el grafo dado en la figura 11.8?

Solución.J {a ,b }, {b , g } , {g , f }J {a ,h }, {h , e }, {e , f }J {a ,h }, {h , g } , {g , f }J {a ,d } , {d ,c }, {c , f }

J {a ,b }, {b , c } , {c , f }J {a ,d } , {d ,e } , {e , f }J {a ,b }, {b , c } , {c ,d } , {d , e} , {e , f }J {a ,d } , {d ,c }, {c ,b } , {b ,g }, {g , f }

Por lo tanto, hay 8 caminos simples diferentes existentes entre los vértices a y f en el grafo.

7. Siete ciudades a, b, c, d, e, f, y g están conectadas por un sistema de autopistas como sigue:

(1) I-22 va de a a c, pasando por b;(2) I-33 va de c a d, y entonces pasa por b y continúa hacia f;(3) I-44 va de d por e hacia a;(4) I-55 va de f a b, pasando por g; y,(5) I-66 va de g a d;

a) Use los vértices para las ciudades y las aristas dirigidas para los tramos de autopista que las unen, y dibuje un grafo dirigido que modele esta situación.

b) Enumere los caminos simples de g a a.J {g ,b } , {b ,a }J {g , f }, {f , b }, {b ,a }J {g ,d } , {d , e } , {e ,a }J {g ,b } , {b , c }, {c ,d } , {d , e } , {e ,a }J {g ,d } , {d ,b }, {b ,a }J {g ,d } , {d ,c } , {c ,b }, {b ,a }

c) ¿Cuál es el menor número de segmentos de autopista que tendrían que cerrarse para interrumpir el paso de b a d?

J Una de {b , c } , {c ,d }J Otra de {b , f } , {f , g }, {g ,d }J Otra de {b , g } , {g ,d }

d) ¿Es posible salir de la ciudad c y regresar a ella, visitando una sola vez las otras ciudades? No.

e) ¿Cuál es la respuesta de la parte (d) si no es necesario regresar a c?Si.

f) ¿Es posible comenzar en alguna ciudad y viajar por todas las autopistas exactamente una vez? (Se permite visitar una ciudad más de una vez y no es necesario regresar a la ciudad donde se inició el recorrido.) Si.

10. Dé un ejemplo de un grafo conexo G tal que al eliminar cualquier arista de G se obtenga un grafo disconexo.

EJERCICIOS 11.3.

1. Determine |V| para los siguientes grafos o multígrafos G.a). G tiene 9 aristas y todos los vértices tienen grado 3.

|E|=9; g (v )=3|V|Como ∑

ʋ∈V

g ( v )=2|E|, entonces: 2|E|=18, luego,

3|V|=2|E| |V|=18/3 |V|=6 ∴|V|=6 Vértices.

b). G es regular con 15 aristas.

|E|=15; g (v )=x|V| Como ∑

ʋ∈V


x|V|=2|E| x|V|=30 |V|=30/ x

Ahora, cuando x=1, |V|=30; x=2, |V|=15; x=3, |V|=10; x=5, |V|=6; x=6, |V|=5; x=10, |V|=3;x=15, |V|=2;x=30, |V|=1; en este caso G es un grafo disconexo.

c). G tiene 10 aristas con dos vértices de grado 4 y los demás de grado 3.

|E|=10; g (v )=4|V| y g (v )=3|V| Como ∑

ʋ∈V


3|V|=2|E|−4|V| 3|V|=20−8 |V|=12/3 |V|=4

∴|V|=6 Vértices, dos de grado 4 y cuatro de grado 3.

3. Sea G= (V , E ) un grafo conexo no dirigido. a) ¿Cuál es el mayor valor más grande posible para |V| si |E|=19 y grad (ʋ )≥4 para todo ʋ∈V?

Como ∑ʋ∈V

g ( v )=2|E|, entonces: 2|E|=38, ∑ʋ∈V

g ( v )≥4|V|

Se tiene: 4|V|=2|E| |V|=38/ 4 |V|=9.5

∴ El mayor valor más grande posible para |V|=9

4. Sea G= (V , E ) un grafo no dirigido conexo sin lazos, que sea 3-regular (esto es, cada vértice de G tiene grado 3). Si |E|=2|V|−6, ¿Cuánto valen |V| y |E|?.

|E|=2|V|−6, g (v )=3

∑ʋ∈V

g ( v )=2|E|, entonces:

g (v )|V|=2|E| |E|=2|V|−6 3|V|=2 (2∨V∨−6 ) |E|=2 (12 )−6

3|V|=4∨V∨−12 |E|=18 3|V|−4∨V∨¿−12 |V|=12 ∴ |V|=12 y |E|=18

5. Sean G1=(V 1 , E1 ) y G2=(V 2, E2 ) los grafos no dirigidos conexos sin lazos de la figura 11.38.

a). Determine |V 1|, |E1|, |V 2| y |E2|.|V 1|=8, |E1|=14, |V 2|=8 y |E2|=14.

b). Encuentre el grado de cada vértice de V 1. Haga lo mismo para cada vértice de V 2.

V 1. grad (a )=3; grad (b )=4; grad (c )=4; grad (d )=3; grad (e )=3; grad (f )=4; grad (g )=4; grad (h )=3;

V 2. grad (s )=3; grad (t )=4; grad (u )=4; grad (v )=3; grad (w )=4; grad (x )=3; grad ( y )=3; grad (z )=4;

G1 tiene 14 aristas con cuatro vértices de grado 3 y cuatro vértices de grado 4.

G2 tiene 14 aristas con cuatro vértices de grado 3 y cuatro vértices de grado 4.

c). ¿Son isomorfos los grafos G1 y G2?No son isomorfos los grafos; en G2 los vértices de grado 4 ¿yz ¿ forman un ciclo de longitud 4; mientras en G1 los vértices de grado 4 ¿yg¿ no forman un ciclo de longitud 4 entre ellos.

6. a). Sea V= {a ,b , c ,d , e , f }. Dibuje tres grafos no dirigidos sin lazos G1=(V , E1 ), G2=(V , E2 ) y G3=(V , E3 ) tales que, en los tres grafos, grad (a )=3, grad (b )=grad (c )=2 y grad (d )=grad (e )=grad ( f )=1 .

b). ¿Cuántos de los grafos de la parte (a) son conexos?.El segundo.

9. Si G es un grafo no dirigido con n vértices y e aristas, sea

δ=m í nn∈V {grad (ʋ ) } y sea ∆=má xnϵV {grad (ʋ ) }, demuestre que δ ≤( en )≤∆.

16. a). Encuentre un circuito euleriano para el grafo de la figura 11.40.

J a). {a ,d } , {d ,h } , {h , i } , {i , j } , { j ,e } , {e , f }, { f , b }, {b ,g }, {g ,c }

b). Si se elimina la arista {d , e } de este grafo, encuentre un recorrido euleriano para el subgrafo resultante.

{a ,b }, {b ,g },{g , j},{ j , i},{i , h }, {h ,d },{d ,a }

EJERCICIOS 11.5.

1. Dé un ejemplo de un grafo conexo tal que:

a). no tenga circuitos eulerianos ni ciclos hamiltonianos;

b). tenga un circuito euleriano pero no tenga ciclo hamiltonianos;

c). tenga un ciclo hamiltoniano pero no un circuito euleriano;

d). tenga un ciclo hamiltoniano y un circuito euleriano.

Documents

grafos