• Author / Uploaded
• lipeve26

Citation preview

TEORÍA DE GRAFOS

LINA MARCELA OCAMPO

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

MATEMÁTICAS DISCRETAS

LICENCIATURA EN MATEMÁTICAS VI SEMESTRE

ARMENIA, JUNIO 20 DE 2012 UNIVERSIDAD 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: *

+, conjunto de vértices o nodos.

)( )( *( relacionan los nodos. | |

)(

orden del grafo

)+, conjunto de aristas o arcos que su número de vértices.

el grado de un vértice o nodo aristas o arcos que se encuentran en él.

, es igual al número de

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. ) se dice que es incidente con los vértices ( Una arista ( esta lo une al otro.

), si

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 ).

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.

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: estrategias ganadoras (p.ej. Ajedrez).

ayudan

a

determinar

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. b

e

f

a

g c

d Figura 11.7.

Solución. (a). * + * (b). * + * (c). * + * (d). * + * (e). * + * (e). * + *

+* +* + +* +* +*

+* +*

+* +*

+* +

+* +* +*

+* +* +

+ +*

+*

+

+*

+

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

e

f Figura 11.7.

a

g c

Solución.  * +* +*  *  * +*  * +* +*  * +*  *

+ +* +* +* +* +*

d

+ +* +* +* +*

+ +* +* +*

+ + +*

+

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? a

b

Figura 11.8. d

c

Solución. * +*  * +*  * +*  * +* 

+* +* +* +*

+ + + +

   

* * * *

+ + + +

* * * *

+* +* +* +*

+ + +* +*

+* +*

+ +

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. * +* + * +* +* + * +* +* + * +* +* +* +* + * +* +* + * +* +* +* +

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?  Una de * + * + +* +* +  Otra de * +* +  Otra de * 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 | | para los siguientes grafos o multígrafos G. a). G tiene 9 aristas y todos los vértices tienen grado 3.

| | | | ; ( ) ∑ ( ) | |, entonces: | | Como 3| | | | | |

, luego,

| | | |

Vértices.

b). G es regular con 15 aristas. | | ; ∑ Como

( ) ( ) | | | | | |

| | | |, entonces: | |

, luego,

| | ⁄

Ahora, cuando , | | ; , | | ; , | | ; , | | ; , | | ; , | | ; , | | ; , | | ; 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.

| | ; Como ∑

( ) ( )

| | y ( ) | | | |, entonces: | |

, luego,

| | | | 3| | | | | | ⁄ | | Vértices, dos de grado 4 y cuatro de grado 3.

| |

( ) un grafo conexo no dirigido. Sea a) ¿Cuál es el mayor valor más grande posible para | | si | | y grad ( ) para todo ?

3.

Como ∑ Se tiene:

( ) | | | | | |

| |, entonces: | | | |

,∑

( )

| |

El mayor valor más grande posible para | | ( ) un grafo no dirigido conexo sin lazos, que sea 4. Sea | | 3-regular (esto es, cada vértice de G tiene grado 3). Si | | , ¿Cuánto valen | | y | |?. | |

| |

∑

( ) ( )| | | | | |

, ( ) | |, entonces: | | ( | | | |

)

| | | | | |

| | ( )

| |

| | | |

| |

( )y 5. Sean lazos de la figura 11.38.

(

y | |

) los grafos no dirigidos conexos sin

a). Determine | |, | |, | | y | |. | | , | | , | | y | |

.

b). Encuentre el grado de cada vértice de para cada vértice de . .

.

. Haga lo mismo

( ) ( )

; ;

( ) ( )

; ;

( ) ( )

; ;

( )

;

( )

;

( ) ( )

; ;

( ) ( )

; ;

( ) ( )

; ;

( )

;

( )

;

tiene 14 aristas con cuatro vértices de grado 3 y cuatro vértices de grado 4. tiene 14 aristas con cuatro vértices de grado 3 y cuatro vértices de grado 4. c). ¿Son isomorfos los grafos y ? No son isomorfos los grafos; en los vértices de grado 4 ( y ) forman un ciclo de longitud 4; mientras en los

vértices de grado 4 ( entre ellos. * 6. a). Sea ( ), lazos grafos, grad ( ) ( ) ( )

y

+. ( , ( )

) no forman un ciclo de longitud 4

Dibuje tres grafos no dirigidos sin ) y ( ) tales que, en los tres ( ) grad ( ) y grad

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 * ( )+ * ( )+, demuestre que y sea ( ⁄ ) .

16. a). 11.40.

Encuentre un circuito euleriano para el grafo de la figura

a). *



+*

+*

+*

+*

+*

+*

+*

+*

+

+ de este grafo, encuentre un b). Si se elimina la arista * recorrido euleriano para el subgrafo resultante. *

+*

+*

+*

+*

+*

+*

+

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.