TEORA DE GRAFOS
LINA MARCELA OCAMPO
LILIANA INS PREZ VELASCO
MATEMTICAS DISCRETAS
LICENCIATURA EN MATEMTICASVI SEMESTRE
ARMENIA, JUNIO 20 DE 2012UNIVERSIDAD DEL QUINDO
TEORA DE GRAFOS
Conceptos Bsicos:Un grafo es un conjunto de puntos (vrtices) en
el espacio, que estn conectados por un conjunto de lneas (aristas).
Algunos conceptos son:
, conjunto de vrtices o nodos. , conjunto de aristas o arcos que
relacionan los nodos.
orden del grafo su nmero de vrtices.
el grado de un vrtice o nodo , es igual al nmero de aristas o
arcos que se encuentran en l.
La longitud de un camino es igual al nmero 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 vrtice en comn; dos
vrtices son adyacentes si una arista los une.
Una arista se dice que es incidente con los vrtices , si esta lo
une al otro.
Grafo dirigido o dgrafo, 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 multgrafo, es un grafo con varias aristas entre dos
vrtices.
Un camino, es una sucesin finita de vrtices y aristas alternos,
donde cada arista tiene por extremos los vrtices adyacentes.
La longitud de un camino es el nmero de aristas que hay en el
camino.
Un camino cerrado es aquel donde coinciden sus extremos .
Un camino simple, es aquel donde todos los vrtices son
diferentes.
Un ciclo, es un camino cerrado donde el primero y el ltimo
vrtice son el mismo (camino simple cerrado).
Un circuito, es un camino cerrado que no repite aristas.
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.
Un grafo es conexo, si para cada par de vrtices 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 vrtices del grafo
sin repetir ninguno.
EJERCICIOS 11.1
1. Enumere tres situaciones, diferentes de las vistas en esta
seccin, en que un grafo pueda ser til.
Clculo de alternativas en juegos: ayudan a determinar
estrategias ganadoras (p.ej. Ajedrez).
Modelacin y resolucin de problemas.
Control de semforos en cruce.
Plano de una planta de un edificio.
Los grafos se utilizan para modelar trayectos como el de una
lnea de autobs a travs 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.
dabcefgFigura 11.7.
Solucin.(a). (b). (c). (d). (e). (e).
3. Para el grafo de la figura 11.7, Cuntos caminos simples
existes de b a f ?
dabcefgFigura 11.7.
Solucin.
Por lo tanto, existen 6 caminos simples de b a f .
4. Cuntos caminos simples diferentes existes entre los vrtices a
y f en el grafo dado en la figura 11.8?
abcdFigura 11.8.
Solucin.
Por lo tanto, hay 8 caminos simples diferentes existentes entre
los vrtices a y f en el grafo.
7. Siete ciudades a, b, c, d, e, f, y g estn 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 contina 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 vrtices para las ciudades y las aristas dirigidas
para los tramos de autopista que las unen, y dibuje un grafo
dirigido que modele esta situacin.
b) Enumere los caminos simples de g a a.
c) Cul es el menor nmero de segmentos de autopista que tendran
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) Cul 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 ms
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 multgrafos G.a). G
tiene 9 aristas y todos los vrtices tienen grado 3.
; Como , entonces: , luego,
3 Vrtices.
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 vrtices de grado 4 y los dems de
grado 3.
; y Como , entonces: , luego,
3 Vrtices, dos de grado 4 y cuatro de grado 3.
3. Sea un grafo conexo no dirigido. a) Cul es el mayor valor ms
grande posible para si y grad para todo ?
Como , entonces: , Se tiene:
El mayor valor ms grande posible para
4. Sea un grafo no dirigido conexo sin lazos, que sea 3-regular
(esto es, cada vrtice de G tiene grado 3). Si , Cunto valen y
?.
,
, entonces:
y
5. Sean y los grafos no dirigidos conexos sin lazos de la figura
11.38.
a). Determine , , y ., , y .
b). Encuentre el grado de cada vrtice de . Haga lo mismo para
cada vrtice de .
. ; ; ; ; ; ; ; ;
. ; ; ; ; ; ; ; ;
tiene 14 aristas con cuatro vrtices de grado 3 y cuatro vrtices
de grado 4. tiene 14 aristas con cuatro vrtices de grado 3 y cuatro
vrtices de grado 4.
c). Son isomorfos los grafos y ?No son isomorfos los grafos; en
los vrtices de grado 4 y forman un ciclo de longitud 4; mientras en
los vrtices de grado 4 y no forman un ciclo de longitud 4 entre
ellos.
6. a). Sea . Dibuje tres grafos no dirigidos sin lazos , y tales
que, en los tres grafos, grad , grad y grad
b). Cuntos de los grafos de la parte (a) son conexos?.El
segundo.
9. Si G es un grafo no dirigido con n vrtices y e aristas, sea y
sea , demuestre que .
16. a). Encuentre un circuito euleriano para el grafo de la
figura 11.40.
a).
b). Si se elimina la arista de este grafo, encuentre un
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.
