TIPOS DE GRAFOS (Simples, Completos, Bipartidos)

TIPOS DE GRAFOS

GRAFOS SIMPLES
Son aquellos grafos que no tienen lazos ni lados paralelos.

GRAFO COMPLETO DE N VÉRTICES (k_n)
Es el grafo en donde cada vértice está relacionado con todos los demás sin lazos ni lados paralelos. Se indica como k_n  en donde n es el número de vértices del grafo.

La valencia en cada uno de los vértices de los grafos completos es (n – 1), y el numero de lados esta dado por la expresión

                     Núm. De lados = n(n – 1)

                                                     2
en donde n es el numero de vértices del grafo.

COMPLEMENTO DE UN GRAFO (G‘)
Es el grafo que le falta al grafo G, de forma que entre ambos formas de grafo completo de n vértices. Este grafo no tiene lazos ni ramas paralelas.

GRAFO BIPARTIDO
es el grafo que esta compuesta por dos conjuntos de vértices, A ={a₁,a_2, a₃…, a_n} y B = {b₁,b₂,…, b_m} en donde los elementos del conjunto B, pero entre los vértices de un mismo conjunto no existe arista que los una.

Una forma muy sencilla de saber si un grafo es bipartido es aplicar el hecho de que nunca tiene un ciclo de longitud impar, además de que debe cumplir con la característica mencionada anteriormente.

GRAFO BIPARTIDO COMPLETO (K_{n, m})
Es el grafo que esta compuesto por dos conjuntos de vértices, uno de ellos A ={a₁,a_2, a₃…, a_n} Y otro B= {b₁,b₂,…, b_m), y en el cada vértice de A esta unido con todo los vértices de B, pero entre los vértices de un mismo conjunto no existe arista que los una. El grafo bipartido completo se indica como  k_{n, m}.