Semana 13 Teoría de Grafos

UNIVERSIDAD ESPÍRITU SANTO
MATEMÁTICAS DISCRETAS
Unidad 9: Teoría de Grafos
▪ Introducción a los Grafos

▪ Trayectorias y ciclos
Ing. Jonnathan Bravo Moreno, MSc.

Introducción a los Grafos
Figura 1
Cierta persona es responsable de inspeccionar el sistema de

carreteras de Wyoming. En particular, el inspector de carreteras debe
recorrerlas y entregar informes de las condiciones de los caminos, la
visibilidad de las líneas pintadas, el estado de las señales, etcétera.
Como el inspector vive en Greybull, la manera más económica de
inspeccionar todos los caminos sería comenzar en Greybull, recorrer
cada carretera exactamente una vez y regresar a Greybull.
¿Es esto posible?

El problema se puede modelar como una Gráfica.
Los puntos se llaman vértices y las líneas que conectan a los vértices
se llaman aristas.
Si se inicia en el vértice v0 , se viaja por una arista al vértice v1 , por
otra arista al vértice v2 , etcétera, y con el tiempo se llega al vértice vn ;
este viaje completo recibe el nombre de trayectoria o ruta de v0 a vn .
¿Existe una ruta del vértice Gre al vértice Gre que pase una
vez por todas las aristas?
Se dice que los Vértices son adyacentes cuando están

conectados por una arista.
La gráfica (no dirigida) G consiste en el conjunto de
vértices:
y el conjunto de aristas:
La figura muestra una gráfica dirigida. Las aristas
dirigidas se indican por flechas. La arista e1 se asocia con
el par ordenado de vértices (v2, v1) y la arista e7 se asocia
con el par ordenado de vértices (v6, v6). La arista e1 se
denota (v2, v1), y la arista e7 se denota (v6, v6).
Con frecuencia en la manufactura, es necesario hacer agujeros en hojas de metal.

Luego se atornillan las componentes a estas hojas de metal. Los agujeros se perforan
usando un taladro controlado por computadora. Para ahorrar tiempo y dinero, el
taladro debe moverse tan rápido como sea posible. Se modelará la situación como
una gráfica.
Los vértices de la gráfica

corresponden a los agujeros.
Cada par de vértices se
conecta por una arista. En cada
arista se escribe el tiempo para
mover el taladro entre los
hoyos correspondientes.
Una gráfica con números en las aristas se llama gráfica ponderada. Si

la arista e se etiqueta k, se dice que el peso de la arista e es k.
En una gráfica ponderada, la longitud de una ruta es la suma de los

pesos de las aristas en la ruta.
Una ruta de longitud mínima que visita todos los vértices exactamente u
vez representa la ruta óptima que debe seguir el taladro.
Encuentre la ruta óptima que comience en el vértice a y termine en el vértice e.

Ejercicios
Ejercicios
En una gráfica de precedencias, los vértices modelan ciertas
acciones. Por ejemplo, un vértice puede modelar una instrucción
en un programa de computadora. Hay una arista del vértice v al
vértice w si la acción modelada por v debe ocurrir antes que la
acción modelada por w. Dibuje una gráfica de precedencias para
el siguiente programa de computadora.
Ejercicios
En una gráfica de precedencias, los vértices modelan ciertas
acciones. Por ejemplo, un vértice puede modelar una instrucción
en un programa de computadora. Hay una arista del vértice v al
vértice w si la acción modelada por v debe ocurrir antes que la
acción modelada por w. Dibuje una gráfica de precedencias para
el siguiente programa de computadora.
Trayectorias y ciclos
El formalismo de la definición significa: Comience en el vértice v0 ;

recorra la arista e1 hasta v1 ; siga por la arista e2 hasta v2 , y así
sucesivamente.
En la gráfica de la figura es una trayectoria de longitud 4
del vértice 1 al vértice 2:
La trayectoria
(6) que
consiste sólo
en el vértice 6
es una
trayectoria de
longitud 0 del
vértice 6 al
vértice 6.
La gráfica Sí es conexa
La gráfica G no es conexa ya que, por ejemplo,

