Grafos

Matemática Discreta
Universidad Mariano Gálvez
Ing. Leonel Arrecis

Agenda
Unidad 4: Teoría de Grafos.
Definiciones de Grafos.
Subgrafos, Complementos e Isomorfismo

Teoría de Grafos
La teoría de grafos tiene un inicio preciso: Un

articulo publicado en 1736 por el matemático
suizo Leonhard Euler (1707 – 1783). La idea
principal en que se apoya su trabajo surgió de
un problema ahora muypopular, conocido
como los siete puentes de Königsberg.
A partir de su solución, se desarrollaron los

conceptos fundamentales de la teoría de
grafos que veremos a continuación.

Definiciones
Cuando utilizamos

un mapa de carreteras,
nos interesa ver como llegar de un pueblo a
otro, por medio de las carreteras que se
indican en el mapa. Tratamos con 2 clases de
objetos: pueblos y carreteras.

SiV denota el conjunto de pueblos y A el

conjunto de carreteras, podemos definir una
relación R sobre V como aRb si podemos
viajar de a a b usando solamente las
carreteras de A.

Definiciones
Por Ejemplo: Esta figura muestra las formas

posibles de viajar entre 6 pueblos usando las
ocho carreteras indicadas.
Pueblos = {a,b,c,d,e,f}
Carreteras = {{a,b},{a,c},{c,b},…{e,f}}

Definiciones
Ungrafo se representa gráficamente como un

conjunto de puntos (llamados vértices o
nodos), unidos por líneas (aristas). Los grafos
permiten estudiar las interrelaciones entre
unidades que se encuentran en interacción.

Definiciones
Son diagramas que si se interpretan en forma

adecuada proporcionan información, como por
ejemplo los mapas, diagramas de circuitos, o
de flujos entre otros.Definiciones
Un grafo esta compuesto por dos conjuntos

finitos:
Un conjunto de |V| (vértices)
Un conjunto de |E| (aristas)
Y j es la relación de incidencia, que asocia a

cada elemento de |E| un par de elementos de |
V|.
Se denota G={V,E,j}

Grafo
Entre las aplicaciones mas importantes de los

grafos podemos mencionar:
Rutas entre ciudades.
Determinar tiempos máximos y mínimos en un

proceso.Flujo y control en un programa.

Grafo Dirigido o Dígrafo
Definición: Sea V un conjunto finito no vacio,

y sea E⊆VxV. El par (V,E) es un grafo dirigido
(sobre V), o dígrafo (sobre V), donde V es el
conjunto de vértices, o nodos y E es su
conjunto de aristas.
Escribimos G=(V,E) para denotar tal dígrafo.
Son aquellos en los cuales los lados están

orientados (flechas).

Ejemplo de Dígrafo
La figuraproporciona un ejemplo de un grafo

dirigido sobre V = {a, b, c, d, e} con E={(a,a),
(a,b),(a,d),(b,c)}.
La dirección de una arista se indica al colocar
Para
por ejemplo
unacualquier
flecha arista,
dirigida
sobre
(b,c), decimos que la arista es
incidente con los vértices b, c;
La arista (a,a) es un ejemplo de un
1) b es adyacente hacia c
lazo, y el vértice e que no tiene
2) c es adyacente desdeb
aristas incidentes es un vértice
3) el vértice b es el origen o
aislado.
fuente
4) el vértice c es el vértice
terminal

ella.

Grafo no Dirigido
Cuando no importa la dirección de las aristas,

la estructura G = (V,E), donde E es ahora un
conjunto de pares no ordenados sobre V, es
un grafo no dirigido.

Grafo No Dirigido
En un grafo no dirigido, hay aristas no

dirigidas, como las aristas{a,b}, {b,c}, {a,c},
{c,d} de la figura a. Una arista como {a,b}
representa {(a,b),(b,a)}.
(a,b) = (b,a)
Solo si a = b

{a,b} = {b,a}
Para todos a,b

Camino
Definición:

Sean
x,
y
vértices
(no
necesariamente distintos) de un grafo no
dirigido G = (V,E). Un Camino x - y en G, es
una sucesión alternada finita (sin lazos)
x = x0, e1, x1, e2, …, en-1, xn-1, en, xn = y

de vértices y aristas de G, quecomienza en el

vértice x y termina en el vértice y que contiene
las n aristas ei = {xi-1, xi} donde 1≤i≤n.

Camino
La Longitud de un camino es n, el

número de aristas que hay en el camino.
Si n = 0, no existen aristas, x = y, y el camino

se denomina trivial.
Cualquier camino x-y, donde x=y (y n>1) es

un camino cerrado. En caso contrario (x≠y)
el camino es abierto.

NOTA: Un camino...