Teoría de Grafos

Teoría de
grafos
MATEMÁTICAS DISCRETAS
JOSÉ ALFONSO OLAYA B.
INTRODUCCIÓN
La teoría de grafos constituye una de las herramientas básicas
para la modelización de fenómenos discretos, se considera la
piedra angular para la fundamentación matemática en varias
áreas de las ciencias de la computación, como la teoría de
cambio y lógica de diseño, la inteligencia artificial, los lenguajes
formales, los gráficos por computadora, los sistemas operativos,
los compiladores y la organización y recuperación de
información; así como también para la comprensión de las
estructuras de datos y el análisis de algoritmos.
Idea intuitiva
Mapa de las
carreteras de
algún lugar
Grafo de las
carreteras de
algún lugar.
Consta de los
puntos (ciudades)
y líneas
(conexiones) que
los unen.
Definición de Grafo
Representación gráfica de los elementos de un conjunto y las
relaciones binarias sobre estos.
Un grafo G =(V, E, ϕ), consta de un conjunto V no vacío de
vértices, un conjunto E de lados del grafo y una funcion ϕ, la
cual es una función de los lados del conjunto E a un conjunto de
pares ordenados o no ordenados de los elementos (repetidos o
no) de V. Donde los conjuntos V y E del grafo son finitos. Por su
parte, la función se conoce como función de incidencia
Ejemplo de grafo
Terminología:
Grafo dirigido
Un grafo dirigido (o dígrafo) G=(V, E)
consta de un conjunto V de vértices y un
conjunto E de lados, tal que cada e ϵ E
esta asociado a un único par ordenado
de vértices i, j ϵ V y se escribe e=(i, j).
La dirección de un lado en un grafo
dirigido se indica mediante una flecha
dirigida.
Grafo no dirigido
Consta de un conjunto V de vértices y un conjunto E de lados
tales que cada lado e está asociado a un par no ordenado de
vértices
Orden y tamaño
En un grafo (dirigido o no dirigido) G=(V, E), el numero de
vértices de G, denotado como |V| o n, se denomina orden del
grafo.
El numero de lados de G, denotado como |E| o m, se conoce
como tamaño del grafo.
orden |V| =8
tamaño |E| =11
Si |V| y |E| son finitos -> un grafo
es finito si su orden y tamaño lo
son.
Grafo finito,
Incidencia y Un lado incide en dos vértices
adyacencia
Dos vértices son adyacentes si

están unidos por un mismo
lado.
Lados paralelos y lazos
Cuando dos o mas lados distintos son
incidentes al mismo par de vértices, estos
reciben el nombre de lados paralelos.
Un lado de la forma (i, i) que inicia y
termina en el mismo vértice se conoce
como lazo
Grafo simple
Un grafo que no tiene lazos ni

lados paralelos.
Valencia de un vértice
Valencia (o grado) de un vértice, v, es igual al numero de lados
incidentes en v, y se denota como δ(v).
La suma de las valencias de todos los vértices de un grafo no
dirigido, es igual al doble del numero de lados
En un grafo dirigido se tendrán valencia de entrada y valencia de
salida.
En el caso de que un vértice sea adyacente consigo mismo, solo
se considerara una vez
Ejemplo
4 +3 +4 +4 +3 =18
|E| =9.
Grafo completo
Si el grafo es simple con n vértices y existe un lado entre cada
par de vértices distintos.
Cada vértice de G debe ser adyacente con todos los demás
vértices del grafo.
Se denota Kn
Grafos completos
Propiedades de los grafos completos
Tiene exactamente n vértices.
La cantidad total de lados del grafo es:
Cada vértice tiene valencia n - 1.
K2
Ejercicio
Verifique las propiedades de los grafos
completos para K6 y K9
Grafo regular
Todo vértice v tiene la misma valencia
El grafo recibe el nombre de n-regular
Grafos regulares
Todo grafo completo Kn es un grafo (n-1)-regular
Tamaño:
Para K6
Grafo bipartita
El conjunto de vértices V se puede dividir en dos conjuntos
disjuntos no vacíos de vértices V1 y V2
Cada vértice del conjunto V1 sea adyacente en los vértices del
conjunto V2.
Grafo bipartita completo
Todos los vértices del conjunto V1 son adyacentes en todos los
vértices del conjunto V2.
El grafo bipartita se denota como Km,n
Ejemplo:
Determinar si es posible conectar tres casas con los números 1,
2 y 3 a los servicios públicos de luz, agua y alcantarillado, de tal
manera que no haya dos líneas de conexión de dichos servicios
que se crucen una con otra.
Subgrafos
Un grafo G1=(V1, E1) es un subgrafo de G si E1 está contenido en
E y V1 está contenido en V, tal que los lados de E1 sean
incidentes en los vértices de V1
Para obtener un subgrafo a partir de un grafo, se requiere:
1. Eliminar lados de G.
2. Eliminar vértices de G, se deben borrar todos los lados que
tengan por extremo a estos vértices.
subgrafo generador y complemento
Caminos y circuitos
Camino sucesión de lados en la cual todos los lados son
distintos entre si.
Camino simple de longitud n de i a j, si es de la forma (v0, v1, v2,
… , vn), donde los vértices son distintos entre si.
Circuito si es un camino de v a v.
Circuito simple si es un circuito de la forma (v0, v1, v2, … , vn),
donde v0 =vn y los demás vértices son distintos entre si.
Ejemplo
Determinar si las siguientes sucesiones de
lados corresponden a un camino, camino
simple, circuito o circuito simple.
1. (v1, v2, v3, v2, v1)

