grafos 8.2.2
TRANSCRIPT
Familias de Grafos Simples
Tomado de: Rosen, K. (2004). Matemáticas Discretas y sus Aplicaciones
Esteban Andrés Díaz Mina
Introducción
Abordaremos varias familias importantes de grafos
simples que se usan con frecuencia en ejemplos y
que aparecen en muchas aplicaciones.
Grafo Completo
El grafo completo de n vértices, denotado por Kn,
es un grafo simple que contiene exactamente una
arista entre cada par de vértices distintos.
Los grafos Kn para n=1, 2, 3, 4, 5 son mostrados a continuación.
Grafo Ciclo
El ciclo Cn, para n>2 consiste de n vértices
v1, v2, ....., vn y aristas {v1, v2}, {v2, v3}, ..., {vn-1, vn},
{vn, v1}.
Los ciclos C3, C4, C5 son mostrados a continuación.
Grafo Rueda
Se obtiene un grafo rueda Wn cuando
adicionamos un vértice al grafo Cn, para n>2, y
conectamos este nuevo vértice a cada uno de los
vértices de Cn, con una nueva arista.
Los grafos rueda W3, W4, W5 son mostrados a continuación.
Grafos Bipartitas
Algunas veces los grafos tienen la propiedad que
su conjunto de vértices puede ser dividido en dos
subconjuntos disjuntos, tales que cada arista
conecta a un vértice de un subconjunto, a un
vértice en el otro subconjunto.
Definición
Un grafo simple G se llama Bipartita si su
conjunto de vértices V puede ser particionado en
dos conjuntos disjuntos no vacíos V1 y V2, tal que
cada arista en el grafo, conecta a los vértices de
V1 y a los vértices de V2 (tal que una arista en G
no puede conectar dos vértices en V1 o dos
vértices en V2).
Ejemplo
¿C4 es Bipartita?.
v2v1
v3v4
Ejemplo
v2
v3v4
v1
¿C4 es Bipartita?.
Ejemplo
C4 es Bipartita
v2v1
v3v4
Ejemplo
C4 es Bipartita
v2v1
v3v4
v1
v3
v2
v4
V1 V2
Ejemplo
¿C3 es Bipartita?.
v1
v2v3
Ejemplo
C3 no es Bipartita
v1
v2v3
Ejemplo
C6 es Bipartita.
v1 v2
v3
v4v5
v6
v1
v3
v2
v4
V1 V2
v5 v6
Ejemplo
¿Es el siguiente grafo Bipartita?.
Ejemplo
Ejemplo
Ejemplo
Ejemplo
Ejemplo
Si es Bipartita
a
b
e
f
V1 V2
d g
c
Ejemplo
¿Es el siguiente grafo Bipartita?.
Ejemplo
No es Bipartita
Grafo Bipartita Completo
El grafo bipartita completo Km,n es un grafo que
tiene su conjunto de vértices particionado en dos
conjuntos de m y n vértices, respectivamente.
Existe una arista entre dos vértices si y solo si un
vértice está en el primer subconjunto y el otro
vértice está en el segundo subconjunto.
Grafo Bipartita Completo
Los grafos bipartita completo K2,3 y K3,3 se muestran a
continuación.
K2,3 K3,3
Finalizamos
Familias de Grafos Simples
Hasta pronto