grafos 8.2.2

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