2. (v6, v5, v2, v4, v3, v2, v1)
3. (v6, v5, v2, v4)
4. (v2, v6, v5, v2, v4, v3, v2)
5. (v5, v6, v2, v5)
Caminos y circuitos de Euler (eulerianos)
Camino (paseo) de Euler (o euleriano) es
un camino que incluye todos los lados de
un grafo dado una y solo una vez.
Un circuito de Euler (o euleriano) es un
circuito que incluye todos los lados de un
grafo dado una y solo una vez.
No importa la repetición de vértices,
mientras no se repitan los lados.
Grafo conexo
Un grafo no dirigido; se dice que G es un grafo conexo si, para
cualquier par de vértices i y j distintos entre si, existe un camino
de i a j.
Grafo disconexo:
Condiciones para determinar la existencia de un paseo o
circuito de Euler en un grafo no dirigido
1. Un grafo no dirigido G tiene un camino de Euler si y solo si es
conexo y tiene cero o dos vértices de valencia impar.
2. Un grafo no dirigido G tiene un circuito de Euler si y solo si es
conexo y todo vértice de G tiene valencia par.
3. Un grafo no dirigido G tiene un paseo de Euler de i ≠ j si y solo
si i y j son los únicos vértices de valencia impar. Esta condición
indica que el único paseo de Euler posible en el grafo es iniciar
en uno de los vértices de valencia impar y terminar en el otro o
viceversa.
Ejercicio
Determinar
cuáles de estos
grafos tendrán
un paseo o un
circuito de
Euler.
Paseos y circuitos de Hamilton
(hamiltonianos)
Camino hamiltoniano es un camino que pasa a través de cada
uno de los vértices de un grafo dado exactamente una vez.
Un circuito hamiltoniano es un circuito que pasa a través de
cada uno de los vértices de un grafo dado exactamente una vez.
Al recorrer todos los vértices del grafo, no es importante si no
se recorren todos los lados del grafo
Ejemplo
(v1, v7, v2, v3, v4, v5, v6, v1)

Ejercicio
Halle un circuito
hamiltoniano
Teorema de Dirac
Sea G un grafo no dirigido con n
vértices para n ≥3, tal que todos
los vértices de G tienen valencia
mayor o igual que n/2. Entonces,
G contiene un circuito de
Hamilton.
Ejercicio 1
Todos los siguientes subgrafos
son generadores de K4 ,
excepto:
Ejercicio 2
¿Qué tipo es cada uno de los
siguientes grafos?
Ejercicio 3
¿Cuáles de los siguientes grafos contienen un circuito de Euler?
a) K4 b) K9 c) K6 d) K3
e) K11 f) K2 g) K4 h) K7
Ejercicio 4
¿Cuál de las siguientes sucesiones de
lados es un camino?
a) (v1, v2, v3, v2, v1, v4)
b) (v1, v2, v3, v4, v1, v2)
c) (v1, v2, v3, v4, v5, v3)
d) (v1, v2, v1, v3, v1, v4)
Ejercicio 5
¿Cuál de las siguientes sucesiones de lados
es un circuito simple?
a) (v1, v2, v3, v5, v4, v1)
b) (v1, v2, v3, v4, v3, v1)
c) (v1, v3, v5, v4, v3, v1)
d) (v1, v2, v3, v5, v4, v3, v1)
Ejercicio 6
Determinar cuál de los siguientes grafos tiene en forma
simultánea un circuito de Euler y un circuito de Hamilton.
Problemas:
Muestre que :
1. La sumatoria de los grados (valencia) de todos los vértices de un
grafo es par.
2. En un grafo solo puede existir un un número par de vértices de

grado impar.

Teoría de Grafos

Cargado por

Copyright:

Formatos disponibles

Teoría de Grafos

Cargado por

Información del documento

Título original

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

Teoría de Grafos

Cargado por

Copyright:

Formatos disponibles

Teoría de

Dos vértices son adyacentes si

Un grafo que no tiene lazos ni

1. (v1, v2, v3, v2, v1)

(v1, v7, v2, v3, v4, v5, v6, v1)

2. En un grafo solo puede existir un un número par de vértices de

También podría gustarte