Grafo bipartito completo

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
Grafo bipartito completo
Biclique K 3 5.svg
Un grafo bipartito completo con m = 5 y n = 3
Vértices n + m
Aristas mn
Radio
Diámetro
Cintura
Automorfismos
Número cromático 2
Índice cromático max{m, n}

En teoría de grafos, un grafo bipartito completo es un grafo bipartito en el que todos los vértices de uno de los subconjuntos de la partición están conectados a todos los vértices del segundo subconjunto, y viceversa.[1]

Este concepto se puede generalizar al de grafo s-bipartito completo, como un grafo cuyo conjunto de vértices se puede particionar en s subconjuntos, de modo que todos los pares de vértices pertenecientes a subconjuntos diferentes son adyacentes.[1]

Definición[editar]

Un grafo bipartito completo es un grafo bipartito tal que Es decir, un grafo bipartito completo está formado por dos conjuntos disjuntos de vértices y todas las posibles aristas que unen esos vértices.[1]

El grafo completo bipartito con particiones de tamaño y es denotado como .[1]

Ejemplos[editar]


Propiedades[editar]

Sea un grafo bipartito con y , se verifica:[cita requerida]

  • posee árboles de expansión.

Véase también[editar]

Referencias[editar]

  1. a b c d Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.

Bibliografía[editar]

  • Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053.