Sesion1_conceptos_generales ver 2

Vista previa del material en texto

Conceptos 
Generales de Grafos
Teoría de Grafos
Nivel 9
Un poco de historia
Teoría de 
Grafos
Problema de 
los Puentes
Problema de 
los 4 Colores
Un poco de historia
El primer artículo científico 
relativo a grafos fue 
escrito por el matemático 
suizo Leonhard Euler en 
1736. Euler se basó en su 
artículo en el problema de 
los puentes de 
Königsberg.
Un poco de historia
El problema planteaba lo 
siguiente: ¿es posible dar un 
paseo comenzando desde 
cualquiera de estas regiones, 
pasando por todos los puentes, 
recorriendo solo una vez cada 
uno y regresando al mismo 
punto de partida?
Un poco de historia
El problema de los cuatro colores 
trata de probar que sólo 
con cuatro colores se puede 
pintar un mapa trazado en un 
plano o en una esfera, de tal 
modo que las regiones que 
compartan al menos una frontera 
no sean del mismo color.
Un poco de historia
Fue planteado por primera vez en 
1852 por Francis Guthrie, mientras 
coloreaba un mapa de Inglaterra. 
La prueba aceptada hasta ahora 
fue formulada en 1976 por 
Wolfgang Haken y Kenneth Appel
en la Universidad de Illinois, con la 
ayuda de una computadora.
Definición de un grafo
Un grafo es una terna V(g), A(g), fg, donde V(g) 
es un conjunto no vacío cuyos elementos se 
llaman VÉRTICES; A(g) es un conjunto cuyos 
elementos se llaman ARISTAS y fg, es una 
función llamada FUNCIÓN DE INCIDENCIA, que 
asocia a cada arista un par de vértices.
Definición de un grafo
• Un grafo G, donde A(g) es vacío se llama grafo 
vacío.
• Un grafo vacío con un solo vértice se llama
grafo trivial.
EJEMPLO :
Sea: G=( V(g), A(g), fg ), donde V(g) = { V1,V2,V3,V4,V5 }
A(g) = { a1, a2, a3, a4, a5, a6, a7, a8, a9 }
fg =
fg(a1) = ( V1, V2 ), fg(a2) = ( V2, V3 ), fg(a3) = ( V3, V3 ),
fg(a4) = ( V3, V4), fg(a5) = ( V2, V4 ), fg(a6) = ( V4, V5 ),
fg(a7) = ( V5, V2 ), fg(a8) = ( V2, V5 ), fg(a9) = ( V3, V2 ).
f(g) se define de la siguiente manera:
Definición de un grafo
Un grafo G = (V, A) está compuesto de:
V : conjunto de vértices o nodos
A : conjunto de aristas o arcos que conectan los 
vértices en V
a b
d e
c
V = { a, b, c, d, e}
A = { (a, b), (a, c), (a, d),
(b, e), (c, d), (c, e),
(d, e) }
Una arista a = (v, w) es un par de vértices
Ejemplo:
Definición de un grafo
 Grafo dirigido o digrafo: grafo cuyas aristas son 
todas dirigidas.
 Grafo no dirigido o grafo: grafo cuyas aristas 
son todas no dirigidas.
 Grafo mixto: grafo con aristas dirigidas y no 
dirigidas.
Elementos de un grafo
E
le
m
e
n
to
s
 d
e
 u
n
 G
