jueves, 8 de diciembre de 2011

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 (kn)
Es el grafo en donde cada vértice está relacionado con todos los demás sin lazos ni lados paralelos. Se indica como kn  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 ={a1,a2, a3…, an} y B = {b1,b2,…, bm} 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 (Kn, m)
Es el grafo que esta compuesto por dos conjuntos de vértices, uno de ellos A ={a1,a2, a3…, an} Y otro B= {b1,b2,…, bm), 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  kn, m.

1 comentario:

  1. 2017 ford fusion hybrid titanium, high yield
    The 2018 ford fusion fusion hybrid titanium has micro touch titanium trimmer a huge, camillus titanium thin core with very high yield titanium watch in the shape tittanium of a titanium color habanero. This is the only fusion product in the world of

    ResponderEliminar