no hay trayectoria del vértice v2 al vértice v5
Una gráfica conexa es de una “pieza”, mientras que una gráfica no
conexa consiste en varias “piezas”. Estas “piezas” son subgráficas de
la gráfica original y se llaman componentes.
Una subgráfica G de una gráfica G se obtiene seleccionando ciertas

aristas y vértices de G sujetas a la restricción de que si se
selecciona una arista e en G que incide en los vértices v y w, deben
incluirse v y w en G . La restricción asegura que G sea de hecho
una gráfica.
Una subgráfica de la gráfica de la figura es:

Si no se seleccionan aristas, se puede seleccionar uno o los
dos vértices, lo que lleva a las subgráficas G1 , G2 y G3. Si se
selecciona la única arista disponible e1 , deben seleccionarse
los dos vértices en los que e1 es incidente. En este caso, se
obtiene la subgráfica G4 de la figura. Entonces G tiene las
cuatro subgráficas
Rutas y ciclos de Hamilton y Euler
Sir William Rowan Hamilton comercializó un juego a mediados

del siglo XIX en la forma de un dodecaedro (figura 1). Cada
esquina tiene el nombre de una ciudad y el problema era
comenzar en cualquier ciudad, viajar por las aristas, visitar cada
ciudad justo una vez y regresar a la ciudad inicial. La gráfica de
las aristas del dodecaedro se reproduce en la figura 2. El juego
de Hamilton se resuelve si se encuentra un ciclo en la gráfica
que contenga cada vértice justo una vez (excepto por el vértice
inicial y final, que aparece dos veces).
En honor a Hamilton, un ciclo en la gráfica G que contiene cada

vértice en G justo una vez, excepto por el vértice inicial y final que
aparece dos veces, recibe el nombre de ciclo hamiltoniano.
Un ciclo de Euler visita cada arista una vez, mientras que un ciclo
de Hamilton visita cada vértice una vez. Además tiene un grado
impar de vértices por lo que no es ciclo de Euler.
Una gráfica tiene un ciclo de Euler si y sólo si G es conexa y todo vértice tiene grado
par.
La siguiente figura tiene un ciclo de Hamilton?
El problema del agente viajero se relaciona con el problema de
encontrar un ciclo hamiltoniano en una gráfica.. El problema es:
Dada una gráfica ponderada G, encuentre en G un ciclo de Hamilton
con longitud mínima. Si se piensa en los vértices de una gráfica
ponderada como ciudades y en los pesos de las aristas como
distancias, el problema del agente viajero consiste en encontrar una
ruta más corta en la que el agente viajero pueda visitar cada ciudad
una vez, comenzando y terminando en la misma ciudad.
El ciclo C = (a, b, c, d, a) es un
ciclo hamiltoniano de longitud
mínima para G.

Semana 13 Teoría de Grafos

Cargado por

Copyright:

Formatos disponibles

Semana 13 Teoría de Grafos

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Semana 13 Teoría de Grafos

Cargado por

Copyright:

Formatos disponibles

UNIVERSIDAD ESPÍRITU SANTO

Unidad 9: Teoría de Grafos

▪ Introducción a los Grafos

Ing. Jonnathan Bravo Moreno, MSc.

Cierta persona es responsable de inspeccionar el sistema de

¿Es esto posible?

Se dice que los Vértices son adyacentes cuando están

Con frecuencia en la manufactura, es necesario hacer agujeros en hojas de metal.

Los vértices de la gráfica

Una gráfica con números en las aristas se llama gráfica ponderada. Si

En una gráfica ponderada, la longitud de una ruta es la suma de los

Encuentre la ruta óptima que comience en el vértice a y termine en el vértice e.

El formalismo de la definición significa: Comience en el vértice v0 ;

La gráfica G no es conexa ya que, por ejemplo,

Una subgráfica G de una gráfica G se obtiene seleccionando ciertas

Una subgráfica de la gráfica de la figura es:

Sir William Rowan Hamilton comercializó un juego a mediados

En honor a Hamilton, un ciclo en la gráfica G que contiene cada

También podría gustarte