ra
fo
Vértices
Aristas
Caminos
Vértices
V
é
rt
ic
e
s
Puntos que conforman el grafo
Grados, numero de aristas que 
inciden en el vértice. σ(V𝑖)
Se clasifican en adyacentes, aislados, 
terminales
Vértices
VÉRTICES ADYACENTES: Es decir son aquellos vértices unidos por alguna 
arista. En el ejemplo, v2 es adyacente a v1 y a v4 pero no a v3.
Nota: En grafos no dirigidos la relación de adyacencia es simétrica, mientras 
que en grafos dirigidos la relación de adyacencia no es simétrica. 
Vértices
VÉRTICE AISLADO: el que no es adyacente a ningún 
otro. V5 es aislado.
Vértices
VÉRTICE TERMINAL: También denominados como 
vértice colgante o pendiente, son aquellos vértices de 
grado 1. Por ejemplo V4 es terminal.
Vértices
GRADOS DE UN VERTICE: Es la cantidad 
de aristas incidentes en un vértice. Los 
bucles se cuentan doblemente. 
g(v1) = 3 
g(v2) = 3 
g(v3) = 3 
g(v4) = 1 
g(v5) = 0 
Vértices
Propiedad Grafos NO 
dirigidos: En todo grafo se 
cumple que la suma de los 
grados de los vértices es igual 
al doble de la cantidad de 
aristas. 
Vértices
GRADOS VERTICES EN DIGRAFOS
 g+(v):es la cantidad de aristas que inciden 
positivamente en v.(flechas que salen) 
 g -(v) es la cantidad de aristas que inciden 
negativamente en v (flechas que entran). 
 Nota: el lazo (Bucle) se cuenta como 
arista incidente positiva y negativamente 
en el vértice por lo tanto se lo cuenta en 
g+ (v) y en g – (v). 
g(va)+ = 2 
g(vb)+ = 1 
g(vc)+ = 2 
g(vd)+ = 1 
g(ve)+ = 2 
g(vf)+ = 1
g(va)- = 1 
g(vb)- = 1 
g(vc)- = 2
g(vd)- = 2 
g(ve)- = 2
g(vf)- = 1 
a b
d e
c
f
Vértices
Propiedad: La suma de los grados 
positivos de los vértices es igual a la 
suma de los grados negativos y es 
igual a la cantidad de aristas del 
dígrafo. 
a b
d e
c
g(va)+ = 2 
g(vb)+ = 1 
g(vc)+ = 2 
g(vd)+ = 1 
g(ve)+ = 1
g(va)- = 1 
g(vb)- = 1 
g(vc)- = 1 
g(vd)- = 2 
g(ve)- = 2
7 = 7 = 7
Aristas
A
ri
s
ta
s Líneas o arcos que unen los vértices 
de un grafo
Tipos de aristas: adyacentes, 
paralelas, bucles, cruce
Aristas
• Arista dirigida: par ordenado (u, v) 
u v
u v
 Arista no dirigida: par no ordenado (u, v) 
Aristas
Aristas adyacentes: Son las que 
convergen al mismo vértice. 
Aristas paralelas: Son aquellas que 
tienen los mismos vértices inicial y final
Bucles o lazo: Son aquellas que parten 
de un vértice y finalizan en el mismo. 
Cruce: Son aquellas que se cruzan en 
un punto sin hacer conexión. 
Caminos
Sean a y b vértices del conjunto V de un grafo G, existe un 
camino en G si hay una sucesión de aristas entre a y b, 
donde a y b son los extremos del camino. 
Se define como la longitud del camino, al número de 
aristas existentes entre los extremos. Se representa 
Longitud (C1) = 3 
Caminos
Si no se repiten los 
vértices se dice que el 
camino es simple. 
C1={(a,c), (c,d), (d,b)}
Long C1={3}
Un camino es cerrado (ciclo o 
circuito), si los extremos del 
camino son el mismo vértice. 
C2={(a,c), (c,d), (d,b), (b,a)}
Long C2={4}
Referencias
Guía 1: Conceptos Fundamentales De Grafos. 
http://cintia.unicordoba.edu.co/mod/resource/view.php?id=1829
http://www.wikiwand.com/es/Grafo
DE LA HOZ, Alexis, DE LA HOZ FRANCO, Emiro, Paola Ariza Colpas. 
Árboles y grafos. Editorial EDUCOSTA. 2009
http://fmonje.com/UTN/Matematica%20Discreta/Grafos,%20D%C3%AD
grafos%20y%20%C3%81rboles.PDF
http://cintia.unicordoba.edu.co/mod/resource/view.php?id=1829
http://fmonje.com/UTN/Matematica%20Discreta/Grafos,%20D%C3%ADgrafos%20y%20%C3%81rboles.PDF