Sesion2_grafos_conexos ver 10

Vista previa del material en texto

Conceptos 
Generales de Grafos
Teoría de Grafos
Nivel 9
Temas a tratar
Teoría de Grafos
Nivel 9
• Grafos conexos
• Grafos disconexos
• Grafos bipartitos
• Digrafos
Grafos conexos y disconexos
Un grafo es conexo si cada par de vértices está 
conectado por un camino; es decir, si para 
cualquier par de vértices (a, b), existe al menos 
un camino posible desde a hacia b.
Grafo conexo
Grafo no 
conexo, con 
dos 
componentes 
conexas
G’ G 
Grafos conexos y disconexos
Un grafo es doblemente 
conexo si cada par de 
vértices está conectado por 
al menos dos caminos 
disjuntos; es decir, es 
conexo y no existe un vértice 
tal que al sacarlo, el grafo 
resultante sea disconexo.
Camino disjuntos: Dos 
caminos cuyos vértices 
no se repiten.
a b
d c
Grafos conexos y disconexos
Un grafo es doblemente 
conexo si cada par de 
vértices está conectado por 
al menos dos caminos 
disjuntos; es decir, es 
conexo y no existe un vértice 
tal que al sacarlo el grafo 
resultante sea disconexo.
Camino disjuntos: Dos 
caminos cuyos vértices 
no se repiten.
a b
d c
Grafos conexos y disconexos
Un grafo es doblemente 
conexo si cada par de 
vértices está conectado por 
al menos dos caminos 
disjuntos; es decir, es 
conexo y no existe un vértice 
tal que al sacarlo el grafo 
resultante sea disconexo.
Camino disjuntos: Dos 
caminos cuyos vértices 
no se repiten.
a b
d
Grafos conexos y disconexos
Grafo fuertemente 
conexo que es un 
grafo dirigido tal 
que para cualquier 
par de vértices 
existe un camino 
que los une. 
Digrafo fuertemente conexo 
a
b
d
c
Confirme si existen caminos que 
conecten cualquier vértice con los 
demás vértices del grafo
Grafos conexos y disconexos
Digrafo fuertemente conexo 
a
b
d
c
Confirme si existen caminos que 
conecten cualquier vértice con los 
demás vértices del grafo
Origen –
Destino
Camino
A => B (a,b)
A => C (a,b), (b,c)
A => D (a,b), (b,d)
B => A (b,d), (d,a)
B => C (b,c)
B => D (b,d)
C => A (c,d), (d,a)
C => B (c,b)
C => D (c,d)
Grafos bipartitos
Los grafos bipartitos tienen aplicabilidad en los 
problemas de optimización combinatoria que se 
presentan en los problemas de asignación: por 
ejemplo, obreros a trabajos, trabajos a maquinas, 
barcos a muelles, cursos a salones, etc.
Grafos bipartitos
Un grafo G = (V, A) se dice bipartito si el conjunto 
de vértices V puede separarse en dos conjuntos 
disjuntos V = S U T de tal manera que las aristas 
del grafo unen siempre un vértice de S con uno de 
T.
TEOREMA: Un grafo G es bipartito sí y solo sí NO tiene 
ciclos de longitud impar.
Grafos bipartitos
Dicho de otra forma, un grafo es bipartito si sus 
vértices pueden colorearse utilizando dos 
colores de tal forma que no exista ninguna arista 
que conecte dos vértices del mismo color. 
Grafos bipartitos
a b
d c
G G’
En primer lugar aplique el teorema para determinar 
si es bipartito o no
Grafos bipartitos
a b
d c
G G’
No es bipartito No es bipartito
Grafos bipartitos
En primer lugar 
aplique el teorema 
para determinar si es 
bipartito o no
1 2
6
5
4
3
7
Grafos bipartitos
Sí, es bipartito !!
En primer lugar 
aplique el teorema 
para determinar si es 
bipartito o no
1 2
6
5
4
3
7
Grafos bipartitos
Sí, es bipartito !!
Se procede a 
colorear los vértices, 
usando dos colores. 
Por qué vértice se 
inicia?
1 2
6
5
4
3
7
Grafos bipartitos
Se procede a 
colorear los vértices, 
usando dos colores. 
Por qué vértice se 
inicia?
1 2
6
5
4
3
7
Grafos bipartitos
Se procede a 
colorear los vértices, 
usando dos colores. 
Por qué vértice se 
inicia?
1 2
6
5
4
3
7
Grafos bipartitos
Una vez coloreado 
todos los vértices, se 
procede con definir 
los dos conjuntos 
disjuntos.
1 2
6
5
4
3
7
Grafos bipartitos
Definidos los dos 
conjuntos disjuntos, 
ahora se unen los 
vértices de S con uno 
de T.
1 2
6
5
4
3
7
S = {1, 3, 5, 6}
T = {2, 4, 7}
Grafos bipartitos
Definidos los dos 
conjuntos disjuntos, 
ahora se unen los 
vértices de S con uno 
de T.
1 2
6
5
4
3
7
S =
T =
1 653
2 4 7
Grafos bipartitos
Un grafo bipartido en 
el cual todos los 
elementos de S están 
unidos con todos los 
elementos de T se 
denomina grafo 
bipartito completo. 
V1
V2
K3,3
Dígrafos o grafos dirigidos
Un grafo dirigido o digrafo es 
un tipo de grafo en el cual las 
aristas tienen un sentido 
definido, a diferencia del grafo 
no dirigido, en el cual las 
aristas son relaciones 
simétricas y no apuntan en 
ningún sentido.
a b
d e
c
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. 
a b
d e
c
Referencias
Guia 2 - Conceptos fundamentales digrafos.pdf
http://cintia.unicordoba.edu.co/mod/resource/view.php?id=1829
http://estructurasdedatosgrafos.blogspot.com/p/caracterizacion-de-
grafos-editar-grafos.html
DE LA HOZ, Alexis, DE LA HOZ FRANCO, Emiro, Paola Ariza Colpas. 
Árboles y grafos. Editorial EDUCOSTA. 2009
http://cintia.unicordoba.edu.co/mod/resource/view.php?id=1829
http://estructurasdedatosgrafos.blogspot.com/p/caracterizacion-de-grafos-editar-grafos.html
Muchas gracias por